ruby-core

Issue #9695 has been updated by Nobuyoshi Nakada.

Description updated

It's `O(m*n)`, not `O(m**2)`, where `m` and `n` are the lengths of the receiver and the searching strings respectively.

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

* Author: Linus Sellberg
* Status: Open
* Priority: Normal
* Assignee: 
* Category: core
* 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

~~~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. 




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