Author Dennis Sweeney
Recipients Dennis Sweeney, Zeturic, ammar2, corona10, gregory.p.smith, josh.r, pmpp, serhiy.storchaka, tim.peters, vstinner
Date 2020-10-16.19:39:52
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1602877193.0.0.682607769203.issue41972@roundup.psfhosted.org>
In-reply-to
Content
I'm doing a couple more timing tests to try to understand exactly when the cutoff should be applied (based on some combination of needle and haystack lengths).

Can the rolling hash algorithm be made to go sublinear like O(n/m)? It looked like it was pretty essential that it hash/unhash each and every haystack character. You could probably do a bloom-like check where you jump ahead by the needle length sometimes, but you'd then have to re-hash the m characters in the new window anyway.
History
Date User Action Args
2020-10-16 19:39:53Dennis Sweeneysetrecipients: + Dennis Sweeney, tim.peters, gregory.p.smith, vstinner, pmpp, serhiy.storchaka, josh.r, ammar2, corona10, Zeturic
2020-10-16 19:39:53Dennis Sweeneysetmessageid: <1602877193.0.0.682607769203.issue41972@roundup.psfhosted.org>
2020-10-16 19:39:52Dennis Sweeneylinkissue41972 messages
2020-10-16 19:39:52Dennis Sweeneycreate