---
title: "Omöjliga möjligt?"
type: "forum-thread"
url: "https://www.webforum.nu/amne/programmering/87944-omöjliga-möjligt/page2"
topic: "Programmering"
topic_url: "https://www.webforum.nu/amne/programmering"
author: "Dano"
published: "2003-10-08T00:55:37.000Z"
updated: "2004-02-20T16:38:50.000Z"
replies: 82
views: 3942
page: 2
pages: 5
language: "sv-SE"
site: "webForum — webforum.nu"
rights: "Upphovsrätten till varje inlägg tillhör dess författare."
attribution: "Citera som: webForum, https://www.webforum.nu/amne/programmering/87944-omöjliga-möjligt"
---

# Omöjliga möjligt?

_Sida 2 av 5._

## #21 — Dano, 2003-10-08T21:05Z

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.

Permalänk: https://www.webforum.nu/p/1180272

## #22 — Gein, 2003-10-08T21:08Z

Oj, sorry, första moderatormissen. Råkade redigera ditt inlägg  :r 

Skulle skriva nytt:

Det återstår bara att bevisa.

Permalänk: https://www.webforum.nu/p/1180276

## #23 — PeW, 2003-10-08T21:09Z

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

Permalänk: https://www.webforum.nu/p/1180278

## #24 — spango, 2003-10-08T21:16Z

> **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.

Permalänk: https://www.webforum.nu/p/1180284

## #25 — Dano, 2003-10-08T21:16Z

Det är noll faktiskt. ögonblink var väl mer talesätt

Permalänk: https://www.webforum.nu/p/1180285

## #26 — PeW, 2003-10-08T21:22Z

Nåja. När kommer beviset?

Permalänk: https://www.webforum.nu/p/1180299

## #27 — Nickemannen, 2003-10-08T21:39Z

> **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.

Permalänk: https://www.webforum.nu/p/1180322

## #28 — Gein, 2003-10-08T21:41Z

> **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.

Permalänk: https://www.webforum.nu/p/1180323

## #29 — PeW, 2003-10-08T21:50Z

Och definitivt inte noll i åtkomst  (men det kanske å andra sidan även det var bara ett talesätt)  ;)

Permalänk: https://www.webforum.nu/p/1180332

## #30 — niko, 2003-10-08T22:08Z

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.

Permalänk: https://www.webforum.nu/p/1180352

## #31 — Dano, 2003-10-08T22:08Z

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. :)

Permalänk: https://www.webforum.nu/p/1180353

## #32 — Robban, 2003-10-08T22:17Z

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

Permalänk: https://www.webforum.nu/p/1180360

## #33 — Phorpher, 2003-10-08T22:20Z

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...

Permalänk: https://www.webforum.nu/p/1180363

## #34 — Dano, 2003-10-08T22:24Z

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

Permalänk: https://www.webforum.nu/p/1180371

## #35 — PeW, 2003-10-08T22:29Z

> **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.

Permalänk: https://www.webforum.nu/p/1180373

## #36 — Dano, 2003-10-08T22:34Z

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.

Permalänk: https://www.webforum.nu/p/1180374

## #37 — PeW, 2003-10-08T22:35Z

> **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?

Permalänk: https://www.webforum.nu/p/1180375

## #38 — PeW, 2003-10-08T22:36Z

> Men hur som helst, det var jag som kom på det först.

....  hört talas om hashing?

Permalänk: https://www.webforum.nu/p/1180377

## #39 — spango, 2003-10-08T22:54Z

> **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.

Permalänk: https://www.webforum.nu/p/1180390

## #40 — Dano, 2003-10-09T00:17Z

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.

Permalänk: https://www.webforum.nu/p/1180429

---

Tråden på webben: https://www.webforum.nu/amne/programmering/87944-omöjliga-möjligt/page2  
Föregående sida: https://www.webforum.nu/amne/programmering/87944-omöjliga-möjligt.md  
Nästa sida: https://www.webforum.nu/amne/programmering/87944-omöjliga-möjligt/page3.md