Things you shouldn't do: Two pointers in one field.
en.wikipedia.org
en.wikipedia.org
Use half the memory -> buy a smaller memory chip per unit -> spend less per unit -> profit more per unit.
But maybe you should stick with the Ruby. I hear there's money in that.
The number of situations where this particular solution is the best solution is really small!
Or: use twice the memory -> buy a bigger memory chip per unit, adding one dollar to the cost -> charge $1 extra for your $300 unit -> spend less money defusing "your product sucks because it crashes all the time" support calls -> profit more per unit.
But maybe you should stick to hand-rolled assembly. I hear there's geek cred in that.
(But actually, there is a middle ground -- something like Atom: http://hackage.haskell.org/package/atom. You get type safety guarantees at compile time, and you get a minimal runtime, lowering hardware requirements.)
Devices containing little enough memory where techniques like this are useful rarely cost $300 per unit.
This is not the case. Most computers are tiny; the kind of "you've only got 1kB built-in and non-expandable memory" tiny (yet only if you're lucky). And most of those computers are indeed programmed correctly, despite using a number of classical trick like xor linked-lists (the program is small, so really checking it, even if it contains tricks, is doable).
Obviously, you can't really do it so I first pre-sorted the hotels with some common criteria in large chunks, then sampled random bits from the rest of the criteria to fill the memory based portion of the index. When a query would come in a mask was made for the various criteria in the same way as during the indexing, and this mask was then used to get the indices of hotels that might be right, candidates so to speak. Then the candidates would be loaded from disk and checked against all the criteria and an answer would be returned to the caller. It worked pretty good, the disk block caching mechanism really saved the day.
This was on a QnX system before they had a 32 bit/large model version...
That's when programming is fun!
Of course 64K is still not really 'constrained' ;)
I can't tell you how many times I've had the feeling that finally I was doing anything at all that was original and then to find out (usually within five minutes, but this time at least a lot of years later) that it was already old hat when I was a toddler.
Oh well. Keep trying I guess.
One problem with stuff like this is simply to find what is out there given a problem description.
At least.
If I would have found it at all. This is one of those areas where I think I can really feel that having English as a first language - or at least a degree in computer science - would have helped tremendously, just knowing the right terminology can be such a huge advantage.
I can parse your description of it but I could never come up with it in those terms. I'd be looking for "compressed index" or "candidate records algorithm" or something like that.
Come on, Mike. That sort of snipe just isn't like you.
Not really at the same level of bit-tweaking as the XOR lists, but a nice bit of counterintuitiveness still.
Brilliant and deadly. Gotta love it.
The advantages are real, and not just space efficiency. You can traverse fwd and bck with identical code, potentially saving code space as well as data space. Although some other logic is more complicated, you might not need those other functions.
Don't forget, many embedded processors have moderate ROM and incredibly restricted RAM. Saving RAM at the expense of ROM can be a sensible trade-off.