Issue15224
This issue tracker has been migrated to GitHub,
and is currently read-only.
For more information,
see the GitHub FAQs in the Python's Developer Guide.
Created on 2012-06-29 16:37 by Yclept.Nemo, last changed 2022-04-11 14:57 by admin. This issue is now closed.
Files | ||||
---|---|---|---|---|
File name | Uploaded | Description | Edit | |
Range.py | Yclept.Nemo, 2012-06-29 16:37 | Example Range implementation (python) | ||
Range.py | Yclept.Nemo, 2012-06-29 21:42 | Example Range implementation (python) v2 |
Messages (10) | |||
---|---|---|---|
msg164333 - (view) | Author: Yclept Nemo (Yclept.Nemo) | Date: 2012-06-29 16:37 | |
Python 3.3 expands the range class but I would find some additional methods useful: min/max: provides O(1) time __and__: provides intersection: Range(...) & Range(...) examples: intersection #1: a=Range.Range(9,58,4) b=Range.Range(15,69,6) c=a&b print(c) Range(21, 69, 12) list(c) [21, 33, 45, 57] intersection #2: a=Range.Range(-75,-7,4) b=Range.Range(-111, -26, 6) c=a&b print(c) Range(-75, -15, 12) list(c) [-75, -63, -51, -39, -27] intersection #3: a=Range.Range(58,9,-4) b=Range.Range(15,69,6) c=a&b print(c) Range(0, 0, 1) list(c) [] I've attached an example Range class implemented in python that includes the min, max, and __and__ functions. It should be useful because the intersection algorithm is complicated. Extending the range class was a requirement for a python 3.2 project and hopefully python 3.4 can benefit. |
|||
msg164334 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2012-06-29 17:02 | |
max and min for a range object are already O(1) one-liners: >>> a = range(3, 21, 5) >>> a[-1] if a.step > 0 else a[0] # max(a) 18 >>> a[0] if a.step > 0 else a[-1] # min(a) 3 As for __and__, it doesn't feel like a particularly natural operation to me, given that a range object represents an *ordered* sequence of integers rather than just a subset. For example, what should the first element of range(7, -3, -2) & range(10) be? 7 or 1? And why? |
|||
msg164354 - (view) | Author: Yclept Nemo (Yclept.Nemo) | Date: 2012-06-29 21:42 | |
> max and min for a range object are already O(1) one-liners: true; dropping > As for __and__, it doesn't feel like a particularly natural operation to me, given that a range object represents an *ordered* sequence of integers rather than just a subset. True, there is no canonical sorting. However, the concept of the intersection of ordered sets is commonplace and implemented in other libraries, for example: http://www.swi-prolog.org/pldoc/doc_for?object=section%282,%27A.17%27,swi%28%27/doc/Manual/ordsets.html%27%29%29 http://hackage.haskell.org/packages/archive/containers/0.4.1.0/doc/html/Data-Set.html#v:intersection http://hackage.haskell.org/packages/archive/data-ordlist/0.2/doc/html/Data-List-Ordered.html#v:isect My implementation inherets the ordering of the first range: R(1) R(2) R(F) p p p n p n p n p n n n key: p === positive === increasing key: n === negative === decreasing Haskell documentation has an apt paradigm for the ordering: "Elements of the result come from the first set"; similary my implementation selects elements from the first set common to the second. From a programming persepctive this is quite natural too: lcm = (a*b)/gcd(a,b) where lcm determines the ordering. Basically, the behavior of the attached __and__ implementation is driven by python's gcd function. |
|||
msg164355 - (view) | Author: Yclept Nemo (Yclept.Nemo) | Date: 2012-06-29 21:46 | |
>>> a=Range.Range(5,61,4) >>> ar=Range.Range(57,1,-4) >>> b=Range.Range(21,63,6) >>> br=Range.Range(57,15,-6) >>> list(a); list(ar); list(b); list(br) [5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57] [57, 53, 49, 45, 41, 37, 33, 29, 25, 21, 17, 13, 9, 5] [21, 27, 33, 39, 45, 51, 57] [57, 51, 45, 39, 33, 27, 21] >>> list(a&b) [21, 33, 45, 57] >>> list(a&br) [21, 33, 45, 57] >>> list(ar&br) [57, 45, 33, 21] >>> list(ar&b) [57, 45, 33, 21] >>> a&b Range(21, 69, 12) >>> a&br Range(21, 69, 12) >>> ar&br Range(57, 9, -12) >>> ar&b Range(57, 9, -12) |
|||
msg164356 - (view) | Author: Yclept Nemo (Yclept.Nemo) | Date: 2012-06-29 21:49 | |
On a side note, glancing at Python-3.3.0a4/Objects/rangeobject.c: range_contains seems to iterate through the entire range whereas __contains__ from the attached Range.py is O(1) |
|||
msg164370 - (view) | Author: Serhiy Storchaka (serhiy.storchaka) * | Date: 2012-06-30 06:13 | |
> On a side note, glancing at Python-3.3.0a4/Objects/rangeobject.c: > range_contains seems to iterate through the entire range whereas __contains__ from the attached Range.py is O(1) See issue1766304. For int range.__contains__ is O(1), for custom types this optimization is impossible without losing backward compatibility. |
|||
msg164374 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2012-06-30 07:42 | |
> However, the concept of the intersection of ordered sets is commonplace > and implemented in other libraries, for example: None of those are specific to arithmetic progressions (i.e., range-like lists / sets), as far as I can tell. I could see more use for general list-intersection functionality. I'm still -1 on this; it seems too specialised a need to belong in the core language. |
|||
msg164404 - (view) | Author: Yclept Nemo (Yclept.Nemo) | Date: 2012-06-30 17:30 | |
>> None of those are specific to arithmetic progressions (i.e., range-like lists / sets), as far as I can tell. Does this (the data-type involved) really matter? >> I could see more use for general list-intersection functionality. The way to implement generic functionality is to define a protocol and override inherited behavior when necessary. Generic intersection (when semantics can be agreed upon) can computed using the iterator protocol, but __and__ of the range class should be overridden to provide O(1) behavior. So, perhaps a proposal for implementing __and__ for lists as well ? >> I'm still -1 on this; it seems too specialised a need to belong in the core language. While I do see several arguments against the inclusion of __and__: . it would require the inclusion of union and difference operations . vague definition of intersection with regard to ranges. Do you treat range like a linear equation, so only consider intersections at the same index. Also the issue regarding ordering. . re issue1766304, it may be pointless providing an O(1) __and__ for range if it can only work for ints(??) I don't think that complexity or specialisation should matter. A range is already a specialised data type (do any other languages have a range class - separate from slices?) Python's data model provides __and__. Conceptually, why not bring range to its full potential using facilities that python already provides. By the way, I don't have anything at stake in this - just arguing for argument's sake - so you can close this if you feel strongly enough about not implementing it. |
|||
msg164407 - (view) | Author: Mark Dickinson (mark.dickinson) * | Date: 2012-06-30 18:27 | |
Okay, I'm closing this as rejected. Some responses: > I don't think that complexity or specialisation should matter. Well, Python's supposed to be a general-purpose language; range objects *are* generally useful for all sorts of tasks, but it's far from clear that being able to intersect them would be valuable to a wide range of people. > Conceptually, why not bring range to its full potential using facilities that python already provides. Because additions to the language (especially the core language, as opposed to the standard library) are far from free. First the feature needs to be implemented, reviewed, fully tested and documented. Then it needs to be maintained. Other Python implementations (PyPy, IronPython, Jython, etc.) need to create their own implementations. Text book writers need to keep up with the changes. The addition makes the language larger, making more to learn for students of the language and more to teach for teachers. In this particular case, I'm worried that there's a real risk of making a poor API choice that will inhibit later language expansion---you can't just add a method to a builtin type without considering the impact on the language as a whole, both now and in the future. So there's a significant cost in each core language addition, even for something as simple-looking as this. And the benefits of the addition have to be weighed against that cost. In this case, I see very little benefit---I doubt that there's a real and common need for range intersections. And all of the above is before discussing the implementation difficulties associated with this particular feature: it would likely require a C implementation of the gcd function, which is *not* a trivial thing to do efficiently, so we're looking at much more than just a few lines of code, with all the attendant risks of introducing new bugs. |
|||
msg164438 - (view) | Author: Raymond Hettinger (rhettinger) * | Date: 2012-07-01 00:34 | |
FWIW, I concur with rejecting this for the reasons that Mark mentioned. |
History | |||
---|---|---|---|
Date | User | Action | Args |
2022-04-11 14:57:32 | admin | set | github: 59429 |
2012-07-01 00:34:29 | rhettinger | set | nosy:
+ rhettinger messages: + msg164438 |
2012-06-30 18:27:58 | mark.dickinson | set | status: open -> closed resolution: rejected messages: + msg164407 |
2012-06-30 17:30:44 | Yclept.Nemo | set | messages: + msg164404 |
2012-06-30 07:42:16 | mark.dickinson | set | messages: + msg164374 |
2012-06-30 06:13:21 | serhiy.storchaka | set | nosy:
+ serhiy.storchaka messages: + msg164370 |
2012-06-29 21:49:13 | Yclept.Nemo | set | messages: + msg164356 |
2012-06-29 21:46:27 | Yclept.Nemo | set | messages: + msg164355 |
2012-06-29 21:42:42 | Yclept.Nemo | set | files:
+ Range.py messages: + msg164354 |
2012-06-29 17:02:25 | mark.dickinson | set | nosy:
+ mark.dickinson messages: + msg164334 |
2012-06-29 16:37:02 | Yclept.Nemo | create |