-1

Suppose i have a list of hundred natural numbers, set of hundred natural numbers and dictionary of hundred natural numbers (assuming both key and value are natural numbers). I want to access an element in these data types. Which will be the more efficient and faster way to access it? I know i can use some performance tools like timeit or cprofile etc to check the performance but how will i know which data type to choose and when?

Ameet
  • 37
  • 9
  • learn using `timeit` and do your performance testing. Shorter time for execution means it is faster (if you do not know, how you find, which one is better) – Jan Vlcinsky May 12 '14 at 06:30
  • The use cases for a list vs. dictionary should be pretty obvious. Use a list. If you have to quickly look up a specific item based upon some key, then use a dictionary. And *test all assumptions*. – Jonathon Reinhart May 12 '14 at 06:30
  • 1
    @thefourtheye ??? indexing a `list` is O(1) like `dict`, but *always* faster, since no hash need to be computed. Maybe you meant a linked-list which is implemented as `collections.deque`... – Bakuriu May 12 '14 at 06:31
  • Q: What is the performance characteristics of lookups for lists vs. dicts? If you can answer this you've answered your own question. – James Mills May 12 '14 at 06:33
  • @Bakuriu Ah, Sorry I misread the question and got myself totally confused. – thefourtheye May 12 '14 at 06:35
  • Just to be clear, comments in this question are confusing at best. I will provide a short answer. Essentially: Lookups in a ``list`` are O(n) and ``dict`` O(1). – James Mills May 12 '14 at 06:47
  • What exactly are you trying to so? Without an example to show the operations you want to perform, it's hard to be specific; the question as it stands is much too broad. – jonrsharpe May 12 '14 at 07:11

1 Answers1

0

At a high overview:

  • list lookups are O(n)

Where n is the length of the list.

  • dict lookups are O(1)

This is basic Big O notation or Complexity.

James Mills
  • 18,669
  • 3
  • 49
  • 62
  • 1
    Will there be any difference in case set or will its lookup be same as that of list? – Ameet May 12 '14 at 06:58
  • This is not a fair comparison as ``set`` (*sets*) do not have lookup operations like lists or dicts. See: http://stackoverflow.com/questions/7351459/time-complexity-of-python-set-operations and https://wiki.python.org/moin/TimeComplexity – James Mills May 12 '14 at 07:02
  • @JamesMills what precisely do you mean by "lookup operation", here? Membership checks are `O(1)` in `dict` and `set` but `O(n)` in `list`, accessing by key/index is `O(1)` in both `dict` and `list` (see https://wiki.python.org/moin/TimeComplexity). – jonrsharpe May 12 '14 at 07:07
  • There is no way to index an element in a set like you can with a dict lookup via key or element lookup in a list by index. IHMO you should not compare sets with dicts/lists in this way as they have their own special set of operations aka set operations. – James Mills May 12 '14 at 07:12