944,111 Members | Top Members by Rank

Ad:
  • Python Discussion Thread
  • Marked Solved
  • Views: 852
  • Python RSS
Oct 4th, 2009
-1

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

Expand Post »
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.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SuperMetroid is offline Offline
17 posts
since Aug 2009
Oct 4th, 2009
-1

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

If you want to check if the username is present, the easiest thing to do is:
python Syntax (Toggle Plain Text)
  1. usern=['sravan953','Dan08','SuperMetroid','vegaseat']
  2. 'SuperMetroid' in usern
  3. """
  4. >> True
  5. """
Reputation Points: 2
Solved Threads: 30
Posting Whiz in Training
sravan953 is offline Offline
242 posts
since May 2009
Oct 4th, 2009
-1

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

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.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SuperMetroid is offline Offline
17 posts
since Aug 2009
Oct 4th, 2009
-1

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

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 )
python Syntax (Toggle Plain Text)
  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.
Reputation Points: 930
Solved Threads: 668
Posting Maven
Gribouillis is offline Offline
2,656 posts
since Jul 2008
Oct 4th, 2009
1

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

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
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004
Oct 4th, 2009
2

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

I got curious, so I did a little test run ...
python Syntax (Toggle Plain Text)
  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. """
Moderator
Reputation Points: 1333
Solved Threads: 1404
DaniWeb's Hypocrite
vegaseat is offline Offline
5,792 posts
since Oct 2004

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Python Forum Timeline: Python program, need help please.
Next Thread in Python Forum Timeline: Help with a section of code





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC