Давайте исследуем забавный, противоречащий интуиции мир комбинаторики.
Объединение значений для формирования наборов различных комбинаций может быть сложной задачей. Даже если игнорировать порядок, количество возможных наборов тревожно растет.
Для массива из двух значений [1, 2] вы можете сгенерировать:
- [] (пустой набор)
- [1]
- [2]
- [1,2] (or [2,1])
Если повторы разрешены (например, [2, 2]), увеличение будет еще больше. По мере увеличения количества входных значений количество соответствующих выходных наборов выстреливает сквозь крышу!
Назовем входные значения элементами и каждую комбинацию этих значений выбором. Кроме того, давайте рассмотрим несколько элементов, каждый из которых имеет свой выбор. Хорошим рабочим примером может служить меню. Мы смоделируем меню Ye Olde Ice Cream Shoppe, которое предлагает своим клиентам сочетания вкусов мороженого, начинок и сиропа.
Вкус мороженого: ШОКОЛАД, КЛУБНИКА, ВАНИЛЬ.
Начинки: ананас, клубника, кокосовая стружка, орехи пекан.
Сиропы: шоколадный, зефирный, ириски, кленовый.
На выбор есть некоторые ограничения: покупатели могут выбрать любые два мороженого, две начинки и один сироп. Выбор мороженого и топпинга является эксклюзивным, а это означает, что я не могу выбрать, например, ананас + ананас. Покупатель может отказаться от начинки и сиропа, но должен выбрать хотя бы одно мороженое. С этими ограничениями скорость возрастания экспоненциальна, порядка 2 в n-й степени, что значительно меньше, чем если бы порядок был значительным и разрешалось дублирование.
Вкусовые качества
Ye Olde Ice Cream Shoppe на самом деле довольно современен в своем подходе к бизнесу и разрабатывает экспертную систему искусственного интеллекта, чтобы судить, какие сочетания мороженого, топпинга и сиропа приемлемы. Серверы будут видеть предупреждение в их реестрах, когда клиент выбирает неприятный выбор. Затем серверы получают указание дважды проверить с клиентом правильность их заказа.
Шаг 1. Сбор данных
Код для этой статьи можно найти здесь. Я предполагаю, что вы знакомы с JavaScript и Node.js. Практическое знание Lodash (или Underscore) полезно. Код использует базу данных map / reduce для хранения.
Первым шагом будет создание базы данных всех комбинаций мороженого, топпинга и сиропа. Входные данные будут следующими:
С этими данными я могу написать функцию Комбинатор, которая берет каждый пункт меню и генерирует все возможные разрешенные комбинации. Каждая комбинация хранится в виде массива. Например, комбинации мороженого будут выглядеть так:
[ [ ‘CHOCOLATE’, ‘STRAWBERRY’ ], [ ‘CHOCOLATE’, ‘VANILLA’ ], [ ‘CHOCOLATE’ ], [ ‘STRAWBERRY’, ‘VANILLA’ ], [ ‘STRAWBERRY’ ], [ ‘VANILLA’ ] ]
После того, как комбинации мороженого, начинок и сиропов определены, остается только повторить каждую комбинацию элементов с другими:
Это дает комбинацию мороженого, начинки (ей) и сиропа, например:
[ [ 'VANILLA' ], [ 'coconut flakes', 'pecans' ], [] ], [ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'chocolate' ] ], [ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'marshmallow' ] ],...
Показанные варианты выбора переводятся как:
- Ванильное мороженое с кокосовой стружкой и орехами пекан, без сиропа
- Ванильное мороженое с кокосовой стружкой и шоколадным сиропом
- Ванильное мороженое с кокосовой стружкой и зефирным сиропом
Даже с несколькими ограниченными пунктами меню количество разрешенных вариантов составляет 330!
Шаг 2: Хранение данных
Теперь, когда каждая комбинация элементов для заказа определена, можно приступать к дальнейшей работе. Система искусственного интеллекта для определения приемлемых комбинаций выбора оказывается сложной и не будет встроена в операционную систему регистров. Вместо этого запрос AJAX будет отправлен на сервер, на котором размещена программа AI. Входными данными будут варианты меню, выбранные клиентом, а в выходных данных вкусовые качества этих вариантов будут оцениваться следующим образом: [тьфу, м-м-м, вкусно, великолепно]. Оценка вкуса тьфу вызывает вышеупомянутое предупреждение.
Нам нужен быстрый ответ на запрос, чтобы оценки вкусовых качеств были кешированы в базе данных. Учитывая характер экспоненциального роста, это может превратиться в проблему больших данных, если в будущем в меню будет добавлено больше вариантов выбора элементов.
Допустим, принято решение хранить комбинации вариантов и рейтинги в базе данных NoSQL. При использовании PouchDB каждое значение выбора и вкуса сохраняется в виде документов JSON. вторичный индекс (он же просмотр) с каждым выбором в качестве ключа позволит нам быстро найти рейтинг вкусовых качеств. Вместо того, чтобы помещать данные в массив allChoices, как показано выше в buildChoices.js, я могу отправить документы JSON в базу данных для хранения.
Действуя наивно, я могу внести пару изменений в Step1.js, чтобы получить Step2.js: во-первых, мне нужно установить PouchDB через npm, а затем потребовать его. Затем я создаю базу данных NoSQL под названием choices.
var PouchDB = require('pouchdb');
var db = new PouchDB('choices');
Теперь каждый выбор размещается в базе данных вариантов:
Это работает! Вроде, как бы, что-то вроде. Как видно из параметра обратного вызова для db.post, эта операция является асинхронной. В журнале мы видим:
>node Step2.js done?? stored 1 stored 2 stored 3 ...
Таким образом, код говорит, что это сделано до того, как будет сохранена даже запись 1. Это будет проблемой, если мне нужно выполнить дальнейшую обработку в базе данных, а все записи еще не там.
Шаг 3. Исправление и доработка
Есть и более тонкая проблема: потенциальное исчерпание ресурсов. Если база данных ограничивает количество одновременных подключений, большое количество одновременных почтовых запросов может привести к тайм-аутам подключения.
Для Step3.js я немного исправил ошибки, переформатировал и реорганизовал то, что было написано на Step2.js. Одна ошибка заключалась в том, что при каждом запуске в базу данных добавлялось все больше и больше записей, дублируя то, что было раньше. Решением было уничтожить существующую базу данных, воссоздать ее, а затем запустить основную программу:
// remove old
db.destroy(null, function () {
db = new PouchDB('choices');
run();
});
Затем нужно было добавить текущий счетчик сохраненных документов и отправку запросов в процессе, чтобы программа: 1) знала, когда сохранен последний документ; 2) позволяет обрабатывать только пять сообщений одновременно. Теперь метод run () выглядит так (с некоторыми упущениями):
Следует отметить следующие основные изменения:
- postCount отслеживает, сколько сообщений являются неурегулированными.
- Интервальный таймер проверяет postCount и выполняет публикацию и завершает работу, когда становятся доступными места для публикации.
- обработчик done () вызывается, когда все варианты сохранены
Шаг 4: добавление вкусовых качеств
Имея все возможные варианты меню, теперь мы можем позволить ИИ определять вкусовые качества каждого из них. На данный момент ИИ - это всего лишь имитация, которая присваивает случайные значения каждой записи документа в PouchDB. Эти значения будут храниться в базе данных путем обновления каждого документа с оценкой вкуса.
Просто чтобы убедиться, что мы сохранили данные правильно, мы можем выгрузить документы из базы данных в консоль:
db.allDocs({
include_docs: true
})
.then(docs => {
_.each(docs.rows, r => {
console.log(r.doc.choice, r.doc.taste)
});
});
//output looks like:
/*
[ [ 'STRAWBERRY' ], [ 'coconut flakes' ], [ 'maple' ] ] 'sublime'
[ [ 'CHOCOLATE' ], [ 'pecans' ], [ 'chocolate' ] ] 'tasty'
[ [ 'CHOCOLATE', 'STRAWBERRY' ], [], [ 'chocolate' ] ] 'sublime'
[ [ 'VANILLA' ], [], [ 'marshmallow' ] ] 'meh'
[ [ 'CHOCOLATE', 'STRAWBERRY' ],
[ 'pineapple' ],
[ 'marshmallow' ] ] 'meh'
*/
Шаг 5: поиск вкусовых качеств
Документы есть в базе данных, но теперь должен быть способ определить, насколько предпочтительны для выбора покупатели. Это делается путем определения представления, которое представляет собой функцию, которая возвращает ключ для каждого документа вместе со значением. Какой должен быть ключ?
Я мог бы использовать r.doc.choice в качестве ключа, но у массивов есть порядок, и этот порядок может измениться, если элементы меню, определенные на шаге 1, будут позже переставлены. Ключ - это просто идентификатор выбранного варианта и не несет собственного семантического значения. Что должно работать, так это:
- сгладить каждый массив r.doc.choice,
- упорядочить элементы в алфавитном порядке, затем
- соединить их вместе
- результат - это ключ
Однако, если в будущем будет добавлено больше вариантов, длина ключа может превысить предел, разрешенный базой данных. Вместо использования ключа в том виде, в каком он сконструирован, в качестве реального ключа можно использовать хеш-ключ. Хэш SHA256 в шестнадцатеричном формате имеет длину 64 символа, и вероятность хеш-коллизии даже для квадриллиона вариантов практически равна нулю. Написать хэш-функцию для выбора легко, используя крипто модуль Node.js и цепочку Lodash:
Добавление хэша к нашим существующим документам - это простой вопрос перебора каждого документа базы данных, вычисления его хэша и обновления документа с помощью значения ключа:
Затем создается представление базы данных с использованием ключевого поля документа в качестве индекса; Я назову это выбором.
Для любого ключа документа (массива хешей выбора) я могу найти его вкус с помощью представления choice. Теперь все готово для определения того, что выберет покупатель: ну, хорошо, вкусно или великолепно. Чтобы проверить это, мы делаем несколько случайных выборов и смотрим, сможем ли мы найти вкус:
Результаты следующие:
=> node test VANILLA,coconut flakes,pecans,marshmallow tastes ugh CHOCOLATE,pecans,chocolate tastes sublime STRAWBERRY,VANILLA,pineapple,coconut flakes,marshmallow tastes tasty STRAWBERRY,pecans,maple tastes meh VANILLA,coconut flakes,pineapple,chocolate tastes sublime
Вот и все! Все, что осталось, - это написать клиентское программное обеспечение, которое отправляет варианты выбора через AJAX и получает обратно вкусовую ценность (привлекательность). Если это тьфу, то в реестре появляется предупреждение.
В следующем посте я уточню алгоритм, использованный выше. Зацени!
