0

Counter() from Python's collections module is an unordered container, yet when built from same-size integers, the values() view appears as if the Counter was sorted by key first. This happens consistently both on my computer (3.4.3rc1), as well as online IDEs (tio.run, ideone.com) with Python versions up to and including 3.5; not the case with 3.6+ or PyPy.

from collections import Counter
import random

def counter_is_sorted(iterable):
    c = Counter(iterable)
    return list(c.values()) == [v for k, v in sorted(c.items())]

print(counter_is_sorted([random.randrange(1000) for _ in range(50000)]))

True

This is not always true when elements were updated and false for other types and mixed integer sizes:

print(counter_is_sorted([random.randrange(65000, 66000) for _ in range(50000)]))
print(counter_is_sorted([round(random.uniform(0, 10), 2) for _ in range(50000)]))
print(counter_is_sorted([random.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(50000)]))

False
False
False

Is this by design or depending on some particular factors? Under what constraints can we safely assume the values() view to be sorted?

eyllanesc
  • 235,170
  • 19
  • 170
  • 241
Nadstratosfer Gonczy
  • 31
  • 4
  • When I make this a script and execute it in Python 3.7, I see `False`. What is your setup? – brentertainer Jul 20 '19 at 03:23
  • 1
    A `Counter` is derived from `dict`. Since 3.6 `dict`s are insertion ordered (see https://stackoverflow.com/a/39980744/987358) so your assumption isn't true for 3.6+. For 3.5 and older I don't know. – Michael Butscher Jul 20 '19 at 03:39
  • At least one case that will cause issues is a Counter with mixed type keys, e.g. `Counter(['a', 1])` because ordering isn't defined between `str` and `int` types. – brentertainer Jul 20 '19 at 03:54
  • You already saw the ordering not hold in 3.6 and PyPy, so I don't see why you're still entertaining the possibility that it might be guaranteed. – user2357112 Jul 21 '19 at 02:49
  • I see now that the information about 3.6 and PyPy was added in an edit. Well, you have your answer. – user2357112 Jul 21 '19 at 02:55
  • I'm mostly interested _why_ this is so consistent with uniform type on earlier Python versions. The performance boost from not sorting an apparently ordered structure would be negligible anyway. – Nadstratosfer Gonczy Jul 21 '19 at 03:17

0 Answers0