Wednesday, April 2, 2014

Surveying Various Languages’ String-search Algorithms

Nelson Elhage:

It turns out that virtually every other language [than Java] I know of uses an optimized string-search by default, which had the upshot that simply rewriting our Scala code in Ruby(!) would actually make the code dramatically faster and pass our benchmarks! “Oops”.

But inspired by this, I decided to go do a brief survey of common language/VM string-search algorithms[…]

It looks like CFStringFindWithOptionsAndLocale() uses a Java-style slow matching algorithm rather than something like Boyer-Moore.

Comments RSS · Twitter

Leave a Comment