On Mar 16, 2020, at 09:53, Christopher Barker <[email protected]> wrote:
>
>
> Note that the OP used the word "semantics", but primarily meant "performance
> characteristics":
IIRC, the C++ specification includes guaranteed performance characteristics as
part of its library semantics, so an implementation whose std::map::find takes
more than log N time isn’t conforming to C++ semantics. And I don’t think
that’s too unreasonable. For example, Alex Martelli’s sorted dict based on a
list that calls sort after each mutation is a sorted dict if you ignore
performance characteristics, but I don’t think anyone would consider a
general-purpose sorteddict type that has O(NlogN) rather than O(logN) insert
cost usable. (For special cases where you rarely or never mutate after
construction, on the other hand, it’s very usable, which is why it’s been a
popular recipe for decades…)
Meanwhile, one really important bit of non-performance-related semantics that
wasn’t mentioned: dict (like C++ std::unordered_map) works with any hashable
keys; a sorteddict (like C++ std::map) doesn’t care about hashability but
requires ordered keys.
In C++, that’s a type issue: std::map can only be instantiated with a key type
that provides a strict weak ordering and an equivalence relation, which means
that map<double, double> is not legal (unless you specify a custom Pred like
IEEE total_ordering), even though practically it works with real-life
implementations as long as you’re careful never to insert any NaN values. Since
Python containers are heterogeneous, the requirement has to be specified on the
values rather than the types, just like the requirement on hashability for
dict. Which means you could legally use non-NaN floats as keys. (It‘a still
often a bad idea, for the same reason that comparing floats with == is often a
bad idea.) But what about statically typed homogenous sorteddict[T] variables?
Should T be required to be StrictWeakOrdered or NaNOrdered or …? (Is the thread
on adding those ABCs still going on?) Someone needs to specify what the exact
requirement is supposed to be, both at runtime and statically (although the
answer to the latter could just be “no requirement checked” or “must have
__lt__” or whatever). I think SortedContainers has already done at least the
runtime part, so we could just borrow it from there along with everything else.
:)
> However, the OP also had this little function in the CPP version.
>
> int nth_smallest_key(int n, map<int, int>& m) {
> map<int, int>::iterator curr = m.begin();
> for (int i = 0; i < n; i++) {
> curr = next(curr);
> }
> return curr->first;
> }
>
> Which is taking advantage of the fact that the map iterates in sorted order.
>
> But if you have something in sorted order, then iterating over it to get the
> nth object is a lot less efficient that it could be. If this is a common
> use-case (is it??) then it would be nice to provide an API for it more
> directly.
>
> Which, it turns out, SortedDict does, in fact, do:
Yes, and it also includes things like key-slicing (“get the values for all keys
a<=key<b”). Grant started his design based on a long bikeshedding thread on
-ideas, and improved it from there by seeing what problems showed up during
implementation and during use. Even if we’re not going to use SortedContainers,
we should definitely start with its API rather than starting from scratch.
_______________________________________________
Python-ideas mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/[email protected]/message/J5JEZ64JTVMUF7F5PL22FTDKBUDHCZQ7/
Code of Conduct: http://python.org/psf/codeofconduct/
