Computationalitatea computațională
Această implementare necesită operații de înmulțire și divizare k. Asta este, complexitatea sa computațională este O (k).
Algoritmul funcționează mai repede, dar are anumite deficiențe. Chiar și pentru micul n, provoacă un exces de numere întregi, deoarece înmulțește n cu coeficientul binomial, care este un număr suficient de mare. Deci, dacă Integer este un număr întreg nesemnificat constând din patru octeți, atunci depășirea are loc chiar și la n = 50 și k = 8.
Generarea unei combinații aleatorii prin metoda aleatorie de permutare
Primul algoritm, pe care îl descriem, este destul de simplu și evident.
Ideea algoritmului este după cum urmează. Să luăm o listă de obiecte din n elemente G = (g1, G2 ... gn). Acesta va fi setul nostru, de unde vom construi o combinație. Prin combinarea lui H de la n cu k, numim un șir de biți n, în care exact unitățile k. Unitatea de pe locul i înseamnă că în această combinație există un element gi. De exemplu, H poate fi egal cu H '= (1, ... 1, 0, ... 0), unde primele elemente k sunt 1, restul fiind zero. Apoi combinația aleatoare H este o permutare aleatorie a șirului H '.
În STL există o funcție random_shuffle (). care generează o permutare aleatorie.
Prima funcție folosește în mod implicit generatorul de numere aleatoare, al doilea ca parametru. RandomNumberGenerator este un obiect de funcții care are ca parametru un număr n de tip corespunzător rezultatului operației Last-First și returnează un număr aleatoriu r: 0≤r Implementarea algoritmului este foarte simplă, deoarece se bazează pe generarea unei permutări aleatorii - un algoritm care are deja o implementare gata. Acest algoritm implementează mai multe funcții. Aici sunt. RandomFunc este un obiect funcțional care, atunci când este apelat RandomFunc (Max), returnează un număr aleatoriu x din intervalul 0≤x Funcțiile numite RandomCombination () generează o combinație aleatoare prin permutare aleatorie în formatul "subset". Parametrul n (unde este specificat) este dimensiunea setului original, k este dimensiunea combinației generate. RandomAccessIterator este un iterator de acces arbitrar, cu ajutorul parametrilor de acest tip este specificată o secvență de intrare. OutputIterator - iteratorul de ieșire, în care rezultatul este scris. InputIterator este un iterator de intrare. Primele două astfel de funcții primesc o secvență de intrare utilizând iteratori de acces aleatoriu. Ei își calculează lungimea prin aplicarea expresiei std :: distance (First, Last). De fapt, acest lucru le pune capăt utilizării ca iteratori de acces aleatoriu. Dacă iteratorul furnizat nu este un iterator cu acces aleatoriu, atunci puteți utiliza funcțiile care iau parametrul n - lungimea secvenței de intrare. În caz contrar, toate aceste funcții sunt identice. Este foarte important să treci obiectul funcției RandomFunc prin referință, și nu prin valoare, deoarece majoritatea generatoarelor de numere aleatorii utilizează starea lor internă. Astfel, dacă generatorul original transmis funcției este copiat și nu este trecut prin referință, două apeluri RandomCombination () pot duce la același rezultat. Mai jos este implementarea funcțiilor descrise. Ideea algoritmului este de a număra cumva toate combinațiile de la n la k, adică de a atribui fiecărui număr i din intervalul 0≤i Deci, mai întâi definim relația de ordine pe setul de combinații de la n la k. Pentru claritate, vom scrie combinații în formatul "list of bool". Relația noastră de comandă va fi lexicografică. Pentru claritate, să organizăm, de exemplu, toate combinațiile de la 7 la 3 în ordinea indicată. Dacă vă uitați atent la aceste combinații, atunci în ordinea lor este ușor de urmărit dependența recurentă. Luați în considerare primul element al combinațiilor. Mai întâi sunt toate combinațiile în care este 0, atunci - toate în care este egal cu 1. În plus, ordinea de combinare în aceste două subgrupuri se repetă - în fiecare subgrup sunt de prima combinație în care al doilea element - 0, și apoi - în care este 1, și așa mai departe. Numărul de combinații în care primul element este egal cu zero, egal cu numărul de combinații de n-1 la k, iar numărul de combinații, în care primul element este egal cu unu, egal cu numărul de combinații de n-1 la k-1 (răspunsul la întrebarea de ce se întâmplă acest lucru , este descrisă în nota referitoare la a doua proprietate a coeficientului binomial). Deci, dacă numărul de combinații este mai mic decât numărul de combinații de la n-1 la k, atunci primul element al setului nu este inclus în această combinație, în caz contrar intră. Rezumând cele de mai sus, ajungem la următorul algoritm. Datele de intrare. CombNumber - combinație număr, n, k - o pluralitate de rezoluție de intrare și combinații de dimensiuni, Src - set de intrare (secvență), care este ales combinație, Dest - o pluralitate de ieșire, în care combinația va fi scris de algoritm. Datele de ieșire. o combinație înregistrată în Dest. Acest algoritm utilizează în mare măsură calculul coeficientului binomial, astfel încât eficacitatea acestuia depinde de eficiența calculului coeficientului binomial. Numărul maxim de iterații este n (minimul este k). În plus, se utilizează operațiile de atribuire k. Există și operații minore, cum ar fi creșterea și scăderea numerelor întregi. Ele nu mai sunt decât n. Să presupunem că primul algoritm descris în articol (folosind memorie suplimentară) este folosit ca algoritm pentru calculul coeficientului binomial. Complexitatea sa de timp este O (nk) dacă valoarea cerută de C (n, k) nu este calculată până la ora apelului și O (1) dacă este deja în memoria cache. Atunci când se calculează C (n, k), pornind de la algoritm, se calculează și toate celelalte valori necesare ale coeficientului binomial. Acesta este, de fapt, coeficientul binomial trebuie calculat o singură dată, în toate apelurile ulterioare, valorile sunt extrase din memoria cache. Astfel, complexitatea de timp a întregului algoritm de selecție a combinațiilor aleatorii este O (nk) dacă cache-ul nu este plin și O (n) dacă este umplut cu coeficienții binomiali de care avem nevoie. Făcând înainte, vom spune că, în prezența unei cache-uri umplute, algoritmul descris este mai eficient decât algoritmul pentru generarea unei combinații prin metoda aleatorie permutată. Adică, dacă se numește de mai multe ori (de exemplu, cel puțin 5-10 ori), puteți obține un câștig de performanță (umplerea cache-ului se plătește). Dacă este necesară generarea unei singure combinații, atunci, bineînțeles, este mai bine să se aplice algoritmul de generare combinație aleatorie prin metoda aleatorie de permutare. Există multe funcții legate de acest algoritm, dar nu trebuie să fim speriați - toate sunt de același tip. Pe parametrii GetBinomialCoefficient, RandomFunc, n, k, Src, dest, prima, ultima, tipuri RandomAccessIterator, InputIterator, OutputIterator se suprapun aceste constrângeri și cerințe aceleași, și prin aceea că funcțiile care implementează o metodă de generare aleatorie algoritm de permutare. Parametrul CombNumber (dacă este prezent) trebuie să satisfacă condiția 0≤CombNumber≤C (n, k) este numărul de ordine al combinației. Funcțiile cu numele CombinationFromNumberBool () generează o combinație de numărul dat în formatul "list from bool". Intrarea este dată numărului de combinație, dimensiunii sale, probabil, unui obiect funcțional care calculează numărul de combinații (dacă nu este, atunci acesta este selectat în mod implicit). La ieșire, ele trebuie să scrie o secvență de elemente în Dest, care sunt sintactic compatibile cu bool (care poate fi atribuită o valoare de tip bool). Funcțiile cu numele CombinationFromNumber () generează o combinație cu un număr dat în formatul "subset". Pe intrare, ei iau același lucru ca CombinationFromNumberBool (), precum și un iterator (iteratori) care descrie secvența de intrare. La ieșire, ele trebuie să formeze subsecvența dorită (cu alte cuvinte, combinația) și să o scrie la Dest. numele de funcții RandomCombinationFromNumberBool () și RandomCombinationFromNumber () care generează o combinație casual formate, respectiv „lista de bool» și «subset». Intrarea are aceiași parametri ca și funcțiile corespunzătoare fără prefixul "Random", cu excepția parametrului RandomFunc, care este trecut în loc de CombNumber. Pentru că funcția corespunzătoare (fără prefixul «random») cu parametrul CombNumber = RandomFunc (GetBinomialCoefficient (n, k)). Mai jos este implementarea funcțiilor descrise. Funcțiile implementate utilizează semantica iteratorilor STL și, prin urmare, pot fi utilizate la fel de convenabil atât cu matrice regulate, cât și cu containerele din biblioteca standard de șabloane C ++ și chiar cu tipurile personalizate de date. Mai presus de toate, diferite opțiuni pentru funcțiile de apelare pot fi demonstrate folosind următorul program mic. Fișierul Demo.cpp cu programul poate fi descărcat de la link-ul de la sfârșitul articolului. Algoritmul pentru generarea unei combinații aleatorii în formatul "subset" prin metoda permutării aleatorii creează un vector Algoritmul de generare a unei combinații prin numărul său nu utilizează de la sine memorie suplimentară. Dar utilizează funcția GetBinomialCoefficient (), care (într-o singură versiune a algoritmului GetBinomialCoefficient) folosește octetul de memorie O (nk) pentru a cache valorile coeficientului. Așa cum am menționat mai devreme, performanța algoritmilor diferă în condiții diferite. Pentru a arăta performanța comparativă a algoritmilor implementați, vom scrie un program simplu. Aici CTimer este o clasă care măsoară timpul. Codul său nu este dat aici pentru scurtcircuit. 1 este o măsurare a timpului de funcționare al unui algoritm RandomCombination () simplu. 2 este măsurarea timpului de funcționare al algoritmului RandomCombinationFromNumber (), cu condiția ca memoria cache a valorilor coeficienților binomi să nu fie plină. Așa cum vom vedea mai târziu, în astfel de condiții timpul muncii sale este inacceptabil. 3 este măsurarea timpului de funcționare al algoritmului RandomCombinationFromNumber (), cu condiția ca memoria cache a valorilor coeficienților binomi să fie plină. 4 se face pentru compararea timpului de funcționare a doi algoritmi în condiții reale. În rezumat, RandomCombinationFromNumber () este numit de același număr de ori ca RandomCombination () în primul exemplu, dar cache-ul coeficientului binomial este resetat la fiecare 25 de apeluri. Aici este ieșirea programului pe procesorul Core 2 Duo E7500. Din aceasta putem trage următoarele concluzii. Astfel, dacă vom folosi RandomCombinationFromNumber () pentru n = 500 și k = 275, atunci acesta va plăti pentru sine în sensul de executare a timpului pentru apelurile C, unde C<25. Если n и k меньше, то C также уменьшается. Например, для n=250 и k=135 RandomCombinationFromNumber() окупается уже за C<12 вызовов. Эти данные, разумеется, справедливы лишь для целых 32-битных чисел. В общем случае мы имеем объекты некоторых классов, которые, возможно, копируются медленнее. Тогда C может уменьшиться ещё больше. Să presupunem că există o anumită secvență de elemente de lungime n cunoscută în prealabil și care nu se schimbă. În orice mod, indiferent de ce, se alege o subsecvență a acestei secvențe în care elementele nu se repetă. Denumim lungimea lui cu k. Evident, această subsecvență este una dintre combinațiile de la n la k. Prin urmare, aceasta poate fi generată de algoritmul descris anterior pentru generarea unei combinații prin numărul de ordine al combinației. Deoarece algoritmul este determinist, subsecvența este determinată complet de secvența inițială și de numărul combinației. Rezumând cele de mai sus, putem implementa cu ușurință algoritmul pentru stocarea unei subsecvențe. Pentru aceasta ne lipsește o altă funcție - NumberFromCombination (). Pentru a salva combinația, trebuie să scrieți numai fișierele k și numărul combinației în fișier. Astfel, salvând o listă de numere k pe 32 de biți, salvăm 4k-8 octeți, scriind doar 8 octeți în loc de 4k (cu condiția, desigur, că k și n sunt suficient de mici pentru ca numărul combinației să nu depășească 2 32 -1) . Mai jos este implementarea funcțiilor declarate. În acest articol, luăm în considerare două abordări diferite pentru generarea de combinații aleatorii fără repetiții. De asemenea, sunt prezentate rezultatele comparative ale performanței metodelor și sunt clarificate circumstanțele în care urmează a fi folosite unul sau altul. Biblioteca implementată permite utilizarea fără probleme a algoritmilor pentru toate containerele și matricele compatibile cu STL.Estimarea complexității timpului
punerea în aplicare
Descrierea funcțiilor
Cod sursă
Generarea unei combinații prin numărul său
Estimarea complexității timpului
punerea în aplicare
Descrierea funcțiilor
Cod sursă
Utilizarea funcțiilor implementate
Compararea a doi algoritmi
Consumul de memorie
productivitate
Unele proprietăți utile ale algoritmului pentru generarea unei combinații prin numărul său
Depozitarea compactă a combinațiilor
concluzie
Articole similare