Programming

17984 readers

172 users here now

Welcome to the main community in programming.dev! Feel free to post anything relating to programming here!

Cross posting is strongly encouraged in the instance. If you feel your post or another person's post makes sense in another community cross post into it.

Hope you enjoy the instance!

Rules

Follow the programming.dev instance rules
Keep content related to programming in some way
If you're posting long videos try to add in some form of tldr for those who don't want to watch videos

Wormhole

Follow the wormhole through a path of communities [email protected]

founded 2 years ago

MODERATORS

snowe

Ategon

[email protected]

New Book-Sorting Algorithm Almost Reaches Perfection | Quanta Magazine (www.quantamagazine.org)

submitted 5 days ago by [email protected] to c/programming

9 comments fedilink hide all child comments

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.

you are viewing a single comment's thread
view the rest of the comments

[–] onlinepersona 4 points 5 days ago* (last edited 5 days ago) (2 children)

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

[–] promitheas 8 points 4 days ago (2 children)

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

[–] [email protected] 5 points 4 days ago

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)

[–] [email protected] 3 points 4 days ago

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.

[–] [email protected] 4 points 5 days ago (1 children)

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 1 points 5 days ago

I missed that! 😅 Thanks.

Anti Commercial-AI license