Intelligent harddisk?

Hvordan skal det forstås, at data behandles direkte på harddisken? Er skiven belagt med et intelligent computerlag? Eller læses alle spor i et hug, for at finde data? Selve dataprocessering på harddisken foregår jo næppe hurtigere end på processoren. Er vi kommen dertil, at PC'ens CPU er på et niveau, så dens opgaver primært i fremtiden vil overtages af at programmerne sendes til harddisk controleren, eller grafik kortet, for at blive udført?

De fleste søgealgorithmer har i mange år - så vidt jeg ved - været O(log2) baseret. Hvis at dette altså overhovedet er muligt. I de fleste tilfælde, kan dette klares, ved at data sorteres og der laves indeks når data opbevares. Ved O(log2) burde vi ikke have nogen afhængighed af datastørrelse, som betyder noget af dimmensioner. Om det er terabytes, 1000 terabytes, eller en million terabytes, betyder ikke væsentligt for findetiden. Antallet af opslag på harddisken er forholdsvis lav, og kan pipelines (flere harddiske).

Re: Intelligent harddisk?

med hensyn til at behandle data direkte på hd, vil det forhåbentlig aldrig være en løsning, da denne altid vil være den laveste fællesnævner. Derfor vil behandlingen af 50 GB være meega langsom.
Vi kommer nok ikke udenom at dataen skal lagres på en eller anden måde, men problemet ligger i når det ændres eller dataen behandles på den ene eller anden måde.
Som du selv siger vil det måske kunne løses ved at en intiligent harddisk, men uanset hvad ville denne harddisk indeholde en cpu der kan udfører de "intelligente ting". Måske var løsningen mere ligetil. Måske er løsningen mere i retningen af den måde data bliver lagret på. Man må formode at der er en del redundant data, om ikke andet på et lavere niveau. Min ide er lidt similar til den måde svn bruger datastrukturer, altså ved kun at gemme ændringerne og på den måde reducerer størrelsen af uendelig mange atomare commits.

Lidt tættere hjemmepå

Lyder da lidt som samme mission http://www.madalgo.au.dk/ har.

Re: Lidt tættere hjemmepå

Normalt betragtes data, som en sekvens af bits. Hvis vi har en stor mængde bits, og sætter en pointer til at pege på hver eneste bits, kan vi sortere disse pointere, udfra det de peger på. Derved får vi en sorteret liste, der ganske vist fylder lidt ekstra i forhold til vores originale data - men vi bliver i stand til, at kunne lave opslag på enhver sekvens af bits, ved at slå op i listen af de sorterede pointere. Denne algorithme er en log2 algorithme, og dermed ikke væsentligt afhængig af datastørrelsen, når først indekseringen er gjort. Selve indeksteringen, er en n log 2 algorithme, og kan endog foregå i sand tid af en chip (med gigabytes / sek). Min opfattelse er, at det derfor ikke rigtigt er noget i, at udvikle en sådan algorithme, da det er almindeligt kendt. Normalt, vil man dog af pladshensyn ikke lave en pointer til hver bit, men til hver ord, eller betydningsfuld index, for at reducere "index bogen" betydeligt. Hvis det gøres til hver bit, og bruges f.eks 32 bits pointers, er størrelsen jo 32 gange data størrelsen. Men dette betyder næppe noget i forhold til opgaverne, at bruge 32 harddiske.

Algorithmen hvor der er pointers per bits, er også ganske effektivt, til at finde ens forekomster i forbindelse med pakning af data. Ved sorteringen, kan datamængden udvides, f.eks. med den inverterede mængde - derved vil man også opnå information om, hvis to dele af bitstrengen indeholder hinanden inverteret. Eller, bittene kan gemmes bagfra, og det opnås mulighed for at gennemskue dette, udfra sorteringen. De pågældende sekvenser, vil være opført umiddelbart efter hinanden i den sorterede liste.

Jeg kan ikke udelukke, at der findes "spørgekriterier", som ikke umiddelbart er implementeret i o(log2), men normalt skyldes dårligere implementering, at de pågældende programmører er af typen der ikke mener det betaler sig, at sortere navnene før de anbringes i telefonbogen.

Re: Re: Lidt tættere hjemmepå

Sortering af bits? Gemme bits bagfra? Det er forhåbentlig en joke...

Google har noget af svaret

Google arbejder dagligt med terabytes af data på klynger af PCer. Deres løsning hedder "Sawzall" (http://labs.google.com/papers/...html), et programmeringssprog, der ved at begrænse de måder, man kan kombinere delberegninger på, kan gøre beregningerne robuste og parallelle nok til at at kunne afvikles på klynger med over 1000 CPUer, selv om nogle af dem "går ned" under beregningen (det sker faktisk i flertallet af deres beregninger).

Re: Google har noget af svaret

Det er jo også meget godt. Rent konkret hvad gør teleselskaberne med de enorme mængder af data kald/sms/data giver hver eneste time??
De gemmer vel ikke dem i klusters og behandler dem, eller??

Re: Re: Google har noget af svaret

Rent konkret hvad gør teleselskaberne med de enorme mængder af data kald/sms/data giver hver eneste time??

Re: Re: Re: Google har noget af svaret

"Sortering af bits? Gemme bits bagfra? Det er forhåbentlig en joke..."

Vi kan tage eksemplet med bytes:
"Denne tekst skal vi gerne kunne søge i!"
Du laver en pointer, til hver bogstav. Altså, en pointer til D, en til e, en til n osv. Denne pointer, peger på en delmængde af teksten, og vi ønsker netop at kunne søge på en delmængde, f.eks.
"enne".

Sorterer vi vores pointere (ombytter dem), såledese de står i sorteret rækkefølge, er det nemt at finde den pointer, der starter med f.eks. "enne". Det er netop pointeren, som peger på andet bogstav. Der kommer også tekst herefter, men hvis vi i vores sorterede liste, søger på enne, får vi pointer 2. Det er et normalt binært opslag, i en sorteret liste.

Ovenstående er byte baseret, men kunne også være bit baseret. Dette er normalt ikke så relevant, men kan være det, hvis det er maskinkode, eller andet bitorienteret stof. Hvis det er DNA sekvenser, gemt som bits, vil det måske også være nødvendigt med en opløsning ned på bitniveau.

Ved pakning af data, bruges også noget, som svarer til ovenstående metode. Idéen er, at hvis at der to steder står samme indhold i en tekst, så komprimeres dette. Man kan netop umiddelbart se, efter ovenstående sortering, om det skulle være tilfældet. Da vil de to pointere der indeholder samme tekst, stå efter hinanden, i den sorterede pointerliste. Du kan også tilføje indformation, f.eks. teksten bagfra, og derved indtage muligheden for, at noget er "spejlvendt" i din indformationsmængde af andet, og samtidigt alligvel bruge dette, i forbindelse med din komprimering. I princippet kan du bruge enhver algorithme og tilføje, f.eks. at springe hver anden bogstav over, hvis du har tanke om, at måske et enkelt tegn kan være forskelligt.

Pakke metoder anvender sådanne teknikker, og selvom algorithmen måske ikke lige er den ovenstående, er det reelt nok, at altid forvente en opslag i data kan laves med en log2 algorithme. Ellers, er dataene ikke gemt korrekt på forhånd.

Så det er ikke en joke, med sortering af bits, og at evt. gemme bits bagfra, splitte dem i to halvdele med even og odd bytes osv. Det afhænger af opgaven, og hvad man ønsker at søge på. Men svaret er altid, at log2 er muligt.

Notationsforviring om køretider

Notation af køretider:
O(n) læses 'store O' eller 'worst case' og beskriver den øvre grænse for den asymptotiske køretid i h.h.t. en datamængde af størrelsen n.

Der er foreskel på at "søge efter data" og "slå data op". En algoritme har en køretid, er det en algoritme der søger bliver dette til søgetid. Generelt om algoritmer hedder det dog køretid.

Jens Madsen: Nej, en køretid på O(log2) er ikke altid muligt - det ville betyde at hastighedderne på alt ville være en konstant og som du selv nævner uafhængigt af datastørrelse. Derimod er søgetiden ofte for simple søgninger O(n * log(n)) (Flere algoritmer som tager mere end O(n^2) / O(n * log n) kan bevises at være optimale.)

Det afhænger generelt af om at data er/kan sorteret efter et mønster, eller om at all data skal søges igennem. Opslag er generelt meget hurtigere.

Til de uindviede: Ved dataudtræk fra et balanceret søgetræ er tiden O(log n),ø da
log n = h, n er elementer, h er højden af træ

V.h.a. denne notation kan man se en tendens: Man bilver relativt hurtigere og hurtigere til at slaa op, jo mere data der er i denne datastruktur.
Sammenlign med en telefonbog: Jo størrere en telefonbog er, jo flere personer udelukker vi pr. gang vi bladrer en fast procentsats af siderne. Hvis man slavisk ser p samtlige navne i ordbogen vil det tage længere tid, end hvis slår op paa den klassiske facon - men ikke ved små sedler. Hvis man kikke samtlige navne igennem ville man faa set alle N navne og "worst case" ledetiden ville være "tiden det tager at kikke paa et ord" * N = O(k*N) ( da vi kikker paa en tendens og ikke et bestemt tal, fjerne vi alle konstanter: O(N))

http://en.wikipedia.org/wiki/B...tion

Re: Notationsforviring om køretider

Det du siger, er i fuld overensstemmelse med det jeg siger. Hvis du ønsker at søge på nogle data, f.eks. en delstreng af datamængden, kan dette gøres ved at lave en sorteret liste og opslag i denne. Dermed er det opslagstiden O(log2) som gælder. Når derimod du skal have kreeret listen, er det O(n log 2) som gælder, og dermed er det proportional med datamængden. Det sidste kan evt. gøres i chips, og der kan klares meget stor hastighed som jeg beskriver. Det er intet problem at klare mange terabytes. Chippens algorithme kan f.eks. svare til at du tilføjer det til dit træ, der som du beskriver er O(log 2) og dermed omtrent konstant per bytes. I nogle tilfælde kan det implementers så det er konstant per byte.

Det er helt korrekt at det er nødvendigt at lave et sorteret index, og at dette er problemet. Jeg beskriver, hvordan du kan gøre dette, for at søge på en vilkårlig delstreng i en vilkårlig datamængde. Lidt som google. Ofte er problemerne dog mere komplekse, og der skal måske tages højde for "fejl", såsom manglende bits eller bytes, at en enkelt byte er noget andet, eller helt andet. I så fald, er det oftest lidt mere svært, og kan øge kompleksisten drastisk - f.eks. ved at kræve to eller flere opslag. Men, det er stadigt uafhængig af datamængden, såfremt disse er gemt på harddisk (og sorteringen gjort på tidspunktet hvor det gemmes). Gøres sorteringen først bagefter, er dens kompleksitet omtrent proportional med datastørrelsen.

Re: Re: Notationsforviring om køretider

Det du siger, er i fuld overensstemmelse med det jeg siger. Hvis du ønsker at søge på nogle data, f.eks. en delstreng af datamængden, kan dette gøres ved at lave en sorteret liste og opslag i denne. Dermed er det opslagstiden O(log n) som gælder. Når derimod du skal have kreeret listen, er det O(n log n) som gælder, og dermed er det proportional med datamængden - typisk kan det gøres samtidigt med data gemmes, ved at bruge træer. Det sidste kan evt. gøres i chips, og der kan klares meget stor hastighed som jeg beskriver. Det er intet problem at klare mange terabytes. Chippens algorithme kan f.eks. svare til at du tilføjer det til dit træ, der som du beskriver er O(log n) og dermed omtrent konstant per bytes. I nogle tilfælde kan det implementers så det også er konstant per byte.

Det er helt korrekt at det er nødvendigt at lave et sorteret index, og at dette er problemet. Jeg beskriver, hvordan du kan gøre dette, for at søge på en vilkårlig delstreng i en vilkårlig datamængde. Lidt som google. Ofte er problemerne dog mere komplekse, og der skal måske tages højde for "fejl", såsom manglende bits eller bytes, at en enkelt byte er noget andet, eller helt andet. I så fald, er det oftest lidt mere svært, og kan øge kompleksisten drastisk - f.eks. ved at kræve to eller flere opslag. Men, det er stadigt uafhængig af datamængden, såfremt disse er gemt på harddisk (og sorteringen gjort på tidspunktet hvor det gemmes). Gøres sorteringen først bagefter, er dens kompleksitet omtrent proportional med datastørrelsen.

Konklussionen er altså, at finde en delstreng i en tekst er en O(log n) funktion, under forudsætning af at der oprettes et index meddens teksten gemmes, eller at dette index oprettes bagefter, hvilket så er en O(n log n) funktion at kreere indexet.

Samtidigt gælder det omtrent en vilkårlig opgave, trods det mangler tegn, bits mv. Genneralt, kan vi altid forvente, at en "søgeopgave" er identisk med en opslagsopgave, og kompleksiteten er derfor O(log n). Eneste det kræver er, at dataene opbevares i sorteret form samtidigt, f.eks. ved en pointer på hver bit.

Jeg beklager, at jeg kom til at skrive O(log 2), og dette var en fejl. Naturligvis skulle stå O(log n) som ovenstående. O(log n) er dog også omtrent konstant, og regnes ofte som konstant.

Re: Re: Re: Notationsforviring om køretider

Det skal bemærkes, at din søgetid, er under forudsætning af at der søges i ubehandlede rå data. Du får normalt langt bedre søgetider, hvis du når du gemmer data, laver et index - f.eks. ved at gemme en pointer per byte, eller per bit, og oprette sorteret liste over disse pointere - gemmes en pointer per bit eller byte, er det relativt uafhængigt af din søgeopgave. Derved kan du nu ofstest dividere din søgetid med O(n), fordi du har disse sorterede liste der kan laves opslag i til din rådighed. Min søgetid, er under forudsætning af, at du laver en sådan liste når du gemmer.