3
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ You are not always retrieving the first occurrence because "If a value is equal to the value after it, it skips it." \$\endgroup\$ Commented Mar 20, 2013 at 9:20

3 Answers 3

1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ An issue with this script, it's sucking up a TON of memory. \$\endgroup\$ Commented Mar 21, 2013 at 18:59
  • \$\begingroup\$ Tried with 2 other methods, but it looks like the initial one is still the fastest. Please compare which is the best in terms of memory consumption on runtime, using your big data. \$\endgroup\$
    – DevLounge
    Commented Mar 21, 2013 at 21:26
  • \$\begingroup\$ FYI I tried to implement an 100% python way of solving your question. \$\endgroup\$
    – DevLounge
    Commented Mar 22, 2013 at 14:29
3
\$\begingroup\$

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')]
\$\endgroup\$
1
  • \$\begingroup\$ Great example, sorry for skipping out on a csv information. I didn't have a good way to illustrate 41 columns by 5.3 million rows in a csv of mixed integers and strings. I've looking for an example like this, I'm still getting used to sqlite3 syntax. Upvoting as soon as I have enough rep. \$\endgroup\$ Commented Mar 20, 2013 at 15:26
2
\$\begingroup\$

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()}
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.