[Python-ideas] proposed sequence method: index_subseq()

[Jess Austin]

On Tue, Aug 27, 2013 at 10:27 AM, Tal Einat <taleinat at gmail.com> wrote:

> There are many algorithms for sub-sequence search, most of which can
> be significantly more efficient than the one you used under common
> circumstances. For example, see the Knuth-Morris-Pratt algorithm [1],
> and an example Python implementation on the ActiveState cookbook [2].
>

Good point; O(n+m) is better than O(n*m). Minor observation: KMP would
disallow the possibility I raised of subseq being just an iterator, rather
than a sequence. I think that's OK, since my use cases haven't had
iterators here. It actually seems more likely that the "containing" object
will be an iterator, which the recipe you linked would allow. Hmmm....

I really just provided the example code to specify exactly what I meant
rather than as a proposed algorithm, but I'm glad you took it seriously.
This really does want to be more of a function that takes iterators than a
method of sequences.

A good implementation that would work relatively well in most common
> cases could be useful, much as Python's sorting implementation is. I
> think, however, that it would be better to start this as a 3rd party
> module rather than push for immediate inclusion in the stdlib.
>

No push here! I'm just asking questions. Thanks for your insights.

cheers,
Jess
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20130827/9e43bf15/attachment.html>