0

我有大约 400.000 个“项目”。每个“项目”由 16 个双精度值组成。

在运行时，我需要相互比较项目。因此，我正在复制他们的双重价值。这是相当耗时的。

我进行了一些测试，发现无论我将哪些项目相互比较，都只有 40.000 个可能的返回值。

我想将这些值存储在一个查找表中，以便我可以轻松地检索它们而无需在运行时进行任何实际计算。

我的问题是如何有效地将数据存储在查找表中。

问题是，如果我创建一个查找表，它会变得非常庞大，例如：

 item-id, item-id, compare return value

 1    1    499483,49834
 1    2    -0.0928
 1    3    499483,49834
 (...)

总计大约有 1.2 亿个组合。对于现实世界的应用程序来说，这看起来太大了。

但我不确定如何避免这种情况。

有人可以分享一些很酷的想法吗？

非常感谢！

4

2 回答 2

0

假设我对您的理解正确，您有两个输入具有 400K 的可能性，因此 400K * 400K = 160B 条目...假设您将它们按顺序编入索引，并且您以允许每个 2 个八位字节的方式存储您的 40K 可能性，您重新查看大约 300GB 的表大小......很确定这超出了当前的日常计算。因此，您可以改为研究 400K“项目”之间是否存在任何相关性，如果是，是否可以为该相关性分配某种函数，从而为您提供关于 40K 中的哪一个的线索（阅读：哈希函数）结果可能/可能/应该结果。显然，您的哈希函数和查找需要比首先进行乘法更短。或者也许你可以通过某种智能缩减来减少比较时间，就像在某些情况下知道结果一样。或者也许您的一些数学可以使用整数数学或布尔比较进行优化。只是一些想法...

于 2013-07-25T15:33:54.800 回答
0

为了加快速度，您可能应该计算所有可能的答案，并将输入存储到每个答案中。

然后，我建议制作某种使用答案作为键的查找表（因为答案都是唯一的），然后存储获得该结果的所有可能输入。

为了帮助可视化：

假设您有桌子“桌子”。在 Table 内部，您有键，并且与这些键相关联的是值。您所做的是使密钥具有您的答案所采用的任何格式的类型（密钥将是您的所有答案）。现在，为您的 400k 输入提供一个唯一标识符。然后，您将乘法的唯一标识符存储为与该特定键关联的一个值。当您再次计算相同的答案时，您只需将其添加为可以计算该键的另一组输入。

例子：

Table<AnswerType, vector<Input>>

定义输入，如：

struct Input {IDType one, IDType two}

其中一个“输入”可能具有 ID 12384、128，这意味着由 12384 和 128 标识的对象相乘时将给出答案。

因此，在您的查找中，您将拥有如下所示的内容：

AnswerType lookup(IDType first, IDType second)
{
    foreach(AnswerType k in table)
    {
        if table[k].Contains(first, second)
            return k;
    }
}

// Defined elsewhere
bool Contains(IDType first, IDType second)
{
    foreach(Input i in [the vector])
    {
        if( (i.one == first && i.two == second ) ||
            (i.two == first && i.one == second )
            return true;
    }
}

我知道这不是真正的 C++ 代码，它只是作为伪代码，它是一个粗略的原样，但它可能是一个开始的地方。

虽然 foreach 可能仅限于线性搜索，但您可以通过对输入的存储方式进行排序来使“包含”方法运行二进制搜索。

总之，您正在查看将在 O(n^2) 时间内运行的一次性应用程序，以及将在 nlog(n) 中运行的查找。不过，我并不完全确定在所有这些之后记忆会如何。当然，我对它背后的数学了解不多，所以如果你能以某种方式对键进行排序，你也许可以加快线性搜索。

于 2013-07-25T16:16:45.850 回答