På skolen lærer vi, at ved anvendelse af binær søgning skal listen (vi søger i ) være ordnet og må ikke indeholde blanke felter eller dupletter, I det lange uden-for skolen liv finder vi ud af , at med IT og programmringsværktøjer er dette krav til binær - listen knap så stringent (omend det stadig vil være nemmere at søge i listen.)
Jeg er netop "banket" ind i det problem.
Har skrevet en Atmel AT2560 disassembler. Den fungerer men jeg har nogen problemer med at anbringe de rette labels på det rette lokationer. Den disassemblerede liste (et STRINGGRID i Delphi 7) indeholder blanke linier efter JMP, RET, RETI, -- kommandoer for at øge læseligheden og det er dise blanke linier, som "ødelægger" den ordinære binære søgning. Fjerner jeg disse tomme linie (på bekostning af læseligheden) fungerer den binære søgning (indsættelse af labels på rette lokationer), som en sød drøm, men den efterfølgende genetablering af tomme linier (efter jmp, ret - etc (jf. ovenfor) kan tage op til 25 (FYSISKE) minutter (estimeret, men bed) ved et 7500 liniers disassembleret program. Det er utilfredsstillende.
Sekventiel søgning (og udskiftnng på rette sted) tager ca. 10- 15 minutter (7500 linier program - igen noget utilfredsstillende (men bedre end den anden løsning) ), så jeg funderer på, om der er nogen blandt Ekspertens medlemmer, som har nogen erfaringer omkring binær søgning med blanke/dupletter i listen.
Så du har en tabel, eller array/liste, med værdier der ikke egner sig til binær søgning. Du siger, der er huller i for at du bedre kan læse det. Det kan give god mening.
Men så kan man ikke lave binær søgning. Derfor skal du først i dit program trække de relevante data ud, og lægge dem i en liste for sig. Det bevirker så at din oprindelige liste slet ikke behøver være sorteret, for du kaster selvfølgelig lige en sortering efter din nye liste. Det skal bare ske een gang i hver kørsel.
Men du kunne også smide værdierne i en hash-tabel, som kan være hurtigere end binær søgning.
Jeg forklarede problemet for en god ven (som også "roder" lidt med Delphi- programmering). Han sagde, at han ville "se" ( = tænke) lidt på problemet. Det gjorde han.
Løsningen er egentlig ret så enkel, når en ( = jeg) tænker over det. I StringList - felt 1 (= StringList.Cell[0,nn] ) som representerer ADRESSEN indsættes adressen i det uderliggende adressefelt. (altså: StringList.Cell[0,nn] = StringList.Cell[0,nn - 1] ). Dette betyder at i stedet for en blank i adressefeltet nu er en duplet. Brug af en binær søgerutine på denne adresse vil resultere i at søgeresultatet vil vise til dette indsatte felt. (StringList.Cell[0,nn - 1] ) . Hvis det efterfølgende adressefelt er lig med søge-adressen ( StringList.Cell[0,nn] = StringList.Cell[0,nn +1 1] ) er det "bare" at skrive LABEL-adressen i LABEL-feltet ( StringList.Cell[2,nn+1] .
Og mærkeligt nok det virker ...
Og denne binærs søgerutine virker også i de høje dele af Adresse-listen - de hidtidigt afprøvede ignorerer høj-delen .
HASH-tabeller har jeg ikke tænkt over - i det hele taget, men tak for ideen. Vil checke om den løsning er bedre end binær søgning - omend indsætning med binær søgning e900 labels (+/-) i 7500 (+/-) linier tager 1-2 (fysiske sekunder) og det er til at leve med ....
MVH
Kristian
Synes godt om
1 synes godt om dette
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.
