1  #!/usr/bin/env python 
 2   
 3  #  Title: Fast select  
 4  #  Location: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/466330 
 5  #  Last Updated: 2006/01/21  
 6  #  Version no: 1.0  
 7  #  Category: Algorithms  
 8  #   
 9  #   
10  #  Description: 
11  # 
12  #  To quickly select the n-th rank ordered element of a given sequence.  
13  #  (It modifies the ordering of the given sequence). 
14  # 
15  # 
16  #  Discussion: 
17  # 
18  #  The complexity of this is O(n), not O(n ln n) like the sort, but it's Python, so it's  
19  #  slower than the fast CPython TimSort until the given sequence is very long. With Psyco  
20  #  this function becomes useful for much smaller sequences. With ShedSkin  
21  #  (http://shedskin.sourceforge.net/) this can probably become really fast. 
22   
23   
24   
25 -def select(pos, seq): 
26      """select(pos, seq): find the nth rank ordered element 
27      (the least value has rank 0). 
28      Note1: it modifies the seq. 
29      Note2: this function is useful with Psyco, otherwise .sort is 
30      faster until len(seq)>~3e6""" 
31      # Version 1.1, Nov 13 2004, from "Numerical Recipes". 
32      lo = 0 
33      up = len(seq)-1 
34      if pos<lo or pos>up: 
35          raise 'Selection out of bounds.' 
36      else: 
37          while up>=pos and pos>=lo: 
38              i = lo 
39              j = up 
40              tempr = seq[pos] 
41              seq[pos] = seq[lo] 
42              seq[lo] = tempr 
43              # Split in two 
44              while i<j: 
45                  while seq[j] > tempr: 
46                      j -= 1 
47                  seq[i] = seq[j] 
48                  while i<j and seq[i]<=tempr: 
49                      i += 1 
50                  seq[j] = seq[i] 
51              seq[i] = tempr 
52              # Select sub 
53              if pos<i: 
54                  up = i-1 
55              else: 
56                  lo = i+1 
57          return seq[pos] 
58   
59   
60  try: # Import Psyco if available. 
61  # Psyco is almost necessary, otherwise .sort is faster until len(seq)>~3e6 
62      import psyco 
63  except ImportError: 
64      pass 
65  else: 
66      psyco.bind(select) 
67   
68   
69  if __name__ == '__main__': # Test ---------------------- 
70      from time import clock 
71      import random 
72      nrepetiotions = 6 
73      print "nrepetiotions=", nrepetiotions 
74      print "len(list), average min time select of 1"\ 
75            "element of list, min time select(list):" 
76      for j in xrange(6, 21): 
77          n = 2**j 
78          v = [] 
79          for i in range(nrepetiotions): 
80              seq = [random.random() for x in xrange(n+1)] 
81              nd2 = int(n//2) 
82              t1 = clock() 
83              select(nd2, seq) 
84              t2 = clock() 
85              v.append(t2-t1) 
86          print "2^"+str(j)+"=", n, round(1000000*min(v)/n, 3), round(min(v), 3) 
87