Large Dictionaries

[Chris Foote]

Hi all.

I have the need to store a large (10M) number of keys in a hash table,
based on a tuple of (long_integer, integer). The standard python
dictionary works well for small numbers of keys, but starts to
perform badly for me inserting roughly 5M keys:

# keys dictionary metakit (both using psyco)
------ ---------- -------
1M 8.8s 22.2s
2M 24.0s 43.7s
5M 115.3s 105.4s

Has anyone written a fast hash module which is more optimal for
large datasets ?

p.s. Disk-based DBs are out of the question because most
key lookups will result in a miss, and lookup time is
critical for this application.

Cheers,
Chris

[Lawrence D'Oliveiro]

In article <ma***************************************@python. org>,
"Tim Peters" <ti********@gmail.com> wrote:

For example, the O(N log N) heapsort is unreasonable compared to the
O(N**2) bubblesort by that reasoning (pre-sorted is actually a bad
case for heapsort, but a good case for bubblesort)? O(N log N)
sorting algorithms helped by pre-existing order are uncommon, unless
they do extra work to detect and exploit pre-existing order.

Shellsort works well with nearly-sorted data. It's basically a smarter
version of bubblesort with much improved efficiency. It's also very
compact to implement.

[Lawrence D'Oliveiro]

In article <11********************@j55g2000cwa.googlegroups.c om>,
"Iain King" <ia******@gmail.com> wrote:

Lawrence D'Oliveiro wrote:

In article <44********@nntp0.pdx.net>,
Scott David Daniels <sc***********@acm.org> wrote:

>For example, time timsort (Python's internal sort) on pre-sorted
>data; you'll find it is handled faster than random data.

But isn't that how a reasonable sorting algorithm should behave? Less
work to do if the data is already sorted?

An already sorted list can be pathological for Quicksort, depending on
how you code it.

I did say "reasonable". :)

[Tim Peters]

[Tim Peters]

...
O(N log N) sorting algorithms helped by pre-existing order are
uncommon, unless they do extra work to detect and exploit
pre-existing order.

[Lawrence D'Oliveiro] Shellsort works well with nearly-sorted data. It's basically a smarter
version of bubblesort with much improved efficiency. It's also very
compact to implement.

shellsort is much more a refinement of insertion-sort than of
bubblesort, but is not an O(N log N) algorithm regardlesss. A nice,
succinct summary of what was known about shellsort's behavior as of
Sedgewick's 1996 "Analysis of Shellsort and Related Algorithms" can be
found here:

http://www.inf.fh-flensburg.de/lang/...ll/shellen.htm

[Marcin Ciura]

Tim Peters wrote:

shellsort is much more a refinement of insertion-sort than of
bubblesort, but is not an O(N log N) algorithm regardlesss.

With a judiciously chosen increment sequence,
the number of comparisons made by shellsort
*is* of the order N log N for practical values of N.
See Figure 8 in
http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf
Marcin

[Duncan Booth]

Marcin Ciura wrote:

Tim Peters wrote:

shellsort is much more a refinement of insertion-sort than of
bubblesort, but is not an O(N log N) algorithm regardlesss.
With a judiciously chosen increment sequence,
the number of comparisons made by shellsort
*is* of the order N log N for practical values of N.
See Figure 8 in
http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf

That isn't what the reference says. It only covers N up to a few thousand.
Practical values of N need to at least go up into the millions.

Read the summary: Using sequential analysis, the search for optimal increment sequences
for Shellsort was accelerated enough to find them for arrays up to
several thousand elements. .... However, the sequences obtained so far are too short to draw a
reliable conclusion whether an appropriate sequence of increments can
make Shellsort a O(N logN) sorting method on the average. Some
hypotheses may be possible when the sequences are prolonged to sort
arrays of about 10^5 elements.

[Marcin Ciura]

Duncan Booth wrote:

Marcin Ciura wrote:

See Figure 8 in
http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf

That isn't what the reference says. It only covers N up to a few thousand.
Practical values of N need to at least go up into the millions.

Please look at the performance graph of Tokuda's increment sequence.
You can see that it scales pretty well at least up to 100 million.
Marcin

[Duncan Booth]

Marcin Ciura wrote:

Duncan Booth wrote:

Marcin Ciura wrote:

See Figure 8 in
http://sun.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf

That isn't what the reference says. It only covers N up to a few
thousand. Practical values of N need to at least go up into the
millions.

Please look at the performance graph of Tokuda's increment sequence.
You can see that it scales pretty well at least up to 100 million.

Ah sorry, I misread it. It was sequences with several thousand elements,
which corresponds to N of 100 million.

[Klaas]

Thomas Ganss wrote:

Klaas schrieb:

4. Insert your keys in sorted order.

This advice is questionable -
it depends on the at least on the db vendor and probably
sometimes on the sort method, if inserting pre-sorted
values is better.

The article I wrote that you quoted named a specific vendor (berkeley
db) for which my advice is unquestionable and well-known.

-Mike