fork(1) download 
  1. from itertools import groupby
  2. from operator import itemgetter
  3. import random
  4. import time
  5.  
  6. lst = [ 1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0]
  7.  
  8. def makeList(size):
  9.     random.seed()
  10.     return [random.randint(0,1) for r in xrange(size)]
  11.  
  12.  
  13. def runs1(lst, showOutput):
  14.     startLength = {}
  15.     for k,v in groupby(enumerate(lst),key=itemgetter(1)):
  16.         if k:
  17.             v = list(v)
  18.             startLength[v[0][0]] = v[-1][0] + 1 - v[0][0]
  19.     if showOutput == True:
  20.         for s,l in startLength.iteritems():
  21.             print s,l
  22.  
  23. def runs2(lst, showOutput):
  24.     previous = 0
  25.     cnt = 0
  26.     startLength = {} 
  27.     for r in lst: 
  28.         if previous == 0 and r == 1:
  29.             start = cnt
  30.         if previous == 1 and r == 0: 
  31.             startLength[start] = cnt - start
  32.         previous = r
  33.         cnt += 1
  34.     if r == 1:
  35.         startLength[start] = cnt - start
  36.     if showOutput == True:
  37.         for s,l in startLength.iteritems():
  38.             print s,l
  39.  
  40. testList = makeList(10)
  41. print "slow version"
  42. runs1(testList, True)
  43. print "fast version"
  44. runs2(testList, True)
  45.  
  46. benchmarkList = makeList(10000)
  47.  
  48. start = time.time()
  49. runs1(benchmarkList, False)
  50. print "slow ", time.time() - start
  51. start = time.time()
  52. runs2(benchmarkList, False)
  53. print "fast ", time.time() - start
  54.  
  55. start = time.time()
  56. runs1(benchmarkList, False)
  57. print "slow ", time.time() - start
  58. start = time.time()
  59. runs2(benchmarkList, False)
  60. print "fast ", time.time() - start
  61.  
  62. start = time.time()
  63. runs1(benchmarkList, False)
  64. print "slow ", time.time() - start
  65. start = time.time()
  66. runs2(benchmarkList, False)
  67. print "fast ", time.time() - start
  68.  
  69.  
  70.  
Success #stdin #stdout 0.14s 10992KB
comments ()
stdin 
Standard input is empty
stdout 
slow version
9 1
3 2
7 1
fast version
9 1
3 2
7 1
slow  0.00678014755249
fast  0.00244688987732
slow  0.00646996498108
fast  0.00240302085876
slow  0.0064160823822
fast  0.0024139881134
https://ideone.com/ydaX9y
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!