2

I am finding the fastest way to search item in a list. As I found that in Python, it is better to use set to search item instead of using a list. So I replaced the list by set. However, all items in the set are an object. I want to search if there's object id equals to the id that I want to find. If it is, then return that object.

I can do it in a simple for-loop, but I do not know how can it be improved in set if I still loop all elements to find the item.

def find(allItems, id):
  for item in allItems:
      if (item.getId() == id):
          return item

from sets import Set

allItems = Set()

allItems.add(itemObj)

find(allItems, 1)
androidnewbie
  • 374
  • 1
  • 6
  • 23
  • 3
    Use a python dictionary: `allItems = {}`. You can add an item via `allItems[item.getId()] = item`. You can lookup items quickly by their id via `allItems[id]`. – James Lawson Sep 24 '17 at 08:24
  • 3
    Did you not see the big *”Deprecated since version 2.6”* on [`sets`](https://docs.python.org/2/library/sets.html)? `set` is a built in class. But given that your items must already implement `__hash__` and `__eq__` to be placed in a set to begin with, it’s not clear why you need to explicitly check each one’s ID. You’re right that it’s no more efficient than a list if you can’t use the hash – jonrsharpe Sep 24 '17 at 08:26
  • So can you show how to search it using dictionary? – androidnewbie Sep 24 '17 at 08:30
  • @androidnewbie you *index into the dictionary with the key* like so `my_dict[key]`, where `key` is some `id`. This will throw an error if it doesn't exist, which you can try to catch, or you can use the `.get` method, which will return `None` or any provided default value if it isn't in the dict – juanpa.arrivillaga Sep 24 '17 at 08:36
  • @androidnewbie sure! I've posted an answer with an explanation of how to use a dictionary. – James Lawson Sep 24 '17 at 08:41

2 Answers2

2

Below summarises how to use a python dictionary for your example.

def find(allItems, id):
  return allItems[id]

def addItem(allItems, item):
  allItems[item['id']] = item

# create a python dictionary called `allItems`
allItems = {}

# add some items to the dictionary
item1 = { 'id': 1, 'name': 'James' }
item2 = { 'id': 2, 'name': 'Susan' }
addItem(allItems, item1)
addItem(allItems, item2)

# now lookup an item by its id
result = find(allItems, 1)
print result['name']  # ==> 'James'

As the documentation explains, dictionaries are good when you want to lookup items by their id.

Unlike sequences, which are indexed by a range of numbers, dictionaries are indexed by keys ... The main operations on a dictionary are storing a value with some key and extracting the value given the key.

What this means is that you can find the item immediately if you know the item's "key" – i.e. the item's id. There is no need to use a for loop.

James Lawson
  • 8,150
  • 48
  • 47
1

Using python's set, where you allocate the ids 

d = { id, id2, id3, .. idN }

Then you can simply state if id in d to verify an element is in the set (without iterating it). The reason this works is because Set in python implemented like dict's without values (hashtable). This gives you O(1) on average for membership checking. 

s = set([1, 2, 3, 4, 5])

if 1 in s:
    print 'in!'  # in! is printed

Taken fron this answer (Thanks @juanpa.arrivillaga)

CPython's sets are implemented as something like dictionaries with dummy values (the keys being the members of the set), with some optimization(s) that exploit this lack of values

Or, another option is to use sorted collection. (This can't be done with Set so either you implement SortedSet class or use a list object)

One fast searching algorithm is binary search. (bisect module)

You can use this algorithm after you sort your collection.

Chen A.
  • 10,140
  • 3
  • 42
  • 61