06. maj 2007 - 11:21Der er
5 kommentarer og 1 løsning
Containervalg, hashtable
Jeg har en liste beståede af materialer, som er superklasse for en cd-klasse og bog-klasse. Listen er rimelig konstant, idet der er få tilføjelser og sletninger.
Jeg vil gerne kunne Søge i klassen på: Bog/cd –titel. Tekststreng i titel. Forfatter i bog og kunster i cd.
Hvilken container vil være optimal at anvende ? Jeg er blevet foreslået hashtable, fordi den er hurtig at finde en bestemt bog/cd i ud fra key. Men hvordan med sweep og search i sådan en liste. Går det ligeså hurtigt som andre lister ?? Har hashtable ikke nogle bagsider ?
Typisk hævdes at opslag i hashtableller ikke afhænger af antallet af elementer. Men for at opnå skal man beregne en hashværdi af det objekt man vil finde og det kan jo tage tid. Fx viste målinger i v1.1 at man skulle op på 20 elementer for at det var hurtigere at bruge en hashtabel end en arraylist for streng elementer.
Hashtabellen (og Dictionary i 2.0/3.0) har den egenskab, at hvis flere objekter har samme hashværdi, men er forskellige puttes de i en liste og listen må søges igennem lineært.
Nuvel.
I dit eksempel vil det nok være en idé at lave flere end 1 datastruktur, der holder referencer til bøgerne/cd'erne. Dvs måske Dictionary med titel som nøgle. Måske et andet Dictionary med forfatter som nøgle etc. For at søge i ord i titlen skal man nok ikke bruge en hashtabel.
Din klasse udbyder så metoder der slår op i de indre beholdere, men gemmer beholderne væk. Klassen ved så hvornår der indsættes/slettes og må se vedligeholde alle beholdere.
Ulempen ved hashtabeller her er. Den giver altid 0 eller 1 match så at sige. Dvs hvis du laver en nøgle 'H. C. Andersen' men brugeren skriver 'HC Andersen' får du ikke noget match.
En anden ulempe er jo at du holder det hele i hukommelsen, hvis antallet af elementer er stort kan det jo blive et problem.
En løsning kunne være at bruge en database, den er jo lavet til at foretage den slags søgninger.
Tusinde tak for dit fine svar! Du får pointene. Jeg har bare lige et par spørgsmål til din forklaring:
Mange af de søgninger, jeg skal lave, er på dele af titel eller dele af forfatter/kunstner. Tit kan man jo ikke huske titlen/forfatter/kunster helt præcist men søger på dele af titlen/forfatter/kunstner. I dit eksempel, f.eks., kunne man jo søge på 'andersen' Men her der det jo slet ikke en fordel med Hashtable, vel ??? Man kunne ligeså vel anvende 'Linked List', ikke??
Ville man da typisk vælge at søge fra C-# ind i en database ??
Jep en Linked List ville være et godt valg. Men jeg tror jeg ville foreslå at bruge en database: Den er jo lavet til formålet og hvis datamængderne ikke er så store så cacher databasen det i hukommelsen etc.
Beklager i øvrigt stavefejlene i den oprindelige kommentar.
Tak for svaret. Jeg må se om jeg kan nå det. Der er en eksamensopgave.
vil du så vælge at man hver gang men opretter et element straks lægger det i databasen og IKKE lægger det i en container ? Omvendt når man skal hente et element : IKKE henter det fra nogen container men henter det fra databasen ??
Jep jeg ville hente og gemme direkte i databasen hver gang. Begrundelsen: Databasen er lavet til at håndtere store datamængder. Databasen er allerede udstyret med et søgesprog (SQL) og dermed i stand til, at lave de søgninger du beskrev.
(Hvis opgaven går ud på at lave muligheden for søgninger, sådan set fra et datastruktur-synspunkt er det måske en dårlig idé at bruge en database, men det kan jeg jo ikke vurdere).
Tusinde tak for din hjælp! Jeg vil nok delvis bruge databasen og sql bare for at vise at det kan jeg også.
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.