From: Martin Pirker <crf@...>
Date: 2005-01-13T07:31:16+09:00
Subject: Re: brute force string search

georgesawyer <georgesawyer2@hotmail.ok.nospam.com> wrote:
> Martin Pirker <crf@sbox.tu-graz.ac.at> Jan 10, 2005 at 12:49 AM wrote:
>>given: String of several Mb. Problem: find the lines in String containing
> "xyz".
> 
> This seems to be a real-world problem, and it seems the 'String of several
> Mb' is relatively fixed. If so, here are some ideas.
[fascinating read]

This is why even when one finds a "good enough" solution it's still a good
idea to bounce the solution to other people - one never really knows
what useful comments come back :-)


Slicing the data up gives an "overlap" problem.

After some thinking however it's possible to do some presorting of the
data, so a full search must be done at the beginning, but next findings
should be located in area around of last search hit.
e.g. Cutting the search from 100% of a String to specific 1% gives 100
fold improvement -> good :-)

How to do that?
String.index accepts a offset to start from
String.rindex accepts a offset to end with.

So if e.g. I want to search 1Mb in the middle of a 100Mb String i need
a String.yetanotherindex("xyz",startoffset,endoffset), otherwise
performance sucks again.

Looking at string.c of Ruby, .index and .rindex appear to be
quite simple brute-force (that's why they are so fast)

I RFC adding an .index function to String which accepts 3 parameters:
(searchitem, startoffset, endoffset)
IMHO this would make an useful addition to stdlib shipped with Ruby.


Martin