Recitation 2

Homework Tips

• 20 minutes reading documentation will save you 8 hours of writing code
• Be familiar with the What Can I Ask On Diderot? policy
• Talk to other students taking the course – they can help you and you can help them.
• Look for the “Common Problems in Homework x” post on Diderot before asking questions online.

TA Hours

• Come this week! Don’t wait until the last week.
• We will only help you with your code if you construct a minimal counter-example : a simplest test case that fails.

import pandas as pd
import sqlite3
import gzip
import scipy.sparse as sp
from random import shuffle

Views and Data

Pandas loads data and presents you with a view of it. Most read-only operations on the DataFrame change the view but leave the underlying data intact; this allows you to work quickly (because copying is expensive) with very large datasets (big enough that you can only keep one copy in memory).

Here’s an example using a modified version of the Crimes in Boston dataset (CC0):

with gzip.open("crime_min.csv.gz", "rt", encoding="UTF-8") as crime_file:
    crime = pd.read_csv(crime_file)
    crime["date"] = pd.to_datetime(crime['date'], infer_datetime_format=True)

with gzip.open("offense_codes.csv.gz", "rt", encoding="UTF-8") as offense_file:
    offense = pd.read_csv(offense_file).drop_duplicates("code")

crime

It uses a decent amount of memory:

crime.memory_usage(deep=True)

str(sum(crime.memory_usage(deep=True)) // 1024 // 1024) + " MB"

This doesn’t seem like much, but datasets get very large very quickly. Let’s select all reports of “GATHERING CAUSING ANNOYANCE”:

gca = crime[crime.offense_code == 3302]
gca

We see that the created frame is a copy. It has a weak reference to the original DataFrame:

gca._is_copy

We print out the index and see that it refers to the selected rows in the original DataFrame by row id:

gca.index

Making a copy creates a new backing array, independent of the original data:

gca_copy = gca.copy()
print(gca_copy._is_copy)

None

Databases and Indices

pandas and RDBMS software work off of indices. These exist to speed up queries.

The reason indexes are so important is because of data normalization. By allowing us to efficiently connect information dispersed over several tables, we can store data in a way that minimizes redundancy and maximizes throughput. Here’s a basic introduction to the concept.

speed_crime = crime.copy()
speed_crime.index = pd.DatetimeIndex(speed_crime.date)
str(sum(speed_crime.memory_usage(deep=True)) // 1024 // 1024) + " MB"

%%timeit
entries = []
fr, to = pd.to_datetime("2016-11-01"), pd.to_datetime("2016-12-01")
for idx, row in speed_crime.iterrows():
    if (idx > fr)  and (idx < to):
        entries.append(row)

%%timeit
speed_crime.loc["2016-11-01":"2016-12-01"]

2.52 ms ± 32.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

It’s a little quicker! This is why you’re expected to complete hw2_time_series without looping over the data.

The chief gains in this are from vectorization (which is running as much of the code sequentially as low-level as possible), and then from indexing (which is preparing a lookup data structure to find parts of the data more efficiently).

Join operation

The use of an index allows us to join two tables together using common column values. Lets take a look at the offense table:

offense[offense.code.isin([3302, 3116, 1103, 3122, 2401])]

We’ve previously set the code as the index:

offense_indexed = offense.set_index("code")
offense_indexed

Now we can join the two tables, selecting the offense.name where crime.offense_code == offense.code:

crime.join(offense_indexed, on="offense_code", how="left")

Once More With SQLite

conn = sqlite3.connect(':memory:')
crime.reset_index().to_sql("crime", conn, if_exists="replace")
offense.reset_index().to_sql("offense", conn, if_exists="replace")
conn.execute("PRAGMA automatic_index = false;") # Disable automatic indexing for this demo
conn.commit()

conn.execute("SELECT * FROM `crime`;").fetchmany(2)

conn.execute("SELECT * FROM `offense`;").fetchmany(2)

SQLite Indexes and Join

We can set SQLite indexes up pretty easily. Lets try the join query from earlier without one first:

join_query = "SELECT * FROM `crime` LEFT JOIN `offense` ON crime.`offense_code` = offense.`code`;"
conn.execute(join_query).fetchmany(2)

It works, but how does it happen? We can use the EXPLAIN QUERY PLAN instruction to get SQLite to tell us its strategy.

conn.execute(f"EXPLAIN QUERY PLAN {join_query}").fetchall()

SCAN TABLE means it searches the table by looping over it, the slowest way of doing this. What this means is that SQLite has to loop over the offense table once for each entry in crime.

Now lets create an index and do this again:

conn.execute(f"CREATE INDEX code_index ON offense(`code`)")
conn.execute(f"EXPLAIN QUERY PLAN {join_query}").fetchall()

SEARCH TABLE means that the index code_index is used to efficiently locate entries inside offense. This means that SQLite has to efficiently find entries from offense for each entry in crime.

Matrices and Sparse Representation

There’s a basic problem with matrices. An $n \times m$ matrix of type float64 takes $n\times m\times 8$ bytes of memory. That adds up to a lot of space.

That’s why we need sparse representations.

Different Representations

There are two different sparse representations we’re going to use.

The first is the Coordinate or i, j, v format. It’s called that because we store the matrix as pairs of i, j coordinates and v values.

i = [0, 1, 2, 3, 4, 5, 6]
j = [6, 1, 4, 3, 2, 0, 5]
v = [1, 2, 3, 4, 5, 6, 7]

m = sp.coo_matrix((v, (i, j)), shape=(7,7))

Lets convert the matrix to the dense form to see it:

print(str(m.todense()).replace("0", " "))

[[            1]
 [  2          ]
 [        3    ]
 [      4      ]
 [    5        ]
 [6            ]
 [          7  ]]

We can create matrices that are very large. A $10,000\times 10,000$ matrix of float64 will take 1.6 GB of memory to create.

size=20000
i = list(range(size)) * 200
j = list(range(size)) * 200
v = list(range(1, size + 1)) * 200
shuffle(j)
m = sp.coo_matrix((v, (i, j)), shape=(size, size))
m

str((m.col.nbytes + m.row.nbytes + m.data.nbytes) // 1024 // 1024) + " MB"

The most important operation with matrices is matrix multiplication. If we try to use this format to perform matrix multiplication, we’ll have to repeatedly search over the entire list. We need a more efficient way to store the sparse values.

That’s where the Compressed Sparse Row representation comes in:

md = m.tocsr()
md

str((md.data.nbytes + md.indptr.nbytes + md.indices.nbytes) // 1024 // 1024) + " MB"

The Compressed Sparse Row representation stores each row as a (sometimes sorted) list of (index, values) pairs. This allows for much quicker math when the size and density of the matrix is sufficiently large. Here we try it on a matrix of about 1% density:

%%timeit
m * m

8.97 s ± 25.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
md * md

2.76 s ± 6.74 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)