Mailman 3 December 2015 - Python-ideas

@classproperty, @abc.abstractclasspropery, etc.
by K. Richard Pixley Dec. 16, 2020

Dec. 16, 2020

There's a whole matrix of these and I'm wondering why the matrix is currently sparse rather than implementing them all. Or rather, why we can't stack them as: class foo(object): @classmethod @property def bar(cls, ...): ... Essentially the permutation are, I think: {'unadorned'|abc.abstract}{'normal'|static|class}{method|property|non-callable attribute}. concreteness implicit first arg type name comments {unadorned} {unadorned} method def foo(): exists … [View More]now {unadorned} {unadorned} property @property exists now {unadorned} {unadorned} non-callable attribute x = 2 exists now {unadorned} static method @staticmethod exists now {unadorned} static property @staticproperty proposing {unadorned} static non-callable attribute {degenerate case - variables don't have arguments} unnecessary {unadorned} class method @classmethod exists now {unadorned} class property @classproperty or @classmethod;@property proposing {unadorned} class non-callable attribute {degenerate case - variables don't have arguments} unnecessary abc.abstract {unadorned} method @abc.abstractmethod exists now abc.abstract {unadorned} property @abc.abstractproperty exists now abc.abstract {unadorned} non-callable attribute @abc.abstractattribute or @abc.abstract;@attribute proposing abc.abstract static method @abc.abstractstaticmethod exists now abc.abstract static property @abc.staticproperty proposing abc.abstract static non-callable attribute {degenerate case - variables don't have arguments} unnecessary abc.abstract class method @abc.abstractclassmethod exists now abc.abstract class property @abc.abstractclassproperty proposing abc.abstract class non-callable attribute {degenerate case - variables don't have arguments} unnecessary I think the meanings of the new ones are pretty straightforward, but in case they are not... @staticproperty - like @property only without an implicit first argument. Allows the property to be called directly from the class without requiring a throw-away instance. @classproperty - like @property, only the implicit first argument to the method is the class. Allows the property to be called directly from the class without requiring a throw-away instance. @abc.abstractattribute - a simple, non-callable variable that must be overridden in subclasses @abc.abstractstaticproperty - like @abc.abstractproperty only for @staticproperty @abc.abstractclassproperty - like @abc.abstractproperty only for @classproperty --rich [View Less]

10 15

Specify number of items to allocate for array.array() constructor
by Sven Rahmann Feb. 22, 2020

Feb. 22, 2020

At the moment, the array module of the standard library allows to create arrays of different numeric types and to initialize them from an iterable (eg, another array). What's missing is the possiblity to specify the final size of the array (number of items), especially for large arrays. I'm thinking of suffix arrays (a text indexing data structure) for large texts, eg the human genome and its reverse complement (about 6 billion characters from the alphabet ACGT). The suffix array is a long int … [View More]

14 20

Implicit string literal concatenation considered harmful?
by Guido van Rossum March 14, 2018

March 14, 2018

I just spent a few minutes staring at a bug caused by a missing comma -- I got a mysterious argument count error because instead of foo('a', 'b') I had written foo('a' 'b'). This is a fairly common mistake, and IIRC at Google we even had a lint rule against this (there was also a Python dialect used for some specific purpose where this was explicitly forbidden). Now, with modern compiler technology, we can (and in fact do) evaluate compile-time string literal concatenation with the '+' … [View More]

51 165

proposal: "python -m foo" should bind sys.modules['foo']
by Cameron Simpson Jan. 18, 2017

Jan. 18, 2017

Hello all, This is a writeup of a proposal I floated here: https://mail.python.org/pipermail/python-list/2015-August/694905.html last Sunday. If the response is positive I wish to write a PEP. Briefly, it is a natural expectation in users that the command: python -m module_name ... used to invoke modules in "main program" mode on the command line imported the module as "module_name". It does not, it imports it as "__main__". An import within the program of "module_name" makes a new … [View More]instance of the module, which causes cognitive dissonance and has the side effect that now the program has two instances of the module. What I propose is that the above command line _should_ bind sys.modules['module_name'] as well as binding '__main__' as it does currently. I'm proposing that the python -m option have this effect (python pseudocode): % python -m module.name ... runs: # pseudocode, with values hardwired for clarity import sys M = new_empty_module(name='__main__', qualname='module.name') sys.modules['__main__'] = M sys.modules['module.name'] = M # load the module code from wherever (not necessarily a file - CPython # already must do this phase) M.execfile('/path/to/module/name.py') Specificly, this would have the following two changes to current practice: 1) the module is imported _once_, and bound to both its canonical name and also to __main__. 2) imported modules acquire a new attribute __qualname__ (analogous to the recent __qualname__ on functions). This is always the conanoical name of the module as resolved by the importer. For most modules __name__ will be the same as __qualname__, but for the "main" module __name__ will be '__main__'. This change has the following advantages: The current standard boilerplate: if __name__ == '__main__': ... invoke "main program" here ... continues to work unchanged. Importantly, if the program then issues "import module_name", it is already there and the existing instance is found and used. The thread referenced above outlines my most recent encounter with this and the trouble it caused me. Followup messages include some support for this proposed change, and some criticism. The critiquing article included some workarounds for this multiple module situation, but they were (1) somewhat dependent on modules coming from a file pathname and (2) cumbersome and require every end user to adopt these changes if affected by the situation. I'd like to avoid that. Cheers, Cameron Simpson <cs(a)zip.com.au> The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore all progress depends on the unreasonable man. - George Bernard Shaw [View Less]

5 13

solving multi-core Python
by Eric Snow June 3, 2016

June 3, 2016

tl;dr Let's exploit multiple cores by fixing up subinterpreters, exposing them in Python, and adding a mechanism to safely share objects between them. This proposal is meant to be a shot over the bow, so to speak. I plan on putting together a more complete PEP some time in the future, with content that is more refined along with references to the appropriate online resources. Feedback appreciated! Offers to help even more so! :) -eric -------- Python's multi-core story is murky at best. … [View More]Not only can we be more clear on the matter, we can improve Python's support. The result of any effort must make multi-core (i.e. parallelism) support in Python obvious, unmistakable, and undeniable (and keep it Pythonic). Currently we have several concurrency models represented via threading, multiprocessing, asyncio, concurrent.futures (plus others in the cheeseshop). However, in CPython the GIL means that we don't have parallelism, except through multiprocessing which requires trade-offs. (See Dave Beazley's talk at PyCon US 2015.) This is a situation I'd like us to solve once and for all for a couple of reasons. Firstly, it is a technical roadblock for some Python developers, though I don't see that as a huge factor. Regardless, secondly, it is especially a turnoff to folks looking into Python and ultimately a PR issue. The solution boils down to natively supporting multiple cores in Python code. This is not a new topic. For a long time many have clamored for death to the GIL. Several attempts have been made over the years and failed to do it without sacrificing single-threaded performance. Furthermore, removing the GIL is perhaps an obvious solution but not the only one. Others include Trent Nelson's PyParallels, STM, and other Python implementations.. Proposal ======= In some personal correspondence Nick Coghlan, he summarized my preferred approach as "the data storage separation of multiprocessing, with the low message passing overhead of threading". For Python 3.6: * expose subinterpreters to Python in a new stdlib module: "subinterpreters" * add a new SubinterpreterExecutor to concurrent.futures * add a queue.Queue-like type that will be used to explicitly share objects between subinterpreters This is less simple than it might sound, but presents what I consider the best option for getting a meaningful improvement into Python 3.6. Also, I'm not convinced that the word "subinterpreter" properly conveys the intent, for which subinterpreters is only part of the picture. So I'm open to a better name. Influences ======== Note that I'm drawing quite a bit of inspiration from elsewhere. The idea of using subinterpreters to get this (more) efficient isolated execution is not my own (I heard it from Nick). I have also spent quite a bit of time and effort researching for this proposal. As part of that, a number of people have provided invaluable insight and encouragement as I've prepared, including Guido, Nick, Brett Cannon, Barry Warsaw, and Larry Hastings. Additionally, Hoare's "Communicating Sequential Processes" (CSP) has been a big influence on this proposal. FYI, CSP is also the inspiration for Go's concurrency model (e.g. goroutines, channels, select). Dr. Sarah Mount, who has expertise in this area, has been kind enough to agree to collaborate and even co-author the PEP that I hope comes out of this proposal. My interest in this improvement has been building for several years. Recent events, including this year's language summit, have driven me to push for something concrete in Python 3.6. The subinterpreter Module ===================== The subinterpreters module would look something like this (a la threading/multiprocessing): settrace() setprofile() stack_size() active_count() enumerate() get_ident() current_subinterpreter() Subinterpreter(...) id is_alive() running() -> Task or None run(...) -> Task # wrapper around PyRun_*, auto-calls Task.start() destroy() Task(...) # analogous to a CSP process id exception() # other stuff? # for compatibility with threading.Thread: name ident is_alive() start() run() join() Channel(...) # shared by passing as an arg to the subinterpreter-running func # this API is a bit uncooked still... pop() push() poison() # maybe select() # maybe Note that Channel objects will necessarily be shared in common between subinterpreters (where bound). This sharing will happen when the one or more of the parameters to the function passed to Task() is a Channel. Thus the channel would be open to the (sub)interpreter calling Task() (or Subinterpreter.run()) and to the new subinterpreter. Also, other channels could be fed into such a shared channel, whereby those channels would then likewise be shared between the interpreters. I don't know yet if this module should include *all* the essential pieces to implement a complete CSP library. Given the inspiration that CSP is providing, it may make sense to support it fully. It would be interesting then if the implementation here allowed the (complete?) formalisms provided by CSP (thus, e.g. rigorous proofs of concurrent system models). I expect there will also be a _subinterpreters module with low-level implementation-specific details. Related Ideas and Details Under Consideration ==================================== Some of these are details that need to be sorted out. Some are secondary ideas that may be appropriate to address in this proposal or may need to be tabled. I have some others but these should be sufficient to demonstrate the range of points to consider. * further coalesce the (concurrency/parallelism) abstractions between threading, multiprocessing, asyncio, and this proposal * only allow one running Task at a time per subinterpreter * disallow threading within subinterpreters (with legacy support in C) + ignore/remove the GIL within subinterpreters (since they would be single-threaded) * use the GIL only in the main interpreter and for interaction between subinterpreters (and a "Local Interpreter Lock" for within a subinterpreter) * disallow forking within subinterpreters * only allow passing plain functions to Task() and Subinterpreter.run() (exclude closures, other callables) * object ownership model + read-only in all but 1 subinterpreter + RW in all subinterpreters + only allow 1 subinterpreter to have any refcounts to an object (except for channels) * only allow immutable objects to be shared between subinterpreters * for better immutability, move object ref counts into a separate table * freeze (new machinery or memcopy or something) objects to make them (at least temporarily) immutable * expose a more complete CSP implementation in the stdlib (or make the subinterpreters module more compliant) * treat the main interpreter differently than subinterpreters (or treat it exactly the same) * add subinterpreter support to asyncio (the interplay between them could be interesting) Key Dependencies ================ There are a few related tasks/projects that will likely need to be resolved before subinterpreters in CPython can be used in the proposed manner. The proposal could implemented either way, but it will help the multi-core effort if these are addressed first. * fixes to subinterpreter support (there are a couple individuals who should be able to provide the necessary insight) * PEP 432 (will simplify several key implementation details) * improvements to isolation between subinterpreters (file descriptors, env vars, others) Beyond those, the scale and technical scope of this project means that I am unlikely to be able to do all the work myself to land this in Python 3.6 (though I'd still give it my best shot). That will require the involvement of various experts. I expect that the project is divisible into multiple mostly independent pieces, so that will help. Python Implementations =================== They can correct me if I'm wrong, but from what I understand both Jython and IronPython already have subinterpreter support. I'll be soliciting feedback from the different Python implementors about subinterpreter support. C Extension Modules ================= Subinterpreters already isolate extension modules (and built-in modules, including sys). PEP 384 provides some help too. However, global state in C can easily leak data between subinterpreters, breaking the desired data isolation. This is something that will need to be addressed as part of the effort. [View Less]

26 130

OrderedCounter and OrderedDefaultDict
by Ian Foote Feb. 12, 2016

Feb. 12, 2016

I recently wanted to use an OrderedCounter and an OrderedDefaultDict. After a bit of googling I discovered that OrderedCounter is quite easy to implement: from collections import Counter, OrderedDict class OrderedCounter(Counter, OrderedDict): 'Counter that remembers the order elements are first seen' def __repr__(self): return '%s(%r)' % (self.__class__.__name__, OrderedDict(self)) def __reduce__(self): return self.… [View More]

14 23

Fwd: Why do equality tests between OrderedDict keys/values views behave not as expected?
by Alexandre Figura Jan. 21, 2016

Jan. 21, 2016

Hi, I recently compared OrderedDict instances while writing unit tests, and discovered an interesting behavior. If I create two ordered dictionaries with the same keys/values in the same order, I observe that their values are not equal when I compare them. I recently asked a question about this on Stackoverflow: http://stackoverflow.com/questions/34312674/why-values-of-an-ordereddict-ar… Moreover, another user observed that keys of ordered dictionaries are compared in an order insensitive … [View More]

12 40

find-like functionality in pathlib
by Ram Rachum Jan. 11, 2016

Jan. 11, 2016

What do you think about implementing functionality similar to the `find` utility in Linux in the Pathlib module? I wanted this today, I had a script to write to archive a bunch of files from a folder, and I decided to try writing it in Python rather than in Bash. But I needed something stronger than `Path.glob` in order to select the files. I wanted a regular expression. (In this particular case, I wanted to get a list of all the files excluding the `.git` folder and all files inside of it. Thanks, Ram.

15 36

Where to put non-collection ABCs (was: Deprecating the old-style sequence protocol)
by Brett Cannon Jan. 1, 2016

Jan. 1, 2016

Speaking of using ABCs more, where should we put ABCs which have nothing to do with collections? As of right now all ABCs seem to get shoved into collections.abc, but e.g. Awaitable and Coroutine are not types of collections. I personally want to add a context manager ABC with a default __exit__. I opened http://bugs.python.org/issue25637 to discuss this, but I figured a wider discussion wouldn't hurt. Some suggest just putting the ABCs into the abc module. We could create an interfaces module … [View More](top-level or a submodule of ABC). The other option is to put the ABCs in subject-specific modules, so my context manager one would go into contextlib (either top-level or an abc submodule); don't know where the coroutine ones would go since it might be overloading asyncio if we out them there. Anyway, the key point is collections.abc is starting to get non-collections stuff and if we are going to start pushing ABCs more we should decide how we want to organize them in general in the stdlib and instead of dumping them into collections.abc. On Sun, Dec 27, 2015, 09:35 Guido van Rossum <guido(a)python.org> wrote: > I think there's a lot of interesting stuff in this thread. Personally I > don't think we should strive to distinguish between mappings and sequences > structurally. We should instead continue to encourage inheriting from (or > registering with) the corresponding ABCs. The goal is to ensure that > there's one best-practice way to distinguish mappings from sequences, and > it's by using isinstance(x, Sequence) or isinstance(x, Mapping). > > If we want some way to turn something that just defines __getitem__ and > __len__ into a proper sequence, it should just be made to inherit from > Sequence, which supplies the default __iter__ and __reversed__. > (Registration is *not* good enough here.) If we really want a way to turn > something that just supports __getitem__ into an Iterable maybe we can > provide an additional ABC for that purpose; let's call it a HalfSequence > until we've come up with a better name. (We can't use Iterable for this > because Iterable should not reference __getitem__.) > > I also think it's fine to introduce Reversible as another ABC and > carefully fit it into the existing hierarchy. It should be a one-trick pony > and be another base class for Sequence; it should not have a default > implementation. (But this has been beaten to death in other threads -- it's > time to just file an issue with a patch.) > > > -- > --Guido van Rossum (python.org/~guido) > _______________________________________________ > Python-ideas mailing list > Python-ideas(a)python.org > https://mail.python.org/mailman/listinfo/python-ideas > Code of Conduct: http://python.org/psf/codeofconduct/ [View Less]

6 9

Deprecating the old-style sequence protocol
by Andrew Barnert Dec. 31, 2015

Dec. 31, 2015

This idea seems to come up regularly, so maybe it would be good to actually discuss it out (and, if necessary, explicitly reject it). Most recently, at https://github.com/ambv/typehinting/issues/170, Guido said: > FWIW, maybe we should try to deprecate supporting iteration using the old-style protocol? It's really a very old backwards compatibility measure (from when iterators were first introduced). Then eventually we could do the same for reversing using the old-style protocol. The best … [View More]discussion I found was from a 2013 thread (http://article.gmane.org/gmane.comp.python.ideas/23369/), which I'll quote below. Anyway, the main argument for eliminating the old-style sequence protocol is that, unlike most other protocols in Python, it can't actually be checked for (without iterating the values). Despite a bunch of explicit workaround code (which registers builtin sequence types with `Iterable`, checks for C-API mappings in `reversed`, etc.), you still get false negatives when type-checking types like Steven's at runtime or type-checking time, and you still get false positives from `iter` and `reversed` themselves (`reversed(MyCustomMapping({1:2, 3:4}))` or `iter(typing.Iterable)` won't give you a `TypeError`, they'll give you a useless iterator--which may throw some other exception later when trying to iterate it, but even that isn't reliable). I believe we could solve all of these problems by making `iter` and `reversed` raise a `TypeError`, without falling back to the old-style protocol, if the dunder method is `None` (like `hash`), change the ABC and static typer to use the same rules as `iter` and `reversed`, and add `__reversed__ = None` to `collections.abc.Mapping`. (See http://bugs.python.org/issue25864 and http://bugs.python.org/issue25958 for details.) Alternatively, if there were some way for a Python class to declare whether it's trying to be a mapping or a sequence or neither, as C API types do, I suppose that could be a solution. Or maybe the problems don't actually need to be solved. But obviously, deprecating the old-style sequence protocol would make the problems go away. --- Here's the argument against doing so: On 2013-09-22 23:46:37 GMT, Steven D'Aprano wrote: > On Sun, Sep 22, 2013 at 12:37:52PM -0400, Terry Reedy wrote: >> On 9/22/2013 10:22 AM, Nick Coghlan wrote: >>> >>> The __getitem__ fallback is a backwards >>> compatibility hack, not part of the formal definition of an iterable. >>> >> When I suggested that, by suggesting that the fallback *perhaps* could >> be called 'semi-deprecated, but kept for back compatibility' in the >> glossary entry, Raymond screamed at me and accused me of trying to >> change the language. He considers it an intended language feature that >> one can write a sequence class and not bother with __iter__. I guess we >> do not all agree ;-). >> > Raymond did not "scream", he wrote *one* word in uppercase for emphasis. > I quote: > >> It is NOT deprecated. People use and rely on this behavior. It is >> a guaranteed behavior. Please don't use the glossary as a place to >> introduce changes to the language. > > I agree, and I disagree with Nick's characterization of the sequence > protocol as a "backwards-compatibility hack". It is an elegant protocol > for implementing iteration of sequences, an old and venerable one that > predates iterators, and just as much of Python's defined iterable > behaviour as the business with calling next with no argument until it > raises StopIteration. If it were considered *merely* for backward > compatibility with Python 1.5 code, there was plenty of opportunity to > drop it when Python 3 came out. > > The sequence protocol allows one to write a lazily generated, > potentially infinite sequence that still allows random access to items. > Here's a toy example: > > py> class Squares: > ... def __getitem__(self, index): > ... return index**2 > ... > py> for sq in Squares(): > ... if sq > 9: break > ... print(sq) > 0 > 1 > 4 > 9 > > Because it's infinite, there's no value that __len__ can return, and no > need for a __len__. Because it supports random access to items, writing > this as an iterator with __next__ is inappropriate. Writing *both* is > unnecessary, and complicates the class for no benefit. As written, > Squares is naturally thread-safe -- two threads can iterate over the > same Squares object without interfering. Also, elsewhere in the thread, someone else pointed out another example (which I'm rewriting to make it fit better with Steven's): class TenSquares: def __len__(self): return 10 def __getitem__(self, index): if 0 <= index < 10: return index**2 raise IndexError You can iterate this, convert it to a `list`, call `reversed` on it, etc., all in only 6 lines of code. --- Guido's response was: > Hm. The example given there is a toy though. Something with a __getitem__ > that maps its argument to its square might as well be a mapping. I really > think it's time to slowly let go of this (no need to rush into removing > support, but we could still frown upon its use). And it's worth noting that making these examples work without the old-style sequence protocol isn't exactly hard: add a 1-line `__iter__` method, or a 1-line replacement for the old-style `iter`, or, for the second example, just inherit the `Sequence` ABC. Also, the thread-safety issue seems bogus. Any reasonable collection is thread-safe as an iterable. Presumably the counter-argument is that, as trivial as those changes are, they're still not nearly as trivial as the original code, and in a quick&dirty script or interactive session, it may be more than you want to do (especially since it involves importing a module you didn't otherwise need). But I'll leave it to the people who are strongly against the deprecation to explain it, rather than putting words in their mouths. --- Finally, as far as I can tell, the documentation of the old-style sequence protocol is in the library docs for `iter` and `reversed`, and the data model docs for `__reversed__` (but not `__iter__`), which say, respectively: > ... object must be a collection object which supports the iteration protocol (the __iter__() method), or it must support the sequence protocol (the __getitem__() method with integer arguments starting at 0). > ... seq must be an object which has a __reversed__() method or supports the sequence protocol (the __len__() method and the __getitem__() method with integer arguments starting at 0). > If the __reversed__() method is not provided, the reversed() built-in will fall back to using the sequence protocol (__len__() and __getitem__()). Objects that support the sequence protocol should only provide __reversed__() if they can provide an implementation that is more efficient than the one provided by reversed(). [View Less]

6 10

Have max and min functions ignore None
by Franklin? Lee Dec. 31, 2015

Dec. 31, 2015

What do people think about having `max` and `min` ignore `None`? Examples: max(1, None) == 1 min(1, None) == 1 max([1, None]) == 1 max(None, None) == max() or max(None, None) == max([]) (The last one currently throws two different errors.) This change would allow one to use `None` as a default value. For example, def my_max(lst): best = None for x in lst: best = max(best, x) return best Currently, you would initialize `best` to the … [View More]

8 11

Re: [Python-ideas] Using functools.lru_cache only on some arguments of a function
by Franklin? Lee Dec. 31, 2015

Dec. 31, 2015

(Replying to an email I didn't get in my inbox. I hope this goes through correctly.) On Friday, December 4, 2015 at 4:44:47 PM UTC-5, Bill Winslow wrote: > This is a question I posed to reddit, with no real resolution: https://www.reddit.com/r/learnpython/comments/3v75g4/using_functoolslru_cac… > The summary for people here is the following: > Here's a pattern I'm using for my code: > def deterministic_recursive_ calculation(input, partial_state=None): > condition = … [View More]do_some_calculations(input) > if condition: > return deterministic_recursive_calculation(reduced_input, some_state) > Basically, in calculating the results of the subproblem, the subproblem can be calculated quicker by including/sharing some partial results from the superproblem. (Calling the subproblem without the partial state still gives the same result, but takes substantially longer.) Solutions: 1. Rewrite your recursive function so that the partial state is a nonlocal variable (in the closure), and memoize the recursive part. 2. Attach the state to the function, rather than passing it as a parameter. (Also suggested in this comment: https://www.reddit.com/r/learnpython/comments/3v75g4/using_functoolslru_cac…) 3. Wrap the state in a class for which __eq__ is defined to say that all instances of it are the same, and __hash__ always returns a constant (say, the id of the class). I think #1 is the best: The state is a property of the current recursive execution. You make a function which solves the problem, and the recursive function is an inner function of the solver. The state will be lost when you finish computing the answer. If you want to keep the partial state even after the recursion finished, then #2 is the right answer: the state is a property of the solver. I feel that #3 is icky and heavy-handed. The function won't be semantically responsible for the state. Hacking/extending lru_cache is saying the wrong thing about what the partial state is. Cached information (which is what your state is) isn't really an argument to the function as a mathematical input-output box. Also, if you're calling this function multiple times, you as the caller shouldn't be expected to keep track of the cache, so you shouldn't be expected to store it (in global scope). But if it's reusable, it should be stored, so the function should be responsible for storing it. If you want to keep the lru_cache, too, then you can store the recursive function as an attribute. It will even keep itself and your partial state in its closure. Sample code so you can confirm that the state is stored between calls. Just call solve(50) twice in a row, and compare the times. # WARNING: I don't recommend x > 100. # I've killed two interpreters while messing with this. def solve(x): try: rec = solve.rec # To trigger the exception the first time. except: @lru_cache(None) def rec(n, m): return sum( rec(i, j) for i in reversed(range(n)) for j in reversed(range(m))) solve.rec = rec return rec(x, x) [View Less]

2 4

Have max and min functions ignore None
by Gerald Britton Dec. 30, 2015

Dec. 30, 2015

On *Tue Dec 29 06:22:58 EST 2015, Stephen D'Aprano wrote:* > So that's three perfectly reasonable behaviours: max(x, None) is an error > and should raise; > max(x, None) ignores None and returns x; > max(x, None) is unknown or missing and returns None > (or some other sentinel representing NA/Missing/Unknown). For comparison's sake, SQL ignores NULL when doing MAX: e.g. select max(val) from (values (1),(null)) v(val) returns 1 In Python, None is sorta-kinda a bit like … [View More]

3 2

Fwd: Re: Unambiguous repr for recursive objects
by Guido van Rossum Dec. 29, 2015

Dec. 29, 2015

--Guido (mobile) ---------- Forwarded message ---------- From: <python-ideas-owner(a)python.org> Date: Dec 26, 2015 9:33 AM Subject: Re: [Python-ideas] Unambiguous repr for recursive objects To: <gvanrossum(a)gmail.com> Cc: Your message has been rejected, probably because you are not subscribed to the mailing list and the list's policy is to prohibit non-members from posting to it. If you think that your messages are being rejected in error, contact the mailing list owner at … [View More]

9 16

Missing Core Feature: + - * / | & do not call __getattr__
by Stephan Sahm Dec. 28, 2015

Dec. 28, 2015

Dear all, I just stumbled upon a very weird behaviour of python 2 and python 3. At least I was not able to find a solution. *The point is to dynamically define __add__, __or__ and so on via __getattr__* (for example by deriving them from __iadd__ or similar in a generic way). However this very intuitive idea is currently NOT POSSIBLE because * - * / & | and so on just bypass this standard procedure. I found two stackoverflow contributions stating this: http://stackoverflow.com/questions/… [View More]

9 19

Adding collections.abc.Ordered
by Amir Rachum Dec. 27, 2015

Dec. 27, 2015

I am suggesting the addition of a collections abstract base class called "Ordered". Its meaning is that a collection's iteration order is part of its API. The bulk of this mail describes a use case for this. The reason I believe that such abstract base class is required is that there is no way to test this behavior in a given class. An ordered collection has the exact same interface as an unordered collection (e.g, dict and OrderedDict), other than a _promise_ of the API that the order in which … [View More]this collection will be iterated has some sort of meaning (In OrderedDict, it is the order in which keys were added to it.) As examples, set, frozenset, dict and defaultdict should *not* be considered as ordered. list, OrderedDict, deque and tuple should be considered ordered. Before I dive into the use case I am presenting, I would like to point out that a similar discussion was already done on the subject (suggesting at first that OrderedDict would abstract-subclass from Sequence) at the following thread* - http://code.activestate.com/lists/python-ideas/29532/. That thread was abandoned largely from a lack of a clear use case, which I hope will be more clear in this suggestion. I am working on package called basicstruct ( https://pypi.python.org/pypi/basicstruct). The way it works is that you define an object that inherits from basicstruct.BasicStruct, define __slots__ , and automatically get behaviors such as a nice __init__, __str__, comparison functions, attribute access, dict-like access, pickleability, etc. It is similar to namedtuple, except that it is mutable. In the Python documentation, the following is said regarding __slots__: Any non-string iterable may be assigned to __slots__. Mappings may also be used; however, in the future, special meaning may be assigned to the values corresponding to each key. Here's how the current__init__ method of BasicStruct looks like: class BasicStruct(object): """Class for holding struct-like objects.""" __slots__ = () # should be extended by deriving classes def __init__(self, *args, **kwargs): arg_pairs = zip(self.__slots__, args) for key, value in chain(arg_pairs, six.iteritems(kwargs)): setattr(self, key, value) for key in self.__slots__: if not hasattr(self, key): setattr(self, key, None) Notice the following line: arg_pairs = zip(self.__slots__, args) It assumes that __slots__ defines attributes in a certain order. So as a use I would expect that the following code class MyStruct(BasicStruct): __slots__ = ('x', 'y') MyStruct(0, 1) ... will create a struct in which x is 0 and y is 1. However, if I define __slots__ as a set, or dict, the result is undefined. class MyStruct(BasicStruct): __slots__ = {'x', 'y'} # No order is defined here MyStruct(0, 1) # Which is which? So, In BasicStruct's __init__ method it is required to test whether __slots__ was defined with a collection that has a meaningful order. If it was _not_, using non-keyword arguments in __init__ should be forbidden, since the order of __slots__ is arbitrary. Here is how I wish the code would look like: class BasicStruct(object): """Class for holding struct-like objects.""" __slots__ = () # should be extended by deriving classes def __init__(self, *args, **kwargs): ordered = isinstance(self.__slots__, Ordered) if args and not ordered: raise ValueError("Can't pass non-keyword arguments to {}, since " "__slots__ was declared with an unordered " "iterable.".format(self.__class__.__name__)) arg_pairs = zip(self.__slots__, args) for key, value in chain(arg_pairs, six.iteritems(kwargs)): setattr(self, key, value) for key in self.__slots__: if not hasattr(self, key): setattr(self, key, None) Thanks, Amir Rachum * The author of the original thread is Ram Rachum. To avoid some confusion - yes, we are related - Ram is my big brother. It's just so happens that I was looking around for this issue and found that he did so in the past as well. [View Less]

14 48

Re: [Python-ideas] Adding collections.abc.Ordered
by Wes Turner Dec. 27, 2015

Dec. 27, 2015

On Dec 26, 2015 8:11 PM, "Wes Turner" <wes.turner(a)gmail.com> wrote: > > * collections.abc.Ordered > * collections.abc.Reversible > * collections.abc.Infinite [...] > > * collections.abc.Sorted ? > * collections.abc.Recursive ? > > Rationale: > > These are all attributes of collections that would allow us to reason about [complexity, types, runtime]? > > [While someone is at it, annotating functions and methods with complexity class URI fragments … [View More]accessible at runtime could also be useful for [dynamic programming].] > > * Ordered is justified by this thread > * Reversible is distinct from Ordered (because Infinite sequences) > * Infinite is the distinction between Ordered and Reversible > > * collections.abc.Sorted would be a useful property to keep track of (because then you don't have to do element-wise comparisons for each collection member) > > ... > > * collections.abc.Recursive could also be a useful property to mixin [again for dynamic programming] > > https://en.wikipedia.org/wiki/Dynamic_programming https://en.wikipedia.org/wiki/Goal_programming There are more properties of sequences listed here; IDK if this is out of scope for OT: https://en.wikipedia.org/wiki/Sequence#Formal_definition_and_basic_properti… Vague use case: algorithmic selection / unhalting-avoidance with combinatorial data/logic sequences. [e.g. find the fastest halting solution] Practically, Ordered is a property of various types [e.g. is this a poset or not]. There is currently no way to check for .ordered with hasattr. These properties are things we currently keep in mind (some of our 7±2 things) and haven't yet figured out how to annotate with and access at runtime. > > On Dec 26, 2015 7:34 PM, "Wes Turner" <wes.turner(a)gmail.com> wrote: >> >> * collections.abc.Ordered >> * collections.abc.Reversible >> * collections.abc.Infinite [...] >> >> * collections.abc.Sorted ? >> >> On Dec 26, 2015 7:24 PM, "Andrew Barnert via Python-ideas" < python-ideas(a)python.org> wrote: >>> >>> On Dec 26, 2015, at 16:09, Serhiy Storchaka <storchaka(a)gmail.com> wrote: >>> > >>> >> On 27.12.15 01:05, Guido van Rossum wrote: >>> >> There is a precedent for declaring that a method isn't implemented: >>> >> __hash__. The convention is to set it to None in the subclass that >>> >> explicitly doesn't want to implement it. The __subclasshook__ in >>> >> collections.Hashable checks for this. The pattern is also used for >>> >> __await__. >>> > >>> > Yes, this was the first thing that I tried, but it doesn't work, as shown in my example in issue25864. This is yet one thing that should be fixed in Reversible. >>> >>> As Guido pointed out in your typehinting #170, that isn't a bug with typing.Reversible. You can't use typing types in runtime type tests with issubclass. That isn't supposed to work, and the fact that it often kind of does work is actually a bug that he's fixing. So the fact that it doesn't work in this case is correct. >>> >>> That also means your attempted solution to this thread is wrong; typing.Reversible cannot be used as a substitute for collections.abc.Ordered. >>> >>> > May be we have to use this idiom more widely, and specially handle assigning special methods to None. The error message "'sometype' can't be reverted" looks better than "'NoneType' is not callable". >>> >>> I agree with this. A new collections.abc.Reversible (interposed between Iterable and Sequence) would be a potential substitute for Ordered, and would have this problem, which would be solvable by treating __reversed__ = None specially, just like __hash__ = None. And I'm pretty sure it would come up in practice (see issue 25864). And once we've got two or three special methods doing this instead of one, making it more general does sound like a good idea. So, if we need Reversible as a substitute for Ordered, then I think we want the general "is None" test. >>> >>> But I'm still not sure Reversible is a good substitute for Ordered (again, consider an infinitely long collection, or just a lazy proxy that doesn't compute values until needed and doesn't know its length in advance--they're clearly ordered, and just as clearly not reversible), and I'm not sure we actually need either Reversible or Ordered in the first place. >>> >>> _______________________________________________ >>> Python-ideas mailing list >>> Python-ideas(a)python.org >>> https://mail.python.org/mailman/listinfo/python-ideas >>> Code of Conduct: http://python.org/psf/codeofconduct/ [View Less]

1 0

Unambiguous repr for recursive objects
by Serhiy Storchaka Dec. 26, 2015

Dec. 26, 2015

Currently repr() for recursive object replaces its recurred representation wish a placeholder containing "...". For list this is "[...]": >>> a = [1, 2] >>> a.append(a) >>> a [1, 2, [...]] For dict this is "{...}": >>> d = {1: 2} >>> d[3] = d >>> d {1: 2, 3: {...}} For OrderedDict (Python implementation or 3.4-) this is just "...": >>> from collections import OrderedDict >… [View More]

3 3

Buffering iterators?
by Franklin? Lee Dec. 22, 2015

Dec. 22, 2015

(This would be a lot of work that I wouldn't know how to do, but is it worth thinking about? Maybe it's already been done at the level necessary. Also, this is a proposal for the sake of theoretical optimization, in case you don't like that, and it will require a lot of work in a lot of code everywhere. As I see it, even if it's possible and desirable to do this, it would take years of work and testing to make it beneficial.) The move from Python 2 (disclaimer: which I barely touched, so I … [View More]have little sentimental attachment) to Python 3 resulted in many functions returning iterators instead of lists. This saves a lot of unnecessary memory when iterating, say, over the indices of a large list, especially if we break in the middle. I'm wondering, though, about a step backwards: generating values before they're needed. The idea is based on file buffered reading and memory prefetching (https://en.wikipedia.org/wiki/Synchronous_dynamic_random-access_memory#DDR_…). In fact, I'm hoping to take advantage of such things. For example, in `sum(lst[i] * i for i in range(10000))`, `sum` will exhaust the iterator, so it can ask the generator to return buffers, and it will internally read the elements off the lists. It would be the responsibility of the iterator to decide whether to respect the request, and to determine the size of the buffer. It would be the responsibility of the consumer to request it, and consumers should only request it if they think they'll almost definitely consume a lot at a time. The idea is, especially for complex nested iterators, instead of running A B C A B C A B C..., where each is the code for generating a next thing from the previous, that the interpreter runs A A A A A..., B B B B B..., C C C..., which could mean a lot more memory locality in both instructions and objects. There's the possibility that a function has side-effects, so buffering would have different semantics than normal. There's also the possibility that getting the next element is complex enough that it wouldn't help to buffer. If the iterator can't tell, then it should just not buffer. Here's an obnoxious example of where you can't tell: def f(i): return i s = 0 for i in (f(x) for x in range(100)): s += f(i) def f(x): return x + s In fact, all Python function calls are probably unsafe, including with operators (which can be legally replaced during the iteration). Well, `map` and `filter` are possible exceptions in special cases, because the lookup for their function is bound at the call to `map`. It's usually safe if you're just using reversed, enumerate, builtin operators, dict views, etc. on an existing data structure, as long as your iteration doesn't modify entries, unlike so: for i, x in enumerate(reversed(lst)): lst[i+1] = x But I'm looking toward the future, where it might be possible for the interpreter to analyze loops and functions before making such decisions. Then again, if the interpreter is that smart, it can figure out where and when to buffer without adding to the API of iterators. Anyway, here's an idea, how it might be helpful, and how it might not be helpful. [View Less]

3 2

Re: [Python-ideas] Optimizing global names via dict references
by Franklin? Lee Dec. 20, 2015

Dec. 20, 2015

(Sent this from the wrong email and it got rejected. Sorry, Victor, for the double post.) On Dec 20, 2015 2:03 AM, "Franklin?" <redacted> wrote: > > Oops, that was supposed to private. No point now. > > Anyway, after I read Tim's remark, I realized that I overestimated the cost of dict lookups. It's not the complexity, but the constant factor in terms of branches and dereferences. It means that if I want to make an improvement, it would have to be very optimized C. They were … [View More]discussing tricks like having a cell consider itself as its own parent, just to avoid a branch, which is not the level at which I was thinking. > > I think that normal dict operations won't have to slow down, except resize/destruction. I don't use registry, so there is no O(n) notification. This is an important difference from Neil Toronto's original method. > > Reading PEP 266, and rethinking your own work, I'm now considering a separate idea for temporary registries. But I think it'd be reaching into JIT territory, and I'm not confident at all in my JIT knowledge. I can't say that this idea would be an improvement. I'm just putting this out there in the hope that it can make some sense and inspire someone to have a real idea. > > The idea is, when code is running, if a function is called (within a loop?), load its global names into an array and register them with the globals/builtins (which can be done with user dicts by temporarily swapping out their get/set/del). Then replace the function with one that does LOAD_CONSTANT (like in FAT Python) and replace its function calls with "compile the functions the same way before calling" bytecodes. > > This array is for the whole stack. As I imagine it, it will be used during an execution. So for the REPL, it can be a new array per eval, or just globally. > > The trick is, each name will be added to the array once, so the registry will slow down the normal dict operations but each dict change only needs (at most) one notification per stack. > > This can be made to (only) slow down the dicts which are used as scopes, by dynamically swapping out its function pointers upon (temporary?) conversion. > > (You sent this as private?) > > On Dec 19, 2015 7:09 PM, "Victor Stinner" <victor.stinner(a)gmail.com> wrote: >> >> >> Le 19 déc. 2015 21:07, "Franklin? Lee" <leewangzhong+python(a)gmail.com> a écrit : >> > Tim Peters points out how it might be more expensive than a lookup. >> >> Your whole idea rely on the assumption than a dict lookup (two lookups for builtins) is slow. Remember that a dict lookup has a complexity of O(1)! That's why I suggested you to start to benchmark, especially know the time in nanoseconds of a dict lookup. >> >> > He ended up using versioning, because the notification was expensive. >> >> Yeah I also began with notification with a registry of functions before moving to versionning: >> http://faster-cpython.readthedocs.org/readonly.html >> >> Versionning is simple to implement and doesn't make dict operations slower. >> >> Victor [View Less]

2 1

Re: [Python-ideas] Optimizing global names via dict references
by Franklin? Lee Dec. 20, 2015

Dec. 20, 2015

(You sent this as private?) On Dec 19, 2015 7:09 PM, "Victor Stinner" <victor.stinner(a)gmail.com> wrote: > > Le 19 déc. 2015 21:07, "Franklin? Lee" <leewangzhong+python(a)gmail.com> a > écrit : > > Tim Peters points out how it might be more expensive than a lookup. > > Your whole idea rely on the assumption than a dict lookup (two lookups for > builtins) is slow. Remember that a dict lookup has a complexity of O(1)! > That's why I suggested you to start … [View More]

1 0

Optimizing global names via dict references
by Franklin? Lee Dec. 19, 2015

Dec. 19, 2015

(Previous threads from python-dev: "Re: [Python-Dev] Third milestone of FAT Python" https://mail.python.org/pipermail/python-dev/2015-December/142437.html "[Python-Dev] Idea: Dictionary references" (Forked from above thread.) https://mail.python.org/pipermail/python-dev/2015-December/142490.html ) Dictionary References: An Idea in Three Emails Act 1: Stuff Table of Contents: Act 1: Stuff https://mail.python.org/pipermail/python-ideas/2015-December/037511.html - … [View More]Definitions - Problem statement - The idea - The benefits - The costs - What will hold a RefCell? - Add `getref` to `dict` - Implementation issues - Interpreters other than CPython Act 2: More stuff https://mail.python.org/pipermail/python-ideas/2015-December/037512.html - Extension: Scope ancestry - Aside: Classes and scopes do not have the same rules - Extension: Read/write refs - Extension: Read-only refs - Option: Alternative RefCell structure - Option: Replace the methods when detaching a RefCell - Extension: Dynamic scoping - Extension: Thread safety Act 3: Sample pseudocode https://mail.python.org/pipermail/python-ideas/2015-December/037513.html - ScopeDict - Scope ancestry - Alternative RefCell structure - Thread safety == Definitions == "lookup" A dictionary lookup. "exposed RefCell" A RefCell with a PyRef other than by its owner. A RefCell with a refcount > 1. "pyreference" A CPython ref-counted reference. == Problem statement == I propose a CPython interpreter optimization for global name lookups. When a function uses a global name, it requires a lookup during execution. def maxlen(lists): return sum(len(lst) #globals['len'] for lst in lists) This is necessary because: 1. The name might not exist yet. 2. The value might change. Repeated dict lookups are more expensive than, uh, not doing that. Local variables are indexed by array, rather than lookups. (See http://stackoverflow.com/questions/12590058/python-performance-with-global-…) Pythonistas often get around this lookup by saving the name in a local variable. def maxlen(lists): len_ = len return sum(len_(lst) #globals['len'] for lst in lists) They also use a default argument for that variable, which would prevent the lookup during each call. def maxlen(lists, len=len): return sum(len_(lst) #globals['len'] for lst in lists) I think these tricks are theoretically unnecessary. We only need a single lookup, at compile-time. There should be no change to Python's semantics. In fact, this should reinforce the semantics, because the above tricks don't allow for `len` to change, so if this idea is implemented, the tricks would only be used to explicitly disallow changes. == The idea == We use a level of indirection, and allow empty values in the internal dict (scope.__inner__[key] = NULL). Let ScopeDict be a subclass of dict. (It doesn't have to be a subclass. See "ScopeDict should replace dict".) ScopeDict owns a second dict of RefCells. A normal dict owns pyreference to its values. A RefCell will have a pointer to that reference. This means that a RefCell does not need to be notified when a value is set, since it knows where the dict stores its pointer to the value. Instead, when the dict resizes, the dict has to update all of its RefCells. Upon deletion of the dict, ScopeDict will pass ownership of the value pyreferences to the RefCells. That was a simplified view. We can make these optimizations: 1. The RefCells will be held in an array, not a dict. This array will be synced with the dict's internal hash table, and resizes with it. This allows a single lookup for both the value and its RefCell (or lack thereof), because they will be at the same index in different arrays. 2. RefCells won't be created unless they're requested. Obviously. 2a. The array doesn't need to be created unless a RefCell is created. 3. Any time a ScopeDict would touch a RefCell, it would first check that it's not exposed (that is, that the RefCell has no outside references). If it isn't exposed, that Refcell can be safely deleted. 3a. The refs array can also be deleted at this time if it doesn't hold anything. 4. If a key has no corresponding RefCells, it doesn't need to be saved. This can be checked on resize and ScopeDict.__del__, and also can be checked on __delitem__. [See "Pseudocode: ScopeDict"] == The benefits == Every global lookup is done at compile-time. No need to save a local copy of a global variable. Guaranteed to have the most updated value. Even if it didn't exist at compile-time. In particular, it works even for recursive functions and wrapped functions, such as from functools import lru_cache @lru_cache() def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) Access to a global variable during a call is a few C dereferences, plus a few checks and C function calls. No change to the semantics of the language. Possible change in the semantics of CPython: There might be cases where keys live longer than they used to, given the following: 1. `del scope[key]` was called. 2. There was an exposed RefCell for that key. 3. Later, the RefCell stopped being exposed 4. `scope` has not resized since then (and thus didn't clean up its dead cells yet). The above is already possible in garbage-collected interpreter. We can make ScopeDict weakref its RefCells, and have RefCells remove keys with no value when they die, but it would mean extra overhead by wrapping a RefCell with a weakref. Is that worth it? (`getref` will return a strong reference.) == The costs == Memory: - An extra pointer to the refs table in each ScopeDict, and an extra function pointer for the new function. - An extra array for each ScopeDict, 1/3 to 1/4 the size of the internal dict table (depends on how big pointers are on the platform). Note: Since the refs table is the same size as the internal hash table, Raymond Hettinger's compact dict idea will also decrease the size of the refs table. (compact dict idea: https://mail.python.org/pipermail/python-dev/2012-December/123028.html) - Extra memory for each RefCell (a Python object). (There will be at most one RefCell per dict per key.) - The dict will be bigger because it holds empty entries. Execution: - Extra compile time. Functions will do lookups when they're compiled. But we're saving lookups during execution, so it's only extra if the function never gets called or never uses the RefCell. - `getitem`: Must check if the value is NULL. Currently, it only checks the key. - `delitem`: Instead of removing the key, just set the value to NULL. In fact, this is probably cheaper. - Resizing the dict: It will have to copy over all the RefCells (and delete the unused ones) to a new array, too, and update them. - Deleting the dict: The dict will have to DecRef its RefCells, and pass on its value pyreferences to the ones that survive. Python Refs: - We're potentially holding keys even when values have been deleted. This is okay, because most pyreferences to a refcell replace a pyreference to a key. == What will hold a RefCell? == Functions will request RefCells for each global variable they use. They will hold them until they die. Code not in functions (e.g. in module scope), or using eval/exec, will request RefCells during compilation, and they will be used during execution. They will discard the RefCells when they are done executing. == Add `getref` to `dict` == I propose that all dicts should have the ability to return RefCells. As Victor Stinner pointed out in his FAT Python message, using a subclass for scopes would disallow regular dicts being used as scopes by eval and exec. (See end of https://mail.python.org/pipermail/python-dev/2015-December/142397.html) But I think refs can be useful enough that it could be added to the dict interface. Meaning `getref` (via another name... `item`?) can be a new dict method. Upon first use, the dict will generate an empty refs table, and replace its methods with ones that know how to deal with refs. This prevents O(n) memory overhead for dicts that don't need it. == Implementation issues == There are performance _concerns_. I think it can be done with only a few performance _issues_. In my experience in arguing out the idea, the overhead for both memory and execution will be better than what they replace.[*] So while I'm not promising a free lunch, I'm believing in it. There are potential issues with dict subclasses that also change the C function pointers, since I'm proposing that we replace those functions dynamically. I think these issues are solvable, but it would require understanding what's allowed so I would know how to properly wrap that functionality. [*] (Except that there's a tricky case in deep multiple inheritance of scope, which I'd have to figure out. But I don't think it's possible to do that except in classes, and I don't wanna touch class MRO until I understand how the resolution works in C.) [*] (And you can pay a lot of lookups if you keep creating functions that won't get executed, but it's impossible to do such a thing in a loop since the lookups will be done once by the parent. Unless you loop an eval/exec to keep making functions that will never be called, in which case you're a bad person.) == Interpreters other than CPython == It should be possible to use the same idea in IronPython, Jython, and PyPy. I think it's a simple enough idea that I am surprised that it's not already there. In fact, I would not be surprised if PyPy already uses it. In fact, I would not be (very) surprised if I had gotten the idea from PyPy. [View Less]

4 7

Dict literal use for custom dict classes
by Jelte Fennema Dec. 17, 2015

Dec. 17, 2015

I really like the OrderedDict class. But there is one thing that has always bothered me about it. Quite often I want to initialize a small ordered dict. When the keys are all strings this is pretty easy, since you can just use the keyword arguments. But when some, or all of the keys are other things this is an issue. In that case there are two options (as far as I know). If you want an ordered dict of this form for instance: {1: 'a', 4: int, 2: (3, 3)}, you would either have to use: … [View More]

19 35

Contiguous-array-based ordering for OrderedDict
by Franklin? Lee Dec. 17, 2015

Dec. 17, 2015

Here's Tim Peters's 2013 explanation of OrderedDict: http://stackoverflow.com/a/18951209/2963903 He said: > But if [the order list] were a Python list, deleting a key would take O(n) time twice over: O(n) time to find the key in the list, and O(n) time to remove the key from the list. I didn't see why this would need to be the case. 1. If you start searching from the front, then each element would be inspected or shifted, never both. This would mean only one full iteration. 2. You don't … [View More]have to shift for each deletion. You can wait until some threshold is reached before shifting, and maybe that will spread out the cost of shift among deletions enough to make an impact. 3. He then mentions that the linkedlist implementation uses a second dict to map keys to their list nodes. Well, that would solve the cost of lookup for lists, too. So I ended up taking 3.5.0's OrderedDict and implemented the idea. I'm not really sure what to do next, in terms of testing and comparing it against the existing implementation, and whether it's worth pushing for such a design for OrderedDict (current Python version or future C cersion). It's enough for me if I can figure out how this compares in performance, both algorithmically and actually, to the current implementation. -------------------------------------------------------------------- First idea: (link: http://pastebin.com/LESRktJw) Data members (with ListDict() as od): - super() : dict[key] => value - od.__map : dict[key] => index where od.__list[index] = key - od.__list : list[index] => key or `_sentinel` - od.__size : int - number of non-sentinel elements in list (aka len(dict)) - This might be replaceable by len(self). Some algorithms to note: - .__setitem__: Add it to the end of __list if it's new. - .__delitem__: Replace the __list entry with `sentinel`, and attempt to compact the list. - .__compact: Called when items are removed. Naive threshold: If the list is 50% empty, then make a new list and update the indices for each key. - (iterator views): Simply yield things that aren't `sentinel`. - .move_to_end(last=False): The biggest loss. Adding to the front of the list will shift potentially many things up. Maybe if the list were a dequeue, this would be faster. The actual length of __list will slow down iteration through the list, but the factor of O(n) is dependent on the threshold value. And the code itself MIGHT be faster per-element, and maybe (big maybe) easier for the hardware. Needs special review: - __sizeof__: I have no idea if I did this right. - (iterators): Can they be made to sometimes detect additions/removals during iteration? - Exception safety: E.g. in __setitem__, the order of updates for the metadata might leave the dict in an invalid state. Also needs review: - I put a lot of global calls as default args, but the existing use of default args for static name lookup seemed inconsistent. -------------------------------------------------------------------- Second idea: thicker wrapper. Store a key,value,index triple in the internal dictionary, instead of just the value. This will have a wrapper cost on __getitem__ (have to get the value from the triple), but will save many lookups for adding and removing elements (which is probably the less-common use). (At the C level, it should be possible to keep multiple storage dictionaries in lockstep. Also, the triple doesn't need to be exposed to the Python interface, right?) Type: class _DictStorage(object): __slots__ = ['key', 'value', 'index'] Members: (external): ListDict[key] => value super() : dict[key] => [key, value, index] .__list : list[i] => [key, value, index] (same as above) or None .__size : as in the other implementation. Probably just as unnecessary. .__map : (removed; unneeded) Some method implementations: .__getitem__: Grab the [k,v,i] from the inner dict and unwrap it. .__setitem__: If the triple exists, update its value. If it doesn't exist, add in [k, v, len(__list)-1] and append it to __list. (This saves a lookup in the internal dict.) .__delitem__: inner.pop(key), and use the index to None it on the list. (iteration): Same as the first ListDict implementation, except using None instead of _sentinel. .move_to_end, .__compact: Same as the first ListDict, except I won't have to dict.get the keys to update their indices. Third idea: Well, I have to learn PyPy's implementation of OrderedDict. [View Less]

10 25

Trailing-based state restoration
by SAVEANT Pierre Dec. 17, 2015

Dec. 17, 2015

Hi, I got a proposal for a new feature in Python in order to perform hypothetical reasoning in a very simple way. Hypothetical reasoning is mainly used in problem solving search algorithms. In such a process, variables are temporally assigned and later restored to their preceding value. With the assumption that only a small fraction of the variables changes at the same time, it is more efficient to store undo information instead of copying the entire state. The basic data structure to handle … [View More]

2 2