02. marts 2004 - 13:25Der er
45 kommentarer og 1 løsning
Hjælp til register-arkitektur
Jeg arbejder pt. på et highscore-register, som indeholder 50.000 records, og 100.000 skal kunne klares uden problemer, dvs. hurtigt uden det vilde CPU-forbrug, og helst med det lavest mulige RAM-forbrug.
Funktionalitetskravende bringer mig lidt i et dilema, som måske skyldes manglende viden: 1. Et udsnit af registeret skal kunne udtrækkes ud fra start-position og længde (antal records) 2. En given records position skal kunne findes i det samlede register 3. Records skifter ofte position, dog drejer det sig om mindre ændringer 4. Én gang i døgnet resettes registeret, hvilket resulterer i en sandsynlig stor omrokering af alle records.
Records indeholder et minimum af informationer: et ID, et navn og en score - og sorteres ud fra: 1. Højeste score og 2. mindst ID er bedst.
Jeg har lavet en masse forsøg og har bl.a. haft gang i java.util.TreeSet, som er en udemærket og lynhurtig struktur, hvis der skal flyttes rundt, men når når kommer til behandling af positionering, er den elending, den bygger nemlig på chainede entries og har ingen metoder der vedrører index.
Derfor har jeg omskrevet ArrayList til at være en sorteret struktur, der finder index ud fra samme metode, som anvendes i merge-sort (hedder det binær søgemetode?), dvs. at index findes ud fra en tidskompleksitet på O(log(n)), hvor n er antallet af records. Faktisk kræver kun 17 søgninger, at finde en records index blandt 100.000 records. Mit problem er så, at denne struktur er elendig til omrokeringer, da hele det indre array skal kopieres, hvis der indsættes på index 0, eller andre lave positioner. Derfor har jeg opdelt registeret i flere, mindre registre (ArrayList's), og så flytter jeg records'ne rundt mellem delregistrene, hvis det er nødvendigt.
Stadig væk er TreeSet LAAANGT hurtigst til at flytte elementer rundt. Hvis nu jeg kører en test med henholdsvis TreeSet og min egen, sorterede ArrayList, og indlæser 100.000 records fra databasen, tilfældigt sorteret, opbygges 4 TreeSet med 25.000 records i hver på ca. 6 sekunder, mens det tager 20 ArrayList'er med 5.000 records i hver, ca. 90 sekunder.
Nogen der kan hjælpe med ideer, evt. links til noget teoretisk materiale om registre osv. ???
Manuelle og semi-automatiske strategier for identitetsstyring virker - lige indtil nogen beder om dokumentation. For at undgå denne fare har DKTV taget kontrol over sin identitets- og adgangsstrategi.
Det lyder som et job for en database. Har du adgang til SQL ? Hvis du har vil jeg anbefale det. det er langt 'billigere' end at hive sådan en megafil ind i memory.
Nej, der køres mod MySQL, og den er mildest talt elendig. En record's score er en beregnet værdi, og gemmes ikke som sådan i databasen. Da scoren ofte ændres, vil jeg godt undgå at køre høj kobling mod databasen...
Det jeg har tænkt er, at lægger jeg arbejdet over til databasen, opbygges så at sige registeret hver gang et udtræk gennemføres, mens et cached og vedligeholdt register bør kræve mindre i længden.
En vigtig information kunne også være, at highscore-registeret faktisk består af 3 registre, som dog alle fungerer ens. Fordelen ved det cachede register er, at en record blot refereres til, men kun eksisterer én gang. Skal der køres mod databasen, vil hvert udtræk med records start:0 og længde:50 kræve 3 udtræk, ét for hvert register: total, uge og dag.
En record identificeres altid ud fra ID, ikke navn, hvorfor placeringen findes ud fra ID. Navnet er kun til for at kunne sammensætte det rigtige output uden at skulle slå navnet op andet steds. Alle Records er registeret i et HashMap ud fra ID (Integer).
Og ja, det svære er at få alle tre funktionaliteter hurtige. TreeSet er monster-hurtig til add/remove, og derfor gennemfører jeg omrokeringer ved at køre remove/add, og hvis jeg vil finde en placering, må jeg tælle ud fra gennemløb af en iterator.
Hvordan skulle man ud fra dit forslag finde placeringen, og Records fra placering x og længde n?
Den må jeg lige tykke lidt på - det er pænt længe siden jeg arbejdede med binære træer. Har faktisk aldrig arbejdet med det, kun lært det... nåh, må lige grave lidt papirer frem :)
Pointen er at når man står ved en node så kan man checke: nodes below left node nodes below rigth node og beslutte sig for om man skal gå til højre eller venstre.
Er det ikke en sandsynlig ineffektivitet, at root er den først indsatte node? Hvis nu det er den mindste der bliver indsat først, vil det venstre subtræ aldrig få nogen noder, og det højre i stedet få dem alle, eller er det en ubetydelighed?`
Eller er ideen, at man løbende balancerer det samlede træ?
Er et "splay" tree noget jeg kunne overveje i denne situation for at øge performance, og arne, kan du ganske kort forklare hvad et splay tree er og går ud på?
Altså hvis man vil have perfekte binære træer, skal de bygges på et array i stedet for noder (med dårligere performance til følge) ?
Arne, du ka vidst godt snart tillade dig at smide et svar...
Det jeg har forstået omkring splay trees er, at de lægger gennem splay-operationer (noget med at rotere bytte om på left og right), placerer de mest benyttede nøgler som root, eller længere mod toppen af træet - for at forbedre performance.
Jeg testede lige lidt og fandt ud af, at hvis noderne indsættes i træet i rækkefølge, tager det sindsygt lang tid at indsætte bare 20.000 records (ca. 30 sekunder), og ender ofte med en stackOverflowError!!
Derimod tager det under 5 sekunder, hvis records indsættes random.
Måske det ville være en ide jævnligt at balancere træet ?
Det endelige register er blevet et splay-tree, som er en variant binært træ, med det arne forslog med, at alle node holder styr på antallet af underliggende noder 'below', for at optimere søgning efter en værdis index i træet.
Splay-trees virker ved, at hver gang en node tilgås, enten ved add, remove eller contains-operationer, flyttes den tilgåede node som træets root gennem en række højre- og venstre-roteringer. Den opnåede egenskab er, at træets gennemsnitlige dybde halveres og dermed en løbende og effektiv afbalancering.
Resultatet af at køre registeret som ét splay-tree indeholdende alle records er som følger: - Et splay-tree optager præcis lige så meget hukommelse, som hvis TreeSet blev anvendt i stedet, altså ca. 36% mere end hvis TreeList* anvendes. - Søgninger efter index ud fra værdi går lige så hurtigt som med TreeList. - Indlæsning af værdier i splay-tree går lige så hurtigt som med TreeSet, altså meget hurtigere end TreeList.
Som nævnt har det samlede register med TreeSet eller TreeList været opdelt i henholdsvis 4 og 20 delregistre ved 100.000 records.
De gode egenskaber fra TreeSet og TreeList er altså blevet effektivt kombineret med splay-tree.
* TreeList er min egenudviklede ArrayList, der har de egenskaber at være sorteret, og kan finde index ved at søge binært.
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
