c# 匹配内存数据中的固定属性

Question

伙计们，这让我绞尽脑汁

我在 Linq 中有一个缓慢的实现，我需要加快速度。

我需要尽可能快的方法来比较内存(200,000)行中的大量只读数据。

每一行都有一个名字和10个代表名字属性的整数

Brake   8 7 3 2 1 0 4 3 2
Skull   8 7 3 2 1 0 4 3 2
Napkin  3 0 5 3 2 1 3 1 0

在任何单一属性中，每件商品的数量永远不会超过 8 个。所以每个值都可以很好地适合 double

例如:

Brake:873,210,432

现在我的问题是我需要将这些值与每个字段的最大数量进行比较

即:

500,000,000 将返回前 2 个和

000,001,000 只会返回 Napkin，因为其他 2 个在第 4 个位置没有至少 1 个。

我愿意接受任何尽可能快速 的解决方案。会有很多比较，所以速度是我在这里唯一担心的事情。

我目前的实现是这样的:

Items.Where(c => c.A <= 5).Where(c => c.B <= 0).Where(c => c.C <= 0)
.Where(c => c.D <= 0).Where(c => c.E <= 0).Where(c => c.F <= 0)
.Where(c => c.H <= 0).Where(c => c.I <= 0).Where(c => c.J <= 0)

或者(它们的运行速度大致相同)

Items.Where(c => c.A <= 5 && c.B <= 0 && c.C <= 0
 && c.D <= 0 && c.E <= 0 && c.F <= 0 && c.H <= 0
&& c.I <= 0 && c.J <= 0)

Answer 1

实际上，有比我原来的答案更好的方法，但它需要每项 5 位而不是每项 4 位。我将用 16 位值中的三个项目来说明它。您可以使用长整数的前 50 位将其扩展到 10 项。

假设您将三个 4 位计数器保存在一个 16 位整数中。每个计数器都有一个用于计算的附加位(见下文)。因此，您的前三个计数器的 Brake 项目将是:

       3     7     8
Brake 00011 00111 01000

现在，您需要匹配“504”的内容，即第一列中至少有五个项目，第二列中有任意数字，第三列中至少有四个。该掩码将是:

         4     0     5
Search 00100 00000 00101

从逻辑上讲，我们想从 Brake 中减去 Search，并知道是否所有必填字段都大于或等于零。这就是额外位的用武之地。如果我们在每个字段上设置额外位，我们有:

Brake 10011 10111 11000

现在，如果我们在这种情况下做减法，我们最终会得到:

Brake - Search = 01111 10111 10011

请注意，结果最左侧字段的高位为 0。这表明制动值该字段中的数字小于我们要查找的值。

现在，如何在代码中实现这一点。在我的示例中，使用 short，我会:

short Brake = (short)((3 << 10) | (7 << 5) | 8);
short Search = (short)((4 << 10) | (0 << 5) | 5);

short CarryMask = 0x4210;  // sets the high bit in each field.
                           // corresponds to 0100001000010000

// This would have to be done for each value that you want to compare.
short MaskedValue = (short)(Brake | CarryMask);
short diff = (short)(MaskedValue - Search);
short rslt = (short)(CarryMask & diff);

// rslt should equal CarryMask
if (rslt == CarryMask)
{
    // All fields match
}
else
{
    // At least one field doesn't match
}

您可以通过查看 rslt 中的位来确定哪些字段不匹配。每五位(即位 4、9 和 14)应为 1。如果该位为 0，则该字段不满足最小值。

所以要比较单个项目，你必须进行三个操作和一个比较。这将比我之前的回答快很多。

实现

下面的实现假定您在一个字节数组中为每个名称拥有 10 个值。第一个方法 CreateValue 构建一个代表这 10 个值的长整数。

long CreateValue(byte[] values)
{
    // probably should check here to ensure that values is 10 bytes long.
    long val = 0;
    foreach (var b in values)
    {
        // do error check. If b > 15, then this is going to fail.
        val = (val << 5) | b;
    }
    return val;
}

我假设您的数据采用某种格式，您可以方便地将每个项目的字段值放入一个 10 字节的数组中。您需要添加一个保存组合值的 CombinedValue 属性。或者您可能有一个并行数据结构来保存组合值。无论如何，您必须在程序启动时执行此循环一次以创建您将用于比较的数据(或者如果您可以更新各个字段，则可能更新值)。

foreach (var item in DataItems)
{
    byte[] values = GetValuesFromItem(item);
    // if you can't store it in the item, put it in a parallel array or list.
    item.CombinedValue = CreateValue(values);
}

我也假设，当需要搜索时，您可以将要查找的值放入一个字节数组中，然后调用 CreateValue 来获取您要查找的组合值正在寻找。现在您所需要的只是进行比较的方法。

// Carry mask has every 5th bit set.
// This is actually the mask for 12 values.
// That's okay, since nothing will affect those higher bits.
const long CarryMask = 0x842108421084210L;

bool ItemMatches(long itemValue, long searchFor)
{
    long maskedValue = itemValue | CarryMask;
    long diff = maskedValue - searchFor;
    long rslt = diff & CarryMask;
    return (rslt == CarryMask);
}

然后，搜索您的列表变得非常简单:

long searchFor = CreateValue(array_of_values);
foreach (var item in items)
{
    if (ItemMatches(item.CombinedValue, searchFor)
    {
        // The item matches the criteria you specified
    }
}