Запоминание рекурсивной функции в Javascript - PullRequest
1 голос
/ 20 февраля 2020

У меня есть эта рекурсивная функция, которая принимает массив колоды карт и находит индекс определенной карты:

const getCardIndex = (deck, fullCardName) => fullCardName === deck[0] ? 52 - deck.length : getCardIndex(deck.splice(1), fullCardName)

const deck = 'Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spades, Two of Hearts, Two of Diamonds, Two of Clubs, Two of Spades, Three of Hearts, Three of Diamonds, Three of Clubs, Three of Spades, Four of Hearts, Four of Diamonds, Four of Clubs, Four of Spades, Five of Hearts, Five of Diamonds, Five of Clubs, Five of Spades, Six of Hearts, Six of Diamonds, Six of Clubs, Six of Spades, Seven of Hearts, Seven of Diamonds, Seven of Clubs, Seven of Spades, Eight of Hearts, Eight of Diamonds, Eight of Clubs, Eight of Spades, Nine of Hearts, Nine of Diamonds, Nine of Clubs, Nine of Spades, Ten of Hearts, Ten of Diamonds, Ten of Clubs, Ten of Spades, Jack of Hearts, Jack of Diamonds, Jack of Clubs, Jack of Spades, Queen of Hearts, Queen of Diamonds, Queen of Clubs, Queen of Spades, King of Hearts, King of Diamonds, King of Clubs, King of Spades'.split(', ')

const result = getCardIndex(deck, 'King of Spades')

console.log(result)

Есть ли способ ускорить его, т. Е. С помощью напоминания?

Ответы [ 2 ]

1 голос
/ 20 февраля 2020

Как показывают комментарии, нет особых причин делать это рекурсивно. indexOf хорошо решает эту проблему.

Но, если вы решили написать рекурсивное решение, у вашей техники огромная проблема. Вы уничтожаете объект, который пытаетесь найти!

Array.prototype.splice является разрушительным . Изменяет массив, на котором работает. В итоге у вас будет индекс и почти пустая колода карт!

То, что это работает вообще, почти совпадение. Если бы вы хотели использовать slice, это бы сработало и не вызывало этой проблемы. slice просто дает вам копию массива, начиная с одного индекса и заканчивая другим (или в конце массива). splice делает больше. Он удаляет подсписок элемента, вставляет дополнительные и возвращает удаленные. Если вы вызываете его только с начальным индексом, он удаляет остальную часть массива и возвращает его. Так что вызовы deck.slice(1) и deck.splice(1) возвращают одно и то же, но второй также удаляет все возвращенные элементы из вашего массива.

Так что самое быстрое исправление вашей функции это просто:

const getCardIndex = (deck, fullCardName) => 
  fullCardName === deck[0] 
    ? 52 - deck.length 
    : getCardIndex (deck.slice(1), fullCardName)

Но это не имеет особого смысла, если честно. Это работает, но при каждом рекурсивном вызове он создает новый массив, который короче предыдущей версии. Это просто память для простого поиска.

Итак, вот еще один метод, который используется только для индекса:

const getCardIndex = (deck, fullCardName, idx = 0) =>
  idx >= deck.length 
    ? -1
    : deck [idx] == fullCardName
      ? idx
      : getCardIndex (deck, fullCardName, idx + 1)

Обратите внимание, однако, что в этом параметре c нет ничего колоды и карты, кроме имен переменных и функций. Таким образом, мы могли бы преобразовать это в более общую c функцию, например:

const getIndex = (xs, x, idx = 0) =>
  idx >= xs.length 
    ? -1
    : xs [idx] == x
      ? idx
      : getIndex (xs, x, idx + 1)

И там у нас есть рекурсивное решение для нахождения индекса значения в произвольном массиве.

Опять же, однако, есть очень мало причин использовать эту функцию. Это разумное упражнение для изучения рекурсии, но не более того. Вместо этого используйте indexOf.

0 голосов
/ 20 февраля 2020

Для решения, которое заранее определяет решения (O(52) = O(1)), а затем может искать решения за одну операцию, отказаться от рекурсивной функции, превратить колоду в объект, чьи ключи являются именами карт и значения являются указателями на карты, а затем просто найдите свойство карты на объекте:

const deck = 'Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spades, Two of Hearts, Two of Diamonds, Two of Clubs, Two of Spades, Three of Hearts, Three of Diamonds, Three of Clubs, Three of Spades, Four of Hearts, Four of Diamonds, Four of Clubs, Four of Spades, Five of Hearts, Five of Diamonds, Five of Clubs, Five of Spades, Six of Hearts, Six of Diamonds, Six of Clubs, Six of Spades, Seven of Hearts, Seven of Diamonds, Seven of Clubs, Seven of Spades, Eight of Hearts, Eight of Diamonds, Eight of Clubs, Eight of Spades, Nine of Hearts, Nine of Diamonds, Nine of Clubs, Nine of Spades, Ten of Hearts, Ten of Diamonds, Ten of Clubs, Ten of Spades, Jack of Hearts, Jack of Diamonds, Jack of Clubs, Jack of Spades, Queen of Hearts, Queen of Diamonds, Queen of Clubs, Queen of Spades, King of Hearts, King of Diamonds, King of Clubs, King of Spades'.split(', ')
const deckObj = Object.fromEntries(deck.map((str, i) => [str, i]));


console.log(deckObj['King of Spades'])
console.log(deckObj['Ace of Diamonds'])
console.log(deckObj['Queen of Diamonds'])
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...