CKTIS / JavaScript
Výkon a zložitosť: virtualizácia zoznamu s pevnou výškou riadkov
Rozlišujte skutočný čas vykonávania od toho, ako náklady rastú s veľkosťou údajov. Virtualizácia zoznamu s pevnou výškou riadkov vypočíta viditeľný rozsah a obmedzí počet vykreslených prvkov, ale automaticky neznižuje náklady na ukladanie ani spracovanie celej množiny údajov.
Verzia: ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntax
const totalHeight = count * rowHeight;
const maxScroll = Math.max(0, totalHeight - viewportHeight);
const top = Math.min(Math.max(0, scrollTop), maxScroll);
const start = Math.max(0, Math.floor(top / rowHeight) - overscan);
const end = Math.min(count, Math.ceil((top + viewportHeight) / rowHeight) + overscan);
const offset = start * rowHeight;Výkon zahŕňa okrem iného čas vykonávania, využitie pamäte a odozvu. Zložitosť opisuje, ako náklady rastú s veľkosťou vstupu: O(1) znamená náklady ohraničené nezávisle od tejto veľkosti, zatiaľ čo O(n) označuje najviac lineárny rast. Ide o analytický model, nie o záruku času v milisekundách. ECMAScript určuje správanie jazyka, nie náklady na vykresľovanie rozhrania. Pred optimalizáciou zmerajte reprezentatívnu záťaž v cieľovom prostredí.
Virtualizácia zoznamu s pevnou výškou riadkov znamená vykresľovať iba viditeľnú časť zoznamu a prípadne aj rezervu overscan. Pre count riadkov s rovnakou výškou rowHeight je celková výška count * rowHeight. Príklad vypočíta polootvorený rozsah [start, end), hodnotu offset a totalHeight a zohľadňuje čiastočne viditeľné riadky. Obmedzí scrollTop na platný rozsah posúvania.
Za predpokladu konštantných nákladov číselných operácií vyžaduje výpočet rozsahu čas O(1) a dodatočnú pamäť O(1). Vykreslenie k = end - start riadkov si vyžaduje prácu úmernú k, ak má vykreslenie každého riadka konštantné náklady. Uloženie všetkých n záznamov stále vyžaduje pamäť O(n); filtrovanie celej množiny údajov pri každom posunutí túto výpočtovú výhodu ruší.
Ide o príklad výpočtu, nie o úplný komponent DOM. Integrácia by mala zachovať posúvateľnú oblasť s výškou totalHeight a umiestniť rozsah na pozíciu offset. Skutočný rozstup riadkov vrátane medzier musí zodpovedať rowHeight; rôzne výšky vyžadujú iný algoritmus. Treba tiež riešiť fokus, prístupnosť a zmeny údajov. Príklad používa syntax ES2015 a nevyžaduje rozhrania API prehliadača; prítomnosť Node 24 v repozitári nedokazuje podporu týchto API v prehliadači.
Príklady
function visibleRange(count, rowHeight, viewportHeight, scrollTop, overscan) {
// Preconditions: all arguments and count * rowHeight are safe integers.
// count and overscan are nonnegative; rowHeight and viewportHeight are positive.
// Heights and scrollTop use consistent units.
const totalHeight = count * rowHeight;
const maxScroll = Math.max(0, totalHeight - viewportHeight);
const top = Math.min(Math.max(0, scrollTop), maxScroll);
const start = Math.max(0, Math.floor(top / rowHeight) - overscan);
const end = Math.min(count, Math.ceil((top + viewportHeight) / rowHeight) + overscan);
return { start, end, offset: start * rowHeight, totalHeight };
}
console.log(JSON.stringify(visibleRange(100, 20, 40, 45, 1)));
console.log(JSON.stringify(visibleRange(0, 20, 40, 0, 1)));Výsledok
{"start":1,"end":6,"offset":20,"totalHeight":2000}
{"start":0,"end":0,"offset":0,"totalHeight":0}Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.