java – 动态编程实现不好或HashMap慢?
发布时间:2020-12-15 02:14:18 所属栏目:Java 来源:网络整理
导读:参见英文答案 How do I write a correct micro-benchmark in Java?????????????????????????????????????11个 我有两种我正在测试的Fibonacci方法.两者都应该是线性的.我不明白memoization或HashMap查找比我想象的要慢. 我知道递归函数不应该通过添加DP来加
参见英文答案 >
How do I write a correct micro-benchmark in Java?????????????????????????????????????11个
我有两种我正在测试的Fibonacci方法.两者都应该是线性的.我不明白memoization或HashMap查找比我想象的要慢. 我知道递归函数不应该通过添加DP来加速,但是因为它是静态的,所以它只需要计算一次(永远不会超出范围).第一次执行后,它从HashMap中检索答案. 我这样做是为了准备实现O(log n)斐波那契函数和基准测试,但是当我看到这个时,我会略微绕道而行. (即使对迭代方法添加memoization也会减慢它的速度). 请赐教,我此刻感觉很傻. 迭代方法: public static int linearIterativeFib(int x) { if (x <= 2) { return 1; } else { int prev = 0; int result = 1; for (int i = 2; i <= x; i++) { int temp = result; result += prev; prev = temp; } return result; } } 递归方法: static Map<Integer,Integer> memo = new HashMap<Integer,Integer>(); public static int linearRecursiveFib(int x) { if (x <= 2) { return 1; } else if (memo.containsKey(x)) { return memo.get(x); } else { int result = linearRecursiveFib(x - 1) + linearRecursiveFib(x - 2); memo.put(x,result); return result; } } 并进行单元测试: @Test public void testSpeed() { int input = 35; long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { fib.linearIterativeFib(input); } System.out.println("Iterative approach took " + (System.currentTimeMillis() - start) + "ms"); start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { fib.linearRecursiveFib(input); } System.out.println("Recursive approach took " + (System.currentTimeMillis() - start) + "ms"); } 返回: Iterative approach took 6ms Recursive approach took 132ms 解决方法
首先,java中的递归比迭代慢.
而不是做包含然后得到,为什么不只是得到并做一个空检查?哈希和铲斗需要计算两次,不确定性能影响有多大. 自动装箱.使用带有原始地图的外部库可能是个好主意,例如gnu Trove.不确定性能增益会是什么,但你会分配更少的对象. 检查性能测量是否合理也是一个好主意.在递归的情况下,第一次或前几次迭代的方式是否比其余的慢?平均值可能不是一个好的衡量标准.有一个延迟直方图会很高兴. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |