0

Are there any other ways than sort() to find the second smallest integer in this row:

10 12 2 5 15
user2989433
  • 53
  • 1
  • 6
  • `sorted('10 12 2 5 15'.split(),reverse=True)[1]` – Hackaholic Nov 06 '14 at 17:49
  • sorting is definately not the best way to do this anyway, as it sorts the whole list - which is wasteful. – will Nov 06 '14 at 17:51
  • @will Unless you evaluate the performance for your exact use case and find out that surprisingly it is the most efficient way. – moooeeeep Nov 06 '14 at 17:53
  • When sorting is or isn't more efficient is irrelevant, because the question asks for alternatives to sorting. – chepner Nov 06 '14 at 17:54
  • @moooeeeep without sorting, you only need to traverse the list once, so if the list is long, then sorting it and taking the second entry is going to be a bad technique. How long it needs to be for this to happen depends on the relative speeds, `sort()` is written in `c` though, so it takes a while before a python implementation takes over. For a `random.shuffle()`'d `range(length)` list, on my machine at least, it has to be around 200000 elements long before a naive pure python approach beats it. – will Nov 06 '14 at 18:17
  • @chepner, i know, but i thought i might point it out to Hackaholic. – will Nov 06 '14 at 18:20

1 Answers1

1

you can use heapq.nsmalles :

>>> import heapq
>>> l=[10, 12, 2, 5 ,15]
>>> print(heapq.nsmallest(2, l)) [1]
5

The most important feature of a heap is that heap[0] is always the smallest item. More‐ over, subsequent items can be easily found using the heapq.heappop() method, which pops off the first item and replaces it with the next smallest item (an operation that requires O(log N) operations where N is the size of the heap)

The nlargest() and nsmallest() functions are most appropriate if you are trying to find a relatively small number of items. If you are simply trying to find the single smallest or largest item (N=1), it is faster to use min() and max() . Similarly, if N is about the same size as the collection itself, it is usually faster to sort it first and take a slice (i.e., use sorted(items)[:N] or sorted(items)[-N:] ). It should be noted that the actual implementation of nlargest() and nsmallest() is adaptive in how it operates and will carry out some of these opti`mizations on your behalf (e.g., using sorting if N is close to the same size as the input). (reference : python cookbook 3rd edition)

Mazdak
  • 105,000
  • 18
  • 159
  • 188