Почему мой простой кеш не работает?

-2

У меня есть кусок кода, который я написалПочему мой простой кеш не работает?

private int CountChangeOptions(int[] coins, int j, int N) 
{ 
    if(j == 0) 
     return 0; 
    if(N == 0) 
     return 1; 
    if(j == 1) 
     return N % coins[0] == 0 ? 1 : 0; 

    int sum = 0; 
    int k = coins[j - 1]; 
    for(int i = N; i >= 0; i -= k) 
    { 
     sum += CountChangeOptions(coins, j - 1, i); 
    } 
    return sum; 
}

что оценивает правильно (хотя и не достаточно быстро). Поскольку CountChangeOptions(coins, x, y) для большинства coins будет в процессе работы алгоритма будет вызываться несколько раз с тем же x, y я решил реализовать стратегию кэширования

private int CountChangeOptions(int[] coins, int j, int N) 
{ 
    if(j == 0) 
     return 0; 
    if(N == 0) 
     return 1; 
    if(j == 1) 
     return N % coins[0] == 0 ? 1 : 0; 

    int sum = 0; 
    int k = coins[j - 1]; 
    for(int i = N; i >= 0; i -= k) 
    { 
     sum += CountOrGetFromCache(coins, j - 1, i); 
    } 
    return sum; 
} 

private int CountOrGetFromCache(int[] coins, int j, int i) 
{ 
    if(_cache[j, i] == null) 
    { 
     _cache[j, i] = CountChangeOptions(coins, j, i); 
    } 
    return (int)_cache[j, i]; 
}

где _cache является int?[][], который был установлен ранее с _cache = new int[N+1, N+1]. Однако в этом случае некоторые из тестовых случаев не выполняются. Любая идея почему?

источник

2016-10-26 Deadly Nicotine

Для каких входов вы получаете неправильный вывод? Вы пробовали отлаживать это? О, и вы можете использовать более описательные имена переменных - имена, такие как 'j',' i', 'N' и' k', не очень полезны, когда вам нужно отслеживать ошибки в алгоритме. –

Если ваш массив 'coins' изменяется, то кешированные значения будут недействительными. –

Как вы инициализируете 'int? [] []' Используя 'new int [N + 1, N + 1]'? Это приводит к ошибке для меня: 'Не может неявно преобразовать тип 'int [*, *]' в 'int? [] []''. Можете ли вы показать объявления для '_cache' и как именно вы его инициализируете? –

Единственная проблема, которую я вижу в том, что переменная _cache неправильно инициализируется

_cache = new int[N+1, N+1]

вместо

_cache = new int[coins.Length+1, N+1]

Кроме этого, оба решения функционально одинаковы. Я не считаю, что есть функциональный тестовый пример, который работает для первой (медленной) реализации и не выполняется для второй реализации.

Я предполагаю, что вы используете какой-либо веб-сайт, такой как HackerRank или его подобное, и первое решение, вероятно, отключается, давая вам ощущение, что оно работает, а второе быстрее, но не приводит к тайм-ауту, но приводит к неправильному результату ,

источник

2016-10-28 16:24:28 Vikhram

Почему мой простой кеш не работает?

ответ

Смежные вопросы