存储和检索 512 位数字的最有效方法

本文关键字：有效 方法 数字 检索 存储 | 更新日期: 2023-09-27 17:56:10

我有一个 512 个字符的字符串，只包含 0， 1。我正在尝试将其表示为可以节省空间的数据结构。BitArray是最有效的方法吗？

我还在考虑使用 16 int32 来存储数字，然后是 16 * 4 = 64 字节。

存储和检索 512 位数字的最有效方法

最有效的可能意味着许多不同的事情......

  1. 从内存管理的角度来看最高效？
  2. 从 CPU 计算的角度来看最高效？
  3. 从使用角度来看最有效？（关于编写使用数字进行计算的代码）

对于 1 - 使用 byte[64] 或 long[8] - 如果您不进行计算或不介意编写自己的计算。

对于3来说，绝对BigInteger是要走的路。 你已经定义了数学函数，你只需要将二进制数转换为十进制表示。

编辑：听起来你不想要BigInteger，因为大小问题...但是我认为您会发现您当然必须将其解析为可枚举/收益组合，其中您一次解析一点，并且不会同时将整个数据结构保存在内存中。

话虽如此...我可以帮你把字符串解析成 Int64 的数组...... 感谢王王在这里的部分声明。

// convert string into an array of int64's
// Note that MSB is in result[0]
var result = input.Select((x, i) => i)
                .Where(i => i % 64 == 0)
                .Select(i => input.Substring(i, input.Length - i >= 64 ? 
                    64 : input.Length - i))
                .Select(x => Convert.ToUInt64(x, 2))
                .ToArray();

如果您决定想要不同的数组结构byte[64]或任何应该易于修改的内容。

编辑2：好吧，我很无聊，所以我写了一个EditDifference函数来玩... 给你。。。 

static public int GetEditDistance(ulong[] first, ulong[] second)
{
    int editDifference = 0;
    var smallestArraySize = Math.Min(first.Length, second.Length);
    for (var i = 0; i < smallestArraySize; i++)
    {
        long signedDifference;
        var f = first[i];
        var s = second[i];
        var biggest = Math.Max(f, s);
        var smallest = Math.Min(f, s);
        var difference = biggest - smallest;
        if (difference > long.MaxValue)
        {
            editDifference += 1;
            signedDifference = Convert.ToInt64(difference - long.MaxValue - 1);
        }
        else
            signedDifference = Convert.ToInt64(difference);
        editDifference += Convert.ToString(signedDifference, 2)
            .Count(x => x == '1');
    }
    // if arrays are different sizes every bit is considered to be different
    var differenceOfArraySize = 
        Math.Max(first.Length, second.Length) - smallestArraySize;
    if (differenceOfArraySize > 0)
        editDifference += differenceOfArraySize * 64;
    return editDifference;
}

使用 .NET 中的 BigInteger。它可以轻松支持 512 位数字以及对这些数字的操作。

BigInteger.Parse("your huge number");

BitArray（有512位），byte[64]，int[16]，long[8]（或其中的List<>变体）或BigInteger都将比您的String效率高得多。我想说的是，一般来说，byte[]是表示此类数据的最惯用/最典型的方式。例如，ComputeHash使用 byte[] 和 Stream 处理byte[]，如果将此数据存储为 BLOB 存储在数据库中，byte[]将是处理该数据的最自然方式。出于这个原因，使用它可能是有意义的。

另一方面，如果此数据表示一个数字，您可能会执行数字操作，例如加法和减法，则可能需要使用BigInteger。

这些方法彼此具有大致相同的性能，因此您应该主要根据有意义的内容在它们之间进行选择，其次根据使用中基准的性能进行选择。

最有效的

方法是有八个UInt64/ulong或Int64/long类型变量（或单个数组），尽管这可能不是查询/设置的最佳选择。解决这个问题的一种方法是，实际上，使用BitArray（它基本上是前一种方法的包装器，包括额外的开销[1]）。这是一个选择的问题，要么是易于使用，要么是高效存储。

如果这还不够，您可以随时选择应用压缩，例如 RLE 编码或其他各种广泛使用的编码方法（gzip/bzip/等）。不过，这将需要额外的处理能力。

这取决于您对效率的定义。

[1] 附加开销，如存储开销。BitArray 内部使用 Int32 -array 来存储值。除此之外，BitArray还存储其当前的突变版本，"分配"的整数和同步根的数量。尽管对于较小的值量，开销可以忽略不计，但如果将大量值保留在内存中，则可能会出现问题。

相关文章：