Orders of magnitude

[Robert Brewer]

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

[Paul Rubin]

"Robert Brewer" <fu******@amor.org> 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.

[Josiah Carlson]

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

[PF]

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.

[Paul Rubin]

Josiah Carlson <jc******@nospam.uci.edu> 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.

[Peter Otten]

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

[Michel Claveau/Hamster]

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

[Buck Nuggets]

"Robert Brewer" <fu******@amor.org> wrote in message news:<ma*************************************@pyth on.org>...

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

[Christian Tismer]

Buck Nuggets wrote:

"Robert Brewer" <fu******@amor.org> wrote in message news:<ma*************************************@pyth on.org>...

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

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 :^) <mailto:ti****@stackless.com>
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 [phone] home [phone] mobile [phone]
PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04
whom do you want to sponsor today? http://www.stackless.com/

[Stefan Axelsson]

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)

[Buck Nuggets]

Christian Tismer <ti****@stackless.com> wrote in message news:<ma*************************************@pyth on.org>...

Buck Nuggets wrote:

"Robert Brewer" <fu******@amor.org> wrote in message news:<ma*************************************@pyth on.org>...

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).

[Dang Griffith]

On 30 Mar 2004 06:57:16 -0800, bu*********@yahoo.com (Buck Nuggets)
wrote:

Christian Tismer <ti****@stackless.com> wrote in message news:<ma*************************************@pyth on.org>...

Buck Nuggets wrote:

> "Robert Brewer" <fu******@amor.org> wrote in message news:<ma*************************************@pyth on.org>...
>
> 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).

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

[Buck Nuggets]

Dang Griffith <no*****@noemail4u.com> 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

[Paul Rubin]

Dang Griffith <no*****@noemail4u.com> 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.