Ruby » Ruby master

Bug #9695

Updated by nobu (Nobuyoshi Nakada) about 10 years ago

http://nelhagedebugsshit.tumblr.com/post/81301884746/surveying-various-languages-string-search-algorithms 

 ~~~ruby 
 12.upto(21).map do |i| 
   needle='a'*(2**(i-1)) + 'b' 
   haystack = 'a' * (2**i) 
   a = Time.now; haystack.include?(needle); b=Time.now 
   t = b-a 
   p [t, t/haystack.length**2] 
 end 
 ~~~ 

 gives 

 ~~~ 
 [0.000237363, 1.4147937297821046e-11] 
 [0.000851294, 1.2685269117355347e-11] 
 [0.003081808, 1.1480629444122315e-11] 
 [0.013984239, 1.3023837469518185e-11] 
 [0.035659327, 8.302584057673811e-12] 
 [0.136899401, 7.968593912664801e-12] 
 [0.545703233, 7.941027186461724e-12] 
 [2.217092242, 8.065734589763452e-12] 
 [8.965134534, 8.15374235935451e-12] 
 [36.113581501, 8.211277759301083e-12] 
 =>  
 ~~~ 

  

 Wasn't me that found it but it seems the founder hasn't reported it yet.  

Back