Searching a python list quickly?

Question

I have a dictionary and a list. The list is made up of values. The dictionary has all of the values plus some more values.

I'm trying to count the number of times the values in the list show up in the dictionary per key/values pair.

It looks something like this:

for k in dict:
 count = 0
 for value in dict[k]:
  if value in list:
   count += 1
   list.remove(value)
 dict[k].append(count)

I have something like ~1 million entries in the list so searching through each time is ultra slow.

Is there some faster way to do what I'm trying to do?

Thanks, Rohan

Answer 1

for val in my_list:
   if val in my_dict:
      my_dict[val] = my_dict[val] + 1
   else:
      my_dict[val] = 0

What you still need

• Handle case when val is not in dict

Answer 2

If you search in a list, then convert this list to a set, it will be much faster:

listSet = set(list)

for k, values in dict.iteritems():
    count = 0
    for value in values:
        if value in listSet:
            count += 1
            listSet.remove(value)
    dict[k].append(count)

list = [elem for elem in list if elem in listSet]
# return the original list without removed elements

Answer 3

You're going to have all manner of trouble with this code, since you're both removing items from your list and using an index into it. Also, you're using list as a variable name, which gets you into interesting trouble as list is also a type.

You should be able to get a huge performance improvement (once you fix the other defects in your code) by using a set instead of a list. What you lose by using a set is the ordering of the items and the ability to have an item appear in the list more than once. (Also your items have to be hashable.) What you gain is O(1) lookup time.

Answer 4

I changed the last line to append to the dictionary. It's a defaultdict(list). Hopefully that clears up some of the questions. Thanks again.