CODEWITHSUNDEEP
python
androidnewbie
androidnewbie

Reputation: 374

Python Fastest search algorithm using set

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)

Upvotes: 2

Views: 4612

Answers (2)

James Lawson
James Lawson

Reputation: 8618

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.

Upvotes: 2

Chen A.
Chen A.

Reputation: 11280

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.

Upvotes: 1

Related Questions