Odpowiedź Broroofa jest naprawdę sprytna - imponująco sprytna, naprawdę ... zgodna z RFC4122, nieco czytelna i kompaktowa. Niesamowite!
Ale jeśli patrzysz na to wyrażenie regularne, te wiele replace()wywołań zwrotnych, wywołań funkcji toString()i Math.random()funkcji (gdzie używa tylko 4 bitów wyniku i marnuje resztę), możesz zacząć zastanawiać się nad wydajnością. Rzeczywiście, joelpt postanowił nawet wyrzucić RFC dla ogólnej prędkości GUID generateQuickGUID.
Ale czy możemy uzyskać szybkość i zgodność z RFC? Powiedziałem tak! Czy możemy zachować czytelność? Cóż ... Niezupełnie, ale łatwo jest postępować zgodnie z nimi.
Ale najpierw moje wyniki, w porównaniu do Broofa guid(zaakceptowana odpowiedź) i niezgodne z RFC generateQuickGuid:
Desktop Android
broofa: 1617ms 12869ms
e1: 636ms 5778ms
e2: 606ms 4754ms
e3: 364ms 3003ms
e4: 329ms 2015ms
e5: 147ms 1156ms
e6: 146ms 1035ms
e7: 105ms 726ms
guid: 962ms 10762ms
generateQuickGuid: 292ms 2961ms
- Note: 500k iterations, results will vary by browser/cpu.
Więc moim 6 iteracji optymalizacji, pobiłem najpopularniejszą odpowiedź o ponad 12X , przyjętym Odpowiedź na 9X , a odpowiedź szybko niezgodnego przez 2-3x . I nadal jestem zgodny z RFC4122.
W jaki sposób? Umieściłem pełne źródło na http://jsfiddle.net/jcward/7hyaC/3/ i na http://jsperf.com/uuid-generator-opt/4
Aby uzyskać wyjaśnienie, zacznijmy od kodu broofa:
function broofa() {
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.random()*16|0, v = c == 'x' ? r : (r&0x3|0x8);
return v.toString(16);
});
}
console.log(broofa())
Zastępuje więc xdowolną losową cyfrą szesnastkową, ylosowymi danymi (z wyjątkiem wymuszania 2 najwyższych bitów 10zgodnie ze specyfikacją RFC), a wyrażenie regularne nie pasuje do znaków -lub 4, więc nie musi się z nimi obchodzić. Bardzo, bardzo zręczny.
Pierwszą rzeczą, którą należy wiedzieć, jest to, że wywołania funkcji są drogie, podobnie jak wyrażenia regularne (chociaż używa tylko 1, ma 32 wywołania zwrotne, po jednym dla każdego dopasowania, a w każdym z 32 wywołań wywołuje Math.random () i v. toString (16)).
Pierwszym krokiem w kierunku wydajności jest wyeliminowanie RegEx i jego funkcji zwrotnych oraz użycie prostej pętli. Oznacza to, że mamy do czynienia z postaciami -i, 4podczas gdy Broofa nie. Zauważ też, że możemy użyć indeksowania tablicy ciągów, aby zachować jego elegancką architekturę szablonów ciągów:
function e1() {
var u='',i=0;
while(i++<36) {
var c='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'[i-1],r=Math.random()*16|0,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:v.toString(16)
}
return u;
}
console.log(e1())
Zasadniczo ta sama wewnętrzna logika, z wyjątkiem tego, że sprawdzamy -lub 4, a użycie pętli while (zamiast replace()wywołań zwrotnych) daje nam prawie trzykrotną poprawę!
Kolejny krok jest niewielki na komputerze, ale robi znaczną różnicę na urządzeniach mobilnych. Wykonajmy mniej wywołań Math.random () i wykorzystajmy wszystkie losowe bity zamiast wyrzucać 87% z nich losowym buforem, który jest przesuwany z każdą iteracją. Przenieśmy też tę definicję szablonu z pętli, na wypadek, gdyby pomogła:
function e2() {
var u='',m='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx',i=0,rb=Math.random()*0xffffffff|0;
while(i++<36) {
var c=m[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:v.toString(16);rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
}
return u
}
console.log(e2())
To oszczędza nam 10-30% w zależności od platformy. Nie jest zły. Ale kolejny duży krok pozbywa się wywołań funkcji toString wraz z klasycznym optymalizatorem - tabelą przeglądową. Prosta 16-elementowa tabela odnośników wykona zadanie toString (16) w znacznie krótszym czasie:
function e3() {
var h='0123456789abcdef';
var k='xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx';
/* same as e4() below */
}
function e4() {
var h=['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'];
var k=['x','x','x','x','x','x','x','x','-','x','x','x','x','-','4','x','x','x','-','y','x','x','x','-','x','x','x','x','x','x','x','x','x','x','x','x'];
var u='',i=0,rb=Math.random()*0xffffffff|0;
while(i++<36) {
var c=k[i-1],r=rb&0xf,v=c=='x'?r:(r&0x3|0x8);
u+=(c=='-'||c=='4')?c:h[v];rb=i%8==0?Math.random()*0xffffffff|0:rb>>4
}
return u
}
console.log(e4())
Kolejna optymalizacja to kolejny klasyk. Ponieważ obsługujemy tylko 4 bity wyjścia w każdej iteracji pętli, zmniejszmy liczbę pętli o połowę i przetwarzamy 8 bitów w każdej iteracji. Jest to trudne, ponieważ wciąż musimy obsługiwać pozycje bitów zgodne z RFC, ale nie jest to zbyt trudne. Następnie musimy stworzyć większą tabelę wyszukiwania (16 x 16 lub 256) do przechowywania 0x00 - 0xff i budujemy ją tylko raz, poza funkcją e5 ().
var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e5() {
var k=['x','x','x','x','-','x','x','-','4','x','-','y','x','-','x','x','x','x','x','x'];
var u='',i=0,rb=Math.random()*0xffffffff|0;
while(i++<20) {
var c=k[i-1],r=rb&0xff,v=c=='x'?r:(c=='y'?(r&0x3f|0x80):(r&0xf|0x40));
u+=(c=='-')?c:lut[v];rb=i%4==0?Math.random()*0xffffffff|0:rb>>8
}
return u
}
console.log(e5())
Próbowałem e6 (), który przetwarza 16-bitów jednocześnie, wciąż używając 256-elementowej LUT, i wykazywał malejące zwroty z optymalizacji. Chociaż miało mniej iteracji, wewnętrzna logika była skomplikowana przez zwiększone przetwarzanie i działała tak samo na komputerze stacjonarnym, a tylko ~ 10% szybciej na telefonie komórkowym.
Ostateczna technika optymalizacji do zastosowania - rozwiń pętlę. Ponieważ zapętlamy określoną liczbę razy, technicznie możemy to wszystko zapisać ręcznie. Próbowałem tego raz z jedną losową zmienną r, którą ciągle zmieniałem, a wydajność była pełna. Ale z czterema zmiennymi przypisanymi losowymi danymi z góry, a następnie za pomocą tabeli odnośników i zastosowania odpowiednich bitów RFC, ta wersja pali je wszystkie:
var lut = []; for (var i=0; i<256; i++) { lut[i] = (i<16?'0':'')+(i).toString(16); }
function e7()
{
var d0 = Math.random()*0xffffffff|0;
var d1 = Math.random()*0xffffffff|0;
var d2 = Math.random()*0xffffffff|0;
var d3 = Math.random()*0xffffffff|0;
return lut[d0&0xff]+lut[d0>>8&0xff]+lut[d0>>16&0xff]+lut[d0>>24&0xff]+'-'+
lut[d1&0xff]+lut[d1>>8&0xff]+'-'+lut[d1>>16&0x0f|0x40]+lut[d1>>24&0xff]+'-'+
lut[d2&0x3f|0x80]+lut[d2>>8&0xff]+'-'+lut[d2>>16&0xff]+lut[d2>>24&0xff]+
lut[d3&0xff]+lut[d3>>8&0xff]+lut[d3>>16&0xff]+lut[d3>>24&0xff];
}
console.log(e7())
Zmodyfikowany: http://jcward.com/UUID.js -UUID.generate()
Zabawne jest to, że generowanie 16 bajtów losowych danych jest łatwą częścią. Cała sztuczka polega na wyrażaniu tego w formacie String z zachowaniem zgodności z RFC, a najsilniej osiąga się to dzięki 16 bajtom losowych danych, rozwijanej pętli i tabeli odnośników.
Mam nadzieję, że moja logika jest poprawna - bardzo łatwo jest popełnić błąd w tego rodzaju żmudnej pracy. Ale wyniki wyglądają dobrze dla mnie. Mam nadzieję, że podobała Ci się ta szalona jazda dzięki optymalizacji kodu!
Pamiętaj: moim głównym celem było pokazanie i nauczenie potencjalnych strategii optymalizacji. Inne odpowiedzi obejmują ważne tematy, takie jak kolizje i naprawdę losowe liczby, które są ważne dla generowania dobrych UUID.