[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug#39258] KMP string search algorithm?
From: |
Leo Famulari |
Subject: |
[bug#39258] KMP string search algorithm? |
Date: |
Mon, 1 Jun 2020 18:24:14 -0400 |
On Mon, Jun 01, 2020 at 12:11:52PM +0200, zimoun wrote:
> Dear,
>
> > > Often our search strings are only literal strings. So, we can save some
> > > time
> > > by using string-contains instead of invoking the regexp engine. Patch 2
> > > does
> > > this. In addition, guile's string-contains uses a naive O(n^2) string
> > > search
> > > algorithm. We should perhaps use the O(n) Knuth-Morris-Pratt
> > > algorithm[1]. In
> > > fact, a comment on line 2006 of libguile/srfi-13.c in the guile source
> > > code
> > > mentions this. If implemented, the KMP algorithm could speed up guix
> > > search
> > > further.
> > >
> > > [1]:
> > > https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
>
> It could improve.
> Well, I will try to do some back-to-envelop computations because I am
> not convinced that the mean value of 'n' (length of description,
> isn't) is large enough to really see an improvement for the end-user;
> the visible bottleneck is I/O.
>
> All the best,
> simon
>
> ps;
> To be honest, I thought this kind of algorithm was the default. :-)
I also recommend taking a look at the Boyer Moore string search
implementation in (guix build grafts).
It would be great to generalize it and make it accessible to other parts
of Guix.