[Algoritme] Optimaal zoeken

[rickiii]

Dag allen,

ik probeer op mijn werk een optimaal masker-verzameling te vinden voor een zoekopdracht.

Het gaat om 4 cijfers: 0000 t/m 9999

In het geval van: 1000 t/m 2000 zouden de maskers zijn: { '1', '2000' }
Met als resultaat de nummers 1000 t/m 1999 & 2000

In het geval van: 1100 t/m 1200 zouden de maskers zijn: { '11', '1200' }
Met als resultaat de nummers 1100 t/m 1199 & 1200

De bedoeling is dus om met zo min mogelijk maskers de volledige lading te dekken.
Een zoekmasker wordt dus gebruik om een aantal zoekresultaten te behalen, maar een zoekopdracht is zeer kostbaar qua tijd.

Daarnaast komt nog eens bij dat het handmatig filteren van gevonden resultaten een factor 10 sneller is dan een zoekopdracht. Dus liever 10 resultaten filteren (checken of deze in de range zit) dan 1 keer extra zoeken.

Als er iemand is die me hiermee kan helpen, dan hoor ik het graag, want ik zou niet weten hoe ik kan bewijzen dan mijn manier te snelste is. Elke input is welkom.

Rick

[curry684]

En wat is er mis met gouwe ouwe B-search?

[edit]
* curry684 leest nog eens door en vermoed dat dat een domme vraag was, maar weet het niet zeker... wat is nu je lijst en welke en hoeveel elementen wil je daaruit zoeken op welke criteria?

Want je geeft nu wel heel leuk je veronderstelde methode weer, maar niet de gewenste pre- en postcondities...

[ Voor 78% gewijzigd door curry684 op 14-01-2004 10:08 ]

[rickiii]

curry684 schreef op 14 januari 2004 @ 10:05:
En wat is er mis met gouwe ouwe B-search?

[edit]
* curry684 leest nog eens door en vermoed dat dat een domme vraag was, maar weet het niet zeker... wat is nu je lijst en welke en hoeveel elementen wil je daaruit zoeken op welke criteria?

Want je geeft nu wel heel leuk je veronderstelde methode weer, maar niet de gewenste pre- en postcondities...

De pre conditie is: Je hebt geen zoekresultaten.
De post conditie is: Je hebt 1 of meerdere zoekresultaten.

[RickN]

Ik snap d'r geen zak van, ik heb echt géén idee wat je nou eigenlijk wilt zoeken....

Ben je aan het pattern-matchen ofzo? Oh en je pre- en postconditie zijn ongeveer net zo verhelderend als:

pre: wat ik wil geldt niet
post: wat ik wil geldt wel

[Verwijderd]

RickN schreef op 14 januari 2004 @ 13:55:
Ik snap d'r geen zak van, ik heb echt géén idee wat je nou eigenlijk wilt zoeken....

Ben je aan het pattern-matchen ofzo? Oh en je pre- en postconditie zijn ongeveer net zo verhelderend als:

pre: wat ik wil geldt niet
post: wat ik wil geldt wel

Hier nog een, lijkt mij als je op een nummer range wilt zoeken, dat je gewoon via
waarde >= minimum EN waarde <= maximum zoekt, lijkt me het simpelst en snelst. Zeker in een DB met een index op waarde

[curry684]

Verwijderd schreef op 14 januari 2004 @ 14:27:
[...]

Hier nog een, lijkt mij als je op een nummer range wilt zoeken, dat je gewoon via
waarde >= minimum EN waarde <= maximum zoekt, lijkt me het simpelst en snelst. Zeker in een DB met een index op waarde

Lijkt mij dus ook, maar blijkbaar wil Mahler geen hulp als ie niet duidelijk wil vertellen wat het probleem en de randvoorwaarden ervan nu eigenlijk zijn.

Een probleem bestaat uit een preconditie A en een postconditie B, en het beste algoritme is de snelste route van A naar B. Hoe we dat algoritme moeten vinden zonder A en B te kennen weet ik ook niet.

[Soultaker]

Mijn begrip van het probleem is als volgt. De TS heeft een domein van integers van 0 tot 1000 (tot en met 999 dus), waarbij die getalen altijd met vier decimalen gerepresenteerd worden (7 als 0007 bijvoorbeeld).

Nu kan de TS 'masks' definiëren, die een deel van het domein matchen; namelijk alle getallen een prefix hebben gelijk aan de mask. De mask '12' matcht dus '1234' (want '12' is een prefix van '1234') maar niet '3412'; feitelijk matcht die mask de getallen van 1200 tot 1300 (tot en met 1299).

Nu ga ik een beetje gokken, want dit staat niet zo duidelijk in de topic start, maar ik neem aan dat de TS een deelverzameling van het domein heeft; een aantal getallen dus. Nu is het de bedoeling dat hij deze deelverzameling definiëert door middel van een aantal masks. Als het subdomein de getallen van 0 tot 10 bevat, dan kan 'ie bijvoorbeeld de masks ( 0000, 0001, ..., 0009 ) gebruiken om het hele subdomein te omvatten.

De bedoeling van de TS is echter om het gebruikte aantal masks te minimaliseren. In het voorbeeld dat ik gaf kun je bijvoorbeeld ook alleen '000' gebruiken, want we hadden al eerder gezien dat dat dan de getallen van 0 tot 10 matcht. Dit klinkt me als een programmeeropgave in de oren (ik kan me zo weinig voorstellen bij een praktijksituatie waarin je dit zou wilen). Als het ook een huiswerkopgave is, dan wil ik de TS verzoeken dat er even bij te vermelden, dan kunnen we onze hulp daarop aanpassen. Het probleem zoals ik dat nu heb geschetst is trouwens vrij simpel op te lossen.

[rickiii]

curry684 schreef op 14 januari 2004 @ 14:34:
[...]

Lijkt mij dus ook, maar blijkbaar wil Mahler geen hulp als ie niet duidelijk wil vertellen wat het probleem en de randvoorwaarden ervan nu eigenlijk zijn.

Ik heb ook andere dingen te doen vandaag, dus ik kon niet direct reageren.

Soultaker schreef op 14 januari 2004 @ 15:05:
Mijn begrip van het probleem is als volgt. De TS heeft een domein van integers van 0 tot 1000 (tot en met 999 dus), waarbij die getalen altijd met vier decimalen gerepresenteerd worden (7 als 0007 bijvoorbeeld).

Nu kan de TS 'masks' definiëren, die een deel van het domein matchen; namelijk alle getallen een prefix hebben gelijk aan de mask. De mask '12' matcht dus '1234' (want '12' is een prefix van '1234') maar niet '3412'; feitelijk matcht die mask de getallen van 1200 tot 1300 (tot en met 1299).

Nu ga ik een beetje gokken, want dit staat niet zo duidelijk in de topic start, maar ik neem aan dat de TS een deelverzameling van het domein heeft; een aantal getallen dus. Nu is het de bedoeling dat hij deze deelverzameling definiëert door middel van een aantal masks. Als het subdomein de getallen van 0 tot 10 bevat, dan kan 'ie bijvoorbeeld de masks ( 0000, 0001, ..., 0009 ) gebruiken om het hele subdomein te omvatten.

De bedoeling van de TS is echter om het gebruikte aantal masks te minimaliseren. In het voorbeeld dat ik gaf kun je bijvoorbeeld ook alleen '000' gebruiken, want we hadden al eerder gezien dat dat dan de getallen van 0 tot 10 matcht. Dit klinkt me als een programmeeropgave in de oren (ik kan me zo weinig voorstellen bij een praktijksituatie waarin je dit zou wilen). Als het ook een huiswerkopgave is, dan wil ik de TS verzoeken dat er even bij te vermelden, dan kunnen we onze hulp daarop aanpassen. Het probleem zoals ik dat nu heb geschetst is trouwens vrij simpel op te lossen.

Je hebt het 100% goed begrepen. Ik dacht duidelijk geweest te zijn, maar helaas. Ik vindt jouw uitleg toegevoegde waarde voor mensen die het nog niet begrepen. Bedankt.

Overigens wil ik daarbij toevoegen dat het absoluut een werksituatie is. Ik werk met een interface die zelf in de Database gaat zoeken en ik moet trapsgewijs filteren. (SQL zou inderdaad veel handiger zijn, maar helaas is er geen directe toegang tot een database)

Ik heb als oplossing nu dat alle 1000 resultaten opgevraagd worden en die vervolgens te filteren... maar dat is niet erg efficient met een paar honderd concurrent users.

Heel erg simpel lijkt dit me niet op te lossen. Misschien denk ik te moeilijk.
Ik zit te denken aan een soort controle of het verschil kleiner van 1000, kleiner dan 100, kleiner dan 10 is en vervolgens maskers te kiezen daartussen en die vervolgens te filteren.

Overigens is het gunstiger om in 1 keer 100 stuks op te halen en die te filteren, dan 2 (tot 9) keer 10 stuks op halen en die te filteren.

[ Voor 27% gewijzigd door rickiii op 14-01-2004 17:15 ]

[Juup]

Dus iemand geeft jou een deelverzameling (bv. 1000 t/m 1345 en 2000 en 543 ofzo) en jij wilt een minimaal aantal filters weten dat deze lading dekt, bv {10, 11, 12, 130, 131, 132, 133, 1340, 1341, 1342, 1343, 1344, 1345, 2000, 0543 }

[rickiii]

Juup schreef op 14 januari 2004 @ 22:08:
Dus iemand geeft jou een deelverzameling (bv. 1000 t/m 1345 en 2000 en 543 ofzo) en jij wilt een minimaal aantal filters weten dat deze lading dekt, bv {10, 11, 12, 130, 131, 132, 133, 1340, 1341, 1342, 1343, 1344, 1345, 2000, 0543 }

Ja... hmm alleen het snappen van het probleem is al moeilijk genoeg blijkbaar

[Appesteijn]

Moet je filter uit alleen de eerst n getallen bestaan? Anders zou je, om alles te kunnen matchen, 0*** tm 9*** + *0** tm *9*** etc. dan kan je met 40 filters de hele verzameling matchen.
Als ik het zo tenminste goed begrijp....

[Skinkie]

kost het plaatsen + zoeken van een mask niet meer tijd dan de resultaten te indexeren cq in een tree te stoppen?

helemaal omstreden: pomp al je records in SQLite (25000 inserts in 1 transactie kost 0,9sec), doe je select query drop de database... maar dit is meer scripten dan programmeren...

[Opi]

Appesteijn schreef op 14 januari 2004 @ 23:44:
Moet je filter uit alleen de eerst n getallen bestaan? Anders zou je, om alles te kunnen matchen, 0*** tm 9*** + *0** tm *9*** etc. dan kan je met 40 filters de hele verzameling matchen.
Als ik het zo tenminste goed begrijp....

Tenzij er combinaties zijn zoals 01** tm 99**. Een methode die je zou kunnen gebruiken is door eerst te kijken welk mask het grootste deel van de verzameling beslaat. Vervolgens kan je in het resterende deel van de verzameling kijken welk mask daar het meest efficiënt is. Enige nadeel, waarvoor ik zo snel ook nog geen oplossing voor heb verzonnen, is dat het mogelijk is dat 2 suboptimale masks effectiever zijn dan 2 keer een optimaal mask.

[Soultaker]

OpifexMaximus schreef op 15 januari 2004 @ 00:32:
Enige nadeel, waarvoor ik zo snel ook nog geen oplossing voor heb verzonnen, is dat het mogelijk is dat 2 suboptimale masks effectiever zijn dan 2 keer een optimaal mask.

Dat is gelukkig onmogelijk.

De echte uitdaging is overigens om dit in lineaire tijd te doen, of, in een algemenere formulering van het probleem, in O(m*n) tijd, met m het aantal getallen in het domein en n het aantal 'cijfers' dat gebruikt wordt per getal (in dit geval dus 4).

[ Voor 40% gewijzigd door Soultaker op 15-01-2004 03:01 ]

[Apollo_Futurae]

Opzetje:

input: een verzameling van 'bereiken' (paren getallen; een paar (a,b) stelt het bereik a tot en met b voor; (c,c) is dus alleen het getal c).

output: een verzameling met maskers die precies de input bestrijken.

1. Check de input: controleer of voor elk paar het tweede getal minstens zo groot is als het eerste en controleer of er geen negatieve getallen tussen zijn (dit kun je eventueel weglaten, bij voorbeeld als je parser of dataconstructor dit soort gevallen al opvangt).
2. Breng de paren getallen in een goede vorm: zoek naar overlappende en precies aansluitende bereiken, en voeg deze samen.
(Na deze stap kun je alle bereiken apart en onafhankelijk behandelen, aangezien bereiken onderling door minstens één getal gescheiden zijn en maskers nooit getallen kunnen 'overslaan'.
3. Voor elk bereik:
Haal alle mogelijke hele duizendtallen eruit: voeg de bijbehorende maskers toe aan de outputverzameling, en pas het bereik als volgt aan: splits het in drie stukken (voor de duizendtallen, de duizendtallen, na de duizendtallen); het eerste en laatste stuk hou je, het middelste laat je weg.
Herhaal dezelfde procedure achtereenvolgens met honderdtallen, tientallen en eenheden.

Commentaar is van harte welkom, maar ik zal pas maandag of dinsdag weer kunnen reageren .

[Soultaker]

De methode van Apollo_Futurae lijkt me correct. Hoe je precies de duizendtallen eruit haalt, ligt niet direct voor de hand, maar gezien de beperkte invoer is elke methode wel min of meer goed genoeg.

[rickiii]

de methode van Apollo_Futurae klinkt goed.
Dit is ongeveer mijn gekozen manier, behalve de tientallen en eenheden, welke beter gefilterd kunnen worden na afloop.

ik ga niet verder dan de eerste twee getallen met het creeren van maskers.
Dit is volgens mij nog niet optimaal, maar gemiddeld wel de snelste manier. (als ik een nog meer optimale verzameling van maskers wil hebben moet ik uren extra tijd besteden aan tijdswinst per zoekopdracht van hooguit 1 of 2 seconden.

Bedankt voor het meedenken!

[Soultaker]

Uren?! Hoe krijg je dat voor elkaar? Heb je een heleboel aparte gevallen? Hoeveel tijd heb je dan per geval nodig?

[curry684]

Soultaker schreef op 21 januari 2004 @ 16:11:
Uren?! Hoe krijg je dat voor elkaar? Heb je een heleboel aparte gevallen? Hoeveel tijd heb je dan per geval nodig?

Volgens mij bedoelt ie dat x uur extra developtijd hoogstens een winst van een paar seconden per query oplevert en dat ie dat geen rendabele investering vindt