[Python-ideas] Re: deque: Allow efficient operations
On 30/04/20 3:32 am, Christopher Barker wrote: I've wondered about Linked Lists for a while, but while there are many versions on PyPi, I can't find one that seems to be mature and maintained. Which seems to indicate that there isn't much demand for them. I think this is probably because a linked list is more of a design pattern than a concrete data structure. In situations where you want a linked list in particular, rather than just a container that supports certain operations, you really need the references implementing the links to be embedded in the objects being kept in the list. This makes it difficult to abstract, especially if your objects need to be part of more than one list at a time. -- Greg ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/TFZAVVZ2A3WAMPTMNOPUSNGIZTWBRJNM/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On 29/04/20 11:32 pm, Steven D'Aprano wrote: My reasoning was that *eventually* for a big enough list, the cost of making the copy would outweigh the cost of moving the items. I don't know if my reasoning was valid or not, I think it's not. They're both O(n) in the length of the list, so at most they will differ by a constant factor for large n. -- Greg ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/FYNTET632SAORICSJQP5E4VENH2XKRLZ/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
On Apr 29, 2020, at 11:15, Tom Forbes wrote: > >> Thread 2 wakes up with the lock, calls the function, fills the cache, and >> releases the lock. > > What exactly would the issue be with this: > > ``` > import functools > from threading import Lock > > def once(func): >sentinel = object() >cache = sentinel >lock = Lock() > >@functools.wraps(func) >def _wrapper(): >nonlocal cache, lock, sentinel >if cache is sentinel: >with lock: >if cache is sentinel: >cache = func() >return cache > >return _wrapper > ``` You’ve written an exactly equIvalent to the double-checked locking for singletons examples that broke Java 1.4 and C++03 and led to us having once functions in the first place. In both of those languages, and most others, there is no guarantee that the write to cache in thread 1 happens between the two reads from cache in thread 2. Which gives you the fun kind of bug that every few thousand runs you have corrupted data an hour later, or it works fine on your computer but it crashes for one of your users because they have two CPUs that don’t share L2 cache while you have all your cores on the same die, or it works fine until you change some completely unrelated part of the code, etc. Java solved this by adding volatile variables in Java 5 (existing code was still broken, but just mark cache volatile and it’s fixed); C++11 added a compiler-assisted call_once function (and added a memory model that allows them to specify exactly what happens and when so that the desired behavior was actually guaranteeable). Newer languages learned from their experience and got it right the first time, rather than repeating the same mistake. Is there anything about Python’s memory model guarantee that means it can’t happen in Python? I don’t think there _is_ a memory model. In CPython, or any GIL-based implementation, I _think_ it’s safe (the other thread can’t be running at the same time on a different core, so there can’t be a cache coherency ordering issue between the cores, right?), but what about on Jython, or PyPy-STM, or a future GIL-less Python? And in both of those languages, double-checked locking is still nowhere near as efficient as using a local static. > Seems generally more correct, even in single threaded cases, to pay the > overhead only in the first call if you want `call_once` semantics. Which is > why you would be using `call_once` in the first place? But you won’t be paying the overhead only on the first call, you’ll be paying it on all of the calls that before the first one completed. That’s the whole point of the lock, after all—they have to wait until it’s ready—and they can’t possibly do that without the lock overhead. And for the next few afterward, because they’ll have gotten far enough to check even if they haven’t gotten far enough to get the lock, and there’s no way they can know they don’t need the lock. And for the next few after that, because unless the system only runs one thread at a time and synchronizes all of memory every time you switch threads they may not see the write yet anyway. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/G4ZDP6UYOL323VGX4IFRGGA5OVIEDD6P/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
> On Apr 29, 2020, at 11:15 AM, Tom Forbes wrote: > > What exactly would the issue be with this: > > ``` > import functools > from threading import Lock > > def once(func): >sentinel = object() >cache = sentinel >lock = Lock() > >@functools.wraps(func) >def _wrapper(): >nonlocal cache, lock, sentinel >if cache is sentinel: >with lock: >if cache is sentinel: >cache = func() >return cache > >return _wrapper > ``` This recipe is the best variant so far and gives us something concrete to talk about :-) Benefits: Guarantees the wrapped function is not called more than once. Restrictions: Only works with zero argument functions. Risks: Any reentrancy or recursion will result in deadlock. Limitations: No instrumentation. No ability to reset or clear. Won't work across multiple processes. It would be nice to look at some compelling use cases. Off hand, I can't think of time when I would have used this decorator. Also, I have a nagging worry that holding a non-reentrant lock across an arbitrary user defined function call is recipe for deadlocks. That's why during code reviews we typically check every single use of Lock() to see if it should have been an RLock(), especially in big systems where GC, __del__, or weakref callbacks can trigger running any code at just about any time. Raymond ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/B32VKG5IPHKEL4Y7MP7WMQZXZYYWVT64/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
> On Apr 29, 2020, at 12:02 PM, Christopher Barker wrote: > > On Apr 29, 2020, at 08:33, Christopher Barker wrote: > > I've wondered about Linked Lists for a while, but while there are many > > versions on PyPi, I can't find one that seems to be mature and maintained. > > Which seems to indicate that there isn't much demand for them. > > Isn't much demand for a *generic* linked list. It would probably be a good > recipe though -- so users could have a starting point for their custom > version. In case you're interested, the pure python OrderedDict code uses a doubly linked list augmented by a dictionary to quickly find individual links. It may be worth taking at look.¹ The implementation was mostly obvious. The only trick was to use weakrefs for the backlink to avoid creating a reference cycle — the original version just lets GC do the clean-up, but users wanted to avoid cycles entirely. Raymond ¹ https://github.com/python/cpython/blob/3.8/Lib/collections/__init__.py#L78 ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/5ZSDX4FBSZEG3W6CGY6DNDOTLDOK7AQJ/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On 29/04/2020 20:54, Andrew Barnert via Python-ideas wrote: On Apr 29, 2020, at 12:03, Christopher Barker wrote: Isn't much demand for a*generic* linked list. It would probably be a good recipe though -- so users could have a starting point for their custom version. I think what would be really handy would be a HOWTO on linked lists that showed the different options and tradeoffs and how to implement and use at least a few different ones, and showed why they’re useful with examples. (And also showed why the Sequence/Iterable API can be helpful but also why it’s not sufficient.) Isn't the point that you should be approaching a datastructure in Python thinking about what you want it to do, not how it's implemented underneath? That sort of micromanagement smacks of premature optimisation. -- Rhodri James *-* Kynesim Ltd ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/X4FQMNUQLVVHPCCA7VGACO4NA4YZLLXJ/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Thu, Apr 30, 2020 at 5:56 AM Andrew Barnert via Python-ideas wrote: > > On Apr 29, 2020, at 12:03, Christopher Barker wrote: > > > > > > Isn't much demand for a *generic* linked list. It would probably be a good > > recipe though -- so users could have a starting point for their custom > > version. > > I think what would be really handy would be a HOWTO on linked lists that > showed the different options and tradeoffs and how to implement and use at > least a few different ones, and showed why they’re useful with examples. (And > also showed why the Sequence/Iterable API can be helpful but also why it’s > not sufficient.) > > Then the collections module (and the tutorial?) could both just have a > sentence saying “Python doesn’t have a linked list type because there are so > many useful kinds of linked lists and they’re all easy to build but very > different—see the Linked Lists HOWTO for details.” > > But if I wrote it, it would probably be 4x as long as any novice would want > to read. > Summary, for novices: "Just use a built-in list and don't worry about it. Performance of built-in types is usually 'good enough' even if it isn't perfect." It's only the experts who need this sort of thing, so I'm not too bothered if novices can't implement LLs efficiently in Python. ChrisA ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/UFMIEFDYM3ZTFIEM7DJ53W7X3KUHAXVL/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Apr 29, 2020, at 12:03, Christopher Barker wrote: > > > Isn't much demand for a *generic* linked list. It would probably be a good > recipe though -- so users could have a starting point for their custom > version. I think what would be really handy would be a HOWTO on linked lists that showed the different options and tradeoffs and how to implement and use at least a few different ones, and showed why they’re useful with examples. (And also showed why the Sequence/Iterable API can be helpful but also why it’s not sufficient.) Then the collections module (and the tutorial?) could both just have a sentence saying “Python doesn’t have a linked list type because there are so many useful kinds of linked lists and they’re all easy to build but very different—see the Linked Lists HOWTO for details.” But if I wrote it, it would probably be 4x as long as any novice would want to read. (I think I wrote some blog posts on linked lists in Python years ago, and ended up building a Haskell-style lazy list out of a trigger function and then showing how to do Fibonacci numbers by recursively zipping it, or something crazy like that.) In the old days we could probably just post three different simple recipes on ActiveState and link to them from the docs and let people build on the examples there, rather than try to write it all up-front and fit it into the Python docs style, but that doesn’t work so well anymore. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/CTSBRBTMALAM6JFW6H4JPT2SAADK44A6/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: zip(x, y, z, strict=True)
On Apr 29, 2020, at 07:08, Barry Scott wrote: > > >> On 28 Apr 2020, at 16:12, Rhodri James wrote: >> >>> On 28/04/2020 15:46, Brandt Bucher wrote: >>> Thanks for weighing in, everybody. >>> Over the course of the last week, it has become surprisingly clear that >>> this change is controversial enough to require a PEP. >>> With that in mind, I've started drafting one summarizing the discussion >>> that took place here, and arguing for the addition of a boolean flag to the >>> `zip` constructor. Antoine Pitrou has agreed to sponsor, and I've chatted >>> with another core developer who shares my view that such a flag wouldn't >>> violate Python's existing design philosophies. >>> I'll be watching this thread, and should have a draft posted to the list >>> for feedback this week. >> >> -1 on the flag. I'd be happy to have a separate zip_strict() (however you >> spell it), but behaviour switches just smell wrong. > > Also -1 on the flag. > > 1. A new name can be searched for. > 2. You do not force a if on the flag for every single call to zip. Agreed on both Rhodri’s and Barry’s reasons, and more below. I also prefer the name zip_equal to zip_strict, because what we’re being strict about isn’t nearly as obvious as what’s different between shortest vs. equal vs. longest, but that’s just a mild preference, not a -1 like the flag. In addition to the three points above: Having one common zip variant spelled as a different function and the other as a flag seems really bad for learning and remembering the language. And zip_longest has a solidly established precedent. And I don’t think you want to add multiple bool flags to zip? Also, just look at these: zip_strict(xs, ys) zip(xs, ys, strict=True) The first one is easier to read because it doesn’t have the extra 5 characters to skim over that don’t really add anything to the meaning, and it puts the important distinction up front. It’s also shorter, and a lot easier to type with auto-complete—which isn’t nearly as big of a deal, but if this is really meant to be used often it does add up. And it’s obviously more extensible, if it really is at all possible that we might want to eventually deprecate shortest or add new end behaviors like yielding partial tuples or Soni’s thing of stashing the leftovers somehow (none of which I find very convincing, but others apparently do, and picking a design that rules them out means explicitly rejecting them). A string or enum flag instead of a book solves half of those problems (as long as “longest” is one of the options), but it makes others even worse. The available strings aren’t even discoverable as part of the signature, auto-complete won’t help at all, and the result is even longer and even more deemphasizes the important thing. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/3JKAI25VFIGBO4HPWQ6S22PNKZ6ZOCCT/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
Thanks for all the details -- it really makes the point I was trying to make. On Apr 29, 2020, at 08:33, Christopher Barker wrote: > > I've wondered about Linked Lists for a while, but while there are many > versions on PyPi, I can't find one that seems to be mature and maintained. > Which seems to indicate that there isn't much demand for them. > Isn't much demand for a *generic* linked list. It would probably be a good recipe though -- so users could have a starting point for their custom version. Also -- as you point out, while it may be useful for a linked list to be a Sequence, the API shouldn't be only that -- it'd almost defeat the purpose of a linked list at all. -CHB > I think there’s lots of demand for them, but there are so many different > variants that can’t substitute for each other (try taking any nontrivial > sample code using Haskell’s single-linked, no-handle, immutable > tail-sharing list and rewriting it with C++’s doubly-linked handled mutable > list, or vice-versa), and most of the key operations fit so poorly with > Python’s sequence/iterable API, and they’re all so easy to build, that > people just build the one they need whenever they need it. > > I do have a few different linked lists in my toolbox that have come up > often enough that I stashed them (an immutable cons, a handled > double-linked list, a cffi wrapper for a common style of C > internally-linked lists, probably others), but half the time I reach for > one I have to modify it anyway, so I haven’t bothered to turn them into a > package I just import and use. > > And, while I did add the whole (Mutable)Sequence API to each one (because > it’s convenient for debugging and REPL exploration to be able to list(xs), > or to get a repr that’s written in terms of a from_iter classmethod so I > can eval it back, etc.), I usually don’t use that API for anything but > debugging. When you’re dealing with linked lists, you usually need to deal > with the nodes directly. For example, one big reason to use linked lists is > constant-time splicing, but you can’t splice in constant time if all you > have is the head/handle and/or an opaque iterator that only knows how to go > forward; you need the node before the splice point (or, for doubly-linked, > after is fine too). Another reason to use (Lisp/Haskell-style) linked lists > is that they automatically release nodes as you iterate unless you keep a > reference to the head, but that’s clumsy to do with Python-style APIs. And > so on. > > > -- Christopher Barker, PhD Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/5QCUQDP7KYKFC2PUCGZGUUYI22S7R7XB/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Apr 29, 2020, at 08:33, Christopher Barker wrote: > > I've wondered about Linked Lists for a while, but while there are many > versions on PyPi, I can't find one that seems to be mature and maintained. > Which seems to indicate that there isn't much demand for them. I think there’s lots of demand for them, but there are so many different variants that can’t substitute for each other (try taking any nontrivial sample code using Haskell’s single-linked, no-handle, immutable tail-sharing list and rewriting it with C++’s doubly-linked handled mutable list, or vice-versa), and most of the key operations fit so poorly with Python’s sequence/iterable API, and they’re all so easy to build, that people just build the one they need whenever they need it. I do have a few different linked lists in my toolbox that have come up often enough that I stashed them (an immutable cons, a handled double-linked list, a cffi wrapper for a common style of C internally-linked lists, probably others), but half the time I reach for one I have to modify it anyway, so I haven’t bothered to turn them into a package I just import and use. And, while I did add the whole (Mutable)Sequence API to each one (because it’s convenient for debugging and REPL exploration to be able to list(xs), or to get a repr that’s written in terms of a from_iter classmethod so I can eval it back, etc.), I usually don’t use that API for anything but debugging. When you’re dealing with linked lists, you usually need to deal with the nodes directly. For example, one big reason to use linked lists is constant-time splicing, but you can’t splice in constant time if all you have is the head/handle and/or an opaque iterator that only knows how to go forward; you need the node before the splice point (or, for doubly-linked, after is fine too). Another reason to use (Lisp/Haskell-style) linked lists is that they automatically release nodes as you iterate unless you keep a reference to the head, but that’s clumsy to do with Python-style APIs. And so on. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/DGBRHXGXHAMERZRQW2WN5XMU22WBIHUK/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
> Thread 2 wakes up with the lock, calls the function, fills the cache, and > releases the lock. What exactly would the issue be with this: ``` import functools from threading import Lock def once(func): sentinel = object() cache = sentinel lock = Lock() @functools.wraps(func) def _wrapper(): nonlocal cache, lock, sentinel if cache is sentinel: with lock: if cache is sentinel: cache = func() return cache return _wrapper ``` It ensures it’s invoked once, it’s fast and it doesn’t require acquiring a lock needlessly. Always wrapping a lock around a static value to account for a small edge case seems redundant, more than “it’s usually not optimal”. It’s never optimal: in multi-threaded cases you’re causing needless contention, and in single threaded cases all your calls are now slower. Seems generally more correct, even in single threaded cases, to pay the overhead only in the first call if you want `call_once` semantics. Which is why you would be using `call_once` in the first place? > On 29 Apr 2020, at 18:51, Andrew Barnert wrote: > > On Apr 29, 2020, at 00:34, Tom Forbes wrote: >> >> It’s not quite that easy, either you needlessly lock all calls or you end >> up invoking it twice. >> >> What you want is to acquire a lock if the cache is empty, check if another >> thread has filled the cache while you where waiting on the lock, call the >> function, fill the cache and return. > > Thread 1 sees the cache is empty, so it acquires the lock, runs the function. > > Thread 2 sees the cache is empty, so it tries to acquire the cache and blocks. > > Thread 1 finishes the function, fills the cache, and releases the lock. > > Thread 2 wakes up with the lock, calls the function, fills the cache, and > releases the lock. > > You’ve now run the function twice instead of once, and the first caller got a > different value than the one every subsequent caller can get. > > There are actually plenty of cases where this is acceptable (the function is > safe, and idempotent, and while it’s slow it’s not so slow that occasionally > running it twice is worse than locking a zillion times)—but in those cases, > just not using a lock is even better. In fact, if you can compare-and-swap at > the end (which requires a lock to simulate in Python, but it’s a much more > granular one than locking over the whole expensive function call), you can > even use it in more cases (in particular, where the function isn’t idempotent > but you need to value to be). > > This is exactly why users should be encouraged to just lock the whole thing. > It’s always correct. It’s usually not optimal, but often good enough. The one > really common and simple case where it’s not good enough is single-threaded > code. Anything else where you need to optimize, you really do need to > understand the pattern you’re trying to optimize for (and the environment(s) > you’re running under) and write your own function. > > ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/MHTUCWAKNA72ACADM6N6VNCYRM3IBY7T/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
29.04.20 17:56, Ram Rachum пише: Thanks everybody for your answers, and especially Ricky for finding this note. Please not that the optimization mentioned in the comment still keeps the linear complexity for these operations. It just reduces the constant multiplier. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/5GPWJE4TGNKQTB54GPH3TELCGBB2OYPP/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: zip(x, y, z, strict=True)
On Tue, Apr 28, 2020 at 7:49 AM Brandt Bucher wrote: > With that in mind, I've started drafting one summarizing the discussion > that took place here, and arguing for the addition of a boolean flag to the > `zip` constructor. Since you've gotten a few -1s, I'll add a +1 -- for reasons posted here before, a flag is far more likely to actually get used :-) -- but that's why we need a PEP. However, I urge you to consider a trinary switch instead: "shortest" (default) | "longest" | "equal" Yes, we already have zip_longest, but if we're adding switching behavior to zip(), it might as well handle all cases -- that seems a cleaner API to me. -CHB -- Christopher Barker, PhD Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/TIJ6JBBX7GMRRVYTE7I7EXNLXMHTOIQY/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Wed, Apr 29, 2020 at 8:02 AM Ram Rachum wrote: > Thanks everybody for your answers, and especially Ricky for finding this > note. > which seems to indicate that if one were to implement this code more efficiently, it would be considered for inclusion. I will note that for the most part, the Python specs are for the API, and do not guarantee particular performance characteristics. Dicts are efficient because they need to be for reasonable performance of the entire interpreter, but it isn't part of the Mapping ABC. Is there a single instance of the SAME ABC being implemented in two ways, with different performance characteristics? I've wondered about Linked Lists for a while, but while there are many versions on PyPi, I can't find one that seems to be mature and maintained. Which seems to indicate that there isn't much demand for them. -CHB > On Wed, Apr 29, 2020 at 2:20 PM Ricky Teachey wrote: > >> I was playing around with deque today, and there were a couple of >>> operations I wanted to do, that can't really be done efficiently with deque >>> because of its implementation. >>> >>> ... >>> >>> What do you think about adding [O(1) insert and remove] this to `deque`? >>> >> >> _collectionsmodule.c has this note, so it sounds like this is intended to >> be a possibility if there is enough interest: >> >> /* insert(), remove(), and delitem() are implemented in terms of rotate() >>> for simplicity and reasonable performance near the end points. If for some >>> reason these methods become popular, it is not hard to re-implement this >>> using direct data movement (similar to the code used in list slice >>> assignments) and achieve a performance boost (by moving each pointer only >>> once instead of twice). */ >> >> >> >> https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958 >> >> >> >> --- >> Ricky. >> >> "I've never met a Kentucky man who wasn't either thinking about going >> home or actually going home." - Happy Chandler >> > ___ > Python-ideas mailing list -- python-ideas@python.org > To unsubscribe send an email to python-ideas-le...@python.org > https://mail.python.org/mailman3/lists/python-ideas.python.org/ > Message archived at > https://mail.python.org/archives/list/python-ideas@python.org/message/JUOQ6DASMKMV52FKIQYAQQ4MJLYBK4LA/ > Code of Conduct: http://python.org/psf/codeofconduct/ > -- Christopher Barker, PhD Python Language Consulting - Teaching - Scientific Software Development - Desktop GUI and Web Development - wxPython, numpy, scipy, Cython ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/TS2WR6WVXWLHHY63FWWJA43GHIZORDAI/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
Thanks everybody for your answers, and especially Ricky for finding this note. On Wed, Apr 29, 2020 at 2:20 PM Ricky Teachey wrote: > I was playing around with deque today, and there were a couple of >> operations I wanted to do, that can't really be done efficiently with deque >> because of its implementation. >> >> ... >> >> What do you think about adding [O(1) insert and remove] this to `deque`? >> > > _collectionsmodule.c has this note, so it sounds like this is intended to > be a possibility if there is enough interest: > > /* insert(), remove(), and delitem() are implemented in terms of rotate() >> for simplicity and reasonable performance near the end points. If for some >> reason these methods become popular, it is not hard to re-implement this >> using direct data movement (similar to the code used in list slice >> assignments) and achieve a performance boost (by moving each pointer only >> once instead of twice). */ > > > > https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958 > > > > --- > Ricky. > > "I've never met a Kentucky man who wasn't either thinking about going home > or actually going home." - Happy Chandler > ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/JUOQ6DASMKMV52FKIQYAQQ4MJLYBK4LA/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
> On 29 Apr 2020, at 12:36, remi.lape...@henki.fr wrote: > > Also, removing an element from a doubly-linked list is not a O(1) operation, > it's O(n). It's O(1) once you have a pointer to the element but you have to > iterate over the list to get it and that would take O(n) operations, so > making deque a doubly-linked list would not be faster anyway. In the cases where a DLL is the reasonable design choice remove is O(1) in my experience. The reason is that you have the element in your hand by other means then scanning the DLL. This was a heavily used pattern when I worked on DEC VMS device drivers. Async I/O requests could be cancelled and removed from the list of outstanding I/O for a device in O(1). Indeed the VAX had instructions to implement this pattern in hardware. Barry ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/O7LECTMOQEJUXT2NENFOYN3YEWU3EDL7/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: zip(x, y, z, strict=True)
> On 28 Apr 2020, at 16:12, Rhodri James wrote: > > On 28/04/2020 15:46, Brandt Bucher wrote: >> Thanks for weighing in, everybody. >> Over the course of the last week, it has become surprisingly clear that this >> change is controversial enough to require a PEP. >> With that in mind, I've started drafting one summarizing the discussion that >> took place here, and arguing for the addition of a boolean flag to the `zip` >> constructor. Antoine Pitrou has agreed to sponsor, and I've chatted with >> another core developer who shares my view that such a flag wouldn't violate >> Python's existing design philosophies. >> I'll be watching this thread, and should have a draft posted to the list for >> feedback this week. > > -1 on the flag. I'd be happy to have a separate zip_strict() (however you > spell it), but behaviour switches just smell wrong. Also -1 on the flag. 1. A new name can be searched for. 2. You do not force a if on the flag for every single call to zip. Barry > > -- > Rhodri James *-* Kynesim Ltd > ___ > Python-ideas mailing list -- python-ideas@python.org > To unsubscribe send an email to python-ideas-le...@python.org > https://mail.python.org/mailman3/lists/python-ideas.python.org/ > Message archived at > https://mail.python.org/archives/list/python-ideas@python.org/message/BZUJUTAVOHJEUZ6QEIRZWZHKCRXE6AAS/ > Code of Conduct: http://python.org/psf/codeofconduct/ > ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/XEQIZHKWNKFDWQCBK4FAEGP2TEMDTMMP/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Wed, Apr 29, 2020 at 01:42:05PM +0300, Ram Rachum wrote: > I was iterating through items of a deque, and in some cases I wanted to > delete an item that I've found. Deleting items from a container while iterating through it is an anti-pattern, easy to get wrong, prone to bugs, and in a high-level language like Python, very likely to be slower than creating a new container and copying it across. I haven't tried it with dequeues, but some versions ago I tried to find the cross-over point where it was more efficient to delete items from a list in place, instead of copying: mylist[:] = [x from x in mylist if not condition] versus: for i in range(len(mylist)-1, -1, -1): if condition: del mylist[i] My reasoning was that *eventually* for a big enough list, the cost of making the copy would outweigh the cost of moving the items. I don't know if my reasoning was valid or not, but I was unable to find any such cutoff on my computer, up to hundreds of millions of items. Deletion was always slower. But, if you insist on doing it, dequeues support deletion. > As far as I understand, this is an > operation that should be O(1) in a linked list, but Python only provides an > O(N) way to do that, which is `del d[i]`. Dequeues are not linked lists. I don't believe that they are implemented as linked lists, and I know that they certainly do not offer a linked list API. You could try rotating the dequeue, popping it, then rotating it back. That might be faster, if rotation is fast. But if you are only deleting one or two items, is that deletion a bottle-neck in your code? > The same can be said for inserting items in the middle. If you want to insert and delete items in the middle, you are probably better off using a list. Dequeues are explicitly optimised for insertion and deletion at the ends, not the middle. It's a tradeoff. > What do you think about adding this to `deque`? Not much. If you have a clever implementation in mind that will make deletion more efficient, that's an implementation detail that will depend on (1) whether you have someone willing and able to do the work and (2) whether or not that implementation will rule out other possible future improvements. > The API will be tricky, > admittedly, because you'll have to save some kind of reference to a cell in > the deque. I think you mean the implementation will be tricky. The API will surely be trivial: either `del mydeque[i]`, as now, or `mydequeue.delete(i)`. If you have some other API in mind, please describe it. -- Steven ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/24RPFEJ6V6Y2ACZYKJRWJUV6TJUWKLTO/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
A deque is a data structure that exists outside of Python and the only guarantee is that adding an element at the top or the front is O(1). Giving more guarantee would force trade-offs and impose them to other implementations. If you want fast deletion, you should use another data structure. Also, removing an element from a doubly-linked list is not a O(1) operation, it's O(n). It's O(1) once you have a pointer to the element but you have to iterate over the list to get it and that would take O(n) operations, so making deque a doubly-linked list would not be faster anyway. I think the data structure that you are looking for would be a skipped-list, or alternatively (but the implementation is more involved) a red-black tree. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/JXI3KKZZBD4ORTBKMZVMC7XNUNIK7DYB/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
Hello, On Wed, 29 Apr 2020 13:58:15 +0300 Ram Rachum wrote: > On Wed, Apr 29, 2020 at 1:54 PM Paul Sokolovsky > wrote: > > > If you want a different data structure, [...] implement such a > > data structure > > > > And if I wanted an answer like "it's the way that it is because it's > the way that it is" I wouldn't be posting on python-ideas. > > Is there a strategic decision to limit deque to certain operations of > doubly-linked lists and not others? Deque is not doubly-linked list, they are completely different data structures. Even if a particular Python implementation uses doubly-linked list as an internal implementation strategy. There're other Python implementations which realize deque in other ways, which guarantee performance only for operations defined for deque and not for any other data structure. (E.g., an obvious implementation is an array with head/tail pointers). > That would make sense. Is that > decision written somewhere with the rationale behind it? That would > be interesting to read. -- Best regards, Paul mailto:pmis...@gmail.com ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/ZBZ7TPNRCIQKBDDJ4AJQ7PPBTQ5FT4G2/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
> > I was playing around with deque today, and there were a couple of > operations I wanted to do, that can't really be done efficiently with deque > because of its implementation. > > ... > > What do you think about adding [O(1) insert and remove] this to `deque`? > _collectionsmodule.c has this note, so it sounds like this is intended to be a possibility if there is enough interest: /* insert(), remove(), and delitem() are implemented in terms of rotate() > for simplicity and reasonable performance near the end points. If for some > reason these methods become popular, it is not hard to re-implement this > using direct data movement (similar to the code used in list slice > assignments) and achieve a performance boost (by moving each pointer only > once instead of twice). */ https://github.com/python/cpython/blob/d16a1520c2b22c3cbde7547937ba283db3e88ff5/Modules/_collectionsmodule.c#L952-L958 --- Ricky. "I've never met a Kentucky man who wasn't either thinking about going home or actually going home." - Happy Chandler ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/M645KVEY6RUQG6SXQ3KTMY6GUPWVHYQN/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Wed, Apr 29, 2020 at 9:15 PM Chris Angelico wrote: > I'm not seeing any evidence that this is a doubly-linked list. It > might happen to be implemented using one in current versions of > CPython, but that's not mandated anywhere. (And it's not a pure DLL - it's a DLL of blocks of 64 elements apiece. I'm not sure if that's significant or not.) ChrisA ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/UYH5DJI32JSSYWAQSKGZD62NFSMSIXDX/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Wed, Apr 29, 2020 at 9:01 PM Ram Rachum wrote: > Is there a strategic decision to limit deque to certain operations of > doubly-linked lists and not others? That would make sense. Is that decision > written somewhere with the rationale behind it? That would be interesting to > read. > """Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.""" I'm not seeing any evidence that this is a doubly-linked list. It might happen to be implemented using one in current versions of CPython, but that's not mandated anywhere. Is there a particular reason to mandate this for all Pythons for all time? As Paul says, you can always implement your own doubly linked list. ChrisA ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/W2KYK2OQKXKKV6Q4YIADBAXHJRY4EIYU/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
On Wed, Apr 29, 2020 at 1:54 PM Paul Sokolovsky wrote: > If you want a different data structure, [...] implement such a > data structure > And if I wanted an answer like "it's the way that it is because it's the way that it is" I wouldn't be posting on python-ideas. Is there a strategic decision to limit deque to certain operations of doubly-linked lists and not others? That would make sense. Is that decision written somewhere with the rationale behind it? That would be interesting to read. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/X2LDG4JMVFACX3KJBX5BLFVFNTIQ3TUT/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: deque: Allow efficient operations
Hello, On Wed, 29 Apr 2020 13:42:05 +0300 Ram Rachum wrote: > I was playing around with deque today, and there were a couple of > operations I wanted to do, that can't really be done efficiently with > deque because of its implementation. > > I was iterating through items of a deque, and in some cases I wanted > to delete an item that I've found. As far as I understand, this is an > operation that should be O(1) in a linked list, but Python only > provides an O(N) way to do that, which is `del d[i]`. > > The same can be said for inserting items in the middle. > > What do you think about adding this to `deque`? The API will be > tricky, admittedly, because you'll have to save some kind of > reference to a cell in the deque. Deque is a data structure which allows efficient insertion/deletion from 2 ends of the structure, period. If you want a different data structure, like linked list, or doubly-linked list, with different set of operations, implement such a data structure (it's trivial, and being done by other people all the time). > Thanks, > Ram. -- Best regards, Paul mailto:pmis...@gmail.com ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/MPWX45VK5SAG4JMGQ5F73MRLDWDMKNJC/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] deque: Allow efficient operations
I was playing around with deque today, and there were a couple of operations I wanted to do, that can't really be done efficiently with deque because of its implementation. I was iterating through items of a deque, and in some cases I wanted to delete an item that I've found. As far as I understand, this is an operation that should be O(1) in a linked list, but Python only provides an O(N) way to do that, which is `del d[i]`. The same can be said for inserting items in the middle. What do you think about adding this to `deque`? The API will be tricky, admittedly, because you'll have to save some kind of reference to a cell in the deque. Thanks, Ram. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/C4BASDFJI5UGAAV3AR4VELNFD2XQE4YV/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
On 28/04/2020 23:58, Andrew Barnert via Python-ideas wrote: Really, we either need descriptors that can somehow work for globals and class attributes (which is probably not solveable), or some brand new language semantics that aren’t built on what’s already there. The latter sounds like probably way more work than this feature deserves, but maybe the experience of Swift argues otherwise. Or you can do it up front, once you have the information to do it with. There aren't that many occasions when lazy evaluation actually wins you anything much; basically when you have moderately expensive information that you may not need at all but will use a lot if you do need it. -- Rhodri James *-* Kynesim Ltd ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/3ATLHCE557B4UA2OUXBAZZSZ5SCJFCY5/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
What you want is to acquire a lock if the cache is empty, check if another thread has filled the cache while you where waiting on the lock, call the function, fill the cache and return. I don’t see how you could implement that with two independent decorators without locking all accesses (before `once`) or having the chance that it’s called more than once (after `once`). Tom > On 29 Apr 2020, at 08:15, Andrew Barnert via Python-ideas > wrote: > > On Apr 28, 2020, at 16:25, Steven D'Aprano wrote: >> >> On Tue, Apr 28, 2020 at 11:45:49AM -0700, Raymond Hettinger wrote: >> >>> It seems like you would get just about everything you want with one line: >>> >>>once = lru_cache(maxsize=None) >> >> But is it thread-safe? > > You can add thread safety the same way as any other function: > >@synchronized >@once >def spam(): >return 42 in a slow and non-thread-safe and non-idempotent way and > also launch the missiles the second time we’re called > > Or wrap a with lock: around the code that calls it, or whatever. > > Not all uses of once require thread safety. For the really obvious example, > imagine you’re sharing a singleton between coroutines instead of threads. And > if people are really concerned with the overhead of lru_cache(maxsize=None), > the overhead of locking every time you access the value is probably even less > acceptable when unnecessary. > > So, I think it makes sense to leave it up to the user (but to explain the > issue in the docs). Or maybe we could add a threading.once (and > asyncio.once?) as well as functools.once? > > > ___ > Python-ideas mailing list -- python-ideas@python.org > To unsubscribe send an email to python-ideas-le...@python.org > https://mail.python.org/mailman3/lists/python-ideas.python.org/ > Message archived at > https://mail.python.org/archives/list/python-ideas@python.org/message/RSJLUF4R6TM3HSILZYWGB366WUHQT755/ > Code of Conduct: http://python.org/psf/codeofconduct/ ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/LZPL7SIIEDUZW7P6CTRYJCXZVQOJJL24/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Adding a "once" function to functools
On Apr 28, 2020, at 16:25, Steven D'Aprano wrote: > > On Tue, Apr 28, 2020 at 11:45:49AM -0700, Raymond Hettinger wrote: > >> It seems like you would get just about everything you want with one line: >> >> once = lru_cache(maxsize=None) > > But is it thread-safe? You can add thread safety the same way as any other function: @synchronized @once def spam(): return 42 in a slow and non-thread-safe and non-idempotent way and also launch the missiles the second time we’re called Or wrap a with lock: around the code that calls it, or whatever. Not all uses of once require thread safety. For the really obvious example, imagine you’re sharing a singleton between coroutines instead of threads. And if people are really concerned with the overhead of lru_cache(maxsize=None), the overhead of locking every time you access the value is probably even less acceptable when unnecessary. So, I think it makes sense to leave it up to the user (but to explain the issue in the docs). Or maybe we could add a threading.once (and asyncio.once?) as well as functools.once? ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/RSJLUF4R6TM3HSILZYWGB366WUHQT755/ Code of Conduct: http://python.org/psf/codeofconduct/
