Ask HN: Algorithms and data structures for humans and physical objects?
7 comments
I haven't seen much literature about the subject, but you have the Spaghetti Sort which is half funny and half serious (offering near linear time complexity)
https://en.wikipedia.org/wiki/Spaghetti_sort
https://en.wikipedia.org/wiki/Spaghetti_sort
> For example, a sorting algorithm for a human to sort a pile of books or papers, or a structure for someone to manage a large bookshelf so that they can find a book quickly given its name.
Are we assuming that the human actually remembers the name of a book? If you go stand next to a big physical bookstore's help desk for an hour or even hang out at the library, you'll see a bunch of people go by there and ask for help finding a book they can sort of describe, but can't really remember the exact name of.
Are we assuming that the human actually remembers the name of a book? If you go stand next to a big physical bookstore's help desk for an hour or even hang out at the library, you'll see a bunch of people go by there and ask for help finding a book they can sort of describe, but can't really remember the exact name of.
Maybe changing it into finding an archive file given its ID (not an auto-incrementing key, but something like its owner's national identification number) is better? They both belong to the category of creating a sorted dictionary structure in the physical world.
I'm not sure I fully understand your response, but I'd say this to illustrate my perspective on the problem. Go hang out in a bookstore or library for a while and eavesdrop on the help desk.
You'll see a number of interactions take this sort of form.
"Hey I'm looking for this book my friend showed me last month. It's a big book with a cover that's got some white letters. It's a love story set in England and it has a great action scene at a farm. I don't remember the author's name, but one of his other books was a movie that had a dog in it."
You'll see a number of interactions take this sort of form.
"Hey I'm looking for this book my friend showed me last month. It's a big book with a cover that's got some white letters. It's a love story set in England and it has a great action scene at a farm. I don't remember the author's name, but one of his other books was a movie that had a dog in it."
I think this what the field of library science tackles (among other things):
https://en.wikipedia.org/wiki/Library_science
More specifically, classifications: https://en.wikipedia.org/wiki/Library_classification
(of which Dewey is one of the more famous ones: https://en.wikipedia.org/wiki/Dewey_Decimal_Classification
But every organization system has its cost, and it's probably not worth it for small collections (like a stack of papers).
The professors I've seen attempt to do this just put each paper into piles sorted by last name, and then search among that pile for a specific name when needed. It's an old-fashioned indexing system.
There's also this old metafilter thread; several people there mention a "sort-all" device: https://ask.metafilter.com/222379/Quickest-way-to-alphebatiz...
More specifically, classifications: https://en.wikipedia.org/wiki/Library_classification
(of which Dewey is one of the more famous ones: https://en.wikipedia.org/wiki/Dewey_Decimal_Classification
But every organization system has its cost, and it's probably not worth it for small collections (like a stack of papers).
The professors I've seen attempt to do this just put each paper into piles sorted by last name, and then search among that pile for a specific name when needed. It's an old-fashioned indexing system.
There's also this old metafilter thread; several people there mention a "sort-all" device: https://ask.metafilter.com/222379/Quickest-way-to-alphebatiz...
Wow, this insight really helps. Thanks for the pointers!
A popular book about this is Algorithms to Live By
Is there algorithms and data structures for humans to manage physical objects, or researches on this topic? For example, a sorting algorithm for a human to sort a pile of books or papers, or a structure for someone to manage a large bookshelf so that they can find a book quickly given its name.
Obviously, human algorithms should be designed with different assumptions than computer algorithms. Humans can insert objects into an array in near constant time, don't have constant time random access, and physical objects can't be copied, etc. These assumptions change the properties of existing algorithms, and may raise new algorithms into view under these new assumptions. But exactly how? What term should I start searching with?
This question originally came out when I collected and hand-sorted hundreds of exam papers as a TA.