455,532 Members | 1,374 Online
Need help? Post your question and get tips & solutions from a community of 455,532 IT Pros & Developers. It's quick & easy.

# Orders of magnitude

 P: n/a x = [chr(a) + chr(b) for a in xrange(100) for b in xrange(100)] # list version: c = [] for i in x: if i not in c: c.append(i) t1.timeit(1) 2.0331145438875637 # dict version: c = {} for i in x: if i not in c: c[i] = None t2.timeit(1) 0.0067952770534134288 # bsddb version: c = bsddb.btopen(None) for i in x: if i not in c: c[i] = None t3.timeit(1) 0.18430750276922936 Wow. Dicts are *fast*. I'm dedup'ing a 10-million-record dataset, trying different approaches for building indexes. The in-memory dicts are clearly faster, but I get Memory Errors (Win2k, 512 MB RAM, 4 G virtual). Any recommendations on other ways to build a large index without slowing down by a factor of 25? Robert Brewer MIS Amor Ministries fu******@amor.org Jul 18 '05 #1
13 Replies

 P: n/a "Robert Brewer" writes: I'm dedup'ing a 10-million-record dataset, trying different approaches for building indexes. The in-memory dicts are clearly faster, but I get Memory Errors (Win2k, 512 MB RAM, 4 G virtual). Any recommendations on other ways to build a large index without slowing down by a factor of 25? Sort, then remove dups. Jul 18 '05 #2

 P: n/a Sort, then remove dups. A list 10 million integers suck up ~160 megs of memory with Python. I doubt the strings would fit even then. I would suggest a multi-phase method. Break the sequence up into 100k element blocks each and remove duplicates using dictionaries. Sort each block individually and write each to a file. Merge the 100 files by using a heapq. #heap is structured like... [("next string in file a", file_handle_a), ("next string in file b", file_handle_b),...] If you keep using heappop and heappush from heapq, along with a single string of memory, you can remove duplicates quite easily, and certainly won't run out of memory. - Josiah Jul 18 '05 #3

 P: n/a It all boils down to how much space your keys take. When you look for dupes, you must hold only the keys in memory, not the data (it'll be a lot faster this way). I'd say create a bsddb with btree sort to hold all your keys. Should take about 20 minutues to fill it. Then scan it in sorted key order, and duplciates will appear next to each other. Jul 18 '05 #4

 P: n/a Josiah Carlson writes: Sort, then remove dups. A list 10 million integers suck up ~160 megs of memory with Python. I doubt the strings would fit even then. I meant sort externally. I thought these records were in a disk file or something. Jul 18 '05 #5

 P: n/a Robert Brewer wrote: # bsddb version: c = bsddb.btopen(None) for i in x: if i not in c: c[i] = None You might try a minor change: for i in x: c[i] = None The fewer the redundancies the larger the speed gain (I suppose; that really needs testing to be sure). Peter Jul 18 '05 #6

 P: n/a Bonjour ! Les dictionnaires sont plus rapides lors de la recherche ("... in ..."), car il y a utilisation de la clef. Avec une liste, la recherche est séquentielle. in english (try) : For search (... in ...) : - dictionnary use key search - list use sequentiel search @-salutations -- Michel Claveau Jul 18 '05 #7

 P: n/a "Robert Brewer" wrote in message news:... I'm dedup'ing a 10-million-record dataset, trying different approaches for building indexes. The in-memory dicts are clearly faster, but I get Memory Errors (Win2k, 512 MB RAM, 4 G virtual). Any recommendations on other ways to build a large index without slowing down by a factor of 25? In case you are interested in alternatives approaches...here's how I typically do this: step 1: sort the file using a separate sort utility (unix sort, cygwin sort, etc) step 2: have a python program read in rows, compare each row to the prior, write out only one row for each set ks Jul 18 '05 #8

 P: n/a Buck Nuggets wrote: "Robert Brewer" wrote in message news:...I'm dedup'ing a 10-million-record dataset, trying different approachesfor building indexes. The in-memory dicts are clearly faster, but I getMemory Errors (Win2k, 512 MB RAM, 4 G virtual). Any recommendations onother ways to build a large index without slowing down by a factor of25? In case you are interested in alternatives approaches...here's how I typically do this: step 1: sort the file using a separate sort utility (unix sort, cygwin sort, etc) step 2: have a python program read in rows, compare each row to the prior, write out only one row for each set Good solution, but wayyyy too much effort. You probably know it: If you are seeking for duplicates, and doing it by complete ordering, then you are thwowing lots of information away, since you are not seeking for neighborship, right? That clearly means: it must be inefficient. No offense, just trying to get you on the right track! ciao - chris -- Christian Tismer :^) Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ Jul 18 '05 #9

 P: n/a Buck Nuggets wrote: step 1: sort the file using a separate sort utility (unix sort, cygwin sort, etc) step 2: have a python program read in rows, compare each row to the prior, write out only one row for each set It might be worth mentioning that if your idea of 'sameness' is identical textual representation, the '-u' flag of 'sort' does step 2 for you. Won't work in the more general case, but then 'sort' might not work either. YMMV. Stefan, -- Stefan Axelsson (email at http://www.cs.chalmers.se/~sax) Jul 18 '05 #10

 P: n/a Christian Tismer wrote in message news:... Buck Nuggets wrote: "Robert Brewer" wrote in message news:... In case you are interested in alternatives approaches...here's how I typically do this: step 1: sort the file using a separate sort utility (unix sort, cygwin sort, etc) step 2: have a python program read in rows, compare each row to the prior, write out only one row for each set Good solution, but wayyyy too much effort. You probably know it: If you are seeking for duplicates, and doing it by complete ordering, then you are thwowing lots of information away, since you are not seeking for neighborship, right? That clearly means: it must be inefficient. No offense, just trying to get you on the right track! Ha, that's ok. I've been doing exactly this kind of thing for over twenty years (crusty old database developer). I think that you will find that it is more efficient in both development and run time. And it's simple enough that once you start down this path you won't need to brainstorm on how to get it to work. Rather than taking 2-18 hours with the previously mentioned solutions (which require index-building and 10 million index lookups), you'll probably do the entire thing in about 10 minutes (9 minutes to sort file + 1 minute to check dups). Jul 18 '05 #11

 P: n/a On 30 Mar 2004 06:57:16 -0800, bu*********@yahoo.com (Buck Nuggets) wrote: Christian Tismer wrote in message news:... Buck Nuggets wrote: > "Robert Brewer" wrote in message news:... > > In case you are interested in alternatives approaches...here's how I > typically do this: > > step 1: sort the file using a separate sort utility (unix sort, cygwin > sort, etc) > > step 2: have a python program read in rows, > compare each row to the prior, > write out only one row for each set Good solution, but wayyyy too much effort. You probably know it: If you are seeking for duplicates, and doing it by complete ordering, then you are thwowing lots of information away, since you are not seeking for neighborship, right? That clearly means: it must be inefficient. No offense, just trying to get you on the right track!Ha, that's ok. I've been doing exactly this kind of thing for overtwenty years (crusty old database developer). I think that you willfind that it is more efficient in both development and run time. Andit's simple enough that once you start down this path you won't needto brainstorm on how to get it to work.Rather than taking 2-18 hours with the previously mentioned solutions(which require index-building and 10 million index lookups), you'llprobably do the entire thing in about 10 minutes (9 minutes to sortfile + 1 minute to check dups). From a crusty old unix developer to a crusty old database developer... Part 2 can be done by piping the output of sort to the 'uniq' program (available in cygwin and mingw also, I think). And it's no effort, if it fits the bill. It may be inneficient with regards to sorting algorithms, but extremely efficient in terms of system and developer resources. --dang Jul 18 '05 #12

 P: n/a Dang Griffith wrote in message news:<8e******************************@news.terane ws.com>... From a crusty old unix developer to a crusty old database developer... Part 2 can be done by piping the output of sort to the 'uniq' program (available in cygwin and mingw also, I think). And it's no effort, if it fits the bill. It may be inneficient with regards to sorting algorithms, but extremely efficient in terms of system and developer resources. ha, yep - forgot to mention that you can drop dupes right in some sort utilities or via a program like uniq. I suppose the only reason to use python after the sort would be if you have some unusual rules to include in the delta calculation (don't include this record if status-field='del', etc). ks Jul 18 '05 #13

 P: n/a Dang Griffith writes: From a crusty old unix developer to a crusty old database developer... Part 2 can be done by piping the output of sort to the 'uniq' program (available in cygwin and mingw also, I think). From a maybe even crustier unix developer: "sort -u" strips dups. Jul 18 '05 #14

### This discussion thread is closed

Replies have been disabled for this discussion.