c - 二维数组中最快的搜索算法

Question

所以，我有一个二维数组，int a[X][Y]; X 可以达到 10 000 000 而 Y 最大 6。 给定一个数组 int v[Z] (Z <= Y)，我必须查看是否在 a 中找到包含 v 中所有元素的一行。

最快的算法是什么？您将如何实现？

我已经尝试过逐行获取然后使用 2 个 for 搜索的经典方法，一个用于 v 元素，一个用于 a 元素，但是它花费的时间太长。

最好(最快)的方法是什么？

int check()
{
    int nrfound;

    for (int l = 0; l < lines_counter; l++) for each line in a array
    {
        nrfound = 0;

        for (int i = 0; i < n; i++) { // for each element in v array

            for (int j = 0; j < m; j++) // for each element in a[l] line
                if (v[i] == a[l][j])
                    nrfound++;
            if (nrfound == Z)
                return 0;
        }
    }
    return 1;
}

Answer 1

我看到三件事需要考虑:

• 使用线程。
• 如果可能，在构建int a[X][Y] 表时，我会创建额外的数组int[6][Y]，其中将包含:
  • 包含 1、2、3 .. 6 个元素的索引列表。这可以让您缩小搜索范围。
• 对于每个 X 计数它的值的哈希值。然后统计V值的Hash。
  • 比较哈希码，而不是每个单独的值。