5 ms·
New book-sorting algorithm almost reaches perfection
- baruchel 2y agoI recall presenting a problem to my students a few years ago based on the 'Library Sort' algorithm. I still clearly remember the title of the original paper: 'Insertion Sort is O(n log n)'.
- deathanatos 2y agoPresumably this: https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaMo06-librarysort.pdf https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaMo06-l... Kind of a click-baity title.
- foota 2y agoIt's sort of click bait, but also true, right? This is just insertion sort using non-fixed indexing?
- zeroonetwothree 2y agoThis is a different problem though, despite the similar name.
- acbart 2y agoI was actually just looking at this problem last week, when I realized I needed to keep items in a database table positioned arbitrarily, ideally without needing to manipulate the rest of the list. So if a user adds in a new element after element 5, that element becomes 6, without needing to update the original item that came after element 5. There are indeed very sophisticated algorithms to manage this problem and minimize theoretical bounds. But it also seemed like the simplest solution for this particular version of the problem is to just use fractional amounts, and occasionally pay a penalty to relayout the list.
- tetris11 2y agoIsn't that hash table chaining?
- jon_richards 2y agoMore like tree rebalancing.
- jes5199 2y agolike line numbers in an old BASIC program
- williamdclt 2y agoHa, I had this exact problem asked as an interview question. IIRC their real life solution was to leave gaps between elements (eg index 0, 100, 200… instead of 0, 1, 2) and re index when needed. Probably works well enough, what I came up with is (as you say) the idea of fractional indexing, but dealing with decimals is a pain so you can instead represent them as vectors, which you can just represent as a string of numbers that you sort lexicographically. So an element inserted between elements 1 and 2 gets an index 11 (anything between 11-19 is fine). Between 1 and 11 is 101. Between 11 and 2 is 12 (or anything between 12-19). Note that these indexes are not numbers, they’re string that are compared lexicographically. I’m sure there’s downsides, eg it takes a lot more memory to sort these indexes (strings are much larger than numbers). It feels a bit too smart to not have unexpected downsides.
- Etheryte 2y agoVery similar to my first intuition on how to approach this problem. An interesting question that comes to mind is how should you pick index sizes and how often should you rebalance the whole thing. Make the index too large and you're wasting a lot of space you'll never need, too small and you're forced to rebalance too often. I'm guessing an ideal index size is such that you can rebalance at most once a night with a cron job and then avoid rebalances the whole rest of the day. To be fair, this sounds like one of those classic problems that someone for sure already figured out in the 50s or 60s, just under a different name and/or context. Hash chaining is a similar idea, but not quite the same.
- AstroJetson 2y agoCool. This is Lisa and Laura, they are my two retired teachers that are now helping in the library to sort shelves. Can you explain to them what you want them to now do? I read the paper and I would like to say, it's confusing at best. But I'm hoping you can help out.
- gessha 2y agoA lot of things are confusing at first but then we discover intuitive ways to explain and teach them to others. Also, don’t discredit the intelligence of retirees, teachers and librarians in the same post. It’s bad for karma and makes you sound like a douche. I’m sure they can figure it out.
- AstroJetson 2y agoWasn't my intent. The article was "how to do this" with lots of great pictures. Linked page was full of high level math. I was mocking the "This one simple trick can make your shelves full" attitude. So you answered and I'll ask, "what do they do, it does not seem simple" except for the Database people filling .... Thanks (former teacher)
- aladinn57 2y agoSounds promising! What's the key innovation behind it?
- TheRealNGenius 2y ago[dead]
- doodpants 2y agoOff topic, but now I want a screen saver of the animation at the top of the article...
- ColinDabritz 2y ago"Kuszmaul remembers being surprised that a tool normally used to ensure privacy could confer other benefits." It was surprising to me too! But reflecting on it more closely, most performance isn't about "faster" in a literal sense of "more instructions run per time", but about carefully choosing how to do less work. The security property here being "history independence" is also in a way stating "we don't need to, and literally cannot, do any work that tracks history". It's definitely an interesting approach to performance, essentially using cryptography as a contraint to prevent more work. What properties do we need, and what properties can we ignore? The question becomes if we MUST ignore this property cryptographically, how does that affect the process and the related performance? It certainly feels like it may be a useful perspective, a rigorous approach to performance that may be a path to more improvements in key cases.
- zeroonetwothree 2y agoThe actual better algorithm does use history dependence though. So I found this part of the article misleading.
- nickburns 2y agoSo it's basically a matter of figuring out what problem context can and should be selectively hidden from the algorithm in order to make it work 'smarter' and not 'harder.' Weird.
- pradn 2y agoThat's a good insight. I had always thought the key to good algorithm / data structure design was to use all the information present in the data set. For example, if you know a list is sorted, you can use binary sort. But perhaps choosing how much of it to omit is key, too. It comes up less often, however. I can't think of a simple example.
- koolba 2y ago> But perhaps choosing how much of it to omit is key, too. It comes up less often, however. I can't think of a simple example. An example of that is a linked list with no particular sort order. By not caring about maintaining an order the insertion appends or preprends a node and is O(1). As soon as you have to maintain any additional invariant, the insertion cost goes up. Either directly or amortized.
- tetris11 2y agoClean links for mobile users Game: https://patorjk.com/games/subpixel-snake/ https://patorjk.com/games/subpixel-snake/ Code: https://github.com/patorjk/subpixel-snake https://github.com/patorjk/subpixel-snake Resource for subpixel geometries: https://geometrian.com/resources/subpixelzoo/ https://geometrian.com/resources/subpixelzoo/
- TheRealNGenius 2y agoWrong post
- 9dev 2y agoThis probably belongs to the post on subpixel snake, not this one on the library sort algorithm :)
- thaumasiotes 2y ago> lowering the upper bound to (log n) times (log log n)^3 — equivalent to (log n)^(1.000...1) This is true! One of the things I find cool about big-O complexity using polynomial reference classes is that logarithms give you an infinitesimal value. Take that, "infinitesimals don't really exist" people!
- sfelicio 2y agoWait. What? Do you have a reference where I can learn about this?
- thaumasiotes 2y agoI don't really understand what you're asking for. You can easily just verify the claim for yourself. The limit as x goes to infinity of (ln x) / (x^k) is zero for all positive k. So if you want to approximate the behavior of a logarithm with a function of the form f(x) = x^k, k must be greater than 0 [because x^0 = o(ln x)], but less than every positive real number. This is the definition of an infinitesimal. That's why it makes sense to say that x (log x)^3 is equivalent to x^{1.000000...[infinite 0s]...1}. Though in this analogy, it's more like x^{1.000000...3}.
- da39a3ee 2y ago>> Do you have a reference where I can learn about this? > I don't really understand what you're asking for. That comes across as rude and condescending; please don't communicate like that. Your English skills seem OK but in case you still need help, they're asking for a "reference" -- that's an online source of some sort probably, where they can "learn about" it -- that means that the reference would contain content helping them to understand the topic better. For example, the helpful content you gave after your rude and condescending initial comment would be an example of such content.
- User23 2y agoOnly believing things that you can easily reason through if you are presented with some external authority really is a cognitive antipattern though. I’d say that prologue was more medicinal than condescending. It’s good to remind people in the age of LLMs and ubiquitous search that “you can just think things.”
- msmitha 2y agoI was shocked to discover how the British Library (millons of books, many many new ones every week) manages this. The first book to arrive earlier this year went on the shelf at 2025.0000001. The next went at 2025.0000002, right next to it. The electronic catalogue does the rest. No need to re-shuffle books around, but not a solution supportive of book-browsing.
- crazygringo 2y agoReminds me of how Amazon doesn't arrange its items by similarity like a store does, so a model of vacuum cleaner might be next to a set of kitchen plates. They actually intentionally avoid similarities so pickers won't accidentally grab a similar but wrong thing. I lose track of so many infrequently used objects in my home -- which storage bin in which closet did I put the x-acto blade refills in? -- and one bin will overflow while another is half-empty because I try to keep similar items together. Sometimes I fantasize about tracking every possession in a spreadsheet that points to which bin, so I'd never lose anything and could always use storage space with maximum efficiency. But then I know I'd be lazy and skip updating the spreadsheet when I put something new away... plus it just seems so inhumanly weird, like something a robot would so rather than a person.
- ryao 2y agoIs there any reason to think that this algorithm will actually be faster than what is currently done in practice? For arrays in B-tree nodes, which is the main place where I have encountered this problem, I doubt it will be faster than just using `memmove()`, and for truly large arrays, it would be easier to use a B tree. If that is the case, this joins a number of algorithms that are asymptotically faster than algorithms in use and paradoxically slower than them. Examples of such algorithms include all of the fast matrix multiplication algorithms, which are slower than good implementations of the the textbook O(n^3) algorithm (GEMM).
- melvyn2 2y agoThese are sometimes called Galactic Algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm https://en.wikipedia.org/wiki/Galactic_algorithm The very first example on the page has a pretty good quote describing their usefulness: >>> An example of a galactic algorithm is the fastest known way to multiply two numbers, which is based on a 1729-dimensional Fourier transform. It needs O(n log n) bit operations, but as the constants hidden by the big O notation are large, it is never used in practice. However, it also shows why galactic algorithms may still be useful. The authors state: "we are hopeful that with further refinements, the algorithm might become practical for numbers with merely billions or trillions of digits."
- dchftcs 2y agoOne interesting thing about working on numbers so large is that it becomes harder to assume that memory access is constant time. It's already not that easy now (cache miss vs hit, and external memory), but when you operate on data sizes that large, memory accesses matter by at least the square or cube root of N. If you require largely sequential access it is possible to outperform an algorithm that requires conditional random access by some function of those factors, which can make some algorithms look much worse or better compared to the classical analysis. Of course, it still does not matter whether your algorithm is going to finish in a couple of trillion years or a trillion trillion years.
- teleforce 2y agoAm I the only one that's trying to find the main papers that're being described in the article both the original problem, and the near optimal algorithm paper [1],[2]. Apparently both of them are linked deep inside the article, perhaps Quanta can make it mandatory to list all the reference towards the end of the article, it will be very helpful for the readers. [1] Nearly Optimal List Labeling: https://arxiv.org/abs/2405.00807 https://arxiv.org/abs/2405.00807 [2] A sparse table implementation of priority queues: https://link.springer.com/chapter/10.1007/3-540-10843-2_34 https://link.springer.com/chapter/10.1007/3-540-10843-2_34
- svat 2y agoBoth papers are linked very clearly in the article, and it was easy to quickly find them just skimming through the article without even reading: > This problem was introduced in a 1981 paper where "1981 paper" links to https://link.springer.com/chapter/10.1007/3-540-10843-2_34 https://link.springer.com/chapter/10.1007/3-540-10843-2_34 and in the next paragraph: > Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers where "a study" links to https://arxiv.org/abs/2405.00807 https://arxiv.org/abs/2405.00807 Note that both of these are in the introductory section (third and fourth paragraphs), before the article goes into details, history and context. If this is what counts as “Apparently both of them are linked deep inside the article”, then it appears there exist very different ideas of what “deep inside” means.
- xpe 2y agoI’m trying to figure out a key constraint. Does the problem statement assume a fixed-length pre-allocated array?
- chongli 2y agoNo, it doesn’t assume an array at all. It’s a data structure that maintains a totally ordered set with 3 operations: insert(X), delete(X), label(X) Where label extracts the label of element X (which had previously been inserted but not deleted). The label is a number from 0 to n-1, where n is the number of elements currently stored.