Re: Populating a dictionary, fast [SOLVED]

A Tuesday 13 November 2007, Steven D'Aprano escrigué:
On Tue, 13 Nov 2007 17:27:11 +0100, Francesc Altet wrote:
I don't know exactly why do you need a dictionary for keeping the
data, but in case you want ultra-fast access to values, there is no
replacement for keeping a sorted list of keys and a list with the
original indices to values, and the proper list of values. Then,
to access a value, you only have to do a binary search on the
sorted list, another lookup in the original indices list and then
go straight to the value in the value list. This should be the
faster approach I can think of.

Maybe on Bizarro World, but not on Planet Earth.

Searching a dict takes on average a constant amount of time,
regardless of the key and the size of the dict. Because dicts are the
basis of Python's namespaces, it is optimized up the wazoo, and being
implemented in C it is extremely fast.

Using your suggestion, to get a value: you have to do a binary search
which is O(log N) instead of O(1), then ANOTHER lookup into a list of
indices, and finally a THIRD lookup to actually retrieve the value --
all implemented in relatively slow Python instead of fast C.

Well, the bisect module in Python is implemented in fast C. Apart from
that, you are basically right, see below.

And let's not even discuss the overhead of keeping these three lists
synchronized.

But don't take my word for it: measure for yourself. I'm not even
going to attempt to code your suggestion, but here's how you measure
the time it takes for dictionary lookup.


# Create a dataset to search on.
D = {}
chars = "abcdefghijklmnopqrstuvwxyz"
triplets = (a+b+c for a in chars for b in chars for c in chars)
for i, s in enumerate(triplets):
D[s] = i # D is of the form {'abc': 12345}

# Now time a successful search for an arbitrary triplet.
import timeit
min(timeit.Timer("D['foo']", "from __main__ import D").repeat(6))


On my PC, it takes about 0.2 seconds per million searches.

Oh yes. All of you are right, guys. I've implemented code (attached)
for measuring the lookup times using a a dictionary and using a binary
search approach (using numpy, mostly for space efficiency) and here are
my results:

$ python2.5 gq-dict.py
Creating the dictionary...
Time for dict creation: 89.115
Items in dict: 8191180
Timing queries...
Time for querying: 39.44

$ python2.5 gq-binary-search.py
Creating the lists...
Time for lists creation: 4.245
Sorting...
Time for sorting: 6.195
Timing queries...
Time for querying: 108.1

i.e. a dict approach proves to be almost 3x faster than a regular binary
search (5 us/lookup vs 13 us/lookup).

I think I've got messed on some benchmarks that I've done on that
subject some time ago, but either my memory is bad or I've made some
mistake on those experiments. My apologies.

Cheers,

--
0,0< Francesc Altet     http://www.carabos.com/
V V Cárabos Coop. V.   Enjoy Data
"-"

Attachment: gq-binary-search.py
Description: application/python

Attachment: gq-dict.py
Description: application/python

Relevant Pages

  • Re: Tuple question
    ... | No idea -- could just as well be a dict, an array.array, whatever. ... | lists for dict-keying roles, ... I think you'd have roughly the tuple that languages of the Lisp family ...
    (comp.lang.python)
  • Re: Dict sharing vs. duplication
    ... list or dict value), and thus can safely invalidate exactly the string ... lset ldl 3 nope ... The lset and dict implementations in the core are careful to not invalidate string reps until *after* the modification succeeded, at a small but not zero cost. ... For "deep structures" (nested dicts and lists) the data management code for that behaviour becomes more involved and costly. ...
    (comp.lang.tcl)
  • Re: How to return an array?
    ... *some* toplevel commands have been made to ... - dict set shouls accept paths only as lists, ... and to make syntax more similar to array set. ...
    (comp.lang.tcl)
  • Re: TIP#308 Published: Tcl Database Connectivity (TDBC)
    ... But i see the value in specifing your column names and ordering in just ... So building the list of lists style from a dict based resultset would ...
    (comp.lang.tcl)
  • Re: How to return an array?
    ... The key for making the new "dict" API really good is, ... if paths were lists (and keys looking like lists would ... >> element to a path'd key, whereas array set adds several key value ... seeing [dict set ...] programmers will surely first think about ...
    (comp.lang.tcl)