That rule of thumb is from Jim Gray:
http://en.wikipedia.org/wiki/Jim_Gray_(computer_scientist)
It's held true for a long time. Like any rule of thumb, at some point it may no longer be correct, but we're not at that point yet.
3,480 karma · joined December 7, 2009
https://www.linkedin.com/in/davidwstafford
https://x.com/davidstafford
https://facebook.com/davidst
http://en.wikipedia.org/wiki/Jim_Gray_(computer_scientist)
It's held true for a long time. Like any rule of thumb, at some point it may no longer be correct, but we're not at that point yet.
Ten years ago a typical workstation had around 32GB of disk storage. Today, 32GB of RAM in a workstation is perfectly ordinary.
Take the size of your local disk space today. Ten years from now that will be the amount of RAM in your computer.
It's true. One of the characteristics I always looked for when interviewing programmers was whether they were open to other ways of doing things or whether they fixated on the first solution that presented itself. The best programmers are always looking for a better way.
A Bloom filter is a great data structure but probably not the best choice for this problem. It's not as memory efficient as you think.
Here's why: Think of a Bloom filter as a collection of hash values where each individual hash value is expanded by 44%. The cost of maintaining the same false positive rate of an explicit log2(n) hash is to use 1.44log2(n) bits (see http://en.wikipedia.org/wiki/Bloom_filter for more detail.) So, if you want a false positive rate of 1 in 64k you could store a 16-bit hash in an array or a 23-bit hash in a Bloom filter. That's a significant tax to pay when memory is tight.
In this case it's better to keep a bit array of explicit hashes than to use a Bloom filter.
An array of hashes gives you some options to make it smaller:
1. Sort the array by hash value and store only the differences using a delta coding scheme. The downside is you have to search the entire array (or maintain some indexes into it) to look up a single word.
2. Break the array up into sub-arrays where each sub-array is chosen so the first N bits of the hash are the same (and discarded.) Each sub-array uses a smaller hash value and can still be binary searched.
Of course, strip prefixes and suffixes from the words so the number of hashes that must be stored is reduced.
1.5 bytes per word is easy and with some work you can approach one byte per word with a low error rate.
If you're allowed to do off-line preprocessing on the word list you can do better.
Look up the history of Doug McIlroy's Unix spell checker. He got 75,000 words to fit in about 52k (going from memory here and my copy of Bentley's "Programming Pearls" is at home.) McIlroy traded away random access and had a fairly high error rate to get that much compression. Essentially, what he did was to create a large 1-bit Bloom filter and delta-encoded the differences between set bits (similar to option #1 above.)
If you want to maintain fast random access for individual words you can do this with a Directed Acyclic Word Graph (DAWG). A simple DAWG with fixed node sizes and no stemming of any kind will get two bytes per word on English. Add variable node sizes, stemming and a few other tricks and you can have fast lookup with a near-zero error rate at a cost of about one byte per word.
The discussion here brings back a lot of fond memories. The Apple II was a great computer and easy for a teenager to understand. Source was available for almost everything (and what wasn't officially available had been disassembled and documented with high quality.)
Here's something other HN members might enjoy: Got access to an old Apple with Applesoft BASIC? Try this:
CALL -151
300: AD 30 C0 E6 B8 D0 02 E6 B9 4C B7 00
B1: 4C 00 03
3D0G
VideoRoulette is a sample app for the metadata labs video fire hose API.
In the early/mid 90s I built a compressor called Quantum that outperformed PKZip by an average of 20% to 30%. For a few years it was the best-performing general-purpose compressor available.
Microsoft, Borland, Novell and a handful of other companies licensed it. Cumulatively it saved them hundreds of millions of dollars in cost-of-goods for disks.
My smaller mistake was to not apply for a patent. Quantum was the first compressor with a workable implementation of optimal parsing and about half of the improvement over PKZip was due to it. I was then (and still am) philosophically opposed to software patents but purely from a business standpoint possessing a patent on optimal parsing would have made it difficult for competitors. That said, I don't view the decision to not apply for a patent as being a mistake as much as a deliberate choice.
My bigger mistake was to ignore the retail market. I felt that PKZip owned that and going up against them would be foolish. Instead, I took the low-hanging fruit of selling to software publishers. It was a handful of boutique sales (which one man could do) instead of attempting to penetrate the retail market against a strong, established competitor (which seemed intimidating.)
Except... I was completely wrong. PKZip never made a concerted effort to build a usable Windows version of their product. Phil Katz didn't like Windows and so PKWare was slow to evolve the product from a shell wrapped around the DOS tool into a first-class Windows app.
The world needed an easy-to-use compressor for Windows. An improved UI and support for additional compression formats extended beyond the scope of my original product but I could have done it without difficulty and I rejected the idea for the wrong reasons.
The market was ripe for the taking yet I cleverly convinced myself it wasn't worth trying and settled for less. Fortunately for WinZip they didn't make the same mistake and they quickly rose to a dominant position.
I've come to believe that people who create startups must be, by definition, entirely unqualified for the job. If they were truly qualified they would have some idea of what they were getting themselves into and they would avoid it. Hence, only unqualified people embark on the adventure.
There is, however, an up-side to being unqualified:
The young do not know enough to be prudent, and therefore they attempt the impossible, and achieve it, generation after generation. -- Pearl S. Buck
The young and foolish change the world.
Here's one: How to deal with the police. Their work is boring and it's not unusual for them to go long stretches of time without being paid. They see you coming up the road-- They're curious and you look interesting. They motion for you to pull over and unless you've managed to get so close that you can plausibly claim you didn't see the baton waving you'd better obey them.
The hack: For goodness sake don't sit their dumbly and wait for them to speak up! If you do they'll have to justify pulling you over. "Document!", and you're screwed. The next thirty minutes are spent going through your papers and your belongings while they look for any pretense to hit you up for a fine/bribe. Yes, it's corrupt, but understand that is the only way of life for them. Empathy and understanding will get you much further than casting judgment.
Be the first to speak. Raise your helmet visor, smile and ask for help of some kind. Even something as simple as, "Skolka kilometer Volgograd?" will do. When they answer, nod, smile, shake their hand and say, "Speciba."
There's a 75% chance you're done and you can go on your way. The remaining 25% involves a longer conversation with limited English (and compliment them on their English no matter what) and pointing out your route on a map and where you're going. They may offer you a drink or to share a meal. Feel free to do so if you have time.
I never once paid a bribe which must be some kind of record.
They answer, "10 bits."
"How many base 10 digits do you have in the counter?"
"Three."
"How many bits did you need for each digit?"
Everyone gets it. Explaining arithmetic coding is then much easier.
"The heights of great men reached and kept, were not obtained by sudden flight, but they, while their companions slept, were toiling upward in the night."
If it's friendship then don't involve lawyers (that will almost certainly end it) and find a way to part under terms such that you can remain friends. In this case don't worry about plus or minus ten percent. It won't matter. Go your separate ways and preserve your mutual peace-of-mind.
No, Cuckoo hashing is a trade of a little run-time performance for better memory utilization. It's still O(1). The performance cost amortizes as a constant.
If you have gobs of memory you don't need it. But if you're memory-constrained it's a big win.
The article does not claim that Huffman coding was superseded by dictionary methods. It does not confuse statistical modelling with encoding.
> Even the stereotypical "impractical" research algorithms > (with efficient complexity but huge constants) are > implemented.
Well, they're all Turing machines, but you're not going to find any video processing algorithms that were implemented on a 4K Altair so let's not go too far.
It's interesting to consider a given novel idea and wonder how far back in time it would have been possible to implement it in a practical way and how much further back in time it would have been useful simply to know how it works.
Let me pick a concrete example that we are all familiar with: Hashing. Hashing and hash lookup algorithms have been around a long time. It's an area that people might expect would have been exhausted of significant new ideas long ago. Not so! Cuckoo hashing was invented in 2001 and gives us dramatically more efficient use of memory at a slight performance cost. It can make the difference between a hash table that fits in memory and one that doesn't so it's a meaningful advance.
Cuckoo hashing could have been implemented on a 4k Altair and it would have been useful there. But no one had the idea then.
But wait-- It gets stranger! Cuckoo hashing was literally under our noses and somehow no one saw it! It is a variation of set associative hashing which is what most CPUs had already been doing in their caches for years. It's not exactly the same algorithm but if you check you'll see it's so close the distinctions are minor.
Fascinating, isn't it? Here is an important algorithm that was actually live and running in hardware yet no one considered building it in software for a long time.
Lempel and Ziv's critical insight - that modelling and coding of probabilities are distinct and separable - could have been understood decades earlier. It wouldn't have mattered that their research couldn't be immediately turned into a working tool. Information Theory would have benefitted and we would surely be further along today.
But, yes, it is certainly true that advances in technology give us an incentive to ask questions that had previously been ignored or misunderstood.
http://en.wikipedia.org/wiki/Cuckoo_hashing http://www.ru.is/faculty/ulfar/CuckooHash.pdf
You can get your hash table utilization to almost 100%. If you're willing to accept a 64-bit hash function and you have 2 billion unique strings you'll need just over 16GB to do it all in one pass.
A 64-bit hash is is just barely enough for 2 billion items. You might get a handful of collisions. Add more bits to reduce the probability. 128-bits would double the required size to 32GB but you're unlikely to ever see a collision in your life time.
If 16GB or 32GB is too much you could do it in multiple passes. Make N passes through the text file and adjust the range of hash values you accept to test only 1/N each time.
8 passes through the original file with a generous 128-bit hash would take only 4GB of RAM.
I have the feeling this is more work than you would want to put into the problem, though.
How much memory do you have available?
The Bloom filter is a good way to go. Here is one possibility:
If you have 2 billion unique lines here's how much memory you need for a Bloom filter:
Error rate Memory
------------ --------
1 / thousand 3.35 GB
1 / million 6.70 GB
1 / billion 10.05 GB
1 / 10 billion 11.16 GB
1 / 100 billion 12.28 GB
If you have 12 GB available you can reduce the chance of missing a unique string down to almost zero.
Good advice: There is no substitute for investing with your own money. Investment simulators are absolutely to be avoided.
Hard truth: It will take years but investing will teach you much about yourself that you don't know (and some of it will not be flattering but you will eventually come to grips with it.) Knowing yourself will eventually make you a better investor and thinker.