Performance of list.index - how to speed up a silly algorithm?
in [Python]
|
From: Laszlo Nagy on 29 Apr 2010 18:21 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. Thanks, Laszlo
From: MRAB on 29 Apr 2010 18:57 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.
From: Mensanator on 29 Apr 2010 19:06 On Apr 29, 5:21 pm, Laszlo Nagy <gand...(a)shopzeus.com> 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. > > Thanks, Have you considered using a SQL database? Personally, I would use MS-Access and link it to Python via ODBC. That way, I could use the Access drag-and-drop design tools and either - copy the SQL code of working query designs to Python or - use the ODBC to link to said queries rather than directly to the raw tables Of course, Python has SQLlight now, I just don't know SQL that well. > > Laszlo
From: Peter Otten on 30 Apr 2010 03:20 MRAB wrote: > 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. For example: from itertools import count, izip def iterator_factory(): # columns = ["color", "size", "weight", "value"] rows = [ ["Yellow", "Big", 2, 4], ["Blue", "Big", 3, -4], ["Blue", "Small", 10, 55], #... ] return iter(rows) class Indexer(object): def __init__(self): self.lookup = {} self.counter = count() def __call__(self, value): try: return self.lookup[value] except KeyError: result = self.lookup[value] = next(self.counter) return result def to_list(self): d = self.lookup reverse = dict(izip(d.itervalues(), d.iterkeys())) assert len(reverse) == len(d) return [reverse[i] for i in xrange(len(reverse))] def pairs(rows, dimension_cols, measure_cols, indexers): for row in rows: dv = [indexer(row[col]) for indexer, col in izip(indexers, dimension_cols)] mv = [row[col] for col in measure_cols] yield dv, mv def main(): # dimension_names = ["color", "size"] dimension_cols = [0, 1] # measure_names = ["weight", "value"] measure_cols = [2, 3] indexers = [Indexer() for _ in dimension_cols] facts = pairs(iterator_factory(), dimension_cols, measure_cols, indexers) facts = list(facts) print facts for i, indexer in enumerate(indexers): print "%d: %s" % (i, indexer.to_list()) if __name__ == "__main__": main()
From: Laszlo Nagy on 30 Apr 2010 06:12
>> 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. >> > > For example: > > from itertools import count, izip > > .... > def main(): > # dimension_names = ["color", "size"] > dimension_cols = [0, 1] > > # measure_names = ["weight", "value"] > measure_cols = [2, 3] > > indexers = [Indexer() for _ in dimension_cols] > > facts = pairs(iterator_factory(), > dimension_cols, measure_cols, indexers) > facts = list(facts) > > print facts > for i, indexer in enumerate(indexers): > print "%d: %s" % (i, indexer.to_list()) > > if __name__ == "__main__": > main() > Whew! :-) Thank you for taking the time. I'm not very familiar to itertools yet, so I need some time to understand this *beautiful* code. :-) L |