From: sellberg@...
Date: 2014-04-02T21:19:46+00:00
Subject: [ruby-core:61811] [ruby-trunk - Bug #9695] [Open] Substring search exhibit quadratic behaviour.

Issue #9695 has been reported by Linus Sellberg.

----------------------------------------
Bug #9695: Substring search exhibit quadratic behaviour.
https://bugs.ruby-lang.org/issues/9695

* Author: Linus Sellberg
* Status: Open
* Priority: Normal
* Assignee: 
* Category: 
* Target version: 
* ruby -v: ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-linux]
* Backport: 2.0.0: UNKNOWN, 2.1: UNKNOWN
----------------------------------------
http://nelhagedebugsshit.tumblr.com/post/81301884746/surveying-various-languages-string-search-algorithms

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. 




-- 
https://bugs.ruby-lang.org/