我有大量的(> 5GB(二进制文件,这些文件包含每个文件的二进制格式的长数据类型(除其他数据外(。我的查找值很长,想实现二进制搜索算法,以在文件中查找匹配的位置,该位置匹配,大于最近的长值。自定义二进制搜索算法不是问题,
...但是我正在寻求帮助以比较两个二进制阵列,以确定等效的长度值是否相等,更大或小于查找值。显然,我想逃脱,而不必将二进制阵列延长到长时间,否则问题是没有问题。
我可以比较二进制数组并确定代表性长值是相等,较小还是较大,而无需从二进制数组到长时间进行序列化/转换?该解决方案应比类型转换更快,并且具有较小的内存足迹。
我的真正答案是:
- 为了表现足够好,请使用
BitConverter.ToInt64
。 - 为了更好地表现性能,请自己的字节比较比较
这是第二个选择,这似乎很快。您将获得正常-1、0, 1类型的值您从所有比较方法中获得的值,这意味着:
- A vs. B-> -1表示A小于B
- A vs. B-> 0表示A等于B
- a vs. b-> 1表示A大于b
代码:
public static int Compare(byte[] a, byte[] b)
{
bool aIsNegative = (a[7] & 0x80) != 0;
bool bIsNegative = (b[7] & 0x80) != 0;
if (aIsNegative != bIsNegative)
{
if (aIsNegative)
return -1;
return +1;
}
var a7 = a[7] & 0x7f;
var b7 = b[7] & 0x7f;
if (a7 < b7) return -1;
if (a7 > b7) return +1;
var a6 = a[6]; var b6 = b[6];
if (a6 < b6) return -1;
if (a6 > b6) return +1;
var a5 = a[5]; var b5 = b[5];
if (a5 < b5) return -1;
if (a5 > b5) return +1;
var a4 = a[4]; var b4 = b[4];
if (a4 < b4) return -1;
if (a4 > b4) return +1;
var a3 = a[3]; var b3 = b[3];
if (a3 < b3) return -1;
if (a3 > b3) return +1;
var a2 = a[2]; var b2 = b[2];
if (a2 < b2) return -1;
if (a2 > b2) return +1;
var a1 = a[1]; var b1 = b[1];
if (a1 < b1) return -1;
if (a1 > b1) return +1;
var a0 = a[0]; var b0 = b[0];
if (a0 < b0) return -1;
if (a0 > b0) return +1;
return 0;
}
显然如果要使用此代码,则应编写一些良好的单位测试。在您这样做之前,不要信任此代码。
请注意,只有在使用Little-endian字节订单编码数据时才能正常工作。
如果您需要使用大型字节订单,请扭转该方法中的字节顺序,以便7变为0,6变为1,5变为2等。0,这是小东方。使它从0到7的大个子。
像INT64这样的签名的64位编号以64位(位#63(表示标志的方式进行编码,1表示负数,0表示正值。这就是为什么要在检查符号后才需要将第一个字节掩盖到7位的原因。
我测试了以下方法:
- 使用
[StructLayout(LayoutKind.Explicit, Pack=1)]
的结构,并在8个字节字段顶部明确叠加Int64
字段。令我惊讶的是,这确实比所有替代方案都要差。我猜测,所有的字节都在结构中的所有改组都使它更开销。 - 使用bitconvert.toint64,这也令人惊讶的是,这比我预期的要好得多,所以我的建议实际上是这样做的最上方的瓶颈
- 字节比较比较,仅在第一个字节相等的情况下才进入下一个字节。这似乎表现最好
整个代码示例,使用Benchmark.net可以在此要点中找到。
这是10000个测试容器的基准结果,上面的要点还有更多,包括完整的基准日志:
Method | N | Mean | Error | StdDev |
-------------------- |------ |--------------:|--------------:|--------------:|
StructConversion | 10000 | 171,900.82 ns | 544.7975 ns | 482.9487 ns |
ByteForByte | 10000 | 140,844.09 ns | 1,263.6139 ns | 1,181.9851 ns |
ByteForByteUnrolled | 10000 | 125,728.87 ns | 377.4937 ns | 315.2243 ns |
UsingBitConverter | 10000 | 130,397.25 ns | 497.1728 ns | 465.0557 ns |
注意对于1000个元素,byteforbyte和byteforbyteunrolled结果被逆转。我确实在运行时使用了计算机,因此可能会影响结果。买家当心。
使用结构如何?
public class Program
{
[StructLayout(LayoutKind.Explicit)]
struct ValueStruct
{
[FieldOffset(0)]
public byte byte1;
[FieldOffset(1)]
public byte byte2;
[FieldOffset(2)]
public byte byte3;
[FieldOffset(3)]
public byte byte4;
[FieldOffset(0)]
public uint uint1;
}
static void Main(string[] args)
{
var value1 = new ValueStruct() { byte1 = 0x88, byte2 = 0x99, byte3 = 0xAA, byte4 = 0xBB };
var value2 = new ValueStruct() { byte1 = 0x11, byte2 = 0x22, byte3 = 0x33, byte4 = 0x44 };
Console.WriteLine(value1.uint1);
Console.WriteLine(value2.uint1);
if (value1.uint1 > value2.uint1)
{
Console.WriteLine("value1 is greater than value2");
}
Console.ReadLine();
}
}