Binning and calculating a huge range of data

Question

I have a code that I'm fairly certain does what I want. Bear with me as I explain what I'm doing:

Imagine that there is 10 houses, where there can be one to an infinite number of persons. Each of those persons sends a number of messages, containing their userid and the house number. This can be from 1 to infinite number of messages. I want to know the average number of messages that is sent by each person, for each house, to later plot which house got the largest number of average messages.

Now, that I've explained conceptually, the houses aren't houses, but latitudes, from f.ex -90 to -89 etc. And that a person can send messages from different houses.

This is some sample input:

lat = [-83.76, -44.88, -38.36, -35.50, -33.99, -31.91, -27.56, -22.95,
       -19.00, -12.32,  -6.14,  -1.11,   4.40,  10.23,  19.40,  31.18,
        40.72,  47.59,  54.42,  63.84,  76.77]

userid= [525, 701, 701, 520, 701, 309, 373, 255,
         372,  636, 529, 529, 529, 775,   345,  636,
          367, 366,  372,  251,  273]

The real input is some houndred million values in the range of -90 to 90 for latitudes, and different numbers in no set range for the userid. There are about 100 000 unique userids. These are stored in an SQLite database.

"My code" takes about 13s with 1/300th of my data, so I guess there is a lot of possibilities for optimization. I got the code with great help from J-Richard-Snape in this question. Note that it is my code down until min_lat so he is not held accountable for the code over that. Any suggestions?

import sqlite3 as lite
import numpy as np
import matplotlib.pyplot as plt
from itertools import groupby

def getQuantity(databasepath):
    latitudes = []
    userids = []
    info = []
    con = lite.connect(databasepath)
    with con:
        cur = con.cursor()
        cur.execute('SELECT latitude, userid FROM message')
        con.commit()
        while True:
            tmp = cur.fetchone()
            if tmp != None:
                info.append([float(tmp[0]),int(tmp[1])])
            else:
                break
        info = sorted(info, key=itemgetter(0))
        for x in info:
            latitudes.append(x[0])
            userids.append(x[1])
        info = []
        tmp = 0
        min_lat = -90
        max_lat = 90
        binwidth = 1

        bin_range = np.arange(min_lat,max_lat,binwidth)

        all_rows = zip(latitudes,userids)
        binned_latitudes = np.digitize(latitudes,bin_range)
        all_in_bins = zip(binned_latitudes,userids)
        unique_in_bins = list(set(all_in_bins))
        all_in_bins.sort()
        unique_in_bins.sort()

        bin_count_all = []
        for bin, group in groupby(all_in_bins, lambda x: x[0]):
            bin_count_all += [(bin, len([k for k in group]))]

        bin_count_unique = []
        for bin, group in groupby(unique_in_bins, lambda x: x[0]):
            bin_count_unique += [(bin, len([ k for k in group]))]

        bin_density = [(bin_range[b-1],a*1.0/u) for ((b,a),(_,u)) in         zip(bin_count_all, bin_count_unique)]

        bin_density =  np.array(bin_density).transpose()

        # all_in_bins and unique_in_bins now contain the data
        # corresponding to the SQL / pseudocode in your question

        # plot as standard bar - note you can put uneven widths in as an         array-like here if necessary
        plt.bar(*bin_density, width=binwidth)

Especially info.append([float(tmp[0]),int(tmp[1])]) causes a memory error.

Answer 1

You call con.commit() unnecessarily — there is no change to be committed. You defined all_rows, but never use it. But those are just minor inefficiencies.

The point of using a database is that you can ask it to tell you interesting things about your data. If you are just going to dump out the entire contents of a table for analysis, you might as well use a CSV file.

A query like this would be ideal:

SELECT FLOOR(latitude) AS latitude
     , COUNT(userid) AS message_count
     , COUNT(DISTINCT userid) AS distinct_count
    FROM message
    GROUP BY 1
    ORDER BY 1;

Unfortunately, SQLite lacks a FLOOR() function, so a circumlocution is necessary:

SELECT CASE WHEN latitude = CAST(latitude AS INTEGER) OR latitude >= 0 THEN CAST(latitude AS INTEGER)
            ELSE CAST(latitude - 1 AS INTEGER)
       END AS latitude
     , COUNT(userid) AS message_count
     , COUNT(DISTINCT userid) AS distinct_count
    FROM message
    GROUP BY 1
    ORDER BY 1;

Note that a simple CAST (latitude AS INTEGER) would be inappropriate for histogram binning, as casting truncates towards zero, such that -0.99 < latitude < +0.99 would all map to 0.

It should be trivial to read the results from that query into bin_count_all and bin_count_unique.

Note that to make that query run efficiently, it would be wise to

CREATE INDEX message_latitude_userid ON message (latitude, userid);

Answer 2

When calculating the length of an iterator g we can do so without creating a list and then immediately throwing it away. So where you do

len([k for k in g])

you could do

sum(1 for k in g)

Also, we can import itemgetter to get a potential speedup over your lambda function. Here is an example of how itemgetter works (see docs for more examples):

xs = [0, 1, 2, 3]
ig = itemgetter(2)
ig(xs) == xs[2] 

So given these two suggestions, I would change how you are initializing bin_cnt_all and bin_cnt_unqiue to the following:

from operator import itemgetter
# ...
first = itemgetter(0)
# ...
bin_cnt_all = [(b, sum(1 for k in g)) for b, g in groupby(all_in_bins, first)]
bin_cnt_unique = [(b, sum(1 for k in g)) for b, g in groupby(unique_in_bins, first)]