iterating quickly through list of tuples

Question

I wonder whether there's a quicker and less time consuming way to iterate over a list of tuples, finding the right match. What I do is:

# this is a very long list.
my_list = [ (old1, new1), (old2, new2), (old3, new3), ... (oldN, newN)]

# go through entire list and look for match
for j in my_list:
    if j[0] == VALUE:
        PAIR_FOUND = True
        MATCHING_VALUE = j[1]
        break

this code can take quite some time to execute, depending on the number of items in the list. I'm sure there's a better way of doing this.

score 80 · Answer 1 · answered Apr 15 '13 at 17:51

80

I think that you can use

for j,k in my_list:
  [ ... stuff ... ]

answered Apr 15 '13 at 17:51

Eric

19,525
19
84
147

2

but that won't make the loop execute faster. will it? – memyself Apr 15 '13 at 17:52
You should check out this other question : http://stackoverflow.com/questions/2191699/find-an-element-in-a-list-of-tuples – Eric Apr 15 '13 at 17:54
found it easy to understand, tks – Pedro Lobito Nov 24 '16 at 21:40

Sanjay T. Sharma · Accepted Answer · 2013-04-15T18:17:59.300

29

Assuming a bit more memory usage is not a problem and if the first item of your tuple is hashable, you can create a dict out of your list of tuples and then looking up the value is as simple as looking up a key from the dict. Something like:

dct = dict(tuples)
val = dct.get(key) # None if item not found else the corresponding value

EDIT: To create a reverse mapping, use something like:

revDct = dict((val, key) for (key, val) in tuples)

edited Apr 15 '13 at 18:17

answered Apr 15 '13 at 17:55

Sanjay T. Sharma

22,857
4
59
71

that looks great but will only allow me to search by `old value`. do I need to create two dicts so that I can search in the new and old value fields? – memyself Apr 15 '13 at 18:08
@memyself: Yes, you are correct. If you need to search by *both* old and new values, you'll have to create two dicts. But I guess it's not that bad if all you want is fast look-ups. I have added the sample snippet for creating reverse dict. – Sanjay T. Sharma Apr 15 '13 at 18:16
1

I didn't know about get(), this has just made my life so much simpler. – dgBP Feb 26 '16 at 18:59

score 5 · Answer 3 · answered May 12 '17 at 15:05

The question is dead but still knowing one more way doesn't hurt:

my_list = [ (old1, new1), (old2, new2), (old3, new3), ... (oldN, newN)]

for first,*args in my_list:
    if first == Value:
        PAIR_FOUND = True
        MATCHING_VALUE = args
        break

score 2 · Answer 4 · answered Apr 15 '13 at 17:54

The code can be cleaned up, but if you are using a list to store your tuples, any such lookup will be O(N).

If lookup speed is important, you should use a dict to store your tuples. The key should be the 0th element of your tuples, since that's what you're searching on. You can easily create a dict from your list:

my_dict = dict(my_list)

Then, (VALUE, my_dict[VALUE]) will give you your matching tuple (assuming VALUE exists).

score 1 · Answer 5 · answered May 05 '17 at 08:53

I wonder whether the below method is what you want.

You can use defaultdict.

>>> from collections import defaultdict
>>> s = [('red',1), ('blue',2), ('red',3), ('blue',4), ('red',1), ('blue',4)]
>>> d = defaultdict(list)
>>> for k, v in s:
       d[k].append(v)    
>>> sorted(d.items())
[('blue', [2, 4, 4]), ('red', [1, 3, 1])]

iterating quickly through list of tuples

5 Answers5

Linked

Related