Run time difference for "in" searching through "list" and "set" using Python

user_13814528 0
Viewed 99

My understanding of list and set in Python are mainly that list allows duplicates, list allows ordered information, and list has position information. I found while I was trying to search if an element is with in a list, the runtime is much faster if I convert the list to a set first. For example, I wrote a code trying find the longest consecutive sequence in a list. Use a list from 0 to 10000 as an example, the longest consecutive is 10001. While using a list:

    start_time = datetime.now()
    nums = list(range(10000))
    longest = 0
    for number in nums:
        if number - 1 not in nums:
            length = 0
            ##Search if number + 1 also in the list##
            while number + length in nums: 
                length += 1
            longest = max(length, longest)
    end_time = datetime.now()
    timecost = 'Duration: {}'.format(end_time - start_time)
    print(timecost)

The run time for above code is "Duration: 0:00:01.481939" With adding only one line to convert the list to set in third row below:

    start_time = datetime.now()
    nums = list(range(10000))
    nums = set(nums)
    longest = 0
    for number in nums:
        if number - 1 not in nums:
            length = 0
            ##Search if number + 1 also in the set(was a list)##
            while number + length in nums:
                length += 1
            longest = max(length, longest)
    end_time = datetime.now()
    timecost = 'Duration: {}'.format(end_time - start_time)
    print(timecost)

The run time for above code by using a set is now "Duration: 0:00:00.005138", Many time shorter than search through a list. Could anyone help me to understand the reason for that? Thank you!

set list search python
1 Answers

This is a great question.

The issue with arrays is that there is no smarter way to search in some array a besides just comparing every element one by one.

  • Sometimes you'll get lucky and get a match on the first element of a.
  • Sometimes you'll get unlucky and not find a match until the last element of a, or perhaps none at all.
  • On average, you'll have to search half the elements of they array each time.

This is said to have a "time complexity" of O(len(a)), or colloquially, O(n). This means the time taken by the algorithm (searching for a value in array) is linearly propertional to the size of the input (the number of elements in the array to be searched). This is why it's called "linear search". Oh, your array got 2x bigger? Well your searches just got 2x slower. 1000x bigger? 1000x slower.

Arrays are great, but they're for searching if the element count gets too high.

Sets are clever. In Python, they're implemented as if they were a Dictionary with keys and no values. Like dictionaries, they're backed by data structure called a hash table.

A hash table uses the hash of a value as a quick way to get a "summary" of an object. This "summary" is then used to narrow down its search, so it only needs to linearly search a very small subset of all the elements. Searching in a hash table a time complexity of O(1). Notice that there's no "n" or len(the_set) in there. That's because the time taken to search in a hash table does not grow as the size of the hash table grows. So it's said to have constant time complexity.

By analogy, you only search the dairy isle when you're looking for milk. You know the hash value of milk (say, it's isle) is "dairy" and not "deli", so you don't have to waste any time searching for milk

A natural follow-up question is "then why don't we always use sets?". Well, there's a trade-off.

  • As you mentioned, sets can't contain duplicates, so if you want to store two of something, it's a non-starter.
  • Prior to Python 3.7, they were also unordered, so if you cared about the order of elements, they won't do, either. * Sets generally have a larger cpu/memory overhead, which adds up when using many sets containing small numbers of elements.
  • Also, it's possible that because of fancy CPU features (like CPU caches and branch prediction), linear searching through small arrays can actually be faster than the hash-based look-up in sets.

I'd recommend you do some further reading into data structures and algorithms. This stuff is quite language-independent. Now that you know that set and dict use a Hash Table behind the scenes, you can look up resource that cover hash tables in any language, and that should help. There's also some Python-centric resoruces too, like https://www.interviewcake.com/concept/python/hash-map

user_31412340
Related