1
\$\begingroup\$

Is there a more efficient way of achieving the same result besides setting up a database?

# In reality, contains 4 million tuples.
stuff_tuple = (
    ('hello', 241, 1),
    ('hi', 243, 3),
    ('hey', 242, 2)
)

# Convert tuple to set for faster searching?
stuff_set = set(stuff_tuple)

# Only first two values are known ("hello", 241), ('hi', 243), etc.
for item in stuff_set:
    if item[0] == 'hello' and item[1] == 241:
        print item[2]
\$\endgroup\$
0
4
\$\begingroup\$

If all your queries are similar to the example, you would obviously benefit from storing the data in a dict where a tuple of two values is the key, and the value is a list of ints -- all of the third items that share the same key.

from collections import defaultdict

stuff_dict = defaultdict(list)
for t in stuff_tuple:
    stuff_dict[t[:2]].append(t[2])

for item in stuff_dict['hello', 241]:
    print item
\$\endgroup\$
0
-1
\$\begingroup\$

This question suggests that dictionaries and sets - which are both based on hashtables internally -- are the fastest for random retrieval of hashable data (which your sample seems to b). It's always a good idea to try the base data structures in Python, they're usually pretty high quality :)

If that's not fast enough, you have a couple of options.

If you can come up with a single sortable key value for your list, you could use the bisect module to speed up searches. For example, if you had a deterministic way of turning the first two keys into a number, and then sort on that number, bisect should make it easy to find items quickly. The big drawback here is that you're on the hook for coming up with the method for creating that numberic key, which can be dicey depending on your data set.

The less ambitious (but maybe less risky) is to subdivide the data yourself so you don't search 4 million items every time. If you have to use data like the data in your example, you should look at patterns in your sample for characteristics that group it into similarly sized subsets and store the data that way first -- for example, if your whole table of four million entries included a roughly flat distribution of the second (integer) key you could bust the whole up into buckets in a pre-pass, producing a few hundred or few thousand lists with self-similar second keys:

 list_241 = [('hello', 241, 1), ('goodbye', 241, 2), ('yo!', 241, 3)....]
 list_242 = [('hi', 242, 3), ('hola', 242, 4)...]

then you store the lists in a dictionary and grab them as a first pass, then do the brute force search in the sub-list of thousands instead of the master list of millions. Of course some data won't lend itself to this either, but if it looks anything like your sample it should not be too hard. THe binning doesn't have to be super logical - you could bin on the length of the string in item[0] or the first letter as easily as you could on item 1 -- but to be useful it will need to produces bins of similar size. The nice thing is that with really big lists it's easy to rack up big gains: even going from 1 list of 4million to 10 lists of 400000 will probably make things faster.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.