Isf är det ingen maskinell 'sökning' överhuvudtaget och alla dina jämförelser med etablerade metoder faller pladask
Tycker det börjar lukta avundsjuka. Jag har en sökmotor som söker igenom 15000 arrayer på ett ögonblink. så är det.
Omöjliga möjligt?
Programmeringur Programmering - Övrigt
82 svar · 3 876 visningar · startad av Dano · sida 2 av 5
Frågan, av Dano
Hej. Jag har kommit på 1 sätt att minimera söktiden i arrayer till 0. jag provade och la upp 15000 arrayer med slumpvisa nummer i. Och gjorde en sökmotor på dessa nummer. Om man bara gör en "for loop" och scannar igenom tills man hittar det sökta numret så tar det cirkus 15 sek. Men med min metod är man nere i 0 sek. Och det kvittar också hur många arrayer det är, jag kan lägga upp 1 miljard arra
Läs frågan i sin helhet →
Oj, sorry, första moderatormissen. Råkade redigera ditt inlägg :r
Skulle skriva nytt:
Det återstår bara att bevisa.
He he... varför skulle man vara avundsjuk? Databaser är tråkigt och så är det bara ;)
Men det är lite lustigt med din definition. Först är det 0 sekunder och nu är det ett ögonblick... :e
Dano skrev:
Tycker det börjar lukta avundsjuka. Jag har en sökmotor som söker igenom 15000 arrayer på ett ögonblink. så är det.
Antingen är det avundsjuka, eller så är det vanlig sund skepsis. Kommer man med extraordinära påståenden (vilket du i allra högsta grad gör) får man komma med extraordinära bevis (vilket du hittills inte gjort). Som sagt, fram med ett program som visar hur rackarns fort det går, och du övertygar mig.
Det är noll faktiskt. ögonblink var väl mer talesätt
Nåja. När kommer beviset?
spango skrev:
Dano skrev:
minnesmängden är konstant hela tiden hela vägen från det man startar och till man avslutar, den ökar inte vid sökning.
Vad är det då som kräver en massa minne, om jag får fråga?
Fram med en kompilerad version, alt. en serverbaserad version som kan ta emot en godtycklig indatafil, sen övertygar du mig.
Han kanske lägger alla arrayer i minnet för att få snabbare åtkomst av dom.
Nickemannen skrev:
spango skrev:
Dano skrev:
minnesmängden är konstant hela tiden hela vägen från det man startar och till man avslutar, den ökar inte vid sökning.
Vad är det då som kräver en massa minne, om jag får fråga?
Fram med en kompilerad version, alt. en serverbaserad version som kan ta emot en godtycklig indatafil, sen övertygar du mig.
Han kanske lägger alla arrayer i minnet för att få snabbare åtkomst av dom.
Det ger inte konstant söktid.
Och definitivt inte noll i åtkomst (men det kanske å andra sidan även det var bara ett talesätt) ;)
Och jag upprepar frågan som jag inte fick svar på:
niko skrev:
Behandlar du din slumparray på nåt sätt innan du börjar din sökning? Typ sorterar den eller lägger över hela klabbet i nån Hashtable?
Om ja: Är tiden det tar inräknat i de 0 sekunderna?
Att döma av talet om stor minnesåtgång så är det kanske inte så svårt att räkna ut att Dano tex skapar en ny array som är lika stor som det största talet i första positionen och sen placerar in strängarna i de positioner som motsvaras av talet.
"Sökningen" blir nu en direkt adressering i den nya (glesa) arrayn och tiden det tar att allokera den nya arrayn och placera ut strängarna räknas liksom inte till själva sökningen.
som sagt det är mycket kvar innan det är klart. och det är ingen databas... ännu, det är arrayer än så länge.
förstår att ni är skeptiska, men detta är sant. hur otroligt det än låter. :)
Finns ju också en mikroskopisk möjlighet att du misstar dig. Att du gör en logisk kullerbytta, helt enkelt. :)
Men lycka till i.a.f. Nya algoritmer behövs alltid. :bire
Jag är inte skeptisk.
Jag kan med gott samvete konstatera att det du säger är ren och skär lögn.
Hur du än gör så får du en viss overhead. Även om man bortser från inläsning till minnet och utnyttjar det sättet som niko säger så kommer inläsningen aldrig ta "0 sekunder". Det finns ingeting som tar 0 sekunder att göra. Visst. På 0.000000001 sekunder finns det saker som går att göra. Men inte 0 sekunder. Det är en omöjlighet.
Används din sökalgoritm enbart för tal? Jag funderar på hur ofta man egentligen har användning av att söka på ett tal...
Vad har inläsningen med sökningen att göra?, när du startar ett vanligt program så sker också en "inläsning", liksom. programmet ligger ju såklart i minnet, därför behövs mycket minne. eller trodde du jag skulle läsa in en texfil med alla arrayer eller varje gång man ska söka?. arrayerna ligger i programmet
niko skrev:
"Sökningen" blir nu en direkt adressering i den nya (glesa) arrayn och tiden det tar att allokera den nya arrayn och placera ut strängarna räknas liksom inte till själva sökningen.
Isf är det ingen sökning och isf faller påståendet om att det är en sökmotor.
Ja tyvärr är det så att niko har kommit på mej. förutom en grej:
"niko:största talet i första positionen"
Det ska vara det största talet i något av elementen i arrayen
Alltså, det är en direkt addressering jag har kommit på, programmet VET vilken array som efterfrågas, därmed sker aldrig någon "sökning", därför blir det noll i åtkomst. Men hur som helst, det var jag som kom på det först. Och självklart är detta en sökmotor, en väldigt smart sökmotor, vad NI väljer att kalla det bryr jag mig inte om, den hittar talet som efterfrågas direkt. och hur den gör det är irrelevant.
och phorper, visst kan man omvandla den så att den kan söka på text också, det är bara att göra om texten till ett tal, och sen omvandla tillbaka till text vid sökning. dettta bör inte ta mer än nån millisekund.
Dano skrev:
Vad har inläsningen med sökningen att göra?, när du startar ett vanligt program så sker också en "inläsning", liksom.
Nope, inte hela programmet. Såvida du inte skrivit din applikation för CP/M... men det kanske är det du har?
Dano skrev:
och phorper, visst kan man omvandla den så att den kan söka på text också, det är bara att göra om texten till ett tal, och sen omvandla tillbaka till text vid sökning. dettta bör inte ta mer än nån millisekund.
Riktigt så enkelt är det inte. Ett heltal är som bekant av fix storlek, och således kan man inte garantera att det inte finns två texter som ger samma resultat när man "gör om" den till heltal (d.v.s. hashar den). Sedan är hashningsfunktioner inte heller reversibla.
Dessutom, minnesåtgången är direkt relaterad till skillnaden mellan nollpunkten och maxvärdet för det man indexerar med. Om vi då börjar arbeta med värden som kan vara mellan noll och en biljon krävs alltså fyra biljoner byte minne (drygt tre terabyte).
Det är i längden ingen vidare hållbar lösning, men visst duger den om man har rimligt många objekt av rimligt stor storlek. Dock är det inte precis någon ny princip, jag tror nog att jag (och många med mig...) kan nog rota fram kod som använder exakt samma princip som har ett par år på nacken... faktum är att jag sitter och jobbar på en inlämningsuppgift som gör i princip samma sak.
Pew
sökmotorn är ingen hashfunktion, var har ni fått det ifrån?. jag gör inte om några textsträngar till mindre heltal eller använder några "buckets" för att indexera. jag indexerar ingenting alls, arrayens nr motsvarar arrayens värde bara, det är det som är hela grejen.
såhär funkar det:
typ[45673].varde=45673;
typ[45673].text="hej";
typ[2343].varde=2343;
typ[2343].text="hallo";
enbart för dessa 2 element i arrayen behövs en array som är 45674 i storlek. Det är därför man behöver gräsligt med minne. Men det är så man får "direkt access" utan söktid. eftersom det helt enkelt inte sker någon sökning alls.