Things you shouldn't do: Two pointers in one field. • Hacker News Board

Re: Things you shouldn't do: Two pointers in one field.

#11

Post by lsb » Mon, May 17, 2010, 3:36 AM UTC

jacquesm wrote: post #7

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

One of the trickiest 'resource constrained' code I ever did was an index across 100,000 hotels in 64K of RAM on a whole bunch of criteria, 100's of them. From swimming pool presence to dog walking service (and pets permitted or not) and so on. 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…

Sounds like you invented something like a Bloom filter, kudos!

http://en.wikipedia.org/wiki/Bloom_filter

Re: Things you shouldn't do: Two pointers in one field.

#12

Post by jjs » Mon, May 17, 2010, 3:53 AM UTC

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

But maybe you should stick with the Ruby. I hear there's money in that.

Come on, Mike. That sort of snipe just isn't like you.

Re: Things you shouldn't do: Two pointers in one field.

#13

Post by jacquesm » Mon, May 17, 2010, 3:58 AM UTC

lsb wrote: post #11

jacquesm wrote: post #7

Earlier quoted context omitted.

One of the trickiest 'resource constrained' code I ever did was an index across 100,000 hotels in 64K of RAM on a whole bunch of criteria, 100's of them. From swimming pool presence to dog walking service (and pets permitted or not) and so on. 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…

Sounds like you invented something like a Bloom filter, kudos! http://en.wikipedia.org/wiki/Bloom_filter

Hey cool, thanks for digging that up, it certainly looks similar at first glance.

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.

Re: Things you shouldn't do: Two pointers in one field.

#14

Post by lsb » Mon, May 17, 2010, 4:12 AM UTC

jacquesm wrote: post #13

lsb wrote: post #11

Earlier quoted context omitted.

Sounds like you invented something like a Bloom filter, kudos! http://en.wikipedia.org/wiki/Bloom_filter

Hey cool, thanks for digging that up, it certainly looks similar at first glance. 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…

The name of it was on the tip of my tongue as I read your description, so I googled for "probabilistic constant-space test for membership", and voila, first result.

Re: Things you shouldn't do: Two pointers in one field.

#15

Post by jacquesm » Mon, May 17, 2010, 4:16 AM UTC

lsb wrote: post #14

jacquesm wrote: post #13

Earlier quoted context omitted.

Hey cool, thanks for digging that up, it certainly looks similar at first glance. 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…

The name of it was on the tip of my tongue as I read your description, so I googled for "probabilistic constant-space test for membership", and voila, first result.

I bow to your google fu, that would have taken me a week.

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.

Re: Things you shouldn't do: Two pointers in one field.

#16

Post by rsaarelm » Mon, May 17, 2010, 5:59 AM UTC

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

This also reminds me of a story in the StackOverflow podcast (https://stackoverflow.fogbugz.com/default.asp?W24222), where programs executed as expressive bytecode ended up outperforming machine language programs on a low-memory machine, since the more verbose machine code executable was so much larger that parts of it had to be swapped from disk.

Not really at the same level of bit-tweaking as the XOR lists, but a nice bit of counterintuitiveness still.

Re: Things you shouldn't do: Two pointers in one field.

#17

Post by babycakes » Mon, May 17, 2010, 6:20 AM UTC

jrockway wrote: post #6

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

Use half the memory -> buy a smaller memory chip per unit -> spend less per unit -> profit more per unit. 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 the…

> buy a bigger memory chip per unit, adding one dollar to the cost -> charge $1 extra for your $300 unit

Devices containing little enough memory where techniques like this are useful rarely cost $300 per unit.

Re: Things you shouldn't do: Two pointers in one field.

#18

Post by alextingle » Mon, May 17, 2010, 7:15 AM UTC

jrockway wrote: post #6

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

Use half the memory -> buy a smaller memory chip per unit -> spend less per unit -> profit more per unit. 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 the…

There's no reason code using this technique needs to be buggy. You've got a list of things to test for right there.

Re: Things you shouldn't do: Two pointers in one field.

#19

Post by xilun666 » Mon, May 17, 2010, 7:40 AM UTC

jrockway wrote: post #6

novas0x2a wrote: post #4

Someday you might have to program in an actual resource-constrained environment, and you'd understand why sometimes you have to do stupid things to meet your constraints. 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.

Use half the memory -> buy a smaller memory chip per unit -> spend less per unit -> profit more per unit. 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 the…

You seems to think most computers are complicated, with huge amount of memory needing dedicated and scalable components.

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).

Re: Things you shouldn't do: Two pointers in one field.

#20

Post by nostrademons » Mon, May 17, 2010, 8:11 AM UTC

lsb wrote: post #11

jacquesm wrote: post #7

Earlier quoted context omitted.

One of the trickiest 'resource constrained' code I ever did was an index across 100,000 hotels in 64K of RAM on a whole bunch of criteria, 100's of them. From swimming pool presence to dog walking service (and pets permitted or not) and so on. 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…

Sounds like you invented something like a Bloom filter, kudos! http://en.wikipedia.org/wiki/Bloom_filter

I thought "Bloom filter" too as soon as I read his description. They're used all over information retrieval. It's very common to need to hit the disk to say for sure whether an element satisfies your query, but the vast majority of elements don't. If you can eliminate those seeks entirely with a Bloom filter, your algorithm as a whole will run much faster.