Optimisert graph-datastruktur.

[DrDoogie]

Poster litt i "fienden" sitt forum ("Perl er bedre enn C, mmkay?") da jeg har en litt for stor datastruktur og trenger å vurdere å slakte vekk litt dau-kjøtt.

 

Tanken er da å dytte datastrukturen fra C inn i Perl etterpå.

 

Foreløpig har da graph-ADT'en 40 bytes per nøkkel / element - ALT for mye.

Helst skulle det vært under 10 bytes, men vi får se.

 

Jeg har da kommet frem til at jeg kan implementere det hele i C, med ett array av pekere til vektorer (linked lists).

 

Vi snakker da, for 100 entries, om N * N elementer / noder hvor hvert element trenger 4 bytes til next-pekeren. Reserverer litt å gå på i array'et, men det er ikke så viktig.

 

I tillegg trenger jeg å lagre ett positivt heltall fra 1-1M i hver node, altså 2^20 bit eller rundet opp til 3 byte (hvis vi regner en byte for 8 bit, er litt uklar der).

 

Forslag til effektive graph-datastrukturer som følger med ANSI / ISO C, eller skal jeg bare mekke min egen først som sist?

 

EDIT:

Trenger vel også en counter på et par titusen (2^16), da er vi oppe i 9 bytes.

Legger en struct noe ekstra minne til, eller er det bare en programmeringsmessig konvensjon?

Endret 29. januar 2004 av DrDoogie

[DrDoogie]

Er det du er ute etter sa du? En to-veis lenket liste, der hver node skal ha mulighet til å lagre et tall mellom 1 og 1 000 000?

 

Derimot i C++ har du mange å velge blandt, som f.eks. vektorer; http://www.cppreference.com

 

Disse er raske/gode nok i mange tilfeller.

To-veis har jeg ikke bruk for, og det blir da bortkastet 4 bytes. For 1M noder snakker vi da om 4 MegaByte med ubrukt plass. So, no.

 

Vektorer ja, men spørsmålet mitt var vel... egentlig om det kunne kommes med tips til veldig "barebone", altså optimaliserte, plassbesparende ADT's som allikevel har aksessor-funksjoner (get/set/find).

 

Generelle strukturer er da lite interessante (hvis det er det du foreslår), all den tid minnet er begrenset.

 

Så kanskje det beste er bare å mekke sin egen sak? Burde vel egentlig ikke være nødvendig... men skit au, jeg prøver meg med #include <vector.h>.

[kattemat]

struct node

{

char data[3];

struct node *next;

}

 

Så shifter du litt eller caster data for å hente ut tallet.

[kattemat]

Jes. Struktur er en helt annen sak. En enveislenket liste tar elementer/2 oppslag å søke i gjennomsnitt. Det er gangke mye.

En enkel og effektiv løsning er hashing. Lag deg f.eks. en hashingfunksjon som produserer en 8 bits nøkkel baset på data i strukturen(om som jo er det du søker på). Da vil oppslaget ikke ta lengre tid enn hva det tar å beregne hashen + (elementer/8^2) om du har en optimal fordeling- minneforbruket vil jo dog gå opp til minst(8^2 * 8 - bare for pekerene).

Binærtrær er en annen og rimelig enkel løsning - slev om det er litt kjipt å slette elementer her. B-trær gir kanskje best ytelse/minneforbruk? Men de er også mest komplekse å implementere.

 

mine 2-cent iallfal

Endret 29. januar 2004 av kattemat

[DrDoogie]

En enkel og effektiv løsning er hashing.

...

Da vil oppslaget ikke ta lengre tid enn hva det tar å beregne hashen + (elementer/8^2)

...

Binærtrær er en annen og rimelig enkel løsning - slev om det er litt kjipt å slette elementer her. B-trær gir kanskje best ytelse/minneforbruk?

char[3] høres ut som et godt forslag.

 

Jeg antar at folk kjenner til en graph, men for enkelhets skyld kan man si det er en to-dimensjonel matrise. Det kan implementeres slik ihvertfall.

 

Kolonnene kan da implementeres som array, da dem må gjennomsøkes alle som en anyway.

 

For å forklare litt mer om datastrukturen:

Kolonnene er cd'er. Radene er anbefalinger av andre cd'er for den spesifikke cd'en.

 

For en bruker med en samling cd'er på 200, vil dimensjonene være 200 * 200.

For den neste brukeren vil dimensjonene bli (under forutsetning av at ingen cd'er er felles for brukerne, de har kun forskjellige, unike cd'er) 400 * 200.

 

Og så videre.

 

For et element i raden, vil da dataene være en teller over "anbefalingsvekt", og en indeks i array'et. Hvert element i arrayet (kolonnene) kan da ha en datastruktur med litt ekstra-info, og en lenket liste over anbefalinger (en rad med elementer).

 

Hashing har jeg da egentlig ikke bruk for (perl bruker hashing, og jeg har da foreløpig en 2-dimensjonel hash), all den tid alle rader må gjennomgåes for hver kolonne. Og alle kolonner må gjennomgåes.

 

For 1000 brukere med gjennomsnittlig 200 cd'er (plasskravet tror jeg egentlig er det samme uavhengig av felles cd'er) snakker vi da i perl om (40 bytes per element * 1000 samlinger * 200 anbefalinger), som er 8 MiB.

 

En eneste bruker med 1000 cd'er vil da ha 1000 * 1000 anbefalinger, altså 40 MiB.

 

Så hvis jeg kan korte elementstørrelsen ned til ~9 byte, så er jo det en fordel.

 

B-trær tror jeg heller ikke jeg trenger, da vi snakker om ren sekvensiell gjennomgang. Oppslag tar jeg meg av i en database. Og sletting er unødvendig.

 

Takker for gode tips, forresten!

 

EDIT: Ved nærmere ettertanke så var faktisk bruk av binære trær en genial idé. Hvis jeg da smekker hver bruker sin samling inn i et binært tre, så synker minnekravet og prosesseringsbelastningen ned til log? (N).

Du er ingen idiot du, kattemat.

Endret 29. januar 2004 av DrDoogie