Re: [Python-Dev] Proposal for a new itertools function: iwindow
Raymond Hettinger wrote: No thanks. The resolution of this one was that windowing iterables is not a good idea. It is the natural province of sequences, not iterables. With sequences, it is a matter of using an index and offset. With iterables, there is a great deal of data shifting. Also note that some of the uses are subsumed by collections.deque(). Interesting - the old 'hammer-nail' tunnel vision strikes again, I guess. So moving the question to a different part of the docs, would it make sense to include a deque recipe showing how to use a deque in a generator to permit windowing of an arbitrary iterator? Something like: def window(iterable, window_len=2, window_step=1): itr = iter(iterable) step_range = xrange(window_step) current_window = collections.deque(islice(itr, window_len)) while window_len == len(current_window): yield current_window for idx in step_range: current_window.popleft() current_window.extend(islice(itr, window_step)) Even if an application doesn't use the generator approach directly, it still illustrates how to use a deque for windowing instead of as a FIFO queue or a stack. The thought process was documented in a series of newsgroup postings: http://groups.google.com/group/comp.lang.python/msg/026da8f9eec4becf Thanks for that reference - I was searching the wrong list, so I didn't find it. Cheers, Nick. -- Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia --- http://www.boredomandlaziness.org ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Proposal for a new itertools function: iwindow
On Thu, May 25, 2006, Torsten Marek wrote: Some open question remain: - should iwindow return lists or tuples? - what happens if the length of the iterable is smaller than the window size, and no padding is specified? Is this an error? Should the generator return no value at all or one window that is too small? You should probably try this idea out on comp.lang.python; if there is approval, you'll probably need to write a PEP because of these issues. Note that my guess is that the complexity of the issues relative to the benefit means that BDFL will probably veto it. Side note: if you do want to discuss this further on python-dev, please subscribe -- Aahz ([EMAIL PROTECTED]) * http://www.pythoncraft.com/ I saw `cout' being shifted Hello world times to the left and stopped right there. --Steve Gonedes ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Proposal for a new itertools function: iwindow
Aahz [EMAIL PROTECTED] wrote: Some open question remain: - should iwindow return lists or tuples? - what happens if the length of the iterable is smaller than the window size, and no padding is specified? Is this an error? Should the generator return no value at all or one window that is too small? You should probably try this idea out on comp.lang.python; if there is approval, you'll probably need to write a PEP because of these issues. Note that my guess is that the complexity of the issues relative to the benefit means that BDFL will probably veto it. A PEP for adding a simple generator to a library of generators?? The function does look useful to me. It's useful even if it returns a tuple instead of a list, or if it doesn't support padding. It's still better than nothing, and can still be succesfully used even if it requires some smallish wrapper to achieve the exact functionality. I know I have been implementing something similar very often. Since when do we need a full PEP process, nitpicking the small details to death, just to add a simple function? Giovanni Bajo ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Proposal for a new itertools function: iwindow
Aahz [EMAIL PROTECTED] wrote: Some open question remain: - should iwindow return lists or tuples? - what happens if the length of the iterable is smaller than the window size, and no padding is specified? Is this an error? Should the generator return no value at all or one window that is too small? An itertools windowing function was previously discussed and rejected. Raymond ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Proposal for a new itertools function: iwindow
Raymond Hettinger wrote: Aahz [EMAIL PROTECTED] wrote: Some open question remain: - should iwindow return lists or tuples? - what happens if the length of the iterable is smaller than the window size, and no padding is specified? Is this an error? Should the generator return no value at all or one window that is too small? An itertools windowing function was previously discussed and rejected. A python-dev Google search for itertools window found me your original suggestion to include Jack Diedrich's itertools.window in Python 2.3 (which was only deferred because 2.3 was already past beta 1 at that point). I couldn't find any discussion of the idea after that (aside from your pointing out that you'd never found a real-life use case for the pairwise() recipe in the docs, which is a basic form of windowing). One option would be to add a windowing function to the recipes in the itertools docs. Something like: def window(iterable, window_len=2, window_step=1): iterators = tee(iterable, window_len) for skip_steps, itr in enumerate(iterators): for ignored in islice(itr, skip_steps): pass window_itr = izip(*iterators) if window_step != 1: window_itr = islice(window_itr, step=window_step) return window_itr As you can see, I'd leave the padding out of this function signature - if you want padding you can more easily specify it directly when calculating the iterable to be windowed. Do you want padding before and after the sequence, or just after? Pad with None or with zeroes? Better to expand on the padnone recipe: def pad(iterable, pad_value=None, times=None): Pads an iterable with a repeating value The quantity of padding may be limited by specifying a specific number of occurrences. return chain(iterable, repeat(pad_value, times)) def padwindow(iterable, window_len, pad_value=None): Pads an iterable appropriately for the given window length Padding is added to both the front and back of the sequence such that the first and last windows will each contain one value from the actual sequence. return chain(repeat(pad_value, window_len-1), iterable, repeat(pad_value, window_len-1)) Cheers, Nick. -- Nick Coghlan | [EMAIL PROTECTED] | Brisbane, Australia --- http://www.boredomandlaziness.org ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] Proposal for a new itertools function: iwindow
From: Nick Coghlan [EMAIL PROTECTED] A python-dev Google search for itertools window found me your original suggestion to include Jack Diedrich's itertools.window in Python 2.3 (which was only deferred because 2.3 was already past beta 1 at that point). I couldn't find any discussion of the idea after that (aside from your pointing out that you'd never found a real-life use case for the pairwise() recipe in the docs, which is a basic form of windowing). One option would be to add a windowing function to the recipes in the itertools docs. Something like: def window(iterable, window_len=2, window_step=1): iterators = tee(iterable, window_len) for skip_steps, itr in enumerate(iterators): for ignored in islice(itr, skip_steps): pass window_itr = izip(*iterators) if window_step != 1: window_itr = islice(window_itr, step=window_step) return window_itr No thanks. The resolution of this one was that windowing iterables is not a good idea. It is the natural province of sequences, not iterables. With sequences, it is a matter of using an index and offset. With iterables, there is a great deal of data shifting. Also note that some of the uses are subsumed by collections.deque(). In implementing a draft of itertools window, we found that the data shifting was unnatural and unavoidable (unless you output some sort of buffer instead of a real tuple). Also, we looked at use cases and found that most had solutions that were dominated by some other approach. The addition of a windowing tool would tend to steer people away from better solutions. In short, after much deliberation and experimenting with a sample implementation, the idea was rejected. Hopefully, it will stay dead and no one will start a cruscade for it simply because it can be done and because it seems cute. The thought process was documented in a series of newsgroup postings: http://groups.google.com/group/comp.lang.python/msg/026da8f9eec4becf The SF history is less informative because most of the discussions were held by private email: http://www.python.org/sf/756253 If someone aspires to code some new itertools, I have approved two new ones, imerge() and izip_longest(). The pure python code for imerge() is at: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/491285 The impetus behind izip_longest() was expressed in a newsgroup thread, http://groups.google.com/group/comp.lang.python/browse_thread/thread/f424f63bfdb77c4/38c31991133757f7 . The discussion elicted neither broad support, nor condemnation. Also, the use cases were sparse. Ultimately, I was convinced by encountering a couple of natural use cases. Another thought is that while other solutions are usually available for any given use case, there is a natural tendency to reach for a zip-type tool whenever presented with lock-step iteration issues, even when the inputs are of uneven length. Note, that the signature for izip_longest() needs to include an optional pad value (defaulting to None) -- there are plenty of use cases where an empty string, zero, or a null object would be a preferred pad value. Cheers, Raymond ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] Proposal for a new itertools function: iwindow
Hi, in the last time, I've found myself reimplementing a generator that provides a sliding-window-view over a sequence, and I think this function is of a greater usefullness, so that it might be included in itertools. Basically, what the generator does it return all m consecutive elements from a sequence [i0, i1, ... in]. It then returns [i0, i1, i2], [i1, i2, i3], ... [in-2, in-1, in] (assuming that m = 3). In code, it looks like this: list(iwindow(range(0,5), 3)) [[0, 1, 2], [1, 2, 3], [2, 3, 4]] This list can be generated by using izip(a, a[1:], ..., a[n:]), but typing all the sequence arguments gets tedious. If a is not a sequence but a generator, tee(...) and islice has to be used. It might be possible that the windows should be padded, so that the sequence of windows starts with [pad, pad, ..., i0] and ends with [in, pad, pad, ...] list(iwindow(range(0,5), 3, pad=True)) [[None, None, 0], [None, 0, 1], [0, 1, 2], [1, 2, 3], [2, 3, 4], [3, 4, None], [4, None, None]] Additionally, the value used for padding can be specified. This makes the argument list of this function rather long, but the last two arguments are optional anyway: iwindow(iterable, window_size=3, pad = False, padding_value = None) Some open question remain: - should iwindow return lists or tuples? - what happens if the length of the iterable is smaller than the window size, and no padding is specified? Is this an error? Should the generator return no value at all or one window that is too small? I've attached a Python implementation of this function. If the function is deemed to be actually useful, I'd be happy to brush up my C and provide a C implementation along with docs and tests. best, Torsten PS: Please CC me, as I'm not subscribed to the list -- Torsten Marek [EMAIL PROTECTED] ID: A244C858 -- FP: 1902 0002 5DFC 856B F146 894C 7CC5 451E A244 C858 Keyserver: subkeys.pgp.net iwindow.py Description: application/python signature.asc Description: OpenPGP digital signature ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com