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 -- http://mail.python.org/mailman/listinfo/python-list
