在以大型数组作为成员元素的列表中高效查找对象

本文关键字：列表 高效 对象 查找 元素 成员 大型 数组 | 更新日期: 2023-09-27 18:34:48

嗨，我有一个如下类

class State
{
    int[] some_array;
    //some other members
}

现在我需要比较两个 State 对象是否相同。如果两个状态具有相同的some_array 而不考虑对象的其他成员，我将两个状态定义为相同。

现在我有一个包含数千个 State 对象的列表。如何通过查找有效地获取一个状态并找出列表中存在另一个类似的状态？

我可以将列表中每个状态元素的some_array数组与给定的状态对象进行比较。但这需要如此多的计算 O(N*大小some_array(。如何用最少的计算来做到这一点？

注意：在每种情况下，除一个阵列授权外，其他所有授权几乎相同。因此，查找可以深入到数组中。

在以大型数组作为成员元素的列表中高效查找对象

我不确定这是否可能，但是在数组中创建内容的哈希对我来说听起来是一个很好的解决方案。这样，您可以只比较哈希值，而不是迭代整个数组并比较每个单独的值。

假设顺序很重要，你的算法是O(N(最坏的情况。 如果不同状态的值往往不同，则在比较两个候选元素时，测试通常会很早就失败。 如果数据是完全随机的，则比较两个状态的性能将接近O(1(...第一个数组元素大部分时间会有所不同，前两个元素相同的几率会小得多，等等。 如果你对数组中数据的结构有所了解(例如，最后最有可能有所不同？(，你可以利用它。 当然，数组长度可以不同，请在其他任何事情之前检查一下。

如果数组在

初始化后不会更改，则可以预先计算数组元素的哈希。 但是，除非我的第一句话不适用(在检测到差异之前，您通常会深入数组(，否则哈希可能不是最佳选择。

相关文章：