小整数向量的高效比较

Question

我有小载体。它们中的每一个都由 10 个介于 0 和 15 之间的整数组成。这意味着向量中的每个元素都可以使用 4 位来写入。因此，我可以连接我的矢量元素并将整个矢量存储在单个 long 类型中（在 C、C++、java...）

如果对于 0,...,9 中的每个 i，v1[i] >= v2[i]

，则向量 v1 支配向量 v2

我想写一个方法 compare(long v1, long v2) 如果没有一个向量支配另一个向量，它将 return 0，如果第一个向量支配则为 1，如果第二个向量支配则为 -1。

除了获取每个 i 分量并进行 10 次正常整数比较之外，是否有任何有效的方法来实现比较？

编辑

如果 v1 与 v2 完全相同 returning 1 或 -1 都可以

Answer 1

好吧，在 C 中，您可能可以利用矢量化来执行此操作。我不认为直接比较 4 位操作数是可能的，所以你将不得不重新打包（要么在运行中，要么只是将你的数据保持在更合适的格式）最多 8 位，然后再做比较。由于 10 * 8 = 80 大于 64，因此您将需要 128 位向量指令。

不确定 Java VM 是否支持，但是 this question suggests that JNI is the answer，即从 Java.

调用 C 代码

Answer 2

可以使用位操作来做到这一点。 Space 输出你的值，每个值占用 5 位，其中 4 位用于值，最重要位置的空 0 作为一种间隔位。

在每个值之间放置一个间隔位会阻止 borrows/carries 在相邻值之间传播，这意味着您只需使用常规整数加法或减法即可对向量执行某些类似 SIMD 的算术运算。我们可以使用减法来做向量比较。

要进行测试，您可以将其中一个向量中的所有间距位设置为 1，然后减去第二个向量。如果间隔位下面的 4 位中的值在第二个中更大，那么它将从间隔位中携带该位并在结果中将其设置为零，否则它将保持为 1（第一个值更大大于或等于第二个）。如果第一个向量支配第二个向量，则所有间隔位在减法后都将是一个。

使用整数的简单演示：

#define SPACING_BITS ((1<<4)|(1<<9)|(1<<14)|(1<<19))
int createVector(int v0, int v1, int v2, int v3)
{
    return v0 | (v1 << 5) | (v2 << 10) | (v3 << 15);
}

int vectorDominates(int vectorA, int vectorB)
{
     // returns 1 if vectorA dominates vectorB:
     return (((vectorA | SPACING_BITS) - vectorB) & SPACING_BITS) == SPACING_BITS;
}

int compare(int vectorA, int vectorB)
{
    if(vectorDominates(vectorA, vectorB))
        return 1;
    else if(vectorDominates(vectorB, vectorA))
        return -1;
    return 0;
}

您可以将其扩展为使用 64 位值，使用 50 位来存储 10 个值。您还可以在比较函数中内联对 vectorDominates 的调用。

Demo

小整数向量的高效比较

Efficient comparison of small integer vectors

c

integer

compare

bit-manipulation

string-comparison