4 ms·

My wife was a teacher librarian and I used to give her interview questions related to data storage and retrieval. With no interest or background in CS she had n

My wife was a teacher librarian and I used to give her interview questions related to data storage and retrieval. With no interest or background in CS she had no problem describing optimally efficient algorithms based on analog concepts, questions experienced engineers had difficulty answering.

usrusr 6y ago
I was assigned to medical filing in my nonmilitary service and being a programmer kid I immediately saw it through the algorithmic lens: sort your incoming files (the paper kind) before inserting them in the ordered shelves, sort larger stacks by subdividing into smaller stacks then ordering those (a very cheap operation if everything fits between the fingers of one hand!) in preparation for an ordered merge, sort very large stacks by pre-sorting into unordered buckets first and so on. All tuned on the spot to changing physical constraints like desk space. Or room space, that one time when we did a minor index reorganizion involving several tons of paper. Later when I took courses about RDBMS internals etc it felt like this experience helped a lot.
Swizec 6y ago
You're probably more worried about optimal algorithms when you can't trivially do thousands of operations per millisecond. It's kind of crazy how often the correct answer in engineering is something like "Eh, N is less than 100,000 and this only runs once. Brute force"
- warent 6y ago
  Sometimes that is the case. Too often, in my experience, that assumption is made when it is actually technical debt that someone has to pay off down the road. It smells of move fast and break things.
  - FeepingCreature 6y ago
    To be fair, if it doesn't break, you never know.
Zelizz 6y ago
In high school, I once volunteered at a local library for a few hours, sorting returned book alphabetically. At the start, I tried just grabbing the alphabetically "first" book repeatedly, moving it to the front. This got old fast, so after a little while, I started looking at just the first letters, and grabbing all the books I could fit in my hand with that letter. When I had them all "roughly" sorted, I did the same with the second letter, etc. A few years later I learned about sorting algorithms. It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. In school you don't really spend a few hours manually executing sorting algorithms to build an intuition, so the algorithms can feel a bit like artifacts handed down from the gods. How could someone have come up with these? But then, if that's the specific problem you're trying to solve, developing a fairly efficient and sophisticated (and sometimes opaque to future students) algorithm can feel completely natural.
- C1sc0cat 6y ago
  Back when I had a Saturday job at my local library I used to roughly sort the books alphabetically on the trolley that had the books to be shelved first then go round the shelves.
- thaumasiotes 6y ago
  > It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. The concepts don't directly apply to sorting physical books on a shelf. For example, insertion sort works well (pick up any book, then put it in the correct place). It is O(n^2) as implemented as a standard sorting algorithm, shuffling numbers around in an inflexible array. But bookshelves are nothing like that. On the shelf, you just shove everything to the left (or right) in a single operation, opening the gap you need. This is not O(n^2). The bookshelf is more like a doubly linked list than like an array.
  - Izkata 6y ago
    GP's description is selection sort, not insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life.
082349872349872 6y ago
hashing was originally invented to keep physical clerical staff from bumping into each other in front of the file cabinets

usrusr 6y ago

I was assigned to medical filing in my nonmilitary service and being a programmer kid I immediately saw it through the algorithmic lens: sort your incoming files (the paper kind) before inserting them in the ordered shelves, sort larger stacks by subdividing into smaller stacks then ordering those (a very cheap operation if everything fits between the fingers of one hand!) in preparation for an ordered merge, sort very large stacks by pre-sorting into unordered buckets first and so on. All tuned on the spot to changing physical constraints like desk space. Or room space, that one time when we did a minor index reorganizion involving several tons of paper. Later when I took courses about RDBMS internals etc it felt like this experience helped a lot.

Swizec 6y ago

You're probably more worried about optimal algorithms when you can't trivially do thousands of operations per millisecond. It's kind of crazy how often the correct answer in engineering is something like "Eh, N is less than 100,000 and this only runs once. Brute force"

warent 6y ago
Sometimes that is the case. Too often, in my experience, that assumption is made when it is actually technical debt that someone has to pay off down the road. It smells of move fast and break things.
- FeepingCreature 6y ago
  To be fair, if it doesn't break, you never know.

Zelizz 6y ago

In high school, I once volunteered at a local library for a few hours, sorting returned book alphabetically. At the start, I tried just grabbing the alphabetically "first" book repeatedly, moving it to the front. This got old fast, so after a little while, I started looking at just the first letters, and grabbing all the books I could fit in my hand with that letter. When I had them all "roughly" sorted, I did the same with the second letter, etc. A few years later I learned about sorting algorithms. It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. In school you don't really spend a few hours manually executing sorting algorithms to build an intuition, so the algorithms can feel a bit like artifacts handed down from the gods. How could someone have come up with these? But then, if that's the specific problem you're trying to solve, developing a fairly efficient and sophisticated (and sometimes opaque to future students) algorithm can feel completely natural.

C1sc0cat 6y ago
Back when I had a Saturday job at my local library I used to roughly sort the books alphabetically on the trolley that had the books to be shelved first then go round the shelves.
thaumasiotes 6y ago
> It's interesting to me that my natural book-sorting intuition was O(n^2) selection sort, but then it wasn't a very big leap for me to tweak it a bit and discover a form of O(n)(ish) radix sort. The concepts don't directly apply to sorting physical books on a shelf. For example, insertion sort works well (pick up any book, then put it in the correct place). It is O(n^2) as implemented as a standard sorting algorithm, shuffling numbers around in an inflexible array. But bookshelves are nothing like that. On the shelf, you just shove everything to the left (or right) in a single operation, opening the gap you need. This is not O(n^2). The bookshelf is more like a doubly linked list than like an array.
- Izkata 6y ago
  GP's description is selection sort, not insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life.

082349872349872 6y ago

hashing was originally invented to keep physical clerical staff from bumping into each other in front of the file cabinets