Să explorăm lumea distractivă și contra-intuitivă a combinatoriei.
Combinarea valorilor pentru a forma seturi de combinații distincte poate fi un lucru dificil. Chiar dacă ignorați ordinea, numărul seturilor posibile crește alarmant.
Pentru o matrice de două valori [1, 2], puteți genera:
- [] (set gol)
- [1]
- [2]
- [1,2] (sau [2,1])
Dacă repetările sunt permise ([2, 2] de exemplu), creșterea este și mai mare. Pe măsură ce crește numărul de valori de intrare, numărul seturilor de ieșiri corespunzătoare trage prin acoperiș!
Să numim valorile de intrare obiecte și fiecare combinație a acelor valori a alegere. În plus, să permitem mai multe articole, fiecare cu alegeri distincte. Un bun exemplu de lucru ar fi un meniu. Vom simula meniul Ye Olde Ice Cream Shoppe, care oferă clienților săi combinații de înghețată, toppinguri și arome de sirop.
Aromele de înghețată sunt: CIOCOLATA, FAGOI, VANILA
Garnituri: ananas, căpșuni, fulgi de cocos, nuci pecan
Siropuri: ciocolată, marshmallow, butuc, arțar
Există câteva constrângeri asupra alegerilor: clienții pot alege oricare Două inghetate, Două toppinguri și unu sirop. Opțiunile de înghețată și topping sunt exclusive, ceea ce înseamnă că nu pot alege ananas + ananas, de exemplu. Clientul poate alege să nu aibă toppinguri și nici un sirop, dar trebuie să aleagă cel puțin o înghețată. Cu aceste constrângeri, rata de creștere este exponențială, de ordinul 2 până la a n-a putere, care este considerabil mai mică decât dacă ordinea ar fi semnificativă și s-ar permite duplicate.
Palatabilitate
Ye Olde Ice Cream Shoppe este de fapt destul de modern în abordarea sa de afaceri și dezvoltă un sistem expert în inteligență artificială pentru a judeca care combinații de înghețată, topping și sirop sunt plăcute. Serverelor li se va afișa un avertisment în registrele lor atunci când un client alege o selecție neplăcută. Serverele sunt apoi instruiți să verifice cu clientul dacă comanda lor este corectă.
Pasul 1: Construirea datelor
Codul acestui articol poate fi găsit Aici. Presupun că sunteți familiarizați cu JavaScript și Node.js. O cunoștință de lucru despre Lodash (sau Underscore) este utilă. Codul folosește o bază de date hartă / reducere pentru stocare.
Primul pas va fi crearea unei baze de date cu toate combinațiile de înghețată, topping și sirop. Intrările vor fi după cum urmează:
var menu = {
iceCream: {min: 1, max: 2, values: ["CHOCOLATE", "STRAWBERRY", "VANILLA"]},
topping: {min: 0, max: 2, values: ["pineapple", "strawberry", "coconut flakes", "pecans"]},
syrup: {min:0, max: 1, values: ["chocolate", "marshmallow", "butterscotch", "maple"]}
}Cu aceste date, pot scrie un Combinator funcție care ia fiecare element de meniu și generează toate combinațiile permise posibile. Fiecare combinație este stocată ca o matrice. De exemplu, combinațiile de înghețată ar arăta ca:
[ [ ‘CHOCOLATE’, ‘STRAWBERRY’ ],
[ ‘CHOCOLATE’, ‘VANILLA’ ],
[ ‘CHOCOLATE’ ],
[ ‘STRAWBERRY’, ‘VANILLA’ ],
[ ‘STRAWBERRY’ ],
[ ‘VANILLA’ ] ]Odată ce combinațiile de înghețată, toppinguri și siropuri sunt determinate, nu mai rămâne decât să iterați fiecare combinație de elemente cu celelalte:
var allChoices = [];
_.each(iceCreamChoices, function(ic) {
_.each(toppingChoices, function(tp) {
_.each(syrupChoices, function(sy) {
allChoices.push([ic,tp,sy]);
})
})
})Aceasta produce o combinație de înghețată (înghețată), topping (e) și sirop, cum ar fi:
[ [ 'VANILLA' ], [ 'coconut flakes', 'pecans' ], [] ],
[ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'chocolate' ] ],
[ [ 'VANILLA' ], [ 'coconut flakes' ], [ 'marshmallow' ] ],...Opțiunile afișate se traduc prin:
- Inghetata de vanilie cu fulgi de cocos si nuci pecan, fara sirop
- Inghetata de vanilie cu fulgi de cocos si sirop de ciocolata
- Inghetata de vanilie cu fulgi de cocos si sirop de marshmallow
Chiar și cu doar câteva elemente de meniu restricționate, numărul de opțiuni permise este de 330!
Pasul 2: stocarea datelor
Cu fiecare combinație de articole comandabile acum stabilită, se poate face o lucrare suplimentară. Sistemul AI pentru determinarea combinațiilor de alegeri plăcute se dovedește a fi complex și nu va fi încorporat în sistemul de operare al registrelor. În schimb, o cerere AJAX va fi adresată unui server care găzduiește programul AI. Intrările vor fi opțiunile de meniu ale clientului, iar rezultatul va evalua gustul acelor alegeri ca fiind unul dintre: [ugh, meh, tasty, sublime]. Un grad de gust de ugh declanșează avertismentul menționat anterior.
Avem nevoie de un răspuns rapid la cerere, astfel încât evaluările de gustabilitate vor fi stocate în cache într-o bază de date. Având în vedere natura creșterii exponențiale, aceasta ar putea evolua pentru a deveni o problemă Big Data dacă în viitor vor fi adăugate mai multe opțiuni la meniu.
Să presupunem că este decis să se stocheze combinațiile de alegeri și evaluări într-o bază de date NoSQL. Folosind PouchDB, fiecare alegere și valoare de gust sunt stocate ca documente JSON. A index secundar (aka vedere) cu fiecare alegere ca cheie ne va permite să căutăm rapid ratingul de gust. În loc să împingă datele într-un toate alegerile matricea așa cum se arată mai sus în buildChoices.js, Pot împinge documentele JSON în baza de date pentru stocare.
Procedând naiv, pot face câteva modificări în Step1.js pentru a ajunge la Step2.js: mai întâi de toate, trebuie să instalez PouchDB prin npm, apoi să îl solicitez. Apoi, creez o bază de date NoSQL numită alegeri.
var PouchDB = require('pouchdb');
var db = new PouchDB('choices');Acum, fiecare alegere este postată în baza de date cu alegeri:
var count = 0;
_.each(iceCreamChoices, function(ic) {
_.each(toppingChoices, function(tp) {
_.each(syrupChoices, function(sy) {
//allChoices.push([ic,tp,sy]);
db.post({choice: [ic,tp,sy]}, function(err, doc){
if (err) console.error(err);
else console.log(`stored ${++count}`);
});
})
})
});
console.log('done??');Acest lucru funcționează! Un fel de. După cum se poate deduce din parametrul de apel invers către db.post, acea operațiune este asincronă. Ceea ce vedem în jurnal este:
>node Step2.js
done??
stored 1
stored 2
stored 3
...Deci, codul spune că s-a făcut înainte ca și înregistrarea 1 să fie stocată. Aceasta va fi o problemă dacă mai am de procesat în baza de date și toate înregistrările nu sunt încă acolo.
Pasul 3: Fixare și rafinare
Există, de asemenea, o problemă mai subtilă: epuizarea potențială a resurselor. Dacă baza de date limitează numărul de conexiuni simultane, un număr mare de cereri de postare simultane poate duce la expirarea conexiunii.
Pentru Pasul 3.js, Am făcut un pic de remediere a erorilor, reformatarea și refactorizarea a ceea ce a fost scris în Step2.js. O eroare a fost că fiecare rulare a adăugat din ce în ce mai multe înregistrări la baza de date, duplicând ceea ce era acolo înainte. Soluția a fost să distrugem baza de date existentă, să o recreăm și apoi să executăm programul principal:
// remove old
db.destroy(null, function () {
db = new PouchDB('choices');
run();
});Apoi a fost să adăugăm un număr de documente stocate și să postăm cereri în proces, astfel încât programul: 1) să știe când este stocat ultimul document; 2) permite doar cinci postări să continue în același timp. Metoda run () arată așa acum (cu unele omisiuni):
function run() {
var menu = { //...
}
var iceCreamChoices = new Combinator({ //...
});
var toppingChoices = new Combinator({ //...
});
var syrupChoices = new Combinator({ //...
});
var count = 0;
var total = iceCreamChoices.length * toppingChoices.length * syrupChoices.length;
var postCount = 0;
var postCountMax = 5;
_.each(iceCreamChoices, function (ic) {
_.each(toppingChoices, function (tp) {
_.each(syrupChoices, function (sy) {
var si = setInterval(() => {
if (postCount < postCountMax) {
clearInterval(si);
postChoice(ic, tp, sy);
}
}, 10);
})
})
});
function postChoice(ic, tp, sy) {
++postCount;
db.post({
choice: [ic, tp, sy]
}, function (err, doc) {
--postCount;
done(err);
});
}
function done(err) {
if (err) {
console.error(err);
process.exit(1);
}
console.log(`stored ${++count}`);
if (count === total) {
console.log('done');
}
}
}Principalele modificări de menționat sunt că:
- A postCount urmărește câte postări sunt remarcabile
- Un temporizator de interval verifică postCount și va posta și va ieși atunci când sloturile de postare sunt disponibile
- A Terminat() handler este apelat atunci când toate opțiunile sunt stocate
Pasul 4: Adăugarea gustului
Având toate opțiunile de meniu posibile, putem face acum ca AI să determine gustul fiecăruia. AI este doar o falsă în acest moment, care atribuie valori aleatorii fiecărei înregistrări de documente din PouchDB. Aceste valori vor fi stocate în baza de date prin actualizarea fiecărui document cu o evaluare a gustului.
var _ = require('lodash');
var PouchDB = require('pouchdb');
var db = new PouchDB('choices');
db.allDocs({
include_docs: true
})
.then(docs => {
_.each(docs.rows, r => {
r.doc.taste = palatability();
db.put(r.doc);
});
});
function palatability() {
var scale = Math.round(Math.random() * 10);
var taste;
switch (true) {
// this switch is a horrible hack; don't ever do this ;-P
case (scale < 2):
taste = "ugh";
break;
case (scale < 5):
taste = "meh";
break;
case (scale < 8):
taste = "tasty";
break;
default:
taste = "sublime";
break;
}
return taste;
}Doar pentru a verifica dacă am stocat corect lucrurile, putem arunca documentele din baza de date pe consolă:
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'
*/Pasul 5: Căutarea gustului
Documentele se află în baza de date, dar acum trebuie să existe o modalitate de a determina care este gustul pentru alegerile unui client. Acest lucru se face prin definirea unei vizualizări, care este o funcție care returnează o cheie pentru fiecare document, împreună cu o valoare. Care ar trebui să fie cheia?
Aș putea folosi r.doc.choice ca cheie, dar matricile au o ordine și această ordine s-ar putea schimba dacă elementele de meniu definite la pasul 1 ar fi fost rearanjate ulterior. Cheia este doar un identificator al selecției alegute și nu are un sens semantic propriu. Ce ar trebui să funcționeze este să:
- aplatizați fiecare matrice r.doc.choice,
- ordonați elementele alfabetic, apoi
- concatenează-le împreună
- rezultatul este o cheie
Dacă în viitor se adaugă mai multe opțiuni, lungimea cheii ar putea depăși limita permisă de baza de date. În loc să utilizați cheia așa cum este construită, un hash cheia ar putea fi folosită ca cheie reală. Un hash SHA256 în hexazecime are o lungime de 64 de caractere, iar probabilitatea unei coliziuni hash, chiar și în cazul a patru miliarde de alegeri, este în esență zero. Scrierea funcției hash pentru alegeri este ușoară, folosind Node.js cripto modul și un lanț Lodash:
const crypto = require('crypto');
const _ = require('lodash')
function hash(choice) {
var str = _.chain(choice)
.flatten()
.sortBy()
.join('|')
.value();
return crypto.createHmac('sha256', 'old ice cream')
.update(str)
.digest('hex');
}
module.exports = hash;Adăugarea hash-ului la documentele noastre existente este o simplă chestiune de iterare prin fiecare document de bază de date, calcularea hash-ului său și actualizarea documentului cu o valoare cheie:
const _ = require('lodash');
const hash = require('./hash');
const PouchDB = require('pouchdb');
const db = new PouchDB('choices');
db.allDocs({
include_docs: true
})
.then(docs => {
_.each(docs.rows, r => {
r.doc.key = hash(r.doc.choice);
db.put(r.doc);
});
})
.catch(e => {
console.error(e)
});Apoi, se creează o vizualizare a bazei de date folosind câmpul cheie document ca index; O voi numi alegere.
const PouchDB = require('pouchdb');
const db = new PouchDB('choices');
// doc that defines the view
var ddoc = {
_id: '_design/choice',
views: {
by_key: {
map: function (doc) {
emit(doc.key, doc.taste);
}.toString()
}
}
};
// remove any existing view, then add new one:
db.get(ddoc._id)
.then(doc => {
return db.remove(doc);
})
.then(() => {
db.put(ddoc)
.catch(function (err) {
console.error(err);
});
});Pentru orice cheie de document (matricea hash de alegere), îi pot găsi gustul prin vizualizare alegere. Acum totul este la locul său pentru a determina dacă alegerea unui client este ugh, meh, gustos, sau sublim. Pentru a testa acest lucru, facem câteva alegeri aleatorii și vedem dacă putem găsi gustul:
const choices = [
[['VANILLA'], ['coconut flakes', 'pecans'], ['marshmallow']],
[['CHOCOLATE'], ['pecans'], ['chocolate']],
[['STRAWBERRY', 'VANILLA'], ['pineapple', 'coconut flakes'], ['marshmallow']],
[['STRAWBERRY'], ['pecans'], ['maple']],
[['VANILLA'], ['coconut flakes', 'pineapple'], ['chocolate']],
[['CHOCOLATE, STRAWBERRY'], ['pineapple', 'pecans'], ['butterscotch']],
];
const keys = _.map(choices, c => {
return hash(c);
});
db.query('choice/by_key', {
keys: keys,
include_docs: false,
}, function (err, result) {
if (err) {
return console.error(err);
}
_.each(result.rows, (r, i) => {
console.log(`${choices[i]} tastes ${r.value}`);
})
});Rezultatele sunt:
=> 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 sublimeAsta este! Tot ce a mai rămas este să scrieți un software client care trimite opțiuni prin AJAX și obține o valoare de gust (gust). Daca este ugh, apoi sus apare un avertisment în registru.
Într-o postare ulterioară, rafin algoritmul folosit mai sus. Verifică!
Referințe
Creșterea exponențială nu este grozavă. Explozia combinatorie este.
O mare parte din industria tehnologiei este obsedată de creșterea exponențială. Orice lucru liniar moare sau a murit de ani de zile …
www.torbair.com
Calculator de combinații și permutări
Aflați câte moduri diferite puteți alege articole. Pentru o explicație aprofundată a formulelor, vă rugăm să vizitați …
www.mathsisfun.com
