23

This is a hard enough idea to wrap my head around and I would greatly appreciate any edits/help to get it more readable for those in-the-know.

Is it theoretically possible to have a hard drive that has saved on it one copy of every possible binary permutation of one kilobyte and then have the rest of the system simply create pointers to these locations?

Would a system made such a way be any faster than simply having information stored directly?

To explain another way, say instead of having sentences:

"Hello, I'm Bob." and "That sandwich looks delicious."

...stored on the hard drive, we would have all permutations of the alphabet and other characters up to some number (say, 1000 characters or so), and then have store our sentences as something like:

[Pointer#21381723]

Improve this question
5
  • 21
    You may wish to consider How many unique English tweets are possible? How long would it take for the population of the world to read them all out loud?. You are dealing with very big numbers.
    – user40980
    Sep 15, 2015 at 14:55
  • You might find it interesting how git works, called content addressable.
    – JDługosz
    Sep 15, 2015 at 18:54
  • 5
    github.com/philipl/pifs Is based on the same principal as your idea, except instead of having all permutations of a kb, it uses pi.
    – Waxen
    Sep 15, 2015 at 20:30
  • 12
    Your pointers would have to be 1-kilobyte long. You could choose to not store the blocks that don't make sense in English - in which case you've independently reinvented the idea of compression!
    – user253751
    Sep 15, 2015 at 22:42
  • Basic answer is NO - it's impossible due to the # and size of the permutations But what possible application were you thinking it would be useful for if it were possible??
    – Archangel
    Sep 17, 2015 at 3:04

4 Answers 4

Reset to default
91

There are 28192 possible different 1K blocks. Storing them all would take 28202 bits of storage. Since the universe contains only about 1080 (or ~2266) particles, it's a safe bet that it isn't possible to store them all, and you don't have to wonder about whether it would save time or not.

But there is, in fact a more interesting way of answering this. You are suggesting creating an index into a huge pool of constants. But how would you know which index to dereference? Imagine for the sake of an argument that you want to store only 1-character blocks: a, b, c... Presumably your indices would be 0, 1, 2 etc., since that's the most efficient layout of storing those blocks.

Do you notice something about the arrangement? Your index is, in fact, a coded representation of the stored data! In other words, you don't have to dereference at all, you just have to transform the index into the data you want.

When you store all possible values of something in a table, this always happens: your index becomes merely an encoded version of the data itself, so storing the data becomes unnecessary in the first place. This why in the real world, indices are only useful for sparse data (e.g. all web pages you've visited, not all web pages that could exist, or even all that do exist).

Improve this answer
27
  • 17
    So, in a way, we're already using this system - but we're doing it with lazy evaluation of the kilobyte-sized bit patterns, which allows us to save tons of storage space!
    – Theodoros Chatzigiannakis
    Sep 15, 2015 at 17:21
  • 3
    The storage is slightly reduced, due to overlap (1024 zeros followed by 1024 ones contains 1025 unique patterns)... reduced but still impossibly large. Also, a 1KB block is 2<sup>13</sup> bits, not 2<sup>10</sup>.
    – Ben Voigt
    Sep 15, 2015 at 17:59
  • 2
    Note that the 10^80 limit on particles in the universe doesn't directly mean you can't store more than, say, 10^80 bits in the universe - because with each particle you can potentially store more than one bit of information (based on its position within the universe, and possibly its velocity etc). That doesn't mean you can store every 1K block though - the number of those exceeds the number of particles by an astoundingly large factor, so it's still a very safe bet you can't store them all!
    – psmears
    Sep 15, 2015 at 18:36
  • 2
    @Neil If you have a coding system that allows you to store 10^80 by encoding it as "10^80" then how do you store "10^80"? If some pieces of data are encoded shorter than the actual data, others have to be encoded longer. Or if all of your pieces of data are numbers, then you're storing each decimal digit as a whole byte.
    – Random832
    Sep 15, 2015 at 19:06
  • 3
    With de Bruijn sequences 2^1024 bits would suffice.
    – gronostaj
    Sep 15, 2015 at 19:06
20

As others have already pointed out, you have 2^8192 possibilities for a 1k block. This means you would need 8192 bits to encode the address of a block if all blocks addresses are encoded with the same amount of bits, so your addresses would be 1k long. You wouldn't have gained anything except adding a layer of indirection so you wouldn't gain any performance.

If you wanted to have shorter addresses, you would have to encode some blocks with a short address and some with longer ones and make it so that long ones don't appear that often, and you are now simply compressing data (probably with something like a Huffman code). That would require knowledge of the data you're storing before storing it or regular changes in the encoding. It would also probably be less efficient than other compression algorithms which use blocks of varying length.

Improve this answer
1

There are two problems with that.

First, "all possible binary permutations of one kilobyte" is a huge amount of data. 1024 bytes * 8 bits per byte = 8192 bits in a kilobyte. All possible permutations would be 2^8192. That's around 1.09e+2466 kilobytes! (For purposes of comparison, a 1 TB drive is 1e09 kilobytes.)

Second, even if you did have such an enormous table, and you indexed into it with pointers, what would you do if you wanted to reference some data smaller than exactly 1 KB?

Improve this answer
1
  • 2
    Storing all blocks smaller than 1 KB in addition will not take that much more space. Assuming only byte-sized blocks, the size of the smaller blocks together is just slightly over 1/256 of the size of the 1-KB-blocks. Assuming bit-sized blocks, you add about the same size again.
    – Paŭlo Ebermann
    Sep 15, 2015 at 18:33
-1

As other posters have pointed out, at some point, the size of the pointer needed to index into your list of all possible values nullifies your gain.

However, some languages use a limited version of what you suggest in order to optimize memory usage. Python uses string 'interning' to lessen the number of duplicate strings in memory. You can find more information by searching for 'python string intern'.

Improve this answer
1
  • 2
    The OP is asking about a dense set, containing every permutation. Pointers are only useful for sparse data, where the bits required to hold a pointer are smaller than the bits pointed to. Interning can make the space more sparse if there are duplicates, so there's a connection there, but your answer doesn't really phrase it well.
    – Peter Cordes
    Sep 17, 2015 at 3:59

Not the answer you're looking for? Browse other questions tagged or ask your own question.