ConcurrentHashMap и числа Фибоначчи - непоследовательный результат
Я написал программу для вычисления чисел фибоначчи рекурсивно с помощью метода ConcurrentHashMap и computeIfAbsent():
Программа работает абсолютно нормально, когда я использовал небольшие значения, такие как 8,9,10, но застрял в бесконечном цикле, когда значение, увеличенное с 10 to 20 , никогда не останавливается
public class Test {
static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>();
public static void main(String[] args) {
System.out.println("Fibonacci result for 20 is" + fibonacci(20));
}
static int fibonacci(int i) {
if (i == 0)
return i;
if (i == 1)
return 1;
return concurrentMap.computeIfAbsent(i, (key) -> {
System.out.println("Value is " + key);
return fibonacci(i - 2) + fibonacci(i - 1);
});
}
}
Может кто-нибудь сказать мне, почему он застрял навсегда?
Ответы
Ответ 1
Вы зашли в тупик.
computeIfAbsent на ConcurrentHashMap заблокирует ведро, в которое будет идти соответствующий ключ. Если вы пытаетесь вычислить Fibonacci, который больше, чем количество ковшей на вашей карте, тогда рекурсивные вызовы будут пытаться заблокировать ведро, которое уже заблокировано дальше в стеке вызовов. Но, конечно, эта блокировка не может быть выпущена до тех пор, пока все рекурсивные вызовы не будут завершены. Таким образом, ваш тупик.
Я бы пересмотрел ваше решение использовать ConcurrentHashMap здесь.
Ответ 2
Этот метод рекурсии для вычисления числа фибонаксов имеет экспоненциальную сложность. С кэшированием вы уменьшаете его до линейного, или вы можете использовать простой цикл вместо рекурсии для получения линейного алгоритма.
Интересно, почему вы используете ConcurentHashMap для кеширования. Я бы использовал либо простую карту, либо массив для кэширования.
Карты имеют преимущество против массивов, когда значения являются разреженными, но когда у вас есть последовательность чисел, вы можете использовать простой массив.
Ответ 3
Я взял дамп потока, и мы видим, что поток с блокировкой 0x000000076b70bba0 вызывает проблему с мертвой блокировкой.
Пожалуйста, исправьте меня, если я ошибаюсь.
main - priority:5 - threadId:0x00000000021af000 - nativeId:0x2798 - state:RUNNABLE
stackTrace:
java.lang.Thread.State: RUNNABLE
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
- locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c720> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c5c0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c460> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c300> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c1a0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70c040> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70bee0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.lambda$0(Test.java:20)
at Test$$Lambda$1/834600351.apply(Unknown Source)
at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660)
- locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode)
at Test.fibonacci(Test.java:18)
at Test.main(Test.java:8)
Locked ownable synchronizers:
- None
Ответ 4
В соответствии с Oracle Doc
Некоторые попытки выполнить операции обновления на этой карте другими потоками могут быть заблокированы, пока выполняется вычисление, поэтому вычисление должно быть коротким и простым и не должно пытаться обновлять любые другие сопоставления этой карты
Как справедливо сказано Joe C в самом верхнем ответе, инициализация по умолчанию ConcurrentHashMap имеет небольшое количество ведер, выделенных во время создания экземпляра.
Цель использования ConcurrentHashMap - разрешить одновременную модификацию Карты из нескольких потоков без необходимости их блокировки (ссылка).
Если вы все еще хотите остаться с помощью ConcurrentHashMap для своего приложения, я бы рекомендовал увеличить начальную емкость при ее создании.
static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>(11);
может рассчитать ряд Фибоначчи и включить 25
В соответствии с документом
ConcurrentHashMap()
Создает новую пустую карту с начальным размером таблицы по умолчанию (16).
Тем не менее, я прошу разницы в этом, поскольку я заметил, что размер по умолчанию намного меньше.
Причина этого в том, что вы получаете fibonacci(25) от ConcurrentHashMap<>(11), тогда ConcurrentHashMap<>() < - должно быть по умолчанию здесь 16, но это не так.
