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.