Message338461
All of collections.Counter in-place operators: +=, -=, |= and &= are obviously expected to have time complexity O(b) as in the following example:
a = Counter(...) # e.g 1M elements
b = Counter(...) # e.g. 10 elements
a += b
But in fact, all of them are having O(a + b) time complexity due to inefficient implementation of _keep_positive method, which checks ALL of the elements of "a" counter after modification while it's required only to check CHANGED elements (no more than a size of "b") having time complexity O(b).
See https://github.com/python/cpython/blob/master/Lib/collections/__init__.py#L819
It also unclear if there's even a need to check for non-positives with _keep_positive in ops like __iadd__, __iand__ and __ior__ (except __isub__) as it expects Counters which are always positive.
This unobvious inefficiency leads to unnecessary large execution times while, for example, iteratively accumulating some small Counters into a large one (frequent case). In this case .update method works much faster, but it doesn't check for zeros or negatives for some reason (is this a bug too?). |
|
Date |
User |
Action |
Args |
2019-03-20 12:13:26 | Nikita Smetanin | set | recipients:
+ Nikita Smetanin |
2019-03-20 12:13:26 | Nikita Smetanin | set | messageid: <1553084006.71.0.725416830974.issue36380@roundup.psfhosted.org> |
2019-03-20 12:13:26 | Nikita Smetanin | link | issue36380 messages |
2019-03-20 12:13:26 | Nikita Smetanin | create | |
|