searching a value of a dict (each value is a list)

[bearophileHUGS at lycos.com]

Seongsu Lee:
> What do you think of this? Ideas with less space complexity?

You can put the second group of keys in a second dictionary, so you
don't have to mangle them, and it may be a bit faster.

Regarding the space complexity, I don't know how you can reduce it
with Python. Probably you can create a list of long, sort it and use
bisect on it to find the keys. Such longs can be a combination of
shifted integer OR the other integer that is the key of the original
dict. But I don't how much you can gain like this.

Another solution to reduce space is to use a tiny external module
written in C, Pyrex or D. Here follows some simple D code you can
modify a bit to make it work with Pyd (http://pyd.dsource.org/):


import std.traits: ReturnType;
import std.stdio: writefln;

struct TyInt_int {
    int el, n;
    int opCmp(TyInt_int other) {
        if (el == other.el)
            return 0;
        return (el < other.el) ? -1 : 1;
    }
}

int bisect(TyElem, TyData, TyFun)(TyElem[] a, TyData x, TyFun key) {
    int lo = 0;
    int hi = a.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (x < key(a[mid]))
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

void main() {
    int[][int] int_arr;
    int_arr[1] = [1, 2, 3, 4, 5];
    int_arr[1] = [10, 11, 12],
    int_arr[900000] = [100, 101, 102, 103, 104, 105],
    int_arr[900001] = [20, 21, 22],
    int_arr[999999] = [15, 16, 17, 18, 19];

    int tot_len = 0;
    foreach(arr; int_arr)
        tot_len += arr.length;

    auto data_arr = new TyInt_int[](tot_len);
    int i = 0;
    foreach(n, arr; int_arr)
        foreach(el; arr)
            data_arr[i++] = TyInt_int(el, n);

    data_arr.sort;
    writefln(bisect(data_arr, 100, (TyInt_int ii){return ii.el;}));
}

Bye,
bearophile