Thanks Jason for the pointer to Rabin-Karp, it seems that this algorithm is indeed what `bytes.Index <https://cs.opensource.google/go/go/+/refs/tags/go1.25.5:src/internal/bytealg/bytealg.go;l=69>` uses.
That said I wonder is it appropriate to propose that this algorithm be implemented with generics in the "slices" package? The current `slices.Index(x S, sep E)` seems a bit too primitive, and having a generic `IndexAll(x, sep S)` would be very helpful. On Wednesday, December 10, 2025 at 11:01:48 AM UTC+8 Jason E. Aten wrote: > On Tuesday, December 9, 2025 at 7:54:09 PM UTC-3 awaw... wrote: > > What is the best way of doing `bytes.Index` but on say integer slices > `[]int`? > > > This depends heavily on the length of the needle (query) versus the length > of the haystack (database); and if you'll be doing repeated searches that > might > make it worth doing pre-processing of either one. You can read the > wikipedia page > for the Rabin–Karp string matching algorithm to get a sense of the issues > involved. > Things like the expected versus worst-cases big-O times might be > important, depending on > your use case, and there are various classical algorithms available that > improve > on brute force in various circumstances. > > https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm > > If you want deeper discussion, then CLR[1] and/or Dan Gusfield's book > "Algorithms on Strings, Trees, and > Sequences" might be good reading. > > [1] https://en.wikipedia.org/wiki/Introduction_to_Algorithms > > That said, brute force search is often just fine as it tends to have a > high L1-cache hit rate. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/golang-nuts/3790c40c-ec16-4d49-849e-555328703ce4n%40googlegroups.com.
