1

我正在玩纸牌游戏，并且必须在 MySQL 中存储洗牌的牌组。

在单列中存储一副 52 张牌的最有效方法是什么？并使用 PHP 保存/检索那些。

我需要 6 位来表示从 0 到 52 的数字，因此我想将卡片组保存为二进制数据，但我尝试过使用 PHP 的pack函数，但运气不佳。我最好的方法是保存一串 104 个字符（52 个零填充整数），但这远非最佳。

谢谢。

4

1 回答 1

3

我同意这样做没有必要或不切实际，但为了好玩，为什么不这样做；）

根据您的问题，我不确定您是否打算将所有卡片编码为一个值并相应地存储，或者您是否要单独对卡片进行编码。所以我假设前者。

此外，我假设您有一组 52 张卡片（或物品），用 1 到 52 之间的整数值表示。

我看到了一些方法，概述如下，实际上并非都是为了更好地使用更少的空间，而是为了完整而包括在内：

  1. 使用逗号分隔列表 (CSV)，总长度为 9+2*42+51 = 144 个字符
  2. 将每张卡片变成一个字符，即一张卡片用 8 位表示，总长度为 52 个字符
  3. 用那些必要的 6 位对每张卡进行编码，并仅连接这些位而不会丢失 2 位（如在第二种方法中），总长度为 39 个字符
  4. 将卡片 ID 视为多项式中的系数 p(cards) = cards(1)*52^51 + cards(2)*52^50 + cards(3)*52^49 + ... + cards( 52)*52^0 我们用来识别卡片组。粗略地说 p(cards) 必须在 [0,52^52] 的取值范围内，也就是说这个值可以用 log(52^52)/log(2) = 296.422865343.. 位或一个字节来表示长度分别为 37.052 和 38 的序列。

当然还有其他方法，仅考虑实际、技术或理论方面，通过所列方法也可以看出。

对于理论方法（我认为这是最有趣的），了解一些信息论和熵是有帮助的。本质上，根据对问题的了解，不需要进一步的信息，分别只需要澄清所有剩余不确定性的信息。当我们使用位和字节时，我们最感兴趣的是内存使用，实际上是基于位或字节的（如果您只考虑没有底层技术和硬件的位序列）；也就是说，位代表两种状态之一，因此允许区分两种状态。这实际上是微不足道但重要的：/

然后，如果您想在基数 B 中表示 N 个状态，您将需要该基数中的 log(N) / log(B) 数字，或者在您的示例中 log(52) / log(2) = 5.70.. -> 6 位。您会注意到实际上只需要 5.70.. 位，这意味着我们实际上有 6 位损失。这就是问题转换出现的时刻：不是单独表示 52 个状态，而是可以表示整个卡片组。多项式方法是一种方法。本质上它的工作原理是假设基数为 52，即卡片组表示为 1'4'29'31.... 或从数学上讲：52 + 1 = 1'1 == 53 十进制，1'1 + 1 = 1'2 == 54 十进制，1'52'52 + 1 = 2'1'1 == 5408 十进制，

但是，如果您进一步查看多项式方法，您会注意到总共有 52^52 个可能的值，而我们只会使用 52！= 1 * 2 * 3 * ... * 52，因为一旦固定卡片，剩余的可能性就会减少，不确定性或熵就会减少。（请注意 52! / 52^52 = 4.7257911e-22 ! 这意味着多项式完全浪费空间）。

如果我们现在使用 [1,52!] 中的值，这几乎是理论上的最小值，我们可以用 log(52!) / log(2) = 225.581003124.. bits = 28.1976.. bytes 来表示卡片集. 问题在于，任何这样表示的值都不包含任何我们可以从中得出其语义的结构，这意味着对于 52 个中的每一个！可能的值（好吧 52！- 1，如果你考虑排除原则）我们需要一个参考它的含义，即 52 的查找表！值，那肯定是记忆力过大了。

尽管我们可以对编码有序集的熵递减知识做出妥协。举个例子：我们用序列中该点所需的最小位数对每张卡片进行顺序编码。所以假设剩下 N<=52 张卡片，那么在每一步中，一张卡片可以用 log(N)/log(2) 位表示，这意味着所需的位数会减少，直到最后一张卡片，你不需要首先有点。这将给出（请更正）..

20 * 6 位 + 16 * 5 位 + 8 * 4 位 + 4 * 3 位 + 2 * 2 位 + 1 位 = 249 位 = 31.125.. 字节

但是由于不必要地使用了部分位，仍然会有损失，但是数据中的结构完全弥补了这一点。

所以一个问题可能是，我们可以将多项式与这个结合起来吗？？！？11？！其实，我得想一想，我累了。

一般来说，了解问题的结构会极大地帮助减少必要的内存空间。实际上，在这个时代，对于普通的高级开发人员来说，这样的低级考虑并不那么重要（hej，100kByte 的浪费空间，那又怎样！）并且其他考虑的权重更高；还因为底层技术通常会自行减少内存使用量，无论是您的文件系统还是 gzip-ed Web 服务器响应等。不过，这些事情的一般知识仍然有助于创建您的服务和数据结构。

但是后一种方法是针对特定问题的“压缩程序”；一般压缩的工作方式不同，其中作为示例方法，程序顺序运行数据的字节，对于任何看不见的位序列，将它们添加到查找表并用索引表示实际序列（作为草图）。

够了有趣的谈话，让我们获得技术！

第一种方法“csv”

// your unpacked card set
$cards = range(1,52);

$coded = implode(',',$cards);
$decoded = explode(',',$coded);

第二种方法：1 张卡片 = 1 个字符

// just a helper
// (not really necessary, but using this we can pretty print the resulting string)
function chr2($i)
{
    return chr($i + 32);
}

function myPack($cards)
{
    $ar = array_map('chr2',$cards);
    return implode('',$ar);
}


function myUnpack($str)
{
    $set = array();
    $len = strlen($str);
    for($i=0; $i<$len; $i++) 
        $set[] = ord($str[$i]) - 32; // adjust this shift along with the helper

    return $set;
}

$str = myPack($cards);
$other_cards = myUnpack($str);

第三种方法，1 张卡 = 6 位

$set = ''; // target string
$offset = 0;
$carry = 0;

for($i=0; $i < 52; $i++)
{
    $c = $cards[$i];

    switch($offset)
    {
        case 0:
            $carry = ($c << 2); 
            $next = null;
            break;

        case 2:
            $next = $carry + $c;
            $carry = 0;
            break;

        case 4:
            $next = $carry + ($c>>2);
            $carry = ($c << 6) & 0xff; 
            break;

        case 6:
            $next = $carry + ($c>>4);
            $carry = ($c << 4) & 0xff;
            break;      
    }

    if ($next !== null)
    {
        $set .= chr($next);
    }

    $offset = ($offset + 6) % 8;
}

// and $set it is!


$new_cards = array(); // the target array for cards to be unpacked
$offset = 0;
$carry = 0;

for($i=0; $i < 39; $i++)
{
    $o = ord(substr($set,$i,1));

    $new = array();
    switch($offset)
    {
        case 0:
            $new[] = ($o >> 2) & 0x3f;
            $carry = ($o << 4) & 0x3f;
            break;
        case 4:
            $new[] = (($o >> 6) & 3) + $carry;
            $new[] = $o & 0x3f;
            $carry = 0;
            $offset += 6;
            break;
        case 6:
            $new[] = (($o >> 4) & 0xf) + $carry;
            $carry = ($o & 0xf) << 2;
            break;
    }

    $new_cards = array_merge($new_cards,$new);

    $offset = ($offset + 6) % 8;
}

第四种方法，多项式，刚刚概述（请考虑使用 bigints，因为整数溢出）

$encoded = 0;
$base = 52;
foreach($cards as $c)
{
    $encoded = $encoded*$base + $c;
}

// and now save the binary representation


$decoded = array();
for($i=0; $i < 52; $i++)
{
    $v = $encoded % $base;
    $encoded = ($encoded - $v) / $base;
    array_shift($v, $decoded);
}
于 2013-10-02T08:20:20.477 回答