Lookups in a Sorted List Agains Unsorted Python
Faster Lookups In Python
Comparison of dictionaries and lists
Imagine that you are organizing a data science conference. Y'all are making a listing of attendees. Later you desire to look up a name in this attendee list. How much time does information technology take to find a name if you store the data every bit a list, and as a lexicon? If 100 people are attending your conference, yous don't have to think about lookup speed. You can proceed your information in lists or dictionaries. You tin can even build an Excel tabular array and utilize INDEX and Friction match keys to discover the names you want.
What if you are storing billions of names? Practice you recall it is a good thought to store too many elements in a list? Can dictionaries exercise a ameliorate job in finding a sure particular in a collection of too many elements?
In this blog, I am going to answer time-related questions well-nigh lists and dictionaries.
Let me requite brief definitions of lists and dictionaries.
Lists
Lists are one of the virtually commonly used data types in Python. A list is a sequence of items in an club.
list1 = [iv, 0.22, "Hello", [1, 2, three], -ii.5, 0.22] Lists are mutable, they can be changed after they are created.
Accessing elements of a list:
We can access the elements of a list by their indexes.
print ( list1[0] ) 4
Dictionaries
Dictionaries are unordered collections of fundamental-value pairs, or items.
dict1 = {key1: value1, key2: value2, key3: value3} Dictionaries are also mutable, we tin add, remove, and/or change items every bit needed.
Accessing elements of a lexicon:
We tin access the elements of a dictionary by their keys.
print( dict1[key1] ) value1
Test Run
Time to run tests and compare the lookup speeds of both dictionaries and lists!
Below are the hardware and software configurations of my device. The examination results may vary depending on your reckoner's configuration.
Lists Test Run
Define a function to find a number in a list.
def find_number_in_list(lst, number):
if number in lst:
return Truthful
else:
return False Create a long list and a curt listing to compare the lookup speed.
short_list = list(range(100)) long_list = list(range(10000000))
Call the office and measure time with timeit.
%timeit find_number_in_list(short_list, 99)
1.4 µicrosecond = 0.0000014 second %timeit find_number_in_list(long_list, 9999999)
123 millisecond = 0.123 2nd
As nosotros can meet in the examination run, the larger the listing, the longer it takes.
Listing length comparing: 10000000 / 100 = 100000
Lookup time comparison: 0.123 / 0.0000014 = 87857 Dictionaries test run
Ascertain a function to discover a number in a dictionary.
def find_number_in_dict(dct, number):
if number in dct.keys():
return Truthful
else:
return Imitation Create a long dictionary and a brusk dictionary to compare the lookup speed.
short_dict = {10:x*5 for x in range(i,100)} long_dict = {ten:x*5 for x in range(1,10000000)}
Telephone call the office and measure time using timeit.
%timeit find_number_in_dict(short_dict, 99)
210 nanosecond = 0.00000021 second %timeit find_number_in_dict(short_dict, 9999999)
220 nanosecond = 0.00000022 second
Equally nosotros can meet in the test run, the length of the dictionary doesn't affect the lookup fourth dimension.
Dict length comparison: 10000000 / 100 = 100000
Lookup time comparing: 0.00000021 / 0.00000022 = 0.9545 Analysis Of The Test Run Event
In this unproblematic example, with my laptop'southward configurations,
For 100 items
0.0000014 seconds /0.00000021 seconds= vi.66
A lexicon is vi.6 times faster than a list when we lookup in 100 items.
For x,000,000 items
0.123 seconds /0.00000021seconds = 585714.28
When it comes to 10,000,000 items a dictionary lookup tin be 585714 times faster than a list lookup.
vi.6 or 585714 are but the results of a simple exam run with my computer. These may change in other cases.
Why is looking up entries in a lexicon so much faster?
- You lot have to go through the entire list to get what you want. Still, a dictionary volition return the value you lot enquire for without going through all keys.
- The ii times above for 100 and 10000000 are nigh the same for a dictionary, which is considering a dictionary tin almost instantly jump to the primal it is asked for thanks to the lookups.
- Lookups are faster in dictionaries considering Python implements them using hash tables.
- If we explain the deviation by Large O concepts, dictionaries have abiding time complexity, O(1) while lists have linear time complexity, O(n).
Space-time tradeoff
The fastest way to repeatedly lookup information with millions of entries in Python is using dictionaries. Because dictionaries are the built-in mapping type in Python thereby they are highly optimized. However, we have a typical space-time tradeoff in dictionaries and lists. It means nosotros can decrease the time necessary for our algorithm just we demand to use more than infinite in retentiveness.
Although dictionaries are optimized a lot more in Python 3.half dozen, they still use more memory than lists, since y'all need to utilise infinite for the keys and the lookup equally well, while lists apply space just for the values.
Useful Links
- Time complexity comparisons of other operations similar append, delete, contrary in lists and dictionaries from Geeks for geeks.
- An splendid caption about time complication and big O notation by CS Dojo.
3. A half dozen-minute neat explanation to hash tables and lookups by Gayle Laakmann, the author of the volume Bang-up The Coding Interview.
Thanks for reading.
If yous desire to get into contact, you can email me at seymatas@gmail.com, or you can discover me at https://www.linkedin.com/in/seyma-tas/
Source: https://towardsdatascience.com/faster-lookups-in-python-1d7503e9cd38