提问人:akbiggs 提问时间:9/21/2009 更新时间:9/21/2009 访问量:1237
在 Java 中有效地将向量与一系列数字进行比较
Efficiently comparing a vector to a series of numbers in Java
问:
我有一系列数字,即 6、5、7、8、9、1,通过一些数学过程,我最终将通过重复获得这些数字。出于这个原因,我想使用一个向量来存储此过程产生的最后六个数字,然后将该向量的内容与上面的一系列数字进行比较。如果它与数字序列完全相同,我将结束程序,或者如果不是,则继续数学过程。
我的问题是,我该如何有效地比较数字系列和向量。最初,我打算使用一个简单的 if/else 条件来比较向量中的每个单独值与其在序列中的对应值(例如,其中 v 是一个填充了六个数字的向量,if (v.get(0) == 6 & v.get(1) == 5 ...)),但考虑到在向量等于序列之前,这将被计算多次, 我开始怀疑,与一些替代程序相比,这是否是一个相对昂贵的计算。
我这样做的另一个想法是将一系列数字存储在第二个向量中,然后比较两个向量。但是,由于对向量和 Java 没有经验,我不确定我该如何去做,以及它如何比上面提到的简单的 if 和 else 子句更有效。
关于如何更有效地在一堆数字和向量内容之间进行比较,有什么建议吗?或者,如果不是向量,那么可能是列表或数组?
答:
从数字序列中创建一个哈希值,例如(警告 - 此哈希函数仅用于演示目的):
[N1,N2,N3,N4,N5] -> N1 xor N2 xor N3 xor N4 xor N5.
然后,首先你只需要检查结果向量和原始向量的哈希值,只有当它们匹配时,你才需要比较每个单独的数字。
我猜想,只保留一个向量与目标数字,然后用新生成的数字填充一个新向量,然后遍历它们进行比较,不会太昂贵。您可能在第一个数字上进行了失败的比较,因此只需花费一个比较来检测失败。
似乎无论您使用哪种方法,您都必须收集您的六个数字,因此仅比较整数不会太昂贵。
无论你做什么,请测量!
您应该为比较任务生成至少两种算法并比较它们的性能。选择最快的。
但是,也许第一步是将数学过程的运行时间与比较任务进行比较。如果你的数学过程运行时间是比较的 100 倍或更多,你只需要选择一些简单的东西,不用担心。
如果您只需要对一组数字进行验证,那么直接比较这些数字会更有效。计算哈希值需要您执行一些算术运算,这比比较更昂贵。如果您需要针对多组数字进行验证,则哈希解决方案会更有效。
您应该在这里避免使用 Vector,因为它被实现为线程安全,并且为此有一些开销。请改用 LinkedList 来最大化插入和删除操作,并使用 ArrayList 来最大化随机访问性能。
例:
void repeatedCompute() {
List<Integer> triggerList = new ArrayList<Integer>() {{
add(6);
add(5);
add(7);
add(8);
add(9);
add(1);
}};
List<Integer> intList = new LinkedList<Integer>();
boolean found = false;
while (!found) {
int nextResult = compute();
intList.add(0, nextResult);
if (intList.size() > triggerList.size()) {
intList.remove(intList.size() - 1);
}
if (intList.equals(triggerList)) {
found = true;
}
}
}
int compute() {
return new Random().nextInt(10);
}
比较列表的优点是在第一个元素不匹配后停止比较,您不必触摸所有元素。比较列表非常快!
请注意,&&运算符短路,即只有当左操作数本身不能确定结果时,才会计算右操作数。因此,比较将只考虑那些必要的要素。
然而,我不认为这在任何情况下都会掩盖用于生成你比较的数字的数学计算所花费的时间。使用 jvisualvm 调查时间花在哪里。
评论