fork download
copy 
  1. # your code goes here
  2. import time
  3.  
  4. from functools import wraps
  5. from threading import Thread
  6.  
  7. import random
  8. import string
  9.  
  10. def time_it(f):
  11.     """
  12.     run the function 100,000 times and print time
  13.     """
  14.     @wraps(f)
  15.     def wrapper(*args, **kwargs):
  16.         start_time = time.time()
  17.         for i in range(10000): 
  18.             r = f(*args, **kwargs)
  19.         print(f.__name__, time.time() - start_time)
  20.         return r
  21.     return wrapper
  22.  
  23.  
  24. @time_it
  25. def find_max_alpha_sequence_optimal_way(source):
  26.     answer = [source[0],]
  27.     for l in source[1:]:
  28.         if l >= answer[-1][-1]:
  29.             answer[-1] += l
  30.         else:
  31.             answer.append(l)
  32.     return max(answer, key=lambda x: len(x)) 
  33.  
  34. @time_it
  35. def find_max_alpha_sequence(source):
  36.     answer = [source[0],]
  37.     for l in source[1:]:
  38.         if l >= answer[-1][-1]:
  39.             answer[-1] += l
  40.         else:
  41.             answer.append(l)
  42.     return sorted(answer, key=lambda x: len(x))[-1]
  43.  
  44. @time_it
  45. def max_alpha_sub(s):
  46.     def split_by_alpha_order(s):
  47.         start = 0
  48.         for i,(a,b) in enumerate(zip(s,s[1:])):
  49.             if a>b:
  50.                 yield s[start:i+1]
  51.                 start = i+1
  52.         yield s[start:]
  53.     return max(split_by_alpha_order(s),key=len)
  54.  
  55. @time_it
  56. def max_alpha_sub_simple(s):
  57.     if not s:
  58.         return s
  59.  
  60.     start = 0
  61.     max = (0,1)
  62.     for index in range(1,len(s)+1):
  63.         if index == len(s) or s[index-1]>s[index]:
  64.             if index - start>max[1]-max[0]:
  65.                 max=(start,index)
  66.             start = index
  67.  
  68. functions = (
  69.     find_max_alpha_sequence,
  70.     find_max_alpha_sequence_optimal_way,
  71.     max_alpha_sub,
  72.     max_alpha_sub_simple
  73.     )
  74.  
  75. str = ''.join(random.choice(string.ascii_letters) for _ in range(100))
  76.  
  77. for f in functions:
  78.     t = Thread(target=f, args=(str,))
  79.     t.start()
  80.  
  81.  
Success #stdin #stdout 0.98s 13124KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
max_alpha_sub_simple 0.7382426261901855
max_alpha_sub 0.7849776744842529
find_max_alpha_sequence_optimal_way 0.8798341751098633
find_max_alpha_sequence 0.9213104248046875
https://ideone.com/rFHQsC
language:
Python 3 (python  3.9.5)
created:
6 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!