Big O for JavaScript-arrays
Arrays i JavaScript er veldig enkle å endre ved å legge til og fjerne elementer. Det skjuler på en måte det faktum at de fleste språk har arrays med fast størrelse, og som krever komplekse operasjoner for å endre størrelse. Det virker som om JavaScript gjør det enkelt å skrive arrayskode som yter dårlig. Dette fører til spørsmålet:
Jeg antar at alle rimelige JavaScript-implementasjoner har høyest følgende big O-er.
- Tilgang - O(1)
- Legge til - O(n)
- Foran - O(n)
- Innssetting - O(n)
- Sletting - O(n)
- Bytting - O(1)
JavaScript lar deg forhåndsfylle et array til en viss størrelse, ved å bruke new Array(length) syntaks. (Bonusspørsmål: Er det å lage et array på denne måten O(1) eller O(n)) Dette ligner mer på et konvensjonelt array, og hvis det brukes som et forhåndsstørret array, kan det tillate O(1) tillegg. Hvis logikk for sirkulær buffer legges til, kan du oppnå O(1) innsetting foran. Hvis et dynamisk ekspanderende array brukes, vil O(log n) være gjennomsnittstilfellet for begge disse.
Kan jeg forvente bedre ytelse for noen ting enn mine antakelser her? Jeg forventer ikke at noe er beskrevet i noen spesifikasjoner, men i praksis kan det være at alle store implementasjoner bruker optimaliserte matriser bak kulissene. Finnes det dynamisk ekspanderende matriser eller noen andre ytelsesøkende algoritmer i arbeid?
P.S.
Grunnen til at jeg lurer på dette er at jeg forsker på noen sorteringsalgoritmer, de fleste av dem ser ut til å anta at det å legge til og slette er O(1)-operasjoner når de beskriver deres totale big O.
Svar #1
MERK: Selv om dette svaret var korrekt i 2012, bruker motorer i dag svært forskjellige interne representasjoner for både objekter og arrays. Dette svaret kan være sant eller ikke.
I kontrast til de fleste språk, som implementerer matriser med, vel, matriser, i Javascript er Arrays objekter, og verdier lagres i en hashtabell, akkurat som vanlige objektverdier. Som sådan:
- Tilgang - O(1)
- Legge til - Amortisert O(1) (noen ganger må hashtabellen endres størrelse; vanligvis kreves bare innsettelse)
- Foranlegging - O(n) via
unshift, siden det krever omfordeling av alle indeksene - Innsetting - Amortisert O(1) hvis verdien ikke eksisterer. O(n) hvis du vil forskyve eksisterende verdier (f.eks. ved bruk av
splice). - Sletting - Amortisert O(1) for å fjerne en verdi, O(n) hvis du vil tilordne indekser på nytt via
splice. - Bytting - O(1)
Generelt sett er det å sette eller fjerne en hvilken som helst nøkkel i en dict amortisert O(1), og det samme gjelder for arrayer, uavhengig av hva indeksen er. Enhver operasjon som krever å omnummerere eksisterende verdier er O(n) rett og slett fordi du må oppdatere alle de berørte verdiene.
Svar #2
garanti
Det er ingen spesifisert tidkompleksitetsgaranti for noen array-operasjon. Hvordan arrays presterer avhenger av den underliggende datastrukturen motoren velger. Motorer kan også ha forskjellige representasjoner, og bytte mellom dem avhengig av visse heuristikker. Den opprinnelige array-størrelsen kan eller ikke kan være en slik heuristikk.
virkelighet
For eksempel bruker V8 (per i dag) både hashtabeller og array-lister for å representere arrays. Den har også forskjellige representasjoner for objekter, så arrays og objekter kan ikke sammenlignes. Derfor er array-tilgang alltid bedre enn O(n), og kan til og med være like rask som array-tilgang i C++. Å legge til elementer på slutten er O(1), med mindre du når datastrukturens størrelse og den må skaleres (som er O(n)). Å legge til elementer i starten er verre. Sletting kan være enda verre hvis du gjør noe som delete array[index] (ikke gjør det!), da det kan tvinge motoren til å endre representasjonen sin.
råd
Bruk arrays for numeriske datastrukturer. Det er det de er ment for. Det er det motorer vil optimalisere dem for. Unngå spredte arrays (eller hvis du må bruke dem, forvent dårligere ytelse). Unngå arrays med blandede datatyper (da det gjør de interne representasjonene mer komplekse).
Hvis du virkelig vil optimalisere for en bestemt motor (og versjon), sjekk kild koden for det absolutte svaret.