Performance of list.index - how to speed up a silly algorithm?

MRAB python at mrabarnett.plus.com
Thu Apr 29 18:57:25 EDT 2010


Laszlo Nagy wrote:
> I have some ten thousand rows in a table. E.g.
> 
> columns = ["color","size","weight","value"]
> rows = [
>     [ "Yellow", "Big", 2, 4 ],
>     [ "Blue", "Big", 3, -4 ],
>     [ "Blue", "Small", 10, 55 ],
>     ...
> ]
> 
> Some columns are dimensions, others are measures. I want to convert this 
> to an indexed version, that looks like this:
> 
> dimension_names = ["color","size"] # List of dimension names
> dimension_cols = [0,1] # Column indexes for dimension values
> dimension_values = { # Dimension value occurences for each dimension
>     0: ["Yellow","Blue",....],
>     1: ["Big","Small",...],
> }
> measure_names = ["weight","value"] # List of measure names
> measure_cols = [2,3] # List of measure columns
> facts = [ # Facts, containing tuples of (dimension_value_incides, 
> measure_values )
>     ( (0,0) , (2,4) ),
>     ( (1,0) , (3,-4) ),
>     ( (1,1) , (10,55) ),
>     ...
> ]
> 
> This is how I try to convert to the indexed version:
> 
> #1. Iterate over all rows, and collect possible dimension values.
> 
> cnt = 0
> for row in iterator_factory():
>     cnt += 1
>     for dimension_idx,col_idx in enumerate(dimension_cols):
>         dimension_values[colidx].append(row[cold_idx])
>         if cnt%10000:
>             dimension_values[colidx] = list(set(dimension_values[colidx]))
> 
> #2. Index facts by dimension values
> 
> facts = []
> for row in iterator_factory():
>     dv = []
>     for dimension_idx,col_idx in enumerate(dimension_cols):
>         dv.append( dimension_values[col_idx].index(row[col_idx]) ) # 
> THIS IS THE PROBLEMATIC LINE!
>     mv = [ row[col_idx] for col_idx in measure_cols ]
>     facts.append( dv,mv )
> 
> (In reality, rows and facts are not stored in memory, because there can 
> be 100 000+ facts. I did not want to bore you with the full source code.)
> 
> And finally, here is my problem. If a dimension has many possible 
> values, then the list.index() code above slows down eveything. In my 
> test case, the problematic dimension had about 36 000 different values, 
> and the number of rows was about 60 000. Calling index() on a list of 36 
> 000 values, times 60 000, is too slow.
> 
> Test performance was 262 rows/sec. If I use dv.append(0) instead of " 
> dv.append( dimension_values[col_idx].index(row[col_idx]) ) " then it 
> goes up to 11520 rows/sec. If I exclude the problematic dimension, and 
> only leave the others (with 1000 or less values) then goes up to 3000 
> rows/sec.
> 
> Maybe this should be implemented in C. But I believe that the algorithm 
> itself must be wrong (regardless of the language). I really think that 
> I'm doing something wrong. Looks like my algorithm's processing time is 
> not linear to the number of rows. Not even log(n)*n. There should be a 
> more effective way to do this. But how?
> 
> I had the idea of sorting the rows by a given dimension. Then it would 
> be obvious to speed up the indexing part - for that dimension. PROBABLY 
> sorting all rows would be faster than calling list.index() for each row. 
> But... it does not seem very efficient either. What if I have 1 million 
> rows and 10 dimensions? Do I sort 1 million rows on the disk 10 times? 
> Some of you might have ran into the same problem before, and can tell me 
> which is the most efficient way to do this.
> 
The .index method does a linear search, checking on average 1/2 of the 
items in the list. That's why it's so slow.

In order to avoid that you could build a dict of each value in
dimension_values[col_idx] and its index in a single pass so that it
becomes a quick lookup.



More information about the Python-list mailing list