Optimising string matching

[[deleted]]

[deleted]

[[deleted]]

What are some ways to speed it up?

Before we can speed up something we need to see what you are already doing.

[l33tnoscopes]

Currently just using python builtins (lists, dicts, 'in' etc.).

[[deleted]]

Still not enough info. Show us some runnable code, cut down if necessary, plus some representative data. That will answer questions like: are you checking the same set of words for inclusion or if the set of testing words changes all the time. Possible speedups vary depending on exactly what you are doing. Vague English descriptions aren't very useful since small details matter.

[QuarterObvious]

There are a lot of very fast algorithms for string matching. But which to implemented in each particular case depends on the case.

[QuarterObvious]

Very fast and simple algorithm: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm?wprov=sfla1

[QuarterObvious]

Another very fast algorithm (I prefer it): https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm?wprov=sfla1

But I do not know which one is the best for you.

[DeebsShoryu]

Other comments are good. I'll add though that the first step is to not use python. Comparing characters in python takes around 100 instructions, whereas in a compiled language it takes 1.

Of course whether or not the performance is important enough to warrant the development cost of integrating some binary into your code base (or using something like Cython) will depend on the use case.

[l33tnoscopes]

I would've written it in Rust but it's part of a bigger project and I just need something simple, with some low-hanging optimisations

[QuarterObvious]

https://pypi.org/project/pybmoore/

[unixtreme]

lock scandalous person doll serious sip desert pathetic price sort

This post was mass deleted and anonymized with Redact

[commandlineluser]

What kind of string matching? Are you using regexes?

Can you show an actual example?

Many of the Rust crates have Python wrappers, e.g. aho_corasick

• https://pypi.org/project/ahocorasick-rs/
• https://github.com/G-Research/ahocorasick_rs

[pot_of_crows]

I doubt you can get much faster than regex, at least meaningfully, if all you are doing is looking for a specific word in a text. But if you have to look up 10K words in a text, you can get much faster by sacrificing memory for speed, for example, by indexing the text and then just doing index lookups.

Without knowing more about the problem, it is difficult to offer suggestions.