Which is faster, a Dictionary Lookup or an Index Operation?

Please support our Python advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved

Join Date: Aug 2009
Posts: 17
Reputation: SuperMetroid is an unknown quantity at this point 
Solved Threads: 0
SuperMetroid's Avatar
SuperMetroid SuperMetroid is offline Offline
Newbie Poster

Which is faster, a Dictionary Lookup or an Index Operation?

 
-1
  #1
Oct 4th, 2009
I'm compiling an extremely large list of usernames, and I want to know which is a faster method of checking what is already in the list.

If anyone can give some insight as to how Python deals with each that would be much appreciated!
Last edited by SuperMetroid; Oct 4th, 2009 at 1:00 am.
Reply With Quote Quick reply to this message  
Join Date: May 2009
Posts: 232
Reputation: sravan953 has a little shameless behaviour in the past 
Solved Threads: 28
sravan953's Avatar
sravan953 sravan953 is online now Online
Posting Whiz in Training

Re: Which is faster, a Dictionary Lookup or an Index Operation?

 
-1
  #2
Oct 4th, 2009
If you want to check if the username is present, the easiest thing to do is:
  1. usern=['sravan953','Dan08','SuperMetroid','vegaseat']
  2. 'SuperMetroid' in usern
  3. """
  4. >> True
  5. """
Reply With Quote Quick reply to this message  
Join Date: Aug 2009
Posts: 17
Reputation: SuperMetroid is an unknown quantity at this point 
Solved Threads: 0
SuperMetroid's Avatar
SuperMetroid SuperMetroid is offline Offline
Newbie Poster

Re: Which is faster, a Dictionary Lookup or an Index Operation?

 
-1
  #3
Oct 4th, 2009
Is that the most efficient for an extremely big list?
I really want to know what is going on behind the scenes..
And what would be fastest in Big O notation.
Reply With Quote Quick reply to this message  
Join Date: Jul 2008
Posts: 961
Reputation: Gribouillis is a jewel in the rough Gribouillis is a jewel in the rough Gribouillis is a jewel in the rough 
Solved Threads: 220
Gribouillis's Avatar
Gribouillis Gribouillis is offline Offline
Posting Shark

Re: Which is faster, a Dictionary Lookup or an Index Operation?

 
-1
  #4
Oct 4th, 2009
I don't know exactly what you want to compare, but here is a code which measures the time necessary to execute 1,000,000 times a dictionary lookup (the statement '7498' in D )
  1. from timeit import Timer
  2.  
  3. D = dict()
  4.  
  5. for i in range(10000):
  6. D[str(i)] = i
  7.  
  8. print(Timer("'7498' in D", "from __main__ import D").timeit())
For your problem, I would choose a dictionary lookup over other methods.
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,075
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 939
Moderator
vegaseat's Avatar
vegaseat vegaseat is offline Offline
DaniWeb's Hypocrite

Re: Which is faster, a Dictionary Lookup or an Index Operation?

 
1
  #5
Oct 4th, 2009
Dictionary key searches are highly optimized, since Python itself uses dictionaries internally. There are entire articles published that recommend converting a long list into a dictionary for fast searches. Still faster than a list search even with the time it takes to convert.

I remember seeing one of these articles in:
http://code.activestate.com/recipes/langs/python/
Last edited by vegaseat; Oct 4th, 2009 at 4:15 pm. Reason: activestate
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Join Date: Oct 2004
Posts: 4,075
Reputation: vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice vegaseat is just really nice 
Solved Threads: 939
Moderator
vegaseat's Avatar
vegaseat vegaseat is offline Offline
DaniWeb's Hypocrite

Re: Which is faster, a Dictionary Lookup or an Index Operation?

 
2
  #6
Oct 4th, 2009
I got curious, so I did a little test run ...
  1. # use Python3's dictionary comprehension to
  2. # speed up list searches
  3. #
  4. # the time it takes to create the dictionary
  5. # will be regained after about 6 searches
  6. # as list size increases this goes down to > 1 search
  7. # tested with Python 3.1.1 vegaseat
  8.  
  9. import timeit
  10.  
  11. data = """\
  12. Bill
  13. Brutus
  14. Daphne
  15. Dorky
  16. Al
  17. Kristin
  18. Cloe
  19. Carlos
  20. Pete
  21. Pheobe
  22. Jerry
  23. Jack
  24. Justin
  25. John
  26. Julie
  27. Joe
  28. Moe
  29. Theo
  30. Albert
  31. Alberto
  32. Pauline
  33. Paula
  34. Christopher
  35. Gisela
  36. Lamar
  37. Donna
  38. Demitrius
  39. Frank
  40. Heidi
  41. Margot
  42. Cindy
  43. Doris
  44. Harry
  45. Larry
  46. Dilbert
  47. Mary
  48. Robert
  49. Sophia
  50. Samuel
  51. Candy
  52. Tawny
  53. Terry
  54. Markus
  55. Veronika
  56. Norbert
  57. Zoe
  58. Udo"""
  59.  
  60. # create a list of names from the data
  61. mylist = data.split('\n')
  62.  
  63. # create a dictionary with name:zero pairs from the list
  64. mylist_d = {name:0 for name in mylist}
  65.  
  66. # search for 'Udo' is the last item in the list and dictionary
  67. statement = "'Udo' in mylist"
  68. setup = "from __main__ import mylist"
  69. t = timeit.Timer(statement, setup)
  70. # doing 1000000 passes (default) gives microseconds per pass
  71. elapsed = t.timeit()
  72. sf = "Code %-20s takes %0.3f micro-seconds/pass"
  73. print( sf % (statement, elapsed))
  74.  
  75. statement = "'Udo' in mylist_d"
  76. setup = "from __main__ import mylist_d"
  77. t = timeit.Timer(statement, setup)
  78. elapsed = t.timeit()
  79. sf = "Code %-20s takes %0.3f micro-seconds/pass"
  80. print( sf % (statement, elapsed))
  81.  
  82. print('-'*60)
  83.  
  84. statement = "{name:0 for name in mylist}"
  85. setup = "from __main__ import mylist"
  86. t = timeit.Timer(statement, setup)
  87. elapsed = t.timeit()
  88. sf = "Code %-20s takes %0.3f micro-seconds/pass"
  89. print( sf % (statement, elapsed))
  90.  
  91. print('-'*60)
  92.  
  93. # optional tests to show the last 4 items in list and dictionary
  94. print("Last 4 items in list and dictionary:")
  95. print(mylist[-4:])
  96. print(list(mylist_d.keys())[-4:])
  97.  
  98. """my result -->
  99. Code 'Udo' in mylist takes 2.193 micro-seconds/pass
  100. Code 'Udo' in mylist_d takes 0.182 micro-seconds/pass
  101. ------------------------------------------------------------
  102. Code {name:0 for name in mylist} takes 11.151 micro-seconds/pass
  103. ------------------------------------------------------------
  104. Last 4 items in list and dictionary:
  105. ['Veronika', 'Norbert', 'Zoe', 'Udo']
  106. ['Dilbert', 'Julie', 'Al', 'Udo']
  107. """
May 'the Google' be with you!
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



Tag cloud for Python
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC