Python is famously built around hash tables. So much so that several versions ago they made an improvement to the hash table implementation, and the entire language became several percent faster.
However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?
One reason you don't see a data structure with O(log(n)) operations in this list is that priority queues/heaps are not a built-in type. Weirdly, there isn't a type for them at all, just a bunch of functions (good luck if you use them wrong). https://docs.python.org/3/library/heapq.html
There isn't a type for them for the same kind of reasons that `join` is a method on the joining string. That is, it lets you reuse that code for multiple sequence types, including ones that don't exist yet. This is just something that happens with ad-hoc polymorphism, but it's also good to keep class interfaces small and implement other functionality in terms of them. Herb Sutter would approve.
Making the functions into methods wouldn't make them easier to use, it would just make the abstraction feel more familiar to those from a Java tradition rather than a C++ one.
With the current implementation you can accidentally use first heapify_max and then heappop (forgetting the _max), accidentally append something through the normal list append method, change the priority of something unknowing that that breaks the invariant, or run into problems with "Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order".
These headaches could have been mostly removed if these were in a class. And the option to use a custom sequence type could have surely been preserved.
Not true. I just bought No Man's Sky on a Steam sale a few months ago and have been having a blast with it - only very occasionally neglecting my adult duties because of it.
Stellar Science | Hybrid (USA) Albuquerque NM, Washington DC (Tysons VA), Dayton OH | Full time, interns/co-ops | U.S. citizenship required | https://www.stellarscience.com
Company: We're a small scientific software development company that develops custom scientific and engineering analysis applications in domains including: space situational awareness (monitoring the locations, health and status of on-orbit satellites), image simulation, high power microwave systems, modeling and simulation, laser systems modeling, AI/ML including physics-informed neural networks (PINN), human body thermoregulation, computer vision and image processing, high performance computing (HPC), computer aided design (CAD), and more. All exciting applications and no CRUD. We emphasize high quality code and lightweight processes that free software engineers to be productive.
Experience: Except for interns, we currently require a Bachelors degree in physics, engineering, math, computer science, or a related field. Masters or PhD is a plus. (Roughly 25% of our staff have PhDs.)
Technologies: Lots of C++23, Qt 6.9, CMake, git, OpenGL, CUDA, Boost, Jenkins. Windows and Linux, msvc/gcc/clang/clangcl. AI/ML and analysis projects use Python and C++. Web projects use Java and Typescript/React. We're a bit behind the curve on developer AI adoption, and we're okay with that.
Agreed, seeing that example briefly made me consider whether this blog post was a parody. Sure, it works for this exact example, by relying on i wrapping "down" to MAX_INT on the last iteration. But how long will it take the next developer who works on the code base to figure that out? Will they figure it out before or after committing changes that break it? Or worse yet, before or after shipping code?
Thanks for the excerpts! I was trying to understand the reasoning, which seem to just be in the 2nd excerpt:
- The rules of signed/unsigned are complicated and there is too much auto-conversion - does that mean languages that make this more explicit means this is fine? It just seems ideal to have stronger typing.
- It is mentioned that you can initialized an unsigned int to "-2" - but that presumably could also be fixed in the language.
I'm trying to separate out which is "don't do this in C/C++" and which is "don't do this in any language".
that argument (and many others) also round to essentially "implicit imprecise integer casting is surprising but we do it anyway" which is... perhaps the actual problem???
I've made lints for Go that simply disallow implicit number casting, and omfg the (real, occurring but unnoticed) bugs it found. those kinds of lints are trivial to build, you can just stop doing it. forcing visible casts made many of these problematic patterns extremely suspicious at a glance, catching issues at review time far more easily.
> I'm trying to separate out which is "don't do this in C/C++" and which is "don't do this in any language".
To achieve high performance, any language would need to implement integer addition with a single machine instruction like 'ADD'. Languages can achieve more intuitive behavior by adding an operand check before the 'ADD', or by using an 'ADC' instruction and checking the carry bit afterwards. But adding branch statements to every add operation would slow computation significantly. Clever languages/compilers might deduce certain invariants and variable ranges that enable it to remove some of these branches to help in certain special cases.
Evidently Rust has an optional "safe add" that adds the branches to check for overflow. So newer languages offer more explicit options. But the core issue is more fundamental than language-specific.
I still don't like having explicit conversions everywhere like in rust. Either you're not thinking too hard about it and the explicit conversions are not really doing anything for you, or you are, meaning you need to be reasoning about it every time and justifying why it can never fail and/or injecting error handling. I would be a much happier rust user if index/length types were are i64 and we relegated unsigned types to serialization almost exclusively. I have other gripes for unsigned types btw, those are just my complaints why explicit casts are not a panacea.
> In Python, this works correctly for negative values.
They’re both “broken” in different ways. Arguably C’s brokenness is more apparent and less useful but Python also has footguns: C uses truncated division for its “modulo” so the remainder has the sign of the dividend, Python uses floored division so the remainder has the sign of the divisor instead.
The wiki page for modulo has a pretty extensive page on the subject.
I say you want a pair of operations such that (a, b) = quotient_and_remainder(x, y) gives you a and b such that a * y + b = x
The Euclidean division and remainder work, the other division and remainder also work, and they're both identical for the positive integers so people who only think about the positive integers won't even notice there's a choice here. So I like that Rust provides both pairs, in the same way Rust provides both Wrapping<T> and Saturating<T> because maybe you mean wrapping overflow or maybe you mean saturating overflow and we should make you choose not just assume we know best.
> Python uses floored division so the remainder has the sign of the divisor instead
Serious question, how is that a footgun? In decades of software development I have never needed a negative divisor for modulo. What would you use it for?
Stellar Science | Hybrid (USA) Albuquerque NM, Washington DC (Tysons VA), Dayton OH | Full time, interns/co-ops | U.S. citizenship required | https://www.stellarscience.com
Company: We're a small scientific software development company that develops custom scientific and engineering analysis applications in domains including: space situational awareness (monitoring the locations, health and status of on-orbit satellites), image simulation, high power microwave systems, modeling and simulation, laser systems modeling, AI/ML including physics-informed neural networks (PINN), human body thermoregulation, computer vision and image processing, high performance computing (HPC), computer aided design (CAD), and more. All exciting applications and no CRUD. We emphasize high quality code and lightweight processes that free software engineers to be productive.
Experience: Except for interns, we currently require a Bachelors degree in physics, engineering, math, computer science, or a related field. Masters or PhD is a plus. (Roughly 25% of our staff have PhDs.)
Technologies: Lots of C++23, Qt 6.9, CMake, git, OpenGL, CUDA, Boost, Jenkins. Windows and Linux, msvc/gcc/clang/clangcl. AI/ML and analysis projects use Python and C++. Web projects use Java and Typescript/React. We're a bit behind the curve on developer AI adoption, and we're okay with that.
Just FYI, finally in C++ you can add a top-level exception handler and call boost::stacktrace::from_current_exception (https://www.boost.org/releases/1.85.0/), and get a stack trace on exit as helpful as in Python or Java.
CEOs understands that AI offers potential productivity increases. Using that productivity boost to cut staff is an unimaginative approach. Bolder approaches include using that boost to exceed the expectations of current customers, or to increase sales without proportional increase in staff, etc.
However, I'm surprised to see no data structures at all with O(log(N)) complexity. Surely there are some use cases for which that's desirable?