0

嗨，我有一门课如下

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

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

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

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

注意：在每种情况下，除了一个数组权利之外的所有权利几乎相同。因此，查找可以深入到数组中。

4

2 回答 2

1

I'm not sure if it's possible, but creating a hash of the contents in your array sounds like a good solution to me. That way you can just compare the hashes instead of iterating the whole array and comparing every individual value.

于 2012-05-22T00:23:36.607 回答
0

Assuming order matters, your algorithm is O(N) worst case. If values tend to be different for different states, the test will generally fail very early while comparing elements of two candidates. If the data were completely random, the performance to compare two states to each other would approach O(1)... the very first array elements would differ most of the time, odds of first two being identical would be much smaller, etc. If you know something about the structure of the data in the array (e.g. maybe most likely to differ at the end?) you can exploit that. Of course of the array lengths can be different, check that before anything else.

If the array is not going to change after initialization, you can precalculate a hash of the array elements. However, unless my first statement does not apply (you will generally get far into the array before detecting a difference), a hash may not be the best option.

于 2012-05-22T00:25:09.293 回答