Retrieving the first occurrence of every unique value from a CSV column

Question

A large .csv file I was given has a large table of flight data. A function I wrote to help parse it iterates over the column of Flight IDs, and then returns a dictionary containing the index and value of every unique Flight ID in order of first appearance.

Dictionary = { Index: FID, ... }

This comes as a quick adjustment to an older function that didn't require having to worry about FID repeats in the column (a few hundred thousand rows later...).

Example:

20110117559515, ... 
20110117559515, ... 
20110117559515, ...                     
20110117559572, ...   
20110117559572, ...   
20110117559572, ...                               
20110117559574, ...                               
20110117559587, ...                             
20110117559588, ...

and so on for 5.3 million some rows.

Right now, I have it iterating over and comparing each value in order. If a unique value appears, it only stores the first occurrence in the dictionary. I changed it to now also check if that value has already occurred before, and if so, to skip it.

def DiscoverEarliestIndex(self, number):
    result = {}
    columnvalues = self.column(number)
    column_enum = {}
    for a, b in enumerate(columnvalues):
        column_enum[a] = b
        i = 0
    while i < (len(columnvalues) - 1):
        next = column_enum[i+1]
        if columnvalues[i] == next:
            i += 1
        else:
            if next in result.values():
                i += 1
                continue
            else:
                result[i+1]= next
                i += 1
    else:
        return result

It's very inefficient, and slows down as the dictionary grows. The column has 5.2 million rows, so it's obviously not a good idea to handle this much with Python, but I'm stuck with it for now.

Is there a more efficient way to write this function?

Answer 1

So here is what I came up with, now that I had access to a computer:

raw_data.csv:

20110117559515,1,10,faa
20110117559515,2,20,bar
20110117559515,3,30,baz
20110117559572,4,40,fii
20110117559572,5,50,bir
20110117559572,6,60,biz
20110117559574,7,70,foo
20110117559587,8,80,bor
20110117559588,9,90,boz

code:

import csv
from collections import defaultdict
from pprint import pprint
import timeit


def method1():
    rows = list(csv.reader(open('raw_data.csv', 'r'), delimiter=','))
    cols = zip(*rows)
    unik = set(cols[0])

    indexed = defaultdict(list)

    for x in unik:
        i = cols[0].index(x)
        indexed[i] = rows[i]

    return indexed

def method2():
    rows = list(csv.reader(open('raw_data.csv', 'r'), delimiter=','))
    cols = zip(*rows)
    unik = set(cols[0])

    indexed = defaultdict(list)

    for x in unik:
        i = next(index for index,fid in enumerate(cols[0]) if fid == x)
        indexed[i] = rows[i]

    return indexed

def method3():
    rows = list(csv.reader(open('raw_data.csv', 'r'), delimiter=','))
    cols = zip(*rows)
    indexes = [cols[0].index(x) for x in set(cols[0])]

    for index in indexes:
        yield (index,rows[index])


if __name__ == '__main__':

    results = method1()    
    print 'indexed:'
    pprint(dict(results))

    print '-' * 80

    results = method2()    
    print 'indexed:'
    pprint(dict(results))

    print '-' * 80

    results = dict(method3())
    print 'indexed:'
    pprint(results)

    #--- Timeit ---

    print 'method1:', timeit.timeit('dict(method1())', setup="from __main__ import method1", number=10000)
    print 'method2:', timeit.timeit('dict(method2())', setup="from __main__ import method2", number=10000)
    print 'method3:', timeit.timeit('dict(method3())', setup="from __main__ import method3", number=10000)

Output:

indexed:
{0: ['20110117559515', '1', '10', 'faa'],
 3: ['20110117559572', '4', '40', 'fii'],
 6: ['20110117559574', '7', '70', 'foo'],
 7: ['20110117559587', '8', '80', 'bor'],
 8: ['20110117559588', '9', '90', 'boz']}
--------------------------------------------------------------------------------
indexed:
{0: ['20110117559515', '1', '10', 'faa'],
 3: ['20110117559572', '4', '40', 'fii'],
 6: ['20110117559574', '7', '70', 'foo'],
 7: ['20110117559587', '8', '80', 'bor'],
 8: ['20110117559588', '9', '90', 'boz']}
--------------------------------------------------------------------------------
indexed:
{0: ['20110117559515', '1', '10', 'faa'],
 3: ['20110117559572', '4', '40', 'fii'],
 6: ['20110117559574', '7', '70', 'foo'],
 7: ['20110117559587', '8', '80', 'bor'],
 8: ['20110117559588', '9', '90', 'boz']}

method1: 0.283623933792
method2: 0.37960600853
method3: 0.293814182281

Answer 2

You've given us a small piece of your problem to review, and Janne's suggestion seems reasonable if that piece is considered on its own. But I have the feeling that this isn't the only bit of analysis that you are doing on your data, and if so, you probably want to think about using a proper database.

Python comes with a built-in relational database engine in the form of the sqlite3 module. So you could easily read your CSV directly into a SQLite table, either using the .import command in SQLite's command-line shell, or via Python if you need more preprocessing:

import sqlite3
import csv

def load_flight_csv(db_filename, csv_filename):
    """
    Load flight data from `csv_filename` into the SQLite database in
    `db_filename`.
    """
    with sqlite3.connect(db_filename) as conn, open(csv_filename, 'rb') as f:
        c = conn.cursor()
        c.execute('''CREATE TABLE IF NOT EXISTS flight
                     (id INTEGER PRIMARY KEY AUTOINCREMENT, fid TEXT)''')
        c.execute('''CREATE INDEX IF NOT EXISTS flight_fid ON flight (fid)''')
        c.executemany('''INSERT INTO flight (fid) VALUES (?)''', csv.reader(f))
        conn.commit()

(Obviously you'd need more fields in the CREATE TABLE statement, but since you didn't show them in your question, I can't guess what they might be.)

And then you can analyze the data by issuing SQL queries:

>>> db = 'flight.db'
>>> load_flight_csv(db, 'flight.csv')
>>> conn = sqlite3.connect(db)
>>> from pprint import pprint
>>> pprint(conn.execute('''SELECT MIN(id), fid FROM flight GROUP BY fid''').fetchall())
[(1, u'20110117559515'),
 (4, u'20110117559572'),
 (7, u'20110117559574'),
 (8, u'20110117559587'),
 (9, u'20110117559588')]

Answer 3

One thing that slows you down is if next in thegoodshit.values() because it has to iterate through the values.

A simple way to eliminate duplicate values is to first construct a dictionary where values are the key:

unique_vals = {val: i for i, val in enumerate(columnvalues)}
return {i: val for val, i in unique_vals.iteritems()}

If there are duplicates, this will give the last index of each value, because duplicates get overwritten in the construction of unique_vals. To get the first index instead, iterate in reverse:

unique_vals = {val: i for i, val in reversed(list(enumerate(columnvalues)))}
return {i: val for val, i in unique_vals.iteritems()}