Фон
В моем приложении Group Randomizer одна из функций моего MVP (минимально жизнеспособный продукт) - это создание функции сохранения группы. Когда пользователь нажимает кнопку «Сохранить группу», он сохраняет текущий список параметров как новую группу. Однако основная функциональность этой функции заключается в том, что если она находит существующую сохраненную группу с теми же параметрами, независимо от порядка, появится предупреждение о том, что группа с вашим текущим списком параметров уже существует.
Например, в сохраненной группе №1 есть список людей «Сэм» и «Боб». Если мой текущий список опций - «Боб» и «Сэм», и я пытаюсь сохранить его как новую группу, то выскакивает предупреждение, в котором говорится: «Сохраненная группа с вашим текущим списком опций уже существует. Это сохраненная группа №1 ».
В этом блоге я расскажу, как я создал алгоритм для создания этой функции проверки и применения бритвы Оккама. Если вы не знакомы с бритвой Оккама, определение из Википедии таково:
Бритва Оккама… - это принцип решения проблем, который гласит, что Сущности не должны умножаться без необходимости.
Первая попытка алгоритма проверочной группы
Приведенный ниже код - это моя первая попытка алгоритма группы проверки.
function checkGroups(savedGroup, currentListOfOptions) {
savedGroupHash = {}
// populates the savedGroupHash based on the contents of the savedGroup array parameter
for (let i = 0; i < savedGroup.length; i++){
savedGroupHash[savedGroup[i]] = true
}
// checks the savedGroupHash against the current list of options to check if savedGroupHash contains all of the list of options
for (let j = 0; j < currentListOfOptions.length; j++) {
if (!savedGroupHash.hasOwnProperty(currentListOfOptions[j])) {
return false
}
}
return true
}
Примечание: параметрами для этого алгоритма являются оба массива. Всякий раз, когда «опция» упоминается ниже, это относится к элементу в их соответствующих массивах.
Чтобы дать общее представление о том, как я подошел к этому алгоритму, я создал два цикла for. Первый for цикл заполнен savedGroupHash на основе содержимого параметра savedGroup. Для пар "ключ-значение" ключом является параметр со значением по умолчанию true. Это значение или его отсутствие будет использоваться как логическое значение во втором цикле for. Во втором цикле for я сравнил каждую опцию в параметре currentListOfOptions с savedGroupHash. Как только опция в currentListOfOptions не была включена в savedGroupHash, я возвращал false, который немедленно выходил из функции. В противном случае последняя строка вернет true , поскольку она не вернула false из второго цикла for.
Тестирование первой попытки алгоритма проверочной группы
Основываясь на моем опыте правильного тестирования из моего последнего блога, я решил создать несколько тестовых примеров для тщательного тестирования моего алгоритма. В данном случае на ум пришли три сценария.
1. savedGroup и currentListOfOptions фактически имеют одинаковые параметры, но в другом порядке. Это должно вернуть true.
2. savedGroup включает те же параметры, что и currentListOfOptions, но имеет больше параметров, чем currentListOfOptions. Это должно вернуть false.
3. currentListOfOptions включает те же параметры, что и savedGroup, но имеет больше параметров, чем savedGroup. Это должно вернуть false.
В первом случае будем использовать savedGroup = [“Sam, “Bob”] и currentListOfOptions = [“Bob”, “Sam”]. Затем давайте введем эти две переменные в алгоритм в качестве параметров и запишем в консоль возвращаемое значение.
const savedGroup = ["Sam", "Bob"] const currentListOfOptions = ["Bob", "Sam"] console.log(checkGroups(savedGroup, currentListOfOptions)) //true
Похоже, наш первый тестовый пример прошел успешно. Перейдем ко второму тесту.
Во втором случае воспользуемся savedGroup = [“Sam”, “Bob”, “Jane”] и currentListOfOptions = [“Bob”, “Sam”]. Затем давайте введем эти две переменные в алгоритм и запишем в консоль возвращаемое значение.
const savedGroup = ["Sam", "Bob", "Jane"] const currentListOfOptions = ["Bob", "Sam"] console.log(checkGroups(savedGroup, currentListOfOptions)) //true
Похоже, наш второй тест не прошел. Перейдем к третьему тесту.
В третьем случае воспользуемся savedGroup = [“Sam”, “Bob”] и currentListOfOptions = [“Bob”, “Sam”, “Jane”]. Затем давайте введем эти две переменные в алгоритм и запишем в консоль возвращаемое значение.
const savedGroup = ["Sam", "Bob"] const currentListOfOptions = ["Bob", "Sam", "Jane"] console.log(checkGroups(savedGroup, currentListOfOptions)) //false
Похоже, наш третий тестовый пример прошел.
Хм ... похоже, что этот алгоритм не работает должным образом. После анализа моего кода похоже, что разница в длине каждого параметра может отбрасывать его. Если это так, давайте изменим алгоритм, чтобы учесть это.
Вторая попытка алгоритма проверочной группы
Приведенный ниже код - это моя вторая попытка алгоритма группы проверки.
function checkGroups(savedGroup, currentListOfOptions) {
const savedGroupHash = {}
for (let i = 0; i < savedGroup.length; i++) {
savedGroupHash[savedGroup[i]] = 1
}
for (let j = 0; j < currentListOfOptions.length; j++) {
if (savedGroupHash.hasOwnProperty(currentListOfOptions[j])) {
savedGroupHash[currentListOfOptions[j]] -= 1
} else {
savedGroupHash[currentListOfOptions[j]] = 1
}
}
let sum = Object.values(savedGroupHash).reduce( (acc, current) => acc += current)
if (sum === 0) {
//this means the same group already exists
return true
} else {
//this means the group does not already exist
return false
}
}
Чтобы дать общий обзор этого алгоритма, есть два цикла for, аккумулятор и оператор if / else. Первый цикл for делает почти то же самое, что и первый цикл for в первом алгоритме, но вместо этого предоставляет значение по умолчанию 1. Второй цикл for управляет savedGroupHash для каждого параметра в currentListOfOptions. Если параметр находится в savedGroupHash, уменьшите значение на 1, что приведет к 0, а если нет, добавьте новую пару ключ-значение, где ключ - это сам параметр, а значение равно 1, аналогично первому. для цикла.
Затем с помощью аккумулятора он возьмет сумму всех значений в savedGroupHash. Цель sum - помочь определить, есть ли разница в длине между массивом savedGroup и массивом currentListOfOptions. Я использую sum в условном сравнении в операторе if / else, чтобы вернуть true или false.
Теперь наступает нервотрепка: тестирование этого нового алгоритма.
Тестирование второй попытки алгоритма проверочной группы
Для единообразия я собираюсь использовать те же тестовые примеры, что и при первой попытке алгоритма. Для краткости я также объединю код и результаты всех трех тестовых случаев.
//Test Case #1 const savedGroup = ["Sam", "Bob"] const currentListOfOptions = ["Bob", "Sam"] console.log(checkGroups(savedGroup, currentListOfOptions)) //true //Test Case #2 const savedGroup = ["Sam", "Bob", "Jane"] const currentListOfOptions = ["Bob", "Sam"] console.log(checkGroups(savedGroup, currentListOfOptions)) //false //Test Case #3 const savedGroup = ["Sam", "Bob"] const currentListOfOptions = ["Bob", "Sam", "Jane"] console.log(checkGroups(savedGroup, currentListOfOptions)) //false
Да! Похоже, теперь алгоритм работает так, как задумал! Наконец-то мы можем положить этому конец, но ...
Бритва Оккама
На следующий день, работая над приложением Group Randomizer, я снова взглянул на алгоритм группы проверки. Я продолжал улыбаться успеху этого алгоритма (поскольку на его разработку у меня ушло 1-2 часа), пока я не понял, что второй алгоритм был полным излишеством. Что я имею в виду?
Давайте еще раз посмотрим на тестовые примеры и объясним, почему я изменил алгоритм с первой попытки. Исходным предположением для основной причины неудачи теста была длина массивов для каждого параметра (как отражено в тестовом примере № 2). Во второй попытке алгоритма я манипулировал хешем savedGroupHash, чтобы отслеживать разницу в длинах массивов между savedGroup и currentListOfOptions. sum - это разница между длинами массивов. Если sum был 0, то длина массива такая же, что возвращает true. Любое другое значение вернет false.
Другой способ взглянуть на это, я, по сути, проверял, имеют ли savedGroup и currentListOfOptions одинаковую длину. Поскольку я знаю, что эти два параметра являются типами массивов, я могу просто вызвать .length для каждого параметра, чтобы проверить, имеют ли они одинаковую длину. Если они не одинаковой длины, я могу сразу вернуть false. Код ниже представляет эту реализацию.
if (savedGroup.length !== currentListOfOptions.length) {
return false
}
Теперь я могу изменить первую попытку алгоритма с помощью приведенного выше кода.
function checkGroups(savedGroup, currentListOfOptions) {
//insert new code here
if (savedGroup.length !== currentListOfOptions.length) {
return false
}
savedGroupHash = {}
for (let i = 0; i < savedGroup.length; i++){
savedGroupHash[savedGroup[i]] = true
}
for (let j = 0; j < currentListOfOptions.length; j++) {
if (!savedGroupHash.hasOwnProperty(currentListOfOptions[j])) {
return false
}
}
return true
}
Как вы, наверное, догадались дальше, я выполнил все три тестовых примера с помощью этого алгоритма и прошел все три тестовых примера!
Мне удалось упростить код проверки длин массивов из
for (let j = 0; j < currentListOfOptions.length; j++) {
if (savedGroupHash.hasOwnProperty(currentListOfOptions[j])) {
savedGroupHash[currentListOfOptions[j]] -= 1
} else {
savedGroupHash[currentListOfOptions[j]] = 1
}
}
let sum = Object.values(savedGroupHash).reduce( (acc, current) => acc += current)
if (sum === 0) {
//this means the same group already exists
return true
} else {
//this means the group does not already exist
return false
}
}
to
if (savedGroup.length !== currentListOfOptions.length) {
return false
}
Непреднамеренный результат при первой попытке алгоритма проверочной группы
Пока я проводил тестирование между первым немодифицированным алгоритмом и вторым алгоритмом, я понял, что на самом деле делает первый немодифицированный алгоритм. Хотя он не служил моей преднамеренной цели проверки идентичности групп, он проверял, была ли одна группа, currentListOfOptions, подмножеством другой группы, savedGroup. Я непреднамеренно создал алгоритм проверки подмножеств вместо проверки всего набора. Теперь, если мне нужно будет проверять подмножества в будущем, мне не нужно воссоздавать алгоритм с нуля и использовать первый немодифицированный алгоритм.
Ключевые выводы
При создании этого алгоритма я извлек два основных урока.
- Не копайтесь в кроличьей норе, слишком усложняя свои мысли.
Во время второй попытки алгоритма я все время думал в глубине души, что этот алгоритм должен содержать какое-то сложное решение, потому что это не обычная особенность (что, вероятно, неверно). Как вы понимаете, я решил исправить ошибку окольным путем, когда это можно было сделать с помощью трех строк кода (одна строка, если бы я не использовал фигурные скобки). Если вы начинаете думать, что ваше решение начинает усложняться, сделайте шаг назад и переоцените то, что вы пытаетесь достичь, и посмотрите, можно ли это сформулировать по-другому для, возможно, лучшего подхода.
2. Изучение алгоритмов в целом действительно помогло.
Как и многие начинающие разработчики программного обеспечения, я бы изучал различные структуры данных и алгоритмы и практиковался в решении алгоритмов на таких сайтах, как LeetCode. Сначала я действительно не видел цели изучения этих алгоритмов, потому что мне казалось, что я никогда не буду применять эти алгоритмы вне технических собеседований. Однако во время моей первой попытки создания алгоритма группы проверки я интуитивно использовал хэш для сравнения. Когда я подумал, зачем я это сделал, меня осенило, что это произошло потому, что использование хешей было обычным способом решения алгоритмов LeetCode для улучшения временной сложности с O (n²) до O (n). Теперь я понимаю, что изученные мной алгоритмы могут быть применимы к моему коду, когда я меньше всего этого ожидаю.
