Can you speed up "for " loop in python with sorting ?

Question

If I have a long unsorted list of 300k elements, will sorting this list first and then do a "for" loop on list speed up code? I need to do a "for loop" regardless, cant use list comprehension.

sortedL=[list].sort() 

for i in sortedL:
  (if i is somenumber)
     "do some work"

How could I signal to python that sortedL is sorted and not read whole list. Is there any benefit to sorting a list? If there is then how can I implement?

Answer 1

It would appear that you're considering sorting the list so that you could then quickly look for somenumber.

Whether the sorting will be worth it depends on whether you are going to search once, or repeatedly:

• If you're only searching once, sorting the list will not speed things up. Just iterate over the list looking for the element, and you're done.

• If, on the other hand, you need to search for values repeatedly, by all means pre-sort the list. This will enable you to use bisect to quickly look up values.

The third option is to store elements in a dict. This might offer the fastest lookups, but will probably be less memory-efficient than using a list.

Answer 2

If you want to search within a sorted list, you need an algorithm that takes advantage of the sorting.

One possibility is the built-in bisect module. This is a bit of a pain to use, but there's a recipe in the documentation for building simple sorted-list functions on top of it.

With that recipe, you can just write this:

i = index(sortedL, somenumber)

Of course if you're just sorting for the purposes of speeding up a single search, this is a bit silly. Sorting will take O(N log N) time, then searching will take O(log N), for a total time of O(N log N); just doing a linear search will take O(N) time. So, unless you're typically doing log N searches on the same list, this isn't worth doing.

If you don't actually need sorting, just fast lookups, you can use a set instead of a list. This gives you O(1) lookup for all but pathological cases.

Also, if you want to keep a list sorted while continuing to add/remove/etc., consider using something like blist.sortedlist instead of a plain list.