10,000 ints in 1 page of memory (4KB)

http://undiscoveredfeatures.blogspot.com/2010/12/10000-ints-in-1-page-of-memory-4kb.html

by phamilton • 16 years ago

24 12 16 years ago

undiscoveredfeatures.blogspot.com

copper2• 16 years ago

This looks like a very simplified bloom filter made with a very bad hash function. Mind you, though, I am pretty sure I'd never rediscover that particular data structure by myself :)

Jabbles3• 16 years ago

I'm confused. Is 10000 the number of integers or the maximum integer that has to be stored?

I would have thought it (in general) impossible to store more than 2^15/log2(10000)~2500 integers between 1 and 10000 in 4kB, but I look forward to hearing more.

Fargren• 16 years ago

If you know the maximum integer you can receive, you can do a sort of bucket sort, where the Nth bit in the page represents whether you have revceived number N. So yo can store as many numbers as bits you have available.

Jabbles3• 16 years ago

Well obviously. That idea is not (IMO) worthy of a news post. But it doesn't say that the integers are distinct. I'd be interested to hear if it was possible to store numbers in general better than above.

losvedir• 16 years ago

I would have thought it (in general) impossible to store more than 2^15/log2(10000)~2500 integers between 1 and 10000 in 4kB, but I look forward to hearing more.

Yeah, I was thinking about that, too. Something theoretically screams 'No' to me. You have 2^15 bits of storage available, and each number takes log2(10,000) bits, I can't see storing more than the one divided by the other, if each number is equally likely and random.

But! Since we have flexibility in the order in which the integers are stored in the array, could we store a couple "meta integers"? e.g. Could we put our 2,500 integers in the array in such a way that the bits in log2(10,000) locations spell out a 2,501st integer between 1 and 10,000?

I feel like it can't always work: maybe our 2500 integers are just such that there's no way to put them in to spell out the meta integer. OTOH, that's just one scheme I thought of, and perhaps there is a way I'm not thinking of that we can leverage the order in which we put the integers in the array. There might be some free "information" that way that is not being counted by the simple number of bits of storage.

Another thought: Maybe the default ordering of the integers is ascending, and we can break that known ordering in certain places to convey information about the 2501 integer. But then -- what if all the integers given are the same? Sigh.

amccollum• 16 years ago

Yeah, the title is misleading because really the problem described in the blog post is to store some unknown number of ints between 1 and 10,000. The better solution than a straight bitmap of 10,000 bits is to use all 4KB and devote three bits to each slot. Then you can remember up to 7 occurrences of each integer.

There's no need for bloom filters here because you can already cover all the possibilities using a bitmap.

yish• 16 years ago

Additionally you could decide to only store up to 6 occurrences of each integer in the bit array, use the value of 7 as an indicator that there are 7 or more occurrences and store the actual counts for those cases in a sorted array occupied by the remaining 346 bytes left in the 4KB page.

podperson• 16 years ago

The problem is inadequately defined.

Basically it depends on whether you expect to have to record more than 32000 / 14 = 2200 or so values, in which case simply keep a sorted list of the actual integers using a sorting/insertion algorithm of your choice, or you expect to receive fewer than 8 occurrences of a given integer, in which case use a 10,000 x 3-bit deep bitmap, or you don't care how many occurrences of each integer there were, in which case use a 10,000 x 1-bit deep bitmap.

In any event the unintelligible and buggy proposed solution doesn't seem like a good choice.

10,000 ints in 1 page of memory (4KB)

Related Stories