41–44 of 44 posts
Earlier quoted context omitted.
Sounds like python is not batteries included compared to other languages in this regard!
Do any languages give you min/max at the same time with their standard library data structures? (setting the key function with "key=lambda x: -x" is really easy and works just like changing a comparator function in other languages so I dunno why you guys are talking about it)
BST supports log(n) min/max/inserts/removes (among other stuff).
Earlier quoted context omitted.
There are only two important things taught in CS that most people don't seem to pick up on the job. The most important is order notation. The second is the relation between grammars and state machines. Both are worth as much attention as you can afford for a week. Things not taught in CS that you need to know on the job are legion. By far the most important of these is the use of invariants. Second might be the memor…
I'm learning about invariants in a relatively introductory cs course and I've been told they end up being relatively useless in actual practice. When have you found them useful?
They are right that invariants will not be essential for your assignments, at least for the first couple of years, although they would save you from some dead ends.
You will be able to code some of your invariants as assertions, but as often not. The ones you can't are the ones you have to pay the most attention to.
If the system invariants get too complicated, or hard to express, the design is wrong--reliably. That is when they are most valuable. Millions of systems designed without invariants could have been right, but we're stuck with what we got, instead.
Earlier quoted context omitted.
So, kind of a non sequitur, but I occasionally think about Qt's QList . When introduced, it was odd for reserving space at the beginning as well as the end, so you had constant-time inserts/removals at the beginning. That and storing pointers for any T larger than a pointer also reduced the constant factor on insertion/deletions from the middle. Since it was always stored as a list of pointer-sized items, some code c…
You would probably enjoy reading about an alternative implementation for STL's std::deque, called a tier vector[1][2]. It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!! The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I…
Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?
Anyway, just neat that it's been taken further than I realized!
[1] https://infoscience.epfl.ch/record/213452/files/rrbvector.pd...