优化tribools空间的阵列 [英] Optimize an array of tribools for space

问题描述

让我先从一些背景：

通过tribool我明白，可容纳以下值之一的变量：真正，假或空。

By "tribool" I understand a variable which can hold one of the following values: true, false or null.

在问题<一href=\"http://stackoverflow.com/questions/4350041/copying-array-of-ints-vs-pointers-to-bools/\">Copying整数VS指针的bool数组的，则OP想有tribools的阵列（或多或少），这将是尽可能地小。

In question Copying array of ints vs pointers to bools , the OP wanted to have an array of tribools (more or less) which would be as small as possible.

通过一点点最基本的一点福，我想出了使用它每tribool 2位，并允许64 tribools的OP的阵列存储在16个字节的解决方案，这是确定。

With "a bit of" most basic bit-fu I came up a solution which used 2 bits per tribool and allowed to store the OP's array of 64 tribools in 16 bytes, which is OK.

我使用的tribool机制很简单，如：

The tribool mechanics I used were simple, like:

• Boolean一个意思是空还是不空，


• 布尔B表示真或如果不为空假的。

但转念一想......滴滴的algorithmical定义是：

But then I thought... An algorithmical definition of a "bit" is:

A 位是指定哪个两个同样可能事件不得出现的信息量。

A bit is the amount of information which specifies which of two equally probable events shall occur.

显然真/假值为1有点大。两个真假值作为一个整体是2有点大。

Clearly a true/false value is 1 bit big. Two true-false values as a whole are 2 bit big.

和我们的概念tribool什么？

And what about our conceptual tribool?

我的观点是：中所载资料的规模而言，一个tribool大于1位，但小于2位即可。

• 理由1：假设我们实施上述我们如果布尔值。如果布尔A是空，布尔B的价值是多余的，不带有任何相关信息。


• 2理由：这是不可能的，从2个独立的布尔值存储信息于一体tribool，因此它有

（以上都不是正式的证明，但我相信，我们都必须承认，有关的tribool是严格大于1位大并严格小于2的大小。）

(None of the above is a formal proof, but I believe that we can agree that about the "size" of the tribool being strictly bigger than 1 bit and strictly smaller than 2.)

我的问题是：

如何以编程方式采取的一个tribool比2位的信息越少，其实优势，在软件实施（C，C ++？）ñtribools的阵列将有对于在某些N内存占用比 N / 4 字节小？

How to programatically take advantage of the fact that a tribool has less information than 2 bits, and implement in software (c, c++?) an array of N tribools which would have the memory footprint smaller than N/4 bytes for some N?

是的，我不明白，这样的实现是不是真的硬件友好，会比任何冗余的通用解决方案（如OP的问题psented那些$ P $）执行慢。让我们只是优化的空间，没有效率。

Yes, I do understand that such an implementation isn't really hardware-friendly and would perform slower than any common solution with redundance (as those presented in the OP's question). Let's just optimize for space, not for efficiency.

显然，这实施需要一个tribool比一对的bool中的不同重presentation（其本身是多余的，因为之前所描述）。该理论说，这是可能实现这一目标，我希望看到实际的实现。任何想法？

Clearly this implementation needs a different representation of a tribool than a pair of bools (which is by itself redundant, as described before). The theory says it's possible to achieve that goal and I like to see an actual implementation. Any ideas?

推荐答案

您的直觉是正确的，这当然是可能的。这基本上是算术编码的形式，或者至少它的一个简单的实例。

Your intuition is correct, this is certainly possible. This is basically a form of arithmetic coding, or at least a simple instance of it.

想起来最简单的方法就是想象编码基地3你的tribools多项阵列 - 例如0 = FALSE时，1 =真，2 = NULL。然后下面的数组：

The easiest way to think of it is to imagine encoding your array of "tribools" as a number in base 3 - e.g. 0=FALSE, 1=TRUE, 2=NULL. Then the following array:

{TRUE, FALSE, NULL, NULL, FALSE, FALSE, TRUE}

连接codeS到数

encodes to the number

1022001

然后可以转换成以正常方式为十进制：

which you can then convert to decimal in the normal way:

(1*3^0)+(0*3^1)+(0*3^2)+(2*3^3)+(2*3^4)+(0*3^5)+(1*3^6) = 946

每个tribool占用LN（3）/ LN（2）位（约1.58），因此，使用这种方法，你可以存储20 tribools 32位 - 所以你可以存储 N = 20 数组中的4个字节（其中 N / 4 5）。

Each tribool takes up ln(3)/ln(2) bits (about 1.58), so using this method you can store 20 tribools in 32 bits - so you can store an N=20 array in 4 bytes (where N/4 is 5).

这篇关于优化tribools空间的阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！