New Book-Sorting Algorithm Almost Reaches Perfection | Quanta Magazine (www.quantamagazine.org)
from cm0002@lemmy.world to programming@programming.dev on 26 Jan 06:03
https://lemmy.world/post/24743320

Computer scientists often deal with abstract problems that are hard to comprehend, but an exciting new algorithm matters to anyone who owns books and at least one shelf. The algorithm addresses something called the library sorting problem (more formally, the “list labeling” problem). The challenge is to devise a strategy for organizing books in some kind of sorted order — alphabetically, for instance — that minimizes how long it takes to place a new book on the shelf.

#programming

threaded - newest

aleq@lemmy.world on 26 Jan 09:00 next collapse

I’m not familiar with Quanta from before, but what a fantastic article. It explains the problem and the history in an engaging way that manages to be approachable to us without an academic background in CS while still retaining some academic substance. Very informative!

shalafi@lemmy.world on 27 Jan 00:31 collapse

Comments like this are valuable. I would not have read that but for your well written praise.

onlinepersona@programming.dev on 26 Jan 09:02 next collapse

Could this be used for filesystems? I know little about them but I remember NTFA requires defragmentation to keep performance and ext4 hasn’t ever required that in my experience. No idea about BTRFS, XFS, and others. My inkling is that it would be quite useful, but maybe somebody else could make a more educated guess.

Anti Commercial-AI license

Warl0k3@lemmy.world on 26 Jan 09:47 next collapse

Seems like the answer is yeah!

That’s because the problem also applies to the arrangement of files on hard drives and in databases, where the items to be arranged could number in the billions.

onlinepersona@programming.dev on 26 Jan 10:31 collapse

I missed that! 😅 Thanks.

Anti Commercial-AI license

promitheas@programming.dev on 26 Jan 11:40 collapse

Just a sidenote about ntfs & ext4.

ntfs doesnt require defragmentation on SSDs, and it actually might lower the lifespan of your SSD because of the increase in unnecessary read/writes.

ext4 IIRC works just fine as long as your drive is at most 90% full and you keep that last 10% free.

Its been a while since i read up on that fact about ext4 so someone more experienced can correct me if im wrong

YourAvgMortal@lemmy.world on 26 Jan 19:05 next collapse

You are correct! And moreover, fragmentation was bad on HDDs because they are good at reading sequential data, so fragmentation limited performance by making reads more random. However, SSDs are the opposite and are more performant on random reads, so fragmentation actually benefits them! (some of the time)

shalafi@lemmy.world on 27 Jan 00:27 collapse

Jacked up the first SSD I ever bought. Windows 7 (I think?), NTFS. Defragged it out of habit, even though I knew better. Yep, ran much slower, and it was obvious.

Badland9085@lemm.ee on 26 Jan 15:59 next collapse

Is there anyone here who’s familiar with the paper(s) mentioned in the article? I’d actually like to read them, so if you do, it’d be great if you could share it with me. I couldn’t really find it in the article, unless it’s just hidden under one of their links.

I found the following paper with the authors mentioned:

arxiv.org/abs/2501.11582

But not sure if that’s it. It does have some semblance to the topic though. My search-fu isn’t really doing me great with just author names though.

SpicyLizards@reddthat.com on 15 Feb 08:05 collapse

This is the beauty referenced as the 2022 article in the study: Online List Labeling: Breaking the log2n Barrier