Un aspect proaspăt la Sortare Perl eficientă

Source: http://www.sysarch.com/Perl/sort_paper.html

Uri Guttman şi Larry Rosler Uri Guttman Perl este un consultant independent, şi pe Internet; uri@sysarch.com Larry Rosler este de la Hewlett-Packard Laboratories, Palo Alto, CA; lr@hpl.hp.com Abstract Sortarea poate fi o problemă majoră în programele Perl. Performanţa poate varia în funcţie de ordine de mărime, în funcţie de modul de sortare este scris. În această lucrare, vom examina Perl de sortare funcţie în profunzime şi descrie modul în care să-l utilizaţi cu date simple şi complexe. În continuare vom analiza şi compara mai multe bine-cunoscute optimizări Perl sortare (inclusiv manevra de orci cum şi Transformare Schwartzian). Ne arată apoi cum să îmbunătăţească performanţa lor în mod semnificativ, de ambalare sortkeys multiple într-un singur şir. În cele din urmă, vom prezenta o abordare proaspătă, folosind un fel cu funcţia de sortkeys ambalate şi fără sortsub. Acest lucru oferă o performanţă mult mai bună decât oricare dintre celelalte metode, şi este uşor să pună în aplicare în mod direct sau prin utilizarea unui modul nou, am creat, după :: Records. NOTĂ: după :: Records au murit în timpul dezvoltării, dar cinci ani mai târziu, după :: Maker a fost eliberat şi a face tot ce a fost promis şi mai mult. Găseşte-l pe CPAN Ce este de sortare şi de ce nu le folosim? Sortarea este reamenajarea unei liste într-o ordine definită printr-o secvenţă monoton crescătoare sau descrescătoare a sortkeys , în cazul în care fiecare sortkey este o funcţie unică de prim rang al elementului corespunzător din listă. (Vom folosi sortkeys pe termen lung, pentru a evita confuzia cu tastele de un hash). Sortarea este folosit pentru a reorganiza o listă într-o secvenţă potrivit pentru prelucrare ulterioară sau să căutaţi. În multe cazuri, de ieşire sortate este destinat pentru oameni pentru a citi, sortarea face mult mai uşor de înţeles de date şi de a găsi un dat dorit. Sortarea este folosit în mai multe tipuri de programe şi pe toate tipurile de date. Acesta este un astfel de comună, consumatoare de resurse operaţiune care algoritmi de sortare şi crearea de implementari optime cuprinde o ramură importantă a ştiinţei calculator. Acest articol este despre crearea de soiuri optime folosind Perl. Vom începe cu o scurtă prezentare de sortare, inclusiv teoria algoritm de bază şi de notaţie, unor algoritmi bine-cunoscute de sortare şi de eficienţa lor, de prelucrare a sortkey, sortarea şi în afara Perl. Următoare vom descrie Perl de sortare funcţie [1] şi modalităţi de bază să-l folosească. Apoi, vom acoperi de manipulare sortkeys complexe, ceea ce ridică întrebarea cum să optimizeze procesarea lor. În cele din urmă vom introduce o metodă relativ nouă, care se mişcă tot sortkey prelucrarea din funcţia de sortare, şi care produce un fel cel mai eficient Perl. Un nou modul este de asemenea descris, care pune în aplicare această tehnică de sortare şi care are un sprijin puternic pentru extracţie sortkey (de prelucrare a datelor de intrare pentru a produce sortkeys. Algoritmul de sortare şi teoria O discuţie completă a algoritmului de sortare şi a teoriei este dincolo de sfera de aplicare a acestei lucrări. Această secţiune va acoperi doar teorie suficient de terminologie şi pentru a explica metodele pe care le folosim pentru a compara tehnici de sortare. Complexitatea unui algoritm este o măsură de resursele necesare pentru a executa algoritmul - de obicei nu este o operaţiune critică care trebuie să fie executată de mai multe ori. Partea de teorie algoritm este imaginind care operaţiunea este factorul de limitare, şi apoi formularea o funcţie care descrie numărul de ori operaţiunii este executat. Această funcţie de complexitate este de obicei scris cu mare-O notaţie - O (f (N)) - în cazul în care `O" se citeşte ca `ordinea" şi `f (N)" este o funcţie de N, dimensiunea de datele de intrare stabilite. O (f (N)) comparaţii au unele proprietăţi neobişnuite. Dimensiunea reală a N este de obicei irelevant pentru executarea corectă a unui algoritm, dar influenta sa asupra comportamentului de f (N) este critic. În cazul în care, pentru un algoritm este O (N * LOGN + N), atunci când N este suficient de mare efect de N pe valoarea funcţiei este neglijabilă în comparaţie cu N * expresia LOGN. Deci, pentru ca algoritmul este doar O (N * LOGN). În multe cazuri, funcţia de comandă calculat pentru un algoritm este un polinom de N, dar veţi vedea doar pe termen lung cu cea mai mare putere, şi nu coeficient este indicat. În mod similar, în cazul în care doi algoritmi au aceeaşi ordine, dar o face mai mult de lucru pentru fiecare operaţiune, ele sunt încă echivalentul în spaţiu ordine, chiar dacă s-ar putea fi o diferenta substantiala in real-lume viteze. Acest ultim punct este crucial în tehnicile pe care le va arăta pentru a optimiza felul Perl, toate care au aceeaşi funcţie de mare-O, O (N * LOGN). Iată câteva algoritmi bine-cunoscute şi funcţiile lor de ordine (adaptat din [2]): Notaţie Nume Exemplu O (1) constant matrice sau indicele de hash O (LOGN) logaritmică binar de căutare O (N) liniar şir de comparaţie O (N * LOGN) n log n avansat de sortare O (N ** 2) pătratică simplu de sortare O (N ** 3) cub matrice de multiplicare O (2 ** N) exponenţială set de partiţionare Operaţiune de sortare critic este de a determina, în care, pentru a pune perechi de elemente de date. Comparaţie poate fi la fel de simplu ca a găsi dacă două numere sunt egale sau care este mai mare decât alta (sau de a face operaţiuni similare pe siruri de caractere), sau poate fi destul de complexe. Algoritmi simpli de sortare (cu bule felul sau de inserţie) compara fiecare element de la fiecare dintre celelalte în mod repetat, astfel încât complexitatea lor este O (N ** N). Chiar şi cu optimizarea triunghi ($ x este egal cu $ x, si $ x, comparativ cu $ y este negativ de $ y, comparativ cu $ x), care reduce la funcţia de O ((N * (N-1)) / 2), complexitatea este încă O (N ** N), astfel cum sa explicat mai sus. Dar aceste algoritmi au utilizări lor. Atunci când N este foarte mic, ele pot fi de fapt mai repede decât alte metode, deoarece O (1) şi O (N) deasupra de felul avansate pot depăşi O (N ** 2) comportamentul de felul simple. "Algoritmii de lux sunt lente atunci când N este mic, iar N este de obicei mic algoritmi de lux au constante mari.". [3] de cazuri cu adevarat importante, care sunt în valoare de îngrijire în codificarea, apar atunci când N este mare. Metode avansate de sortare în mod repetat partiţie înregistrările care urmează să fie sortate în seturi mai mici, pentru a reduce numărul total de comparatii necesare.Complexitatea lor este O (N * LOGN), care poate fi mult mai puţin decât O (N ** 2) pentru valori suficient de mari de N. Aceste includ algoritmi de sortare `copac", `coajă de sortare", şi `quicksort". [4] Unii algoritmi de sortare specializate (cum ar fi `fel Radix"), de lucru prin compararea piese de sortkeys numerice, şi poate atinge complexitatea liniar (O (N)) [5].Aceste metode nu sunt de uz general, deci nu le vom aborda în continuare. O proprietate de algoritmi de sortare este dacă acestea sunt stabile. Un fel stabil păstrează ordinea în datele extrase din două elemente care compara egal. Unele probleme de sortare nevoie de stabilitate. Algoritmii de sortare simple sunt, în general, stabile, cele avansate nu sunt. Vom arăta cum să facă un fel de avansate de Perl se comporta stabil, dacă este necesar. O variaţie de sortare de important este atunci când elementele originale de date nu pot fi mutate în jurul valorii de convenabil de amestecarea algoritmul de sortare a lui. Deci, în loc de sortare a elementelor direct, sortarea numerele lor de index. Puteţi utiliza apoi sortate indicii pentru a crea o listă de elemente sortate. Unii sortare operatori în alte limbi (APL vine în minte), pur si simplu returnati indicii sortate, şi este de până la programator de a le folosi corect. Vom arăta cum de a crea un fel de eficiente şi în cazul în care indicele de Perl este util. Sortkeys Dacă sunteţi de sortare un set de elemente de scalare de valoare în cazul în care comparaţia se uită la elementul întreg, sortkey este pur şi simplu element de întregul.Mai general, sortkey se bazează pe anumite proprietăţi care sunt funcţii de toate sau o parte a elementului. Aceste chei pot fi extrase din proprietăţile interne ale părţi ale elementului ( câmpuri ) sau derivate din proprietăţile externe ale elementului (cum ar fi data de modificare a unui fişier numit de către elementul, care este destul de scump pentru a prelua de la sistemul de fişiere). Pentru a evita calculul repetat al sortkeys, procesul de sortare trebuie să păstreze înregistrările şi de asociere între sortkeys lor, extrase sau derivate. Sortare teorie şi algoritmi ignora de obicei, costul de această asociere, aşa cum este de obicei un factor constant al operaţiunii comparaţie. Dar, aşa cum vom vedea mai târziu, în lumea reală, că eliminarea sau reducerea-l deasupra capului de la O (N * LOGN) la O (N) este foarte valoros, mai ales ca N creste. Sortkeys complexe pot adauga foarte mult la regia de fiecare comparaţie. Acest lucru se întâmplă în cazul în care înregistrările trebuie să fie sortate de către primare, secundare, şi mai mici de ordinul chei. Acest lucru este, de asemenea, cunoscut sub numele de a face o subsort pe taste mai mici. Extragerea şi compararea sortkeys complexe, poate fi costisitoare şi de erori. Nu punerea în aplicare de uz general al unui algoritm de sortare se pot sprijini eficient de extragere şi compararea diferitelor tipuri de sortkeys. Prin urmare, cele mai multe implementări de sortare a oferi o interfaţă simplă pentru a apela un sortsub - o subrutină comparaţie personalizat, care este trecut doi operanzi. Aceste operanzii pot fi înregistrările în sine, sau trimiteri la sau indici de înregistrări complexe. Comparaţie returnează o valoare negativă, la zero, sau pozitiv, în funcţie de ordonare a sortkeys celor două înregistrări. Programator este responsabil pentru orice preprocesare a înregistrărilor pentru a genera sortkeys şi orice postprocesare pentru a prelua datele sortate. Funcţia de sortare generic administrează doar comparaţiile şi shuffle operanzii în ordine sortată. Ca Perl lui după funcţie este O (N * LOGN), eficienţa trebuie să provină de la extragerea şi compararea sortkeys folosind cel puţin cantitatea de muncă. O mare parte a acestei lucrări va fi de aproximativ metode de a face extracţie sortkey şi compararea cât mai eficient posibil. Extern de sortare Fiecare sistem de operare populare comercial oferă un fel de utilitate. Unix / POSIX arome au de obicei un fel de comandă, care este rapid si destul de flexibil în ceea ce priveşte extragerea sortkey din fişierele text. În unele cazuri, Unix / POSIX după comandă poate fi mai uşor de cod şi mai eficientă decât utilizarea Perl sortare funcţia. Mai mulţi vânzători care vinde extrem de optimizate comerciale de sortare pachete care au primit zeci de ani de atenţie şi pot gestiona cantităţi masive de date. Dar ei sunt foarte scumpe şi nu sunt potrivite pentru utilizarea în interiorul unui program Perl. Toate acestea sunt capabile de a trata eficient cu cantităţi foarte mari de date, folosind mass-media externe, cum ar fi fişierele de pe disc sau banda pentru depozitare intermediară atunci când este necesar. În schimb, Perl sortare funcţie necesită ca intreaga lista de operanzi să fie în (reale sau - mult mai scump - virtuală) de memorie în acelaşi timp. Deci, Perl nu este instrumentul adecvat pentru a utiliza pentru felul uriaşe (în cazul în care mare este definită de limitele de memorie de sistem de dvs.), care nu se considera în continuare. Interne de sortare Perl sortare funcţie utilizează o punere în aplicare a algoritmului quicksort, care este similar (dar mai robust decât) qsort în funcţia de ANSI / ISO Standard C Library [6]. În cel mai simplu de utilizare, Perl sortare funcţie necesită nu sortsub: @out = sort @in; Acest implicite sortează datele în ordine crescătoare lexicografic, folosind rapid C memcmp funcţie ca operaţiunea comparaţie. În cazul în care o localizare este specificat, el substituie mai complicat şi ceva mai lent, C, strcoll funcţie. Dacă doriţi orice fel de comanda, altele decât aceasta, trebuie să ofere o comparaţie sortsub personalizat. Sortsub poate fi specificat fie ca un bloc de cod, numele de o subrutină, sau o typeglob care se referă la o subrutina (un coderef ). În Perl 5.6, o variabilă care conţine un scalar coderef poate fi, de asemenea, folosit pentru a specifica sortsub. În scopul de a optimiza chemarea sortsub, Perl trece trecerea de obicei de argumente prin intermediul @ _, folosind în schimb, o mai eficientă metodă de destinaţie specială. În cadrul sortsub, variabilele globale speciale pachet de $ a şi $ b sunt pseudonime pentru cele două operanzi comparate. Sortsub trebuie să returneze un număr mai mic decât 0, egal cu 0, sau mai mare decât 0, în funcţie de rezultatul comparării sortkeys de $ a şi $ b. Variabilele speciale $ a şi $ b nu ar trebui să fie folosit pentru a schimba valorile de orice date de intrare, deoarece acest lucru poate rupe algoritmul de sortare. Chiar simplu de sortare particularizată în Perl va fi mai eficientă decât utilizarea comparaţie implicită. Sortare implicită rulează în întregime în cod C în miez Perl, dar orice sortsub trebuie să execute cod Perl. O optimizare bine-cunoscut este de a reduce cantitatea de cod Perl de executare şi să încerce să rămână în interiorul nucleul Perl cât mai mult posibil. Mai târziu vom vedea diverse tehnici de optimizare, care va reduce cantitatea de cod Perl executat. Scopul principal al acestei lucrări este de a efectua toate tipurile utilizând comparaţia implicită. Iată cum un lexicografic explicit ascendentă se va face folosind un sortsub: @out = sort { $a cmp $b } @in; Pentru o simplă măsurare, compara implicit şi explicit în Benchmark-A1 din apendicele A. Metoda implicită este de aproximativ de două ori la fel de rapid ca metoda de explicit. Felul Trivial Noi numim felul triviale cele care folosesc întreaga înregistrare ca sortkey şi de a face doar o cantitate minimă de procesare a înregistrării. Pentru a face felul triviale Perl, altele decât ascendentă lexicografic, trebuie doar pentru a crea o sortsub adecvat. Aici sunt unele comune care îndeplinesc funcţii utile. Cel mai simplu exemplu este sortare ascendent numeric, care utilizează pitoresc monikered `nava spatiala" operator: @out = sort { $a <=> $b } @in; O capacitatea de sortare numerică este necesar, deoarece ordinea lexicografică de, să zicem, (1, 2, 10) nu corespunde cu ordinea numerică. Dacă doriţi ca fel de a fi, în ordine descrescătoare, există trei tehnici care le puteţi utiliza. Cel mai rău este de a anula rezultatul comparaţiei în sortsub. Mai bine este de a inversa ordinea de comparaţie prin schimbarea $ a şi $ b. Acest lucru are aceeaşi viteză ca un fel înainte corespunzător. # descending numeric @out = sort { $b <=> $a } @in; # descending lexicographic @out = sort { $b cmp $a } @in; Cea mai bună metodă este să se aplice inversă funcţia de rezultatul unei implicit, ascendent Sortare lexicografică. @out = reverse sort @in; Reţineţi că acest lucru este mai rapid decât cu ajutorul sortare explicită descendent lexicografic, pentru motivul discutat de mai sus: de sortare implicită este mai rapid decât cu ajutorul unui sortsub. Inversă funcţie este eficientă, deoarece se mişcă doar în jurul valorii de pointeri. O altă problemă comună este de sortare cu insensibilitate caz. Acest lucru este uşor de rezolvat prin LC sau uc funcţie. Fie se va da aceleaşi rezultate. @out = sort { lc $a cmp lc $b } @in; Obiectivul de referinţă A1 analizează aceste exemple, în funcţie de mărimea de intrare. O (N * LOGN) comportamentul este aparentă, precum şi costul de a folosi chiar si un simplu încorporat în funcţie ca şi LC în sortsub. Sortează campuri şi de înregistrare Cele de mai sus felul triviale sorta lista de intrare folosind ca sortkey întregul şir (pentru un fel de lexicografic) sau primul număr în fiecare datum (pentru o sortare numerică). Mai mult de obicei, sortkey se bazează pe o proprietate, care este o funcţie de toate sau o parte din fiecare dată. Mai multe subchei individuale pot fi combinate într-un singur sortkey sau pot fi comparate în perechi individual. Un şir de complex poate fi împărţit în câmpuri, dintre care unele pot servi ca subchei. De exemplu, Unix / POSIX fel comanda prevede construit-in-suport pentru colaţionare bazat pe unul sau mai multe domenii de intrare, Perl sortare funcţia de nu, iar programatorul trebuie să le furnizeze. Un modul CPAN se concentreaza pe felul câmpuri [7]. Dacă datele dvs. sunt înregistrările care sunt siruri de caractere complexe sau referinte la tablouri sau hashes, trebuie să efectuaţi comparaţii pe piesele selectate din înregistrări. Aceasta se numeste sortare de înregistrare . (Felul campat sunt un subset de felul de înregistrări.) În exemple de cod care urmează, KEY () este menit să fie înlocuită cu un cod Perl care efectuează extracţia sortkey. Este cel mai bun este că nu ar fi un apel de subrutină real, deoarece apelurile în cadrul sortsubs subrutină poate fi costisitoare. Apelurile către built-in functii Perl (cum ar fi apelurile la LC , în exemplul de mai sus) sunt ca operatori de Perl, prin urmare, relativ mai puţin costisitoare. Când sortarea înregistrărilor de coarde, $ a şi $ b sunt stabilite la aceste siruri de caractere, astfel încât să extragă sortkeys vă efectua diverse operatiuni de coarde, în general, pe înregistrări. Funcţii utilizate în mod obişnuit pentru această includ scindare , substr , despacheteaza , şi m / /. Iată un exemplu, sortarea o listă de parolă de fişiere prin linii numele de utilizator folosind divizat . Câmpurile sunt separate de doua puncte, iar numele de utilizator este primul câmp. @out = sort { (split ':', $a, 2)[0] cmp (split ':', $b, 2)[0] } @pw_lines; Multi-subcheie de felul În unele cazuri, aveţi nevoie pentru a sorta înregistrările de o subcheie de primar, apoi pentru toate înregistrările, cu aceeaşi valoare subcheia primar, aveţi nevoie pentru a sorta de o subcheie secundar. Un mod oribil ineficient de a face acest lucru este pentru a sorta în primul rând prin subcheia primar, pentru a primi apoi toate înregistrările cu o subcheie dat şi sortaţi-le de subcheia secundar. Metoda standard este de a face un fel de multi-cheie. Aceasta presupune extragerea unei subcheie pentru fiecare domeniu, şi compararea subcheile asociate, în ordinea de prioritate. Deci, dacă două înregistrări cu subcheia primar aceeaşi sunt comparate, acestea vor fi de fapt comparat pe subcheia secundar. Sortare pe mai mult de două chei se face prin extinderea logica. Perl are o caracteristică foarte frumos, ceea ce face multi-cheie felul uşor să scrie. | | (Scurt-circuit sau a operatorului) returnează valoarea efectivă a operandului primul logic adevărat se vede. Deci, dacă utilizaţi | | pentru a înlănţui un set de comparatii cheie, compararea primul este subcheia primar. Dacă o pereche de chei primare compara egal, valoarea sortsub de întoarcere va fi rezultatul comparaţie subcheii secundar. Un exemplu va ilustra aceasta scara `" de comparatii mai bine decât mai mult text. Aici este un fel de trei-subcheie: @out = sort { # primary subkeys comparison KEY1($a) cmp KEY1($b) || # or if they are equal # return secondary comparison # descending numeric comparison KEY2($b) <=> KEY2($a) || # or if they are equal # return tertiary comparison # lexicographic comparison KEY3($a) cmp KEY3($b) } @in; Naive multi-subcheie record felul În cele două exemple anterioare, am arătat un fel de extracţie relativ scump sortkey (prin divizare ), şi un fel de multi-subcheia. Să le combina. Pentru concret, vom face cu o problemă care a primit multa atentie in comp.lang.perl.misc - sortarea o listă de adrese IP în formă `punctata-quad". Fiecare element al listei este un şir de forma "nnn.nnn.nnn.nnn \ tabc.xyz.com \ n", unde nnn reprezinta un intreg zecimal între 0 şi 255, cu sau fără a conduce la zero-padding. În abordarea cea mai naiv, am un fel pe fiecare din aceste patru domenii numerice ar fi chei individuale, în succesiune. @out = sort { my @a = $a =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/; my @b = $b =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/; $a[0] <=> $b[0] || $a[1] <=> $b[1] || $a[2] <=> $b[2] || $a[3] <=> $b[3] } @in; Chiar şi pentru listele de mici, acest lucru este foarte lent, din cauza operaţiunilor executate în mai multe Perl sortsub pentru fiecare dintre cele O (N * LOGN) comparaţii. Calculul un singur plin de string-sortkey Pentru a îmbunătăţi performanţa, vom deriva din aceste patru chei de un singur plin de string-sortkey pentru fiecare adresa IP, pe care le putem folosi apoi pentru a sorta matrice monoton în creştere. Următoarea expresie produce cel mai scurt tasta, un şir de patru octeţi, cu cel de calcul Perl: pack 'C4' => $string =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/ Aceasta foloseşte operatorul virgula fantezie, => , pe care le puteţi citi ca `aplicate". Am sorta apoi aceste sortkeys lexicografic. Următor, atunci, este următoarea abordare pentru realizarea unui fel de eficiente: @out = sort { pack('C4' => $a =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/) cmp pack('C4' => $b =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/) } @in; A2 de referinţă arată că compararea subcheile în perechi este mai puţin eficientă decât de ambalare şi compararea lor pline de siruri de caractere. Această observaţie este valabilă pentru toate metodele de sortare. În referinţă suplimentare de felul avansate pentru această problemă, vom folosi mereu sortkeys preambalate. Cu toate acestea, sortarea naiv este încă teribil ineficient, deoarece ambele sortkeys sunt recalculate de fiecare dată când un operand de intrare este comparat cu un alt. Ceea ce avem nevoie acum este o modalitate de a calcula fiecare sortkey doar o singură dată şi să-şi amintească rezultat. Felul avansate Ca toate felurile în Perl utilizează interna sortare funcţia şi, prin urmare, acelaşi algoritm quicksort, tot felul de Perl sunt de ordinul O (N * LOGN). Noi nu putem imbunatati pe care, aşa că trebuie să abordeze alte aspecte pentru a obţine eficienţă. Ca complexitatea este stabilit, combaterea factorilor de constante pot fi fructuoase, iar în lumea reală, pot produce îmbunătăţiri semnificative ale eficienţei. Atunci când un sortsub are nevoie pentru a genera o sortkey complex, care se face în mod normal, O (N * LOGN) de ori, dar sunt doar înregistrări N, N, prin urmare, sortkeys. Ce se întâmplă dacă am fost pentru a extrage sortkey o singură dată pe înregistrare, şi ţine evidenţa de care a aparţinut care sortkey înregistrare? Caching de sortkeys Mod evident de a asocia sortkeys cu înregistrările de la care au fost create este de a folosi un hash. Hash poate fi creat într-o trecere peste preprocesare a datelor.Dacă dimensiunea aproximativă de set de date este cunoscut, preallocating hash îmbunătăţeşte performanţa. keys my %cache = @in; $cache{$_} = KEY($_) for @in; Următorul stabileşte cache mai eficient, folosind o felie hash: keys my %cache = @in; @cache{@in} = map KEY($_) => @in; Apoi sortsub pur şi simplu felul de valorile de sortkeys cache. @out = sort { $cache{$a} cmp $cache{$b) } @in; În esenţă, am înlocuit calcule lungi în sortsub de căutări rapide (O (1)) de dispersie. Dacă vrei să faci un complex multi-cheie de comparaţie, fie trebuie să utilizaţi un cache separat pentru fiecare subcheia sau subcheile combina într-un mod similar cu optimizări plin de-sortare, vom descrie mai târziu. Aici este un exemplu de fostul: keys my %cache1 = @in; keys my %cache2 = @in; ($cache1{$_}, $cache2{$_}) = map { KEY1($_), KEY2($_) } $_ for @in; @out = sort { $cache1{$a} cmp $cache1{$b) || $cache2{$b} <=> $cache2{$a} } @in; Alternativ, un cache de multi-nivel poate fi folosit, care sacrifică viteza pentru a economisi ceva spatiu: keys my %cache = @in; $cache{@in} = map [ KEY0($_), KEY1($_) ] => @in; @out = sort { $cache{$a}[0] cmp $cache{$b)[0] || $cache{$b}[1] <=> $cache{$a}[1] } @in; Un punct important despre felul în cache este faptul că nu este nevoie de postprocesare pentru a prelua înregistrările sortate. Metoda sortează înregistrările reale, dar foloseste cache pentru a reduce extracţia sortkey la O (N). Manevra orci (OM) Manevra orci (inventat de către Joseph N. Hall [8]), elimină trecere preprocesare asupra datelor, care ar putea salva păstrând o copie a datelor în cazul în care sunt citite direct dintr-un fişier. Face de extracţie sortkey doar o dată pe înregistrare, aşa cum se verifică hash pentru a vedea dacă acesta a fost făcut înainte. De testare şi de depozitare a sortkey se face cu | | = operatorului (scurt-circuit sau de-cesiune), care va evalua şi va atribui expresia din dreapta pentru a lvalue pe stânga, în cazul în care lvalue este falsă. Numele `orci cum" este un joc de cuvinte sau `pe-cache". Declaraţia completă în sortsub arata ca acest lucru: keys my %or_cache = @in; @out = sort { ($or_cache{$a} ||= KEY($a)) cmp ($or_cache{$b} ||= KEY($b)) } @in; În cazul în care vede sortkey de dolari este un cache, şi, dacă nu, se extrage şi memorează în cache-l. Sortkey de $ a este apoi comparat cu sortkey pentru $ b (care se găseşte în acelaşi mod). Aici este un exemplu de o comparaţie cu două subcheie folosind doua cache-uri: keys my %or_cache1 = @in; keys my %or_cache2 = @in; @out = sort { ($or_cache1{$a} ||= KEY1($a)) cmp ($or_cache1{$b} ||= KEY1($b)) || ($or_cache2{$b} ||= KEY2($b)) <=> ($or_cache2{$a} ||= KEY2($a)) } @in; OM are unele defecte minore de eficienţă. Un test suplimentar este necesar, după fiecare sortkey este preluat din cache-sau. În plus, dacă o sortkey extras are o valoare de fals, acesta va fi recalculat de fiecare dată. Acest lucru, de obicei, funcţionează bine, deoarece sortkeys extrase sunt rareori false. Cu toate acestea, cu excepţia cazului când necesitatea de a evita citirea de date de două ori este critică, după explicit cache este întotdeauna uşor mai rapid decât OM. (A se vedea A3 Benchmark.) Transform Schwartzian (ST) O abordare mai eficientă a sortkeys caching, fără a utiliza variabile denumite temporare, a fost popularizat de Randal L. Schwartz, numit şi Transformare Schwartzian [9, 10]. (Ar trebui să fie într-adevăr numit Transformare Schwartz, după modelul Fourier şi transformã Laplace, dar este prea târziu pentru a rezolva numele de acum.) Invenţia semnificativă în ST este utilizarea de tablouri anonime pentru a stoca înregistrări şi sortkeys lor. Cele sortkeys sunt extrase o dată, în timpul unei preprocesare trecere peste toate datele din lista pentru a fi sortate (la fel cum am făcut înainte de calcularea în cache-ul de sortkeys). @out = map $_->[0] => sort { $a->[1] cmp $b->[1] } map [ $_, KEY($_) ] => @in; ST nu a sorta datele reale de intrare. Se sortează trimiterile la tablouri anonime, care conţin înregistrările originale şi sortkeys. Deci, avem de a postprocess pentru a prelua înregistrările sortate din matrice anonimi. Utilizarea ST pentru un fel de multi-subcheie este simplă. Păstrează doar fiecare subcheie succesive extrase în următoarea intrare în matrice anonim. În sortsub, face o sau între comparaţii de subchei succesive, la fel ca OM şi felul naive. @out = map $_->[0] => sort { $a->[1] cmp $b->[1] || $b->[2] <=> $a->[2] } map [ $_, KEY1($_), KEY2($_) ] => @in; Pentru o deconstrucţie foarte luminoase şi reconstrucţie a ST, a se vedea [11]. Sortare ambalate, implicit Fiecare din tehnicile avansate de sortare descrise mai sus, salvează operanzii să fie sortate, împreună cu sortkeys lor. (In felul cache, operanzii sunt cheile de la un hash şi sortkeys sunt valorile hash, în Transform Schwartzian, operanzii sunt primele elemente ale tablouri anonime, cele sortkeys sunt alte elemente de matrice.) Ne extindem acum că ideea de a salva operanzii să fie sortate, împreună cu impachetat-string sortkeys, folosind concatenare. Aceasta optimizare puţin cunoscut îmbunătăţeşte pe ST prin eliminarea sortsub în sine, bazându-se pe sortare lexicografica implicit, care, după cum am arătat mai devreme este foarte eficient. Aceasta este metoda utilizată în noul Sortare :: Maker modul. Pentru a realiza acest obiectiv, vom modifica ST prin inlocuirea matrice sale anonime de siruri de caractere ambalate. În primul rând am pachet într-un singur şir fiecare subcheie, urmată de ultima operand să fie sortate. Apoi ne-am sorta lexicografic pe aceste siruri de caractere, şi în final vom prelua operanzi de la sfârşitul de siruri de caractere. @out = map substr($_, 4) => sort map pack('C4' => /(\d+)\.(\d+)\.(\d+)\.(\d+)/) . $_ => @in; Mai multe metode pot fi utilizate, individual sau în combinaţie, pentru a construi siruri de caractere ambalate, inclusiv de concatenare, pachet , sau sprintf . Mai multe metode pot fi folosite pentru a prelua operanzii, inclusiv substr (prezentat aici), care este probabil să fie cel mai rapid, divizat , despacheteaza sau un regex. Subcheile mai multe sunt pur şi simplu concatenate, delimitate corespunzător, dacă este necesar. Tehnici de calcul pentru chei de diferite tipuri sunt prezentate în Anexa B. Standarde de sortare ambalate, implicit A4 de referinţă compară cele două cele mai avansate de uz general tehnici de sortare, ST-şi ambalate implicite. Aceste tipuri mai multe etape sunt măsurate atât în ​​etapele individuale cu datele salvate intermediare şi ca declaraţiile unice. Sortare ambalate-default este de aproximativ de două ori la fel de rapid ca ST, care este cel mai rapid algoritm de sortare familiar Perl. Anterior, am arătat un fel de banal folosind LC funcţia. Chiar şi pentru acest caz, sortare ambalat-default oferă o performanţă mai bună atunci când mai mult de câteva elemente de date puţine sunt sortate. Vezi A5 Benchmark, care arată cvasi-O (N), comportament pentru sortare ambalat-default (deoarece timpul de sortare este relativ mic pentru extracţie sortkey). Sortarea unei liste de matrice sau hashes Luaţi în considerare problema comuna de sortare de două-dimensional structura de date, o listă de referinţe la tablouri sau a hash-uri, în cazul în care sortkeys sunt funcţii de valorile submembers. Dacă ar fi să folosească metoda de ambalat-implicit, referinţele vor fi convertite la şiruri şi anexat la sortkeys. După sortare, operanzii pot fi preluate ca siruri de caractere, dar nu ar mai fi folosite ca referinţe. În schimb, trebuie să ne folosim indicii ale membrilor listă ca operanzii să fie sortate. De referinţă următor compară un plin-sortkey fel ST, cu un fel de indici care utilizează abordarea ambalat-default. Lista sortate cuprinde trimiteri la tablouri, fiecare dintre care are două elemente: O adresă IP (care serveşte ca sortkey primar), şi un nume de domeniu (care serveşte ca sortkey secundar). Acestea sunt aceleaşi date ca şi utilizate în obiectivele de referinţă de mai sus, împărţite în două elemente de matrice. @out = map $_->[0] => sort { $a->[1] cmp $b->[1] } map [ $_, pack('C4 A*' => $_->[0] =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/, $_->[1]) ] => @in; my $i = 0; keys my %h = @in; @h{ map pack('C4 A* x N' => $_->[0] =~ /(\d+)\.(\d+)\.(\d+)\.(\d+)/, $_->[1], $i++) => @in } = @in; @out = @h{ sort keys %h }; Sortare indexate este mai rapid decât ST din nou. (A se vedea A6 Benchmark.) Felul indexate şi sortează stabile În sortare indexate, indicele auto-incrementarea $ i se asigură că nu există înregistrări matrice va avea sortkeys identice ambalate. Este, de asemenea, asigură că de sortare va fi stabilă. Orice fel Perl pot fi stabilizate prin utilizarea unei astfel de indice final tie-rupere subcheia. Pentru o sortare indexate, indicele este de fapt operandului fiind sortate.Acest fapt oferă un alt avantaj de performanţă posibil pentru sortare indexat. Înregistrările reale să fie sortate (care poate fi siruri lungi), nu trebuie să fie anexate la sortkeys, care ar crea oa doua copie a fiecărei înregistrări. Utilizarea sortare indexate, înregistrările pot fi recuperate după sortare de la datele originale, folosind indicii sortate. Sortare :: Maker modul După :: Maker este pe CPAN şi implementează TRB pentru toate tipurile de valori Perl. Concluzii Impachetare subchei în siruri de caractere care pot fi comparate lexicografic îmbunătăţeşte performanţa tuturor tehnicilor de sortare, în raport cu metoda obişnuită de a compara chei individuale, în perechi. Ambalare operanzii cu sortkeys permite de sortare pentru a se face folosind implicit ascendentă compararea lexicografică (fără sortsub). Acest lucru dă un fel de semnificativ mai rapid decât manevra de orci sau Transformare Schwartzian. Procesul de sortare poate aproximativ O (N) comportament, deoarece O (N * LOGN), timp de sortare în sine este mică în comparaţie cu timpul necesar pentru a extrage sortkeys. Sortare-ambalate sortkey poate fi scris în mod explicit, sau de tip nou :: modul Maker poate fi folosit. Mulţumiri Această idee a fost adus în atenţia noastră de Michal Rutka [12]. John Porter a participat la iniţierea acestui proiect şi a revizuit un proiect de hârtie. Referinte 1. Sortare funcţia de om pagina, http://www.perl.com/CPAN/doc/manual/html/pod/perlfunc/sort.html 2. Kernighan, BW & Pike, R., (1999). Practica de programare, p.. 41. Addison-Wesley. 3. Pike, R. (1989). Note privind programarea în C, http://wwwwbs.cs.tu-berlin.de/~~HEAD=NNS ~~~HEAD=NNS Jutta / c / pikestyle.html 4. Knuth, DE (1998). Arta de a Programarea calculatoarelor: Sortare şi căutarea (Vol. 3, 2-a ediţie), cap. 5. Addison-Wesley. 5. Sedgewick, R. (1983). A lgorithms, cap. 10. Addison-Wesley. 6. ANSI / ISO 9899-1992, sect. 4.10.5.2. American National Standards Institute. 7. Hall, JN, Sort :: Domenii - linii de sortare care conţin câmpuri delimitate , http://www.perl.com/CPAN/modules/by-module/Sort/JNH/ 8. Hall, JN (1998). efectiv de programare Perl , p.. 48. Addison-Wesley. 9. Cum pot gasi o serie de 10. Christiansen, T. & Torkington, N. (1998). Cookbook Perl , Reteta 4.15: "Sortare o listă de câmpuri calculabil". O'Reilly. 11. Christiansen, T., Mult mai mult decât tot ceea ce aţi dorit vreodată să ştiţi despre sortare , http://www.perl.com/CPAN/doc/FMTEYEWTK/sort.html 12. Rutka, M., în comp.lang.perl.misc . http://x4.dejanews.com/ [ST_rn = PS] / getdoc.xp AN 397853353? =) Anexa A: Standarde Un avertisment: analiza comparativă utile depinde de izolarea judicioasă a variabilelor relevante, atât în ​​algoritmii de a fi evaluate şi în seturile de date folosite.Implementari diferite pot da rezultate diferite, relative, chiar cu algoritmi şi aceleaşi date. Astfel, toate rezultatele trebuie să fie verificată în condiţii proprii. Pe scurt, kilometraj dvs. poate varia. În următoarele obiective de referinţă, toate datele reprezintă de timp (în microsecunde), pe linie, în datele de intrare, care medie 35 de caractere pe linie. Toate tablouri nominale şi hashes sunt preallocated, care reduce variaţia în măsurătorile din cauza alocării de stocare. Benchmark A1. Felul Trivial Control @out = @in; Implicit @out = sort @in; Inversa @out = reverse sort @in; Explicit @out = sort { $a cmp $b } @in; Insensibil @out = sort { lc $a cmp lc $b } @in; Numărul de linii: 100 1000 10K 100K Control 5 6 7 8 Implicit 9 13 19 25 Inversa 9 14 19 26 Explicit 17 25 37 50 Insensibil 47 62 91 119 Benchmark A2. Felul naivi (adrese IP) Numărul de linii: 100 1000 10K 100K Subchei separate 697 1251 1732 2758 Sortkeys ambalate 583 1002 1363 1814 Benchmark A3. Felul în cache (sortkeys ambalate) Numărul de linii: 100 1000 10K 100K Caching 66 75 85 74 Triere 49 87 122 164 Total de cache de sortare 116 163 215 240 Orci cum Manevră 125 168 221 256 Benchmark A4. Avansate de ambalat-cheie felul Numărul de linii: 100 1000 10K 100K ST Anon matrice 80 84 84 75 Triere 27 47 76 97 Regăsire 13 18 20 17 O declaraţie 116 150 177 191 Ambalate Implicit Ambalare 61 63 65 67 Triere 9 12 18 25 Regăsire 12 12 13 12 O declaraţie 73 79 86 93 Benchmark A5. Un alt aspect la un fel de banal Insensibil @out = sort { lc $a cmp lc $b } @in; Împachetat @out = map substr($_, 1 + rindex $_, "\0")=> sort => map "\L$_\E\0$_" => @in; Numărul de linii: 10 100 1000 10K 100K Insensibil 19 38 62 91 118 Împachetat 22 22 24 25 27 Benchmark A6. Două-dimensionale plin de-sortkey felul Numărul de linii: 100 1000 10K 100K ST 243 314 359 435 Index 200 285 323 259 Anexa B: plin de explicite, implicite felul B1. Crearea şi combinarea subchei Sortable de coarde Acest lucru este permis de preprocesare (prima harta executat). @sorted = map ... => sort => map KEY($_) . $_ => @data; Pentru a crea şi de a combina subcheile şi operanzi pentru a fi sortate, orice combinaţie de concatenare, interpolare, Pack , sau sprintf poate fi utilizat, acesta din urmă cu două formate simple sau compuse. Fix-şiruri de lungime (ascendent): simpla interpolare pack('... An ...', ...) sprintf('... %s ...', ...) Fix-şiruri de lungime (descendent): Bit-completează şirul primul. $subkey = $string ^ "\xFF" x length $string Apoi, ca un ascendent fata de lungime fixă ​​şir. Bytes Null ("\ 0") sunt folosite pentru a rezilia subchei de coarde de lungimi diferite, ca şi asigură ordonarea lexicografică. Dacă o subcheie şir poate conţine un octet null, atunci acesta trebuie să fie de lungime fixă. Dacă oricare dintre operanzi să fie sortate pot conţine bytes nule, atunci fiecare subcheie trebuie să aibă lungime fixă. Variind de şiruri de lungime (ascendent): Terminate şir cu un octet null, să-l separe de la reuşita subchei sau operand. interpolare: "$ string \ 0" Pack ("... A * x ...", ...) sprintf ('% s ... \ 0 ...', ...) Variind de şiruri de lungime (descendent): Faceti o prepass asupra datelor pentru a găsi lungimea celui mai lung şir. my $len = 0; $len < length and $len = length for map KEY($_) => @data; Apoi, nul-pad-ul pentru fiecare sir la lungime şi se procedează ca mai sus pentru a fixa şiruri de lungime (descendent). $subkey = pack("a$len", $string) ^ "\xFF" x $len Nesemnate, 32-bit numere întregi (ascendent): Pack sau zero-pad-ul de lungime fixă. Preferat - doar 4 octeţi: pack('... N ...', ...) Care poate fi citită - dar 10 octeţi: sprintf('... %.10u ...', ...) Semnate two's-complement 32-biţi întregi (ascendent): Bias la unsigned de xoring bitul de semn, apoi se tratează ca fara semn. $subkey = pack('N', $number ^ (1 << 31)); Numere in virgula mobila (ascendent): Acest cod presupune ca numere in virgula mobila sunt reprezentate în binar utilizând formatul IEEE. Creaţi o subrutină care împachetează o dublă în comandă de reţea (big-endian). BEGIN { my $big_endian = pack('N', 1) eq pack('L', 1); sub float_sort ($) { ($big_endian ? pack 'd', $_[0] : reverse pack 'd', $_[0]) ^ ($_[0] < 0 ? "\xFF" x 8 : "\x80" . "\x00" x 7) } $subkey = float_sort($number); Descendent întregi sau numere in virgula mobila: Nega valoarea, apoi utilizaţi una corespunzătoare de mai sus. B2. Extragerea operanzii din siruri sortate Acest lucru este permis de postprocesare (doua hartă executat). @sorted = map RETRIEVE($_) => sort => map ... => @data; Dacă toate subcheile au cunoscut lungime, utilizaţi lungime totală: Preferată pentru eficienţa: @sorted = map substr($_, $length) => ... TMTOWTDI: @sorted = map unpack("x$length A*", $_) => ... Dacă oricare dintre subchei a diferite lungime, asiguraţi-vă că ultimul caracter în sortkey complet ambalate este un octet null, căuta, apoi, pentru că de la dreapta: Preferată pentru eficienţa: @sorted = map substr($_, 1 + rindex $_, "\0") => ... TMTOWTDI: @sorted = map (split /\0/)[-1] => ... @sorted = map /([^\0]+)$/ => ...