5 ms·

They're 8-digit decimals, not 10, so it works out to 0.96 MiB. I think the parent's solution works. The typical separation between numbers is about 2^7: that w

by uvdiv 14y ago

They're 8-digit decimals, not 10, so it works out to 0.96 MiB. I think the parent's solution works. The typical separation between numbers is about 2^7: that works out to 8 bits per number -- 7 for the length of the '00...0', plus one length-one '1'. 8 bits * 10^6 is 1 MiB exactly. You need a variable-length encoding, so you can fit 2^7 in 7 bits while still allowing larger numbers to be encoded.

jules 14y ago
You're right, I misread that. Still, that's an information theoretic bound, and I'd like to see anybody achieve that. That's not a lot of room to play with until you hit 1 megabyte. Unless you're doing something complicated across multiple numbers, that variable length encoding will already waste 1 bit at which point you're back to 8 bits and already way over budget. Additionally, if I generate a random array, sort it, and compute adjacent differences, then around 30% of the numbers are greater than 2^7.
- emn13 14y ago
  Even though it's almost certainly possible and even practically achievable to compress the required data into the 1MB of space, doing so without using more than 1MB even in temporaries might be impossible. (To get this close to the bound you'll need to use "excess" entropy from one bitpattern to save space in the next; i.e. a delta # doesn't straightforwardly correspond to a bit pattern, but instead depends on context.) Clearly it would be hard, as you say. An argument that you need context info: if you don't use context info, each bit pattern needs to be rounded up to the nearest number of whole bits. That waste's about N/2 bits. According to my calculations, that would raise the bound from 0.96MiB to 1.02MiB, i.e. too much. But really, it's even worse. Let's assume you can indeed define such a compression and you manage to use the context sufficiently to avoid wasting too many bits. Further, you manage to do so without using much temporary space at all. That means you'll need to be updating your sorted list in place. Each update is likely to be a non-trivial task, since you need to find the place to update (with variable-width encoding and no space for luxuries like an index, that's probably a linear scan), and you need to take into account some amount of context - and then, because you've changed some data, recode possibly unbounded amounts (so N) of following context. That makes this sorting algorithm quadratic; and it'll have a high scaling factor too since the operations we're counting here aren't cheap: we're not moving bits around, we're decoding and recoding them all the time in a context-sensitive way and that means doing lots and lots of branches. Assuming the 1MB limit is reasonably inspired because the chip neads to be tiny, you're probably not dealing with the fastest chip in the world. As an estimate, I'd guess this algorithm (if we could make it) would be about 1000000 times slower than a normal sort (assuming a 13 times higher constant factor), and you'd be running it on something very very slow. On a modern processor, a plain sort takes about 75ms, making this thing 75 ks, or approximately 1 day. On that very limited 1MB proc... So even you manage to pull it off (very hard), it's almost certainly going to be very slow.
ChuckMcM 14y ago
There is fairly intuitive way to reason about the storage requirement. Lets start with you've seen no numbers in the range, you have the tuple (99,999,999, 0). That is two 32 bit numbers or 8 bytes of storage. Now lets say you've seen all the numbers in the range, you've got (0, 99,999,999), again 8 bytes of storage, two 32 bit numbers. Since we're describing a linear bit field, the worst case is : (1,1,1,1,1,1,1,1,1, ... 1,0) every odd number and none of the even numbers. So the memory to encode the virtual bit field will be (assuming 32 bit numbers always) 4 bytes * n where 'n' is the number of distinct regions in the bit field. With a perfectly uniform random number generator each number generated has possible outcomes: 1) It splits a region (it causes a string of zeros to have a one in them) (adds 8 bytes) 2) It coalesces a region (it removes the last remaining zero between two regions) (subtracts 8 bytes) I'm sure there are other solutions, and as was pointed out it doesn't really deal with duplicates. I suspect a multi-value bit field might cover that.
- jules 14y ago
  With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, and you'll end up with 8 bytes * 10^6 = 7.6 megabytes. So indeed the chances of this working for a random sequence are extremely slim. You have to have a huge number of coalesces, which is just extremely unlikely when you choose 10^6 random numbers in a range of 10^8. So for almost all inputs this method doesn't work. I simulated it with a Python program and you get about 10^4 coalesces. That doesn't even begin to make a dent in 10^6, and storing this will still take ~7 megabytes.
  - uvdiv 14y ago
    With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, Right. and you'll end up with 8 bytes x 10^6 = 7.6 megabytes. Not if you encode cleverly. The successive differences will be on the scale of 10^8/10^6 = 100, which is a very small number. It takes 7 bits to store, or at least 8 bits in a variable-width encoding.
    - jules 14y ago
      Sure, if you encode cleverly. That is the essential difficulty of the problem which he glosses over (note that he explicitly says that he will store the differences as 4 byte numbers). Getting it under 1.5MB (or even 1.1MB) is probably easy, but I have yet to see an encoding which is sufficiently compact to fit in 1MB.

by uvdiv 14y ago

jules 14y ago

You're right, I misread that. Still, that's an information theoretic bound, and I'd like to see anybody achieve that. That's not a lot of room to play with until you hit 1 megabyte. Unless you're doing something complicated across multiple numbers, that variable length encoding will already waste 1 bit at which point you're back to 8 bits and already way over budget. Additionally, if I generate a random array, sort it, and compute adjacent differences, then around 30% of the numbers are greater than 2^7.

emn13 14y ago
Even though it's almost certainly possible and even practically achievable to compress the required data into the 1MB of space, doing so without using more than 1MB even in temporaries might be impossible. (To get this close to the bound you'll need to use "excess" entropy from one bitpattern to save space in the next; i.e. a delta # doesn't straightforwardly correspond to a bit pattern, but instead depends on context.) Clearly it would be hard, as you say. An argument that you need context info: if you don't use context info, each bit pattern needs to be rounded up to the nearest number of whole bits. That waste's about N/2 bits. According to my calculations, that would raise the bound from 0.96MiB to 1.02MiB, i.e. too much. But really, it's even worse. Let's assume you can indeed define such a compression and you manage to use the context sufficiently to avoid wasting too many bits. Further, you manage to do so without using much temporary space at all. That means you'll need to be updating your sorted list in place. Each update is likely to be a non-trivial task, since you need to find the place to update (with variable-width encoding and no space for luxuries like an index, that's probably a linear scan), and you need to take into account some amount of context - and then, because you've changed some data, recode possibly unbounded amounts (so N) of following context. That makes this sorting algorithm quadratic; and it'll have a high scaling factor too since the operations we're counting here aren't cheap: we're not moving bits around, we're decoding and recoding them all the time in a context-sensitive way and that means doing lots and lots of branches. Assuming the 1MB limit is reasonably inspired because the chip neads to be tiny, you're probably not dealing with the fastest chip in the world. As an estimate, I'd guess this algorithm (if we could make it) would be about 1000000 times slower than a normal sort (assuming a 13 times higher constant factor), and you'd be running it on something very very slow. On a modern processor, a plain sort takes about 75ms, making this thing 75 ks, or approximately 1 day. On that very limited 1MB proc... So even you manage to pull it off (very hard), it's almost certainly going to be very slow.

ChuckMcM 14y ago

There is fairly intuitive way to reason about the storage requirement. Lets start with you've seen no numbers in the range, you have the tuple (99,999,999, 0). That is two 32 bit numbers or 8 bytes of storage. Now lets say you've seen all the numbers in the range, you've got (0, 99,999,999), again 8 bytes of storage, two 32 bit numbers. Since we're describing a linear bit field, the worst case is : (1,1,1,1,1,1,1,1,1, ... 1,0) every odd number and none of the even numbers. So the memory to encode the virtual bit field will be (assuming 32 bit numbers always) 4 bytes * n where 'n' is the number of distinct regions in the bit field. With a perfectly uniform random number generator each number generated has possible outcomes: 1) It splits a region (it causes a string of zeros to have a one in them) (adds 8 bytes) 2) It coalesces a region (it removes the last remaining zero between two regions) (subtracts 8 bytes) I'm sure there are other solutions, and as was pointed out it doesn't really deal with duplicates. I suspect a multi-value bit field might cover that.

jules 14y ago
With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, and you'll end up with 8 bytes * 10^6 = 7.6 megabytes. So indeed the chances of this working for a random sequence are extremely slim. You have to have a huge number of coalesces, which is just extremely unlikely when you choose 10^6 random numbers in a range of 10^8. So for almost all inputs this method doesn't work. I simulated it with a Python program and you get about 10^4 coalesces. That doesn't even begin to make a dent in 10^6, and storing this will still take ~7 megabytes.
- uvdiv 14y ago
  With 10^6 random numbers between 0 and 10^8 almost all operations will be splits, Right. and you'll end up with 8 bytes x 10^6 = 7.6 megabytes. Not if you encode cleverly. The successive differences will be on the scale of 10^8/10^6 = 100, which is a very small number. It takes 7 bits to store, or at least 8 bits in a variable-width encoding.
  - jules 14y ago
    Sure, if you encode cleverly. That is the essential difficulty of the problem which he glosses over (note that he explicitly says that he will store the differences as 4 byte numbers). Getting it under 1.5MB (or even 1.1MB) is probably easy, but I have yet to see an encoding which is sufficiently compact to fit in 1MB.