speeding up idea: Boyer Moore for all subsequence searches.

[kobi2187]

I had an idea:

• using a smart string searching algorithm like boyer-moore, would likely speed up all the applications that use string matching in the std lib.
  I assume it'd be possible for byte arrays to use the same algorithm and not just strings, to get a comparable speedup.
• A related idea is data structures that abstract an algorithm. for example, instead of reversing an array, make a structure that holds this array, and its length, and computes the correct index, as if the array was reversed. 0 would be len-1, 3 would be len -4, -1 would be 0, -2 would be 1.
  something like:
  proc calc(pos:int) = len + (i * -1) -1

There might be other use cases, such as a slice, which is a certain "window" to the underlying sequence.
What do you guys think?

[data-man]

@kobi2187

using a smart string searching algorithm like boyer-moore

strutils.find already uses the "Quick search" algorithm.

[kobi2187]

oh, that's great. didn't know that. Can that be modified to work on other indexable collections?

[data-man]

IMO, the big problem is that the standard library does not use concepts.
This will require a huge work.

[data-man]

Also, see my PR: #6582

[kobi2187]

@data-man what work will it require? besides coming up with names for all the interfaces :-)

[kobi2187]

proc find[T]*(a: SkipTable, s, sub: T[], start: Natural = 0, last: Natural = 0): int
I'm just a beginner, so maybe I got this wrong, but wouldn't something like this work for all indexable sequences? IOW, those which support indexed array access. (because those algorithms require jumping to different indices to skip some work)

[data-man]

wouldn't something like this work for all indexable sequences?

Yes, it can be adapted for any indexable sequences

The best resource for finding strings that I know about: EXACT STRING MATCHING ALGORITHMS
With a full description of algorithms, their analysis and C-source codes.
Also you can port to Nim SMART (string matching algorithms research tool) ;)

[andreaferretti]

I think Cello is relevant here. It is a string library I wrote, mainly aimed at string matching

[Araq]

We always try to use the "best" algorithm but this is not actionable as it is not backed up by any benchmarks.