Omöjliga möjligt?

Ja, men om du skulle indexera på enbart strängar skulle du bli tvungen att hasha.

lägg av med hash nu era potheads ;)

men den där niko har jag en oplockad höna med ;)

Det känns som om man har slängt ut pengar i onödan på att läsa Datastrukturer och Algoritmer...

Som Phorpher förlängt uttrycker det hela: :OO

Dano skrev:

lägg av med hash nu era potheads ;)

men den där niko har jag en oplockad höna med ;)

Kan du hitta någon tillämpning för denna fantastiska upptäckt? ;)
Och det här med databas vet jag inte.. Och som sagt.. För strängar lär hashing behövas. Vare sig du vill eller inte.

Men om vi säger såhär då.

Vi har en "databas" av typen du pratar om. Den innehåller 15 000 poster med registreringsnummer till bilar. Ett registreringsnummer lagras i en sträng.

Herr Karlsson surfar in på bilregistrets hemsida och ska göra en sökning med deras nya system som du lyckligtvis lurat på dem.

Efter ett par sekunder inser herr Karlsson att det inte går att söka på annat än heltal och när han läser det finstilta så står det: "För att söka efter ett registreringsnummer så måste du veta vilket indexnummer det har..."

:OO

Först låt avlägga ett högt och diaboliskt grav.

mohohoahAHAHAHAHA

Du har förgyllt min morgon med underhållande läsning och allmänt roande. Dock har jag nu smulor i mitt tbord eftersom jag gravade när jag tuggade i min macka.

Det där du beskriver är en vanlig lookup table, array, lista, whatever.

(Sorry, var tvungen :bire )

matricks.

Det där du beskriver är en vanlig lookup table, array, lista, whatever.

Du verkar inte fattat överhuvudtaget....... Kanske bäst så.

Phorper

Som sagt, sökmotorn är ingen hash funktion som ni ser. fattar inte varför ni ens tar upp det. Känns som ni hela tiden försöker hitta fel och fusk som jag skulle gjort, varför inte bara inse att jag har kommit på en jävla bra grej istället för att racka ner på något som inte går att racka ner på?. Så jävla missgynnande människor alltså.
Visst finns det tillämpningar. Det är bara att använda fantasin,
Tex personnummer, postnummer, id nummer på varor i affärer, ISBN nummer, telefonnummer, navigeringskoder, finns hur mycket som helst. Tänk dig att ha en databas med personummer över hela sveriges 9 miljoner befolkning och databasen hittar personens namn och hans adress på noll sekunder, det du!
Att du försöker ta ett exempel på något som det inte är gjort för enbart för att förlöjliga, tycker jag bara är ett lågvattenmärke från dig. Den svenska avundsjukan i ett nötskal

Asså.. setup tiden för en sökning ar ju äckligt lång eftersom du maste allokera minnet och sedan lägga in alla i den och där med gå igenom alla element i den. Sedan kan du borja söka. Sedan kan du bara söka på id nummer och sant. Oftast vill man söka på strängar vilket inte alls går med den där taktiken. Minnes åtgången är ju fet som fan också. Har man en stor tabell och vill kunna söka på alla saker snabbt via din metod så kommer minnes åtgången gångras med antalet kolumner i tabellen.

Din metod är en vanlig slät LUT Något som används dagligen.

Dano skrev:

Det där du beskriver är en vanlig lookup table, array, lista, whatever.

Du verkar inte fattat överhuvudtaget. Kanske bäst så.

Phorper

Som sagt, sökmotorn är ingen hash funktion som ni ser. Visst finns det tillämpningar. Det är bara att använda fantasin,
Tex personnummer, postnummer, id nummer på varor i affärer, ISBN nummer, finns hur mycket som helst.
Att du försöker ta ett exempel på något som det inte är gjort för tycker jag bara är ett lågvattenmärke från dig. Löjligt

Faktum är att det inte är du som verkar fatta något. Det du beskriver är lika gammalt som uråldrigt, och har används i rätt liten utsträckning eftersom det finns mycket effektiva algoritmer som kan söka igenom enorma datamängder utan att käka lika mycket minne. En binärsökning genom en sorterad datamängd (t.ex. en trädstruktur eller sorterad array) med en miljon poster kräver 20 "lookups", och inte ett dugg mer minne än datan som används tar upp.

Skulle man göra en tabell enligt din princip för ISBN-nummer, skulle man behöva 11000000000 poster i arrayen (9 siffror från 0-9, plus en kontrollsiffra 0-9 eller X). Med pekare på fyra byte skulle detta kräva 40 GB minne, även om man bara sparade ett hundratal produkter.

Om man som du exemplifierar skulle använda hela Sveriges befolknings personnummer, skulle en binärsökning genom dessa kräva 23 steg, om jag räknat rätt (har jag inte gjort har jag fel på kanske ±1 steg, orkar inte kolla upp). Den tid detta tar är ytterst försumbar, jag skulle anta att vi hamnar en bra bit under en sekund, och den skalar dessutom mycket bra. En biljon poster skulle kräva ≈39 steg, vilket också är försumbart.

Den stora skillnaden i all sökning av databaser ligger i om data anses som statiskt eller dynamiskt.
Om det är statiska dvs sveriges befolkning går det att göra blixtsnabbt, om man inte tar med dom som föds just nu utan skapar en ny statiskt db exempelvis varje vecka.
Men trots allt finns här mycket att göra. Men kolla att söka exempelvis "Zebbie" på Gula sidorna, privatpersoner.
Det är Peter´s arbetskamrat.

Dano skrev:

"niko:största talet i första positionen"
Det ska vara det största talet i något av elementen i arrayen

Jo, det var liksom det jag menade. Första positionen -> talvärdet, andra positionen -> strängvärdet.

Dano skrev:

men den där niko har jag en oplockad höna med

Jag är hemskt ledsen men du lämnade en del rätt tydliga ledtrådar till vad din "upptäckt" egentligen handlade om:

1. Du talar om "väldigt stor minneåtgång"
2. Du postade först din upptäckt i "Webbutveckling övrigt".
3. Du kallar hela tiden en sökfunktion för "sökmotor".

spango

Skulle man göra en tabell enligt din princip för ISBN-nummer, skulle man behöva 11000000000 poster i arrayen (9 siffror från 0-9, plus en kontrollsiffra 0-9 eller X). Med pekare på fyra byte skulle detta kräva 40 GB minne, även om man bara sparade ett hundratal produkter.

svar nej, arrayens storlek är största sökbaka numret, något annat behövs inte. Idag har jag en array med 15000 unika nummer och dom är inte ens helt linjära och dom börjar inte heller på 1 utan 10000, och enligt "din" beräkning skulle detta då ta upp cirkus 100 gig i minne, vilket bull alltså. Jääävligt underligt att jag kan köra det helt utan problem.

Testa ta en mattekurs :D

(10000+15000)*sizeof(void*)
(25000)*4 = 100000 byte

Dano skrev:

svar nej, arrayens storlek är största sökbaka numret, något annat behövs inte. Idag har jag en array med 15000 unika nummer och dom är inte ens helt linjära och dom börjar inte heller på 1 utan 10000, och enligt "din" beräkning skulle detta då ta upp cirkus 100 gig i minne, vilket bull alltså. Jääävligt underligt att jag kan köra det helt utan problem.

Öh? Var får du den häpnadsväckande siffran ifrån? Mina beräkningar är enligt följande simpla princip:
(högsta möjliga värde) - (lägsta möjliga värde) * pekarstorlek
Jag har inte sagt att det beror på något annat än differensen mellan högsta värdet och "nollpunkten", minsta värdet.

\r Jaså matricks, du hann före ;)

matricks

(10000+15000)*sizeof(void*)
(25000)*4 = 100000 byte

Äh!. Det är bara att jämföra då ska ni se.

originalstorlek:
60000 byte

efter min metod:
100000 byte

herregud, skillnaden är inte så stor ser ni. förstår inte käbblet liksom. ni överdriver bara. och detta är också i ett exempel där lägsta sökbara numret börjar på 10 000, oftast gör det inte det. om det hade börjat på tex 1000 så hade arraystorleken bara blivit 64000 byte. och ifall det börjat på 0 hade det inte varit något skillnad alls.

Ganska underhållande tråd :)

Misstänker att Dano inte har särskilt mycket erfarenhet av programmering tidigare. Alla inlägg tyder på brist av erfarenhet, låg ålder och att inte vara direkt insatt i hur saker funkar.. Men men alla har vi varit unga och oerfarna en gång i tiden =).

--- Monolith

ok, lite bättre exempel.. Databas på personer i sverige som är födda mellan 1930 till 2000. ca 9 miljoner personer borde det bli eftersom livs längden är ca 70 år.

1930/01/01 0000
2000/01/01 0000

delta = 7 000 000 000
delta = 7gb
memory usage for index table 7*4=28gb

Detta går inte att köra på 32 bitars maskin så vi måste ha 64bitars och får:

memory usage for index table 7*8=56gb

Med ett binärträd så blir det 9mb*4*2=81mb ungefär.

Dano

Du har helt rätt att en vanlig lookup table som du har skapat är snabb i det avseende att posten man vill hämta motsvarar ett exakt index i ditt fält. Nackdelen är ökad minnesåtgång och det faktum att en post kan endast matchas mot en enda sökvariabel.

Ponera att du har en databas över telefonabbonenter i 08-området. Vi utgår från att längsta telefonnummret är 8 siffror långt och får högst 100 miljoner poster i vår tabell. Eftersom vi är lite smarta gör vi varje post till en pekare som är noll ifall telefonnumret inte existerar, och annars pekar till ett par hundra allokerade bytes, för att spara stora mängder minne.

Information om abbonent 08-10406080 finns således att hämta i Register[10406080] och kräver ingen direkt sökning. Men har du tänkt på hur du ska göra ifall du vill söka efter ett specifikt namn? Hur lång tid tror du det tar att finna information om Anders Andersson eller Örjan Öhberg i din lookup table?

Som du kanske förstår så är din "upptäckt" en metod känd sen länge, och generellt bara effektiv för mindre konsistenta tabeller, t.ex. förberäknade sinusvärden eller dylikt.

Skam den som ger sig dock, bara att fortsätta jobba :-)

Det känns lite onödigt att ni skriver i den här tråden. Med tanke på hans stavfel och sätt att uttrycka sig förstår man ju att han inte är så gammal. Alla vi som läst Algoritmer och datastrukturer eller liknande inser ju att han bara skämtar, även om det är ett tråkigt skämt.

Underhållande tråd! :e
Seriöst, jag tror mer på spango m.fl som är insatta än vad trådskaparen som inte ens kan stava och uttrycka sig på ett vettigt sätt.

Men om nu det Dano säger är sant, kul för han! Får se hur mycket pengar han tjänare på detta och hur länge det dröjer innan vi "vanliga" kan börja använda denna metod. *ironi*

Det är såhär va......
Detta är ett första utkast, och det är bara ett experiment än så länge.
Och ni börjar klanka ner direkt, klaga på min stavning etc etc.
Det är löjligt. har ni kommit på nåt bättre eller?

Jag satt och funderade under dagen hur man ska lösa minnesproblemet.
Det kan man göra med lite enkel lågstadiematematik.

ponera att det lägsta sökbara numret är 12432 och det högsta är 22432.
Och alla nummer följs åt dvs 12342 12433 12434 vilket de oftast gör när man
sysslar med sökbara nummer
då kommer arrayen bli 22432 stor, och arrayens element från 0 till 12432
blir tomma, alltså det är detta som är memoryloss:en. Hur löser man detta?,
istället för att låta arrayens element vara EQUAL till vardet i elementet så gör man såhär.

då börjar man med att lägga in det lägsta sökbara numret i element nummer noll.
och sen fortsätta med det högre osv osv:

test[0].varde=12432;
test[0].text="hejsaneee";

test[1].varde=12433;
test[1].text="hejsanaaa";

test[2].varde=12434;
test[2].text="hejsanvvvv";

osv ända upp till 10 000...............

Sen tar man det lägsta sökbara värdet och använder som en nyckel kan man kalla det.
och gör såhär:

"detsöktavärdet"-12432=arrayens element=direkt addressering

Och detta funkar också om det finns "hål" i de sökbara numrena tex 12432 12435 12440
då sätter man in tomma arrayer som fattas, dock hålen får såklart inte vara för stora
men det är dom oftast inte när det handlar om sökbara nummer.
sådär då var minnesproblemet löst, var det något mer?.

ja vad är det då jag fått fram?

1. en sökmotor med noll i accesstid oavsett storlek
2. minnesproblemet löst. arrayen behöver inte bli större än ursprungliga arrayen.

Whats the problem?

och söka på namn går också att lösa, gör om namnet till ett numeriskt värde när
du tillverkar den nya arrayen och upprepa proceduren ovan, sen vid sökning
omvandlar du "detsöktanamnet" till ett numeriskt och gör en direkt addressering
i arrayen. Ser du inte det?.