Python dictionary inspired hash table implementation

[bearophile]

Moritz Warning:
> Can you provide a Python example that pre-computes an array with strings 
> in a separate function?

Experience tells me that creating benchmarks is a very tricky thing, it's really easy to do something wrong. Here I have created a new pair for you, but I am ready to fix them if someone spots a problem. If you need help just ask me.
You can create two more versions for your data structure and for the hash map of Tango, if you want.

Your timings seem quite good. Python 2.6b may be a bit faster, but 2.5.2 is plenty enough.

------------------

from timeit import default_timer as clock

def main():
    strings = ["key_" + str(i) for i in xrange(1000000)]

    t = clock()
    d = dict.fromkeys(strings, 0)
    print round(clock() - t, 2)
    if len(d) < 200: print d

import psyco; psyco.bind(main)
main()

------------------

import std.stdio: putr = writefln;
import std.string: format;

version (Win32) {
    import std.c.windows.windows: GetTickCount;
    double clock() {
        return cast(double)GetTickCount() * 1.0e-03;
    }
}
version (linux) {
    import std.c.linux.linux: time;
    double clock() {
        return cast(double)time(null);
    }
}

void main() {
    const uint N = 1_000_000;

    // this doesn't save much time
    //auto strings = (cast(string*)malloc(string.sizeof * N))[0 .. N];

    auto strings = new string[N];
    for (uint i; i < N; ++i)
        strings[i] = "key_" ~ format(i);

    auto t = clock();
    int[string] d;
    foreach(s; strings)
        d[s] = 0;
    putr(clock() - t);

    if (N < 200) putr(d);
}


One of the things I miss in Python is the ability to write numbers as 1_000_000.

Bye,
bearophile