Mailman 3 September 2013 - Python-ideas

Introduce collections.Reiterable
by Neil Girdhar 25 Sep '13

25 Sep '13

This is an idea I've wanted for a while: When I call functions that accept an iterable, I often have to check whether the function iterates over the iterable once or more than once. If it iterates more than once, I must not pass a generator, but rather cast to a list. Otherwise, the second iteration through the generator will be empty as the first has exhausted it completely. It would be nice to introduce an abstract base class in collections (docs<http://docs.python.org/3.3/library/collections.abc.html>) between Iterable and Sequence. Right now, Sequence inherits from Iterable. I propose having Sequence inherit from Reiterable, which in turn, inherits from Iterable. All sequences are reiterable, whereas generators are not. However, views in sets and dictionaries, and numpy arrays are examples of Reiterables that are not Sequences. Having such an abstract base class would be useful for debugging in its own right. Also, functions that iterate twice over an iterable can check to make sure the iterable is "re-iterable" using isinstance (the standard approach as per pep 3119 <http://www.python.org/dev/peps/pep-3119/>). But, better yet, itertools could add two functions: auto_tee, which takes an iterable "I" as its parameter, and an integer n. If it is not a reiterable, it calls tee and returns n iterables independently capable of iterating "I". If it is reiterable, it returns [I] * n. This way, the client code can do whatever is easiest and the target code can call auto_tee if necessary. auto_list could do the same sort of thing, but omitting the copy that would normally be incurred if a list were passed in. Maybe this is less useful than I once thought since I've gotten by without it, but I just wanted to throw the idea out there in case it clicks for someone else. Neil

18 128

Numerical instability was: Re: Introduce collections.Reiterable
by Oscar Benjamin 22 Sep '13

22 Sep '13

On 19 September 2013 22:25, Terry Reedy <tjreedy(a)udel.edu> wrote: > On 9/19/2013 8:28 AM, Steven D'Aprano wrote: >> >> def variance(data): >> # Don't do this. >> sumx = sum(data) >> sumx2 = sum(x**2 for x in data) >> ss = sumx2 - (sumx**2)/n >> return ss/(n-1) >> >> Ignore the fact that this algorithm is numerically unstable. > > Lets not ;-) > >> It fails >> for iterator arguments, because sum(data) consumes the iterator and >> leaves sumx2 always equal to zero. > > This is doubly bad design because the two 'hidden' loops are trivially > jammed together in one explicit loop, while use of Reiterable would not > remove the numerical instability. While it may seem that a numerically > stable solution needs two loops (the second to sum (x-sumx)**2), the two > loops can still be jammed together with the Method of Provisional Means. > > http://www.stat.wisc.edu/~larget/math496/mean-var.html > http://www.statistical-solutions-software.com/BMDP-documents/BMDP-Formula1.… > > Also called 'online algorithm' and 'Weighted incremental algorithm' in > https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance > > This was invented and used back when re-iteration of large datasets (on > cards or tape) was possible but very slow (1970s or before). (Restack or > rewind and reread might triple the (expensive) run time.) I'm never quite sure what exactly is meant by "numerical instability" in most contexts because I'm mainly familiar with the use of the term in ODE solvers where an unstable solver will literally diverge from the true solution as if it were an unstable equilibrium. However in that context the error is truncation error rather than rounding error and would occur even with infinite precision arithmetic: http://en.wikipedia.org/wiki/Stiff_equation I'm going to assume that numerical instability is just a way of saying that a method is inaccurate in some cases. Although the incremental algorithm is much better than the naive approach Steven (knowingly) showed above I don't think it's true that constraining yourself to a single pass doesn't limit the possible accuracy. Another point of relevance here is that the incremental formula cannot be as efficiently implemented in Python since you don't get to take advantage of the super fast math.fsum function which is also more accurate than a naive Kahan algorithm. The script at the bottom of this post tests a few methods on a deliberately awkward set of random numbers and typical output is: $ ./stats.py exact: 0.989661716301 naive -> error = -21476.0408922 incremental -> error = -1.0770901604e-07 two_pass -> error = 1.29118937764e-13 three_pass -> error = 0.0 For these numbers the three_pass method usually has an error of 0 but otherwise 1ulp (1e-16). (It can actually be collapsed into a two pass method but then we couldn't use fsum.) If you know of a one-pass algorithm (or a way to improve the implementation I showed) that is as accurate as either the two_pass or three_pass methods I'd be very interested to see it (I'm sure Steven would be as well). Oscar $ cat stats.py #!/usr/bin/env python from __future__ import print_function from random import gauss from math import fsum from fractions import Fraction # Return the exact result as a Fraction. Nothing wrong # with using the computational formula for variance here. def variance_exact(data): data = [Fraction(x) for x in data] n = len(data) sumx = sum(data) sumx2 = sum(x**2 for x in data) ss = sumx2 - (sumx**2)/n return ss/(n-1) # Although this is the most efficient formula when using # exact computation it fails under fixed precision # floating point since it ends up subtracting two large # almost equal numbers leading to a catastrophic loss of # precision. def variance_naive(data): n = len(data) sumx = fsum(data) sumx2 = fsum(x**2 for x in data) ss = sumx2 - (sumx**2)/n return ss/(n-1) # Incremental variance calculation from Wikipedia. If # the above uses fsum then a fair comparison should # use some compensated summation here also. However # it's not clear (to me) how to incorporate compensated # summation here. # http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Compensate… def variance_incremental(data): n = 0 mean = 0 M2 = 0 for x in data: n = n + 1 delta = x - mean mean = mean + delta/n M2 = M2 + delta*(x - mean) variance = M2/(n - 1) return variance # This is to me the obvious formula since I think of # this as the definition of the variance. def variance_twopass(data): n = len(data) mean = fsum(data) / n sumdev2 = fsum((x - mean)**2 for x in data) variance = sumdev2 / (n - 1) return variance # This is the three-pass algorithm used in Steven's # statistics module. It's not one I had seen before but # AFAICT it's very accurate. In fact the 2nd and 3rd passes # can be merged as in variance_incremental but then we # wouldn't be able to take advantage of fsum. def variance_threepass(data): n = len(data) mean = fsum(data) / n sumdev2 = fsum((x-mean)**2 for x in data) # The following sum should mathematically equal zero, but due to rounding # error may not. sumdev2 -= fsum((x-mean) for x in data)**2 / n return sumdev2 / (n - 1) methods = [ ('naive', variance_naive), ('incremental', variance_incremental), ('two_pass', variance_twopass), ('three_pass', variance_threepass), ] # Test numbers with large mean and small standard deviation. # This is the case that causes trouble for the naive formula. N = 100000 testnums = [gauss(mu=10**10, sigma=1) for n in range(N)] # First compute the exact result exact = variance_incremental([Fraction(num) for num in testnums]) print('exact:', float(exact)) # Compare each with the exact result for name, var in methods: print(name, '-> error =', var(testnums) - exact)

4 4

Reduce platform dependence of date and time related functions
by random832＠fastmail.us 20 Sep '13

20 Sep '13

The practice of using OS functions for time handling has its worst effects on Windows, where many functions are unable to process times from before 1970-01-01 even though there is no reason for Python to have such a limitation. It also results in uneven support for strftime specifiers. Some of these functions also suffer from the Year 2038 problem on OSes with a 32-bit time_t type. I propose supplying pure-python implementations (in accordance with PEP 399) for the entire datetime module, and additionally the asctime, strftime, strptime, and gmtime functions in the time module, and calendar.timegm. Unfortunately, functions dealing with local time stamps in the system's idea of local time are still dependent on the platform's C library functions (localtime, mktime, ctime) Or, if this is not practical, supplying alternate implementations of the relevant C functions, and calling these instead wherever these are used. If it is practical to do so, these functions should use python integers as the type for timestamps; if not, they should use 64-bit integers in preference to the platform time_t. Is it reasonable to expose the possibility of an epoch other than 1970 (or of timestamps that handle leap seconds in a different manner than POSIX) at a python level? Even if such a platform ever comes to be supported, it could be done so with a layer that hides these differences.

12 36

Add PassedArgSpec class to types and expose mapping given an ArgSpec.
by Neil Girdhar 19 Sep '13

19 Sep '13

As far as I know, the way that arguments are mapped to a parameter specification is not exposed to the programmer. I suggest adding a PassedArgSpec class having two members: args and kwargs. Then, inspect.ArgSpec can take an argument specification and decode the PassedArgSpect (putting the right things in the right places) and return a dictionary with everything in its right place. I can only think of one use for now, which is replacing "arguments" in the returned tuple of __reduce__ and maybe allowing it to be returned by "__getnewargs__". It might also be nice to store such argument specifications instead of the pair args, kwargs when storing them in lists. Best, Neil

2 1

pickle does not work properly with cooperative multiple inheritance. Propose: "__getnewkwargs__".
by Neil Girdhar 18 Sep '13

18 Sep '13

My understanding of cooperative multiple inheritance is that a class often doesn't know how your parent classes want to be constructed, pickled, etc. and so it delegates to its parents using super. In general, constructors can accept keyword arguments, and forward their unused arguments to parents effortlessly: class A(B): def __init__(self, x, **kwargs): super().__init__(**kwargs) will extract x and forward kwargs. Unfortunately, the same mechanism is not easily available for pickling because __getnewargs__ returns only a tuple. If there were a __getnewkwargs__ method, then we could have class A: def _getnewkwargs__(self): return {**super().__getnewkwargs(), a=self.a, b=self.b} # (new unpacking from PEP448) Note how additional kwargs are added to the dict of kwargs specified by the parent objects. Best, Neil

1 1

Re: [Python-ideas] Keep free list of popular iterator objects
by Kyle Fisher 18 Sep '13

18 Sep '13

Hi Antoine, Thanks for taking the time to respond. Sorry I didn't see your comments earlier, I have my mailing list settings to digest and for some reason they weren't showing up in my inbox. Anyway, I agree that a real-world test case would be best. Marc-Andre tossed out "100 objects" for the free list size, but I'd like to point out that it probably doesn't need to be anywhere near that large. How many iterators are active in the interpreter simultaneously? I think we could get away with only a dozen or so. Perhaps it's best for me at this point to try out the patch in our application and see what some real world results would be. It'd also be nice if there was some other macro-benchmark that I could run this against to verify that it doesn't make things worse, which seems to be Raymond's biggest concern. Is there something like this available? Maybe even just the unit test suite? Thanks, -Kyle

2 3

Add dict.getkey() and set.get()
by Serhiy Storchaka 16 Sep '13

16 Sep '13

I propose to add two methods: dict.getkey(key) returns original key stored in the dict which is equal to specified key. E.g. >>> d = {2: 'a', 5.0: 'b'} >>> d.getkey(2.0) 2 >>> d.getkey(5) 5.0 >>> d.getkey(17) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 17 set.get(value) returns original value stored in the set which is equal to specified value. E.g. >>> s = {2, 5.0} >>> s.get(2.0) 2 >>> s.get(5) 5.0 >>> s.get(17) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 17

12 25

Compressing excepthook output
by אלעזר 16 Sep '13

16 Sep '13

I suggest adding an excepthook that prints out a compressed version of the stack trace. The new excepthook should be the default at least for interactive mode. The use case is this: you are using an interactive interpreter, or perhaps in eclipse's PyDev, experimenting with some code. The code happen to has an infinite recursion - maybe an erroneous boundary condition, maybe the recursion itself was an accident. You didn't catch the RuntimeError so you get a print of the traceback. This is by default a 2000 lines of highly repetitive call chain. Most likely, a single cycle repeating some 300 times. The main problem is that in most environments, by default, you have only a limited amount of lines kept in the window. So you can't just scroll up and see what was the error in the first place - where is the entry point into the cycle. You have to reproduce it, and catch RuntimeError. You can't just use printing for debugging, either, because you won't see them. And even if you can see it, you had lost much of your "history" for nothing. I have tried to implement an alternative for sys.excepthook (see below), which compresses the last simple cycle in the call graph. Turns out it's not trivial, since the traceback object is not well documented (and maybe it shouldn't be, as it is an implementation detail) so it's non trivial (if at all possible) to change the trace list in an existing traceback. I don't think it is reasonable to just send anyone interested in such a feature to implement it themselves - especially given that newcomers ate its main target - and even if we do, there is no simple way to make it a default. Such a compression will not always help, since the call graph may be arbitrarily complex, so there has to be some threshold below which there won't be any compression. this threshold should be chosen after considering the number of lines accessible by default in common environments (Linux/Windows terminals, eclipse's console, etc.). Needless to say, the output should be correct in all cases. I am not sure that my example implementation is. Another suggestion, related but distinct: `class RecursionLimitError(RuntimeError)` should be raised instead of a plain RuntimeError. One should be able to except this specific case, and "Exception messages are not part of the Python API". --- Example for the desired result (non interactive): Traceback (most recent call last): File "/workspace/compress.py", line 48, in <module> bar() File "/workspace/compress.py", line 46, in bar p() File "/workspace/compress.py", line 43, in p def p(): p0() File "/workspace/compress.py", line 41, in p0 def p0(): p2() File "/workspace/compress.py", line 39, in p2 def p2(): p() RuntimeError: maximum recursion depth exceeded 332.67 occurrences of cycle of size 3 detected Code: import traceback import sys def print_exception(name, value, count, size, newtrace): # this is ugly and fragile sys.stderr.write('Traceback (most recent call last):\n') sys.stderr.writelines(traceback.format_list(newtrace)) sys.stderr.write('{}: {}\n'.format(name ,value)) sys.stderr.write('{} occurrences of cycle of size {} detected\n'.format(count, size)) def analyze_cycles(tb): calls = set() size = 0 for i, call in enumerate(reversed(tb)): if size == 0: calls.add(call) if call == tb[-1]: size = i elif call not in calls: length = i break return size, length def cycle_detect_excepthook(exctype, value, trace): if exctype is RuntimeError: tb = traceback.extract_tb(trace) # Feels like a hack here if len(tb) >= sys.getrecursionlimit()-1: size, length = analyze_cycles(tb) count = round(length/size, 2) if count >= 2: print_exception(exctype.__name__, value, count, size, tb[:-length+size]) return sys.__excepthook__(exctype, value, tb) sys.excepthook = cycle_detect_excepthook if __name__ == '__main__': def p2(): p() def p0(): p2() def p(): p() def bar(): p() bar() ### Elazar

3 3

Keep free list of popular iterator objects
by Kyle Fisher 16 Sep '13

16 Sep '13

We tend to do a lot of iterating over dictionaries in our product in some performance critical areas. It occurred to me that allocating a new iterator object every single time seems a little wasteful, especially considering that there's probably only a handful of them alive at any time. Doing a quick test with dictiterobject and 3 free lists (one for Keys, Values and Items) showed about a 4% speedup in this (best) case: python -m timeit -s "a = {'k%d' % i: i for i in xrange($2)}" "[_ for _ in a.iteritems()]" However, this seems like almost too simple of an idea. Has this been tried before? Would it be too little gain? Given that the extra memory used is negligible (3 of each iterator?), how much of a performance gain would be needed to justify it? Thanks, -Kyle

5 16

AST Pretty Printer
by Ryan 16 Sep '13

16 Sep '13

I always encounter one problem when dealing with Python ASTs: When I print it, it looks like Lisp(aka Lots of Irritated Superfluous Parenthesis). In short: it's a mess. My idea is an AST pretty printer built on ast.NodeVisitor. If anyone finds this interesting, I can probably have a prototype of the class between later today and sometime tomorrow. -- Sent from my Android phone with K-9 Mail. Please excuse my brevity.

5 5