The cards are more interesting to me than the word, which I originally thought was going to be some kind of copyright-protecting deliberate mistake.
The cards remind me of Jira tickets, with stamps and names as a kind of audit log of work associated with the ticket. I find myself curious about the information architecture and paper processes that companies built around such tickets going to and fro.
Such architectures probably have fairly close analogues in distributed systems, and there may be a thing or two to learn from how more innovative and efficient organizations structured their paper pushing.
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.
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.
> 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.
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.
This is something of a grandiose claim. How are you thinking of a physical insertion sort working? If you don't have a model, you can't say anything about the time requirements.
But note that if we conceptualize insertion sort like this:
loop:
pick up a book
find the place within the sorted books where this book belongs
open a space for the book
insert the book
the four steps in that model are O(1), O(log n), O(1), and O(1), and the loop repeats n times, so we have an upper bound of O(n log n).
The reason insertion sort is O(n^2) when operating on an array is that step 3, "open a space for the book in our hand" is O(n) in that case, because we can only move one book at a time.
But, while we're here... Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items (you start with 0 of them, and end with n of them, for an average of n/2, which is O(n)):
> find the place within the sorted books where this book belongs
You do this once for each unsorted item (you start with n of them, and end with 0 of them, for an average of n/2, which is O(n)).
Granted, in real life, your brain does a better job of remembering roughly the correct place for each book, so I would say average case with a small number of books you are correct. If you're sorting a large number of books, you need to find the correct spot in less than O(n) comparisons to do better than O(n^2) on the algorithm. I think finding the correct spot would still be O(n), just with a small constant.
Interestingly, if you were sorting a massive volume of books like this and you started to forget the right spot for things, you might modify your strategy and start binary searching for it. This would help you find the spot in O(log(n)), and you'd be doing the sort in O(n*log(n))! It's a small improvement that yields binary insertion sort.
> Insertion sort is O(n^2) on the number of comparison operations, because this step is O(n) on the number of sorted items
Locating the correct position in the sorted items is O(log n) on the number of sorted items. You point this out yourself later in your comment. Because the sorted items are sorted, it's not necessary to examine each of them.
Doing O(log i) work as i varies from 1 to n is O(log n!) work, which is O(n log n); not much different from doing O(log n) work as i varies from 1 to n.
I'm not sure how to interpret the two halves of this quote. It looks to me like I'm doing O(n log n) comparisons, and also finishing the sort in O(n log n) work overall. I'm not taking O(n^2 log n log n) work to finish the sort.
> Because the sorted items are sorted, it's not necessary to examine each of them.
This is true, but I'm being pedantic and calling the quadratic form of insertion sort just "insertion sort", and the form that does a binary search on the sorted items "binary insertion sort".
Ah, my error. If you want to see what I was thinking, imagine I'd pulled the "fuller" quote 'insertion sort, which still requires extra scanning instead of manipulation and remains O(n^2), even in real life'.
The point of my comment was just that the complexity of an algorithm as analyzed under one set of primitive operations doesn't automatically translate into another set of operations, even when at a high level it's the same algorithm. It is dangerous to study CS, learn that selection sort (on arrays, on a computer well described by a C-like language) is O(n^2), and then conclude that selection sort (in any context) is inherently O(n^2). That may be true of selection sort in specific -- it's difficult to avoid concluding that the selection step is roughly ϴ(n), and must always run n times -- but the reasoning is faulty, and won't transfer to other algorithms.
This makes more sense now. The full relevant part of my comment:
> GP's description is selection sort, not insertion sort, which still requires
The double-comma construction is meant to be read as an aside. Probably would've been clearer using parens:
> GP's description is selection sort (not insertion sort), which still requires
I often use the commas though because I'm mentally verbalizing what I type and commas have a pause that makes the aside work even aloud, while it's not clear how you'd verbalize parens.
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.
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.
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.
A possible lexicographic example of a bunny is the entry "hink" in the first edition of the Collins COBUILD English Language Dictionary [1]. I thought it was a mistake when I first learned about it, but some sources state that it was put there deliberately [2] [3].
Speaking of that, I need to find time one of these days to research what the hell "a memo" is. I understand it was a piece of paper of sorts, used in a way similar to how e-mails are used today, but I don't understand how they were delivered to people, what was the equivalent of MTA there. I know how to use the word in writing ("I didn't get the memo"), but not much more than that.
My understanding is these were printed letters circulated internally via the mailroom. Most companies had workers who circulated both internal and external mail - so a couple times a day someone would come by with letters for you, both from the outside world, and from inside the office. Memoranda were generally announcements distributed to many people in the office.
There were normally two trays or boxes for paper on people's desk, one was the "inbox" and one was the "outbox," and the mail person would place the new stuff in the inbox and take anything from the outbox to circulate it around the office.
I never really lived that, although my first desk job did have an inbox and an outbox, the team wasn't big enough to have a mailroom, so we would just use those boxes to drop papers at other people's desks - hence the outbox didn't really get used, but the inbox did. Usually once a day a bundle of mail would get dropped off at the front desk and someone would take a turn walking the letters around the office, but there weren't that many of them as email was already a thing at that point.
Pretty much - I started work before even internal email was a thing, so everything was done on paper. And often hand-written paper at that. Hell, I made the first Word template for a work-item ticket! Before that we had custom forms to fill out.
Even better, the developers worked in a different building to our users, so there would often be a couple of days lag to getting a response. If you needed a quicker answer, you had to phone them, or schedule a meeting if you needed to explain something in more detail.
A person so inclined can still order interoffice routing envelopes ("hundred milers") from most stationers. For the yoots, those were string-tied manilla envelopes with twenty to one hundred little addressing boxes that be re-used until there was no more room to cross out the previous addressee and add a new one.
Found one of those in the stacks of papers from my father's time at IBM. Funny how paper-based information technology was back then - the first thing that comes to mind are the punch cards, but also later program listings were printed out a lot.
We used stacks of "endless paper" core dumps / assembler listings when painting rooms, as you could just unfold a huge stack of paper to protect the floor from paint splatters.
As recently as 2008, I actually used those interoffice routing envelopes to submit the receipts for my expense reports. Then they introduced a new process involving scan and email.
The internal "mail room" used to be a much bigger deal. At large companies, some number of times a day an actual person would come around with a cart, put things in your in-tray and remove things from your out-tray. Once their round had been completed they would return to the mail room to sort the outgoing materials and then repeat the process.
I suspect that one of the reasons "starting in the mail room" used to be so venerated is that it's a good way to get to know a wide swath of people inside a company in a relatively short period.
Better Call Saul shows a lot of said mail room culture; not sure if it's accurate, but it's almost like a documentary in corporate life in the early 2000's. Wouldn't have thought paper was still as much of a thing back when, but, it's a law office and the internet hadn't been that much of a thing yet.
Memo is abbreviated, firstly. The word is memorandum, and as the Latin root suggests, is something to “bring to mind.” Typically written or typed notes, which might get copied and passed around. They have more jargon meanings in certain contexts.
To add to others' comments about mail-rooms and internal posts, a memo would commonly also have a header section with a list of intended recipients and CC (literally, Carbon Copy), plus depending on organisation, an information security classification meaning sometimes they would be distributed via envelope, or require signing receipt for. Envelopes could be sealed in any number of ways, the most common I've seen is masking tape with a signature across it.
Needless to say, the mail-room were privy to a lot of information should they care for it.
Edit: Working where both emails and physical memos were used: Drafting a physical memo elicited a very different state of mind from banging out an email. Printing it out, proof reading on paper, there was a lot more care via reflection knowing this would be in someone's hand and they'd likely be looking at it on their desk, giving full attention, making notes with pen over it, rather than simply a message displayed on a screen while multiple other tasks pop up from other incoming mails or calendar reminders or IM chats. Slower, but a level of preciseness and everything needing to be just right, all the way down to how many spaces after a period vs a colon.
Having worked somewhere that still used physical memos, I can share my experience. They were simply "important" notices and announcements printed on single sheets of paper hand-delivered to our desks by one of the managers or their secretaries. They'd often be on our desks before we got in, containing information that was realized the day before, but anything particularly urgent would be hand-delivered during the work day, usually around lunch.
They were completely interchangeable with emails, including in the way they were written (like short letters). I don't understand why we used them, but alas, we did.
I worked somewhere that used paper memos and initially I thought they were just woefully tech-inept. It turns out if you’re doing shady stuff a written memo that can be immediately shredded is one of the more “secure” methods of communication because it doesn’t create a digital record like an email or a phone call do.
I don’t know if this is still true, but it was sometimes the case that toner would retain images of what had been printed on it and could be recovered by forensic specialists.
We were doing crosscut shredding - to the point of practically atomizing the paper - then incinerating the shredded material in the military before the Shah fell, at least for Secret and above. If the CIA wasn't doing that, well, that's their own lookout.
Many large buildings in the past had mail chutes[1]. I’ve worked in a building with one; it also had a pigeon-hole messagebox per floor so people could get their mail.
It wasn’t used that much, though, except for the odd journal subscription that someone had delivered to their office address. The system would only work with envelopes and magazines, anything bigger had to be collected from a central mailroom.
Sending mail between offices was a little more convoluted —you could just use the post or a courier yourself, but if you got your document or memo in the hands of the right person (typically a mailroom clerk) before a cut-off time, it’d be sent as part of the company’s larger delivery.
I’m a millennial (late thirties), but I’ve worked in offices where there’s an internal mail system in which you write someone’s name on an envelope and then when it gets delivered, the name is scratched off to make it available for reuse for the next internal mailing.
Similar age and experience. Office keys, property tags, t-shirts or other swag, etc. arrive in those campus mail envelopes with the little string-and-knob closure and about 50 places for addressees on them.
I work at a top-5 tech corporation, and we still have that! Though the mail room is the closest destination, with three different outboxes, and personalized in-box slots. It's handy for sending physical items (such as ship-it badges, booklets bringing awareness to this or that, or the occasional physical bill to be expensed).
If I have a package delivered, there's someone with corporate security clearances that will swing it by the desk.
I had an internship at a county hall once (IT department), I had to use those as well to have the back-up tapes I had to switch delivered to our other building every day.
In my experience, the difference is - unfortunately - that Jira tickets end up being discarded once a task has been finished, instead of becoming documentation for a feature. I think that was caused by volume, we'd do 10+ tasks or features a week at our most productive, and it quickly became line- or factory work, instead of carefully crafting individual features.
This is very specific of lexicography (dictionary making) given the huge amount of work, yet the natural partitioning of it. If you like this, you can see a bit more of it in the anime Fune wo amu (舟を編む).
A 386 assembler I used in the late 80s (when the 386 was still new) consistently referred to 32-bit quantities in its documentation and error messages as a "dord", so that's what came to mind when I read this article. I assume that was also either because of a "propagating typo" from "dword" (this was software from Eastern Europe, where English wasn't all that common), or because it seemed more convenient to have "byte", "word", and "dord" all be the same number of characters.
In 1995, Polish Scientific Publishers PWN, a long-time publisher of dictionaries, sued Kurpisz, a new publishing house, for plagiarizing their large dictionary of Polish. The case was closed in favor of PWN in 2005, hitting the Supreme Court along the way.
Among the evidence against Kurpisz was their entry on the nonce word "amikus" (meaning "friend"), which they illustrated with the quotation "spijał się ze swoimi amikusami" (he was getting drunk with his friends) but could not tell the court where they had gotten the quotation from. Nowadays, with libraries digitizing every flimsy old book, they would find the source easily.
It is like a biological mutation, usually nothing. It could result in a massive misinterpretation of prior documents due to a shift in meaning and not understanding the lack of shift in context.
Not very predictable but often hillarious like say Moses being depicted as horned. It probably involves very long timelines even with cultural acceleration.
Imagine "dord" caught on as a synonym for density in all its senses including stupidity. Now imagine one document of a riot caused after accidentally ordering a squad to shoot when calling out about a fire. A poorly chosen "word" causing death gets corrupted to a misplaced "dord" and it gets taken as caused by one idiot who shouldn't have been chosen to lead (also accurate but not intended). A mention of a D or d in the chemical context taken as a stealth insult or joke like 1D10T Error.
Put yourself in the editor's shoes, caring for the dictionary is your life's work. Aside from misspellings, grammatical or factual errors, and typography issues, this is the other kind of bug that can rear its ugly head. Not to mention that you can't issue patches to copies that already shipped :-)
The urgency in that correction slip is amusing (Imperative! Urgent! A ghost word!), considering how inconsequential of a mistake it is.
For some people everything is urgent. Everything.
It's part of the reason that web pages because so unusable. Every single lower middle manager thinks their change is the most important thing in the world.
Wood floats and so do ducks. So logically if the dord of the duck equals the dord of the girl then the girl must be a witch. `checks dords of both duck and girl`. "She's a witch!" -- excerpt from "A More Scientific Guide to Witch Hunts".
I don’t know how that can work in practice. If it’s in a dictionary, it might get used and then... it should be in other dictionaries. Do they cycle them in and out?
This really stopped and made me consider the amount of work that goes into making dictionaries, especially before computers, and the completely mind numbing and awful job it must be to be a dictionary editor. Then again, I'm sure some people out there probably love it but, I just imagined for a moment having to be the person going through those and adding them to the dictionary and honestly, it wasn't a happy thought.
Anyone who did that, or still does, and anyone who enjoys doing that kind of work, I just say props to you guys. People like you work on those little details that makes the world interesting and do the things that get unappreciated but used by everybody. Just wanted to say thanks to all the dictionary editors and people doing work like that. I'm sure you guys don't get appreciated as much as you should.
“ Seven years, my lord, have now passed, since I waited in your outward rooms, or was repulsed from your door; during which time I have been pushing on my work through difficulties, of which it is useless to complain, and have brought it, at last, to the verge of publication, without one act of assistance (1), one word of encouragement, or one smile of favour. Such treatment I did not expect, for I never had a patron before.”
Gee, that version (which wikipedia also links to) is very mangled. "Is not a patrons my lord" ?!
The letter concludes with:
Is not a Patron, my Lord, one who looks with unconcern on a man struggling for life in the water, and when he has reached ground, encumbers him with help? The notice which you have been pleased to take of my labours, had it been early, had been kind; but it has been delayed till I am indifferent, and cannot enjoy it; till I am solitary, and cannot impart it; till I am known, and do not want it. I hope it is no very cynical asperity not to confess obligations where no benefit has been received, or to be unwilling that the public should consider me as owing that to a Patron, which Providence has enabled me to do for myself.
Having carried on my work thus far, with so little obligations to any favourer of learning, I shall not be disappointed though I shall conclude it, if less be possible, with less; for I have been long wakened from that dream of hope, in which I once boasted myself with so much exultation,
There are 'ghost words' which have become established. E.g. _derring-do_:
"The two words _durring_, _dorryng_, _daring_, verbal noun from _durran_, _dorren_ "to dare" v.1, and _don_, _do_, present infinitive of "do" v., literally "daring to do", which, by a chain of misunderstandings and errors, have come to be treated as a kind of substantive combination, taken to mean, Daring action or feats, ‘desperate courage’.
The words come incidentally in their ordinary sense and construction followed by the object ‘that’ (= what, that which) in Chaucer's Troylus; whence, in an imitative passage by Lydgate, in an absolute construction more liable to misunderstanding; Lydgate's _dorryng do_ was misprinted in the 16th cent. editions (1513 and 1555) _derrynge do_, in which form it was picked up by Spenser and misconstrued as a substantive phrase, explained in the Glossary to the Sheph. Cal. as ‘manhood and chevalrie’. Modern romantic writers, led by Sir W. Scott, have taken it from Spenser, printed it _derring-do_, and accentuated the erroneous use."
You could say they completely increased the dord of the whole situation for quite a few years. Ha! Take that! Now we just need a few hundred people to also use it and it slowly becomes real. The circle becomes complete.
The cards remind me of Jira tickets, with stamps and names as a kind of audit log of work associated with the ticket. I find myself curious about the information architecture and paper processes that companies built around such tickets going to and fro.
Such architectures probably have fairly close analogues in distributed systems, and there may be a thing or two to learn from how more innovative and efficient organizations structured their paper pushing.