3

Suppose I have an input which contains space seperated integers which are unique, i.e one does not occur twice. In such a case, will using the following,

setA = set(input().split())

be faster than using the below one? If so(I actually experienced it in this way), why?

listA = list(input().split())

Please do not focus on the fact that there is not a conversion to int, while reading the input.

In a problem I am working on, using list() gives timeout, however by using set(), I am able to run it such that it is in the time limitations. I wonder why this is the case?

edit : In case it might be related, the code which is related,

arr = input().split()

for ele in arr:

    if ele in setA:
        happiness += 1
    elif ele in setB:
        happiness += -1
    else:
        pass

Where arr is a space seperated line of integers, no uniquneness this time.

muyustan
  • 1,555
  • 1
  • 11
  • 23
  • 2
    In `set` membership check takes `O(1)` time, and in `list` it takes `O(n)` times. – Ch3steR Mar 08 '20 at 09:20
  • @Ch3steR I got it, so it is not related to the part they are created, it is about how many times they were subjected to if .... in setA/listA. Thanks! – muyustan Mar 08 '20 at 09:22
  • @Ch3steR Although, it would be nice to have some explanation on why checking a set for membership of an element is faster than checking a list for it. – muyustan Mar 08 '20 at 09:23
  • 3
    `set` is implemented using `hashtables`. For checking membership all that needs to be done is basically to look if the object is at the position determined by its hash, so the speed of this operation does not depend on the size of the set. For lists, in contrast, the whole list needs to be searched, which will become slower as the list grows. – Ch3steR Mar 08 '20 at 09:25
  • 1
    In simple terms Set is more optimized to pick specific elements because of the hash table – Paritosh Yadav Mar 08 '20 at 09:27
  • 1
    Glad to help ;) – Ch3steR Mar 08 '20 at 09:29
  • Does this answer your question? [What makes sets faster than lists?](https://stackoverflow.com/questions/8929284/what-makes-sets-faster-than-lists) – TheMaskedTitan Aug 24 '22 at 18:23

1 Answers1

4

Python’s set class represents the mathematical notion of a set, namely a collection of elements, without duplicates, and without an inherent order to those elements. The major advantage of using a set, as opposed to a list, is that it has a highly an optimized method for checking whether a specific element is contained in the set. This is based on a data structure known as a hash table

However, there are two important restrictions due to the algorithmic underpinnings. The first is that the set does not maintain the elements in any particular order. The second is that only instances of immutable types can be added to a Python set. Therefore, objects such as integers, floating-point numbers, and character strings are eligible to be elements of a set. It is possible to maintain a set of tuples, but not a set of lists or a set of sets, as lists and sets are mutable.

Paritosh Yadav
  • 337
  • 1
  • 3
  • 11