Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #11679
| From | Nobody <nobody@nowhere.com> |
|---|---|
| Subject | Re: testing if a list contains a sublist |
| Date | 2011-08-17 13:28 +0100 |
| Message-Id | <pan.2011.08.17.12.28.42.227000@nowhere.com> |
| Newsgroups | comp.lang.python |
| References | <mailman.27.1313450819.27778.python-list@python.org> <pan.2011.08.16.11.21.47.168000@nowhere.com> <mailman.65.1313504884.27778.python-list@python.org> |
| Organization | Zen Internet |
On Tue, 16 Aug 2011 09:57:57 -0400, John Posner wrote: > How about using Python's core support for "==" on list objects: > for i in range(alist_sz - slist_sz + 1): > if slist == alist[i:i+slist_sz]: > return True This is bound to be asymptotically O(alist_sz * slist_sz), even if the constant factor is reduced by use of ==. Boyer-Moore and regexps are asymptotically O(alist_sz). However, the setup costs are much higher, so you might need alist_sz to be very large before they win out.
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
testing if a list contains a sublist Johannes <dajo.mail@web.de> - 2011-08-16 01:26 +0200
Re: testing if a list contains a sublist Roy Smith <roy@panix.com> - 2011-08-15 20:53 -0400
Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 08:51 +0200
Re: testing if a list contains a sublist alex23 <wuwei23@gmail.com> - 2011-08-16 00:19 -0700
Re: testing if a list contains a sublist alex23 <wuwei23@gmail.com> - 2011-08-16 00:14 -0700
Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 10:00 +0200
Re: testing if a list contains a sublist Johannes <dajo.mail@web.de> - 2011-08-16 17:26 +0200
Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-16 00:24 -0700
Re: testing if a list contains a sublist Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-08-16 14:23 +0200
Re: testing if a list contains a sublist Roy Smith <roy@panix.com> - 2011-08-16 08:53 -0400
Re: testing if a list contains a sublist nn <pruebauno@latinmail.com> - 2011-08-16 07:53 -0700
Re: testing if a list contains a sublist Laszlo Nagy <gandalf@shopzeus.com> - 2011-08-16 17:17 +0200
Re: testing if a list contains a sublist Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-08-16 17:39 +0200
Re: testing if a list contains a sublist Neil Cerutti <neilc@norwich.edu> - 2011-08-16 17:45 +0000
Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 12:12 +1000
Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 18:19 +1000
Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:14 -0700
Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:13 -0700
Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-15 23:14 -0700
Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-16 18:37 +1000
Re: testing if a list contains a sublist ChasBrown <cbrown@cbrownsystems.com> - 2011-08-16 21:13 -0700
Re: testing if a list contains a sublist Nobody <nobody@nowhere.com> - 2011-08-16 12:21 +0100
Re: testing if a list contains a sublist John Posner <jjposner@codicesoftware.com> - 2011-08-16 09:57 -0400
Re: testing if a list contains a sublist John Posner <jjposner@optimum.net> - 2011-08-16 09:57 -0400
Re: testing if a list contains a sublist Nobody <nobody@nowhere.com> - 2011-08-17 13:28 +0100
Re: testing if a list contains a sublist Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-08-20 12:10 +1000
csiph-web