[VBScript] (B)Tree structure

[Verwijderd]

Ik heb een klein scriptje gemaakt dat een aantal items in het geheugen zet. Ik doe dit op het moment d.m.v. een array. Het zoeken hierin si echter zeer ineffiecient, dit gaat liniear. Ik moet nogal vaak zoeken dus dit zijn heel veel if statements.


Als ik nu een BTree structuur kan maken kan ik deze zoekacties met 60% verbeteren schat ik. De vraag is alleen hoe doe ik dit ? Mijn data structuur is de volgende :

voor elk item komt de volgende combo voor :

merk,type,kleur

Dus als je de volgende data hebt :

BMW,3-serie,blauw
BMW,5-serie,groen
BMW,7-serie,geel
Volkswagen,polo,rood

Nu zoekt ie het array door naar eerst het merk, vervolgens voor elk merk naar het type en dan naar de kleur.

Ik wil dus naar :

code:

              merk
                \
                type
                   \
                    kleur

ofwel :

code:

                   BMW                            ->                         Volkswagen
                /      |      \                                                               \
              3-s..   5-..    7-series                                                 polo
             /           |          \                                                          \
       blauw        geel       groen                                                  rood

Hoe doe ik dit in VBScript ?

[NetForce1]

Een multidimensionale array misschien?

[Niemand_Anders]

Simpel? Gewoon de data in een xml bestand knallen en vervolgens met een xpath query de zoekopdracht uitvoeren. Ook zou je een implementatie kunnen maken op basis van het composite design pattern (waarom XML DOM is gebaseerd), maar is een stuk complexer. Een andere oplossing is het gebruik van een database tabel (mdb via odbc) zodat je nog simpeler kunt selecteren op attributen (tabel kolom van een tabel)

En waarom moet het in vbscript? Waarom niet in VB.net of C#? .NET classes welke geinstalleerd zijn in de GAC (Global Assembly Cache) kun je ook via CreateObject benaderen.

[j_du_pee]

Ik zou dit waarschijnlijk niet doen met een array, maar óf met een database, óf met het dictionaryobject

[NetForce1]

j_du_pee schreef op woensdag 04 juli 2007 @ 16:44:
Ik zou dit waarschijnlijk niet doen met een array, maar óf met een database, óf met het dictionaryobject

Dat is waarschijnlijk nog mooier ja, wist niet dat dat in vbscript zat.

[Verwijderd]

Oeps vergeten te vermelden ... het moet in het geheugen omdat het snel moet zijn en niet naar disk mag schrijven of andere database dingen gebruiken.

Waarom VBscript ... tja het is helaas niet mijn keuze maar een andere taal voor deze toepassing is er niet helaas.

Ik heb het al werkend met een multidemensionaal array alleen mijn vraag is dus als ik hierin zoek naar (merk,type) om de kleur te achterhalen moet ik zoveel items door, eerst alle andere merken welke voor het tezoeken merk komen, da's een beetje zonde. Ik weet dat vbscript een beetje gelimiteerd in dit soort dingetjes is en ik ben zelf niet zo'n kenner van vb dus dacht ik dat iemand anders misschien een hint ofzo had hoe dit sneller te maken.

Een dictionaryobject ? ik zal eens kijken maar ik denk niet dat ik mijn structuur daarin krijg temeer ook omdat ik eigenlijk zoek op de eerste twee items (merk,type) en dan de kleur terug wil hebben.

[ Voor 32% gewijzigd door Verwijderd op 04-07-2007 22:03 ]

[Verwijderd]

Ter verduideling :

Ik heb deze data in een multidemensionaal array :

BMW,3-serie,blauw
BMW,5-serie,groen
BMW,7-serie,geel
Volkswagen,polo,rood

Nu stel ik de vraag "Welke kleur heeft een volkswagen van het type polo ?"

Ik lees dus elk element uit tot ik bij volkswagen ben en vervolgens alle volkswagens tot ik bij het type polo. Ik vind dus uiteindelijk "rood" als antwoord. Dit kost veel if statementjes en moet helaas bij elke keer opvragen opnieuw beginnen omdat de vraag elke keer anders is.

Als ik een soort BTree of andere opslag methode kan ik een hoop elemineren aangezien ik dan in 2 stappen bij volkswagen ben i.p.v 4 stappen. Dat is wat ik wil. Ik ga dus nog even uizoeken hoe een dictionary object zijn data opslaat en terug zoekt. Als dit sneller is dan is dat een optie anders is het helaas.

Alle sugesties zijn welkom.

[NetForce1]

Het lijkt mij dat je het beste nested dictionaries kan gebruiken. Een met als key het merk en als value een andere dictionary met als key het type en als value de kleur.
Het gebruik van een database zou ik echter zeker niet van te voren uitsluiten alleen omdat je vermoed dat het trager is. Een dbms heeft nl allerlei luxe optimaliseringstechnieken aan boord waar jij nooit aan kunt tippen met je scriptje.

[Verwijderd]

NetForce1 schreef op woensdag 04 juli 2007 @ 23:18:
Het lijkt mij dat je het beste nested dictionaries kan gebruiken. Een met als key het merk en als value een andere dictionary met als key het type en als value de kleur.
Het gebruik van een database zou ik echter zeker niet van te voren uitsluiten alleen omdat je vermoed dat het trager is. Een dbms heeft nl allerlei luxe optimaliseringstechnieken aan boord waar jij nooit aan kunt tippen met je scriptje.

Ja maar ik heb geen beschikking tot een database en het is helaas ook niet mogelijk (geen schrijfrechten en geen opties aanwezig). Maar bedankt voor de tips.

[Niemand_Anders]

Dan zou ik echt voor de XML oplossing gaan en de resultaten via xpath ophalen. Je zegt dat je geen dingen kunt opslaan. Maar hoe kom je dan aan de gegevens om de array te vullen? Is deze hardcoded of kun je wel een bestand inlezen? In dat laatste geval zou je een xml bestand kunnen wegzetten en daarna inladen. Kun je dat niet, dan zul je de xml boom in je script zelf moeten opbouwen. Dat opbouwen kun je waarschijnlijk het beste als een string (of adodb.stream) doen.

code:

set xml = CreateObject("Microsoft.DomDocument2")
xml.LoadXml("<cars><brand label=""VW""><type label=""Polo""><model color=""red"" engine=""1.4"" /><model color=""blue"" engine=""1.6""/></type></brand></cars>")

set nodes = xml.SelectNodes("//brand[@label='VW']/type[@label='Polo']");
for each node in nodes
    wscript.WriteLine(node.xml) 'doe iets met resultaat
next

Een ander voordeel van xml is dat elke node ook zijn referentie behoud. Als je een select doet op //model[color= 'red'] dan kun je via ParentNode ook weer eenvoudig model terug krijgen. Maar zoals je ziet heb ik ook eenvoudig een extra eigenschap (engine) kunnen toevoegen en zoeker hierop is eenvoudig (//brand[@label='Opel']/type/model[@engine='2.0']) geeft alle opel modellen terug met een 2.0 liter motor.

Kun je zelf via bijv. FTP een xml bestand op de server zetten, dan kun je met xml.Load("path naar xml bestand") het xml bestand inladen. Als het om erg veel definities gaat en je kunt het bestand niet inlezen, dan raad ik je aan de xml boom via het adodb.stream object op te bouwen. Het gebruik ervan is eenvoudig en de performance is een stuk beter dan string bewerkingen in vbscript.

De voordelen: De Microsoft XML parser is een van de beste en snelste verkrijgbaar voor windows en je hebt in 1 stap de resultaten. Een ander voordeel is dat je zeer eenvoudig nieuwe kenmerken kunt toevoegen.

[Verwijderd]

Niemand_Anders schreef op donderdag 05 juli 2007 @ 11:29:
Dan zou ik echt voor de XML oplossing gaan en de resultaten via xpath ophalen. Je zegt dat je geen dingen kunt opslaan. Maar hoe kom je dan aan de gegevens om de array te vullen? Is deze hardcoded of kun je wel een bestand inlezen? In dat laatste geval zou je een xml bestand kunnen wegzetten en daarna inladen. Kun je dat niet, dan zul je de xml boom in je script zelf moeten opbouwen. Dat opbouwen kun je waarschijnlijk het beste als een string (of adodb.stream) doen.

code:

set xml = CreateObject("Microsoft.DomDocument2")
xml.LoadXml("<cars><brand label=""VW""><type label=""Polo""><model color=""red"" engine=""1.4"" /><model color=""blue"" engine=""1.6""/></type></brand></cars>")

set nodes = xml.SelectNodes("//brand[@label='VW']/type[@label='Polo']");
for each node in nodes
    wscript.WriteLine(node.xml) 'doe iets met resultaat
next

Een ander voordeel van xml is dat elke node ook zijn referentie behoud. Als je een select doet op //model[color= 'red'] dan kun je via ParentNode ook weer eenvoudig model terug krijgen. Maar zoals je ziet heb ik ook eenvoudig een extra eigenschap (engine) kunnen toevoegen en zoeker hierop is eenvoudig (//brand[@label='Opel']/type/model[@engine='2.0']) geeft alle opel modellen terug met een 2.0 liter motor.

Kun je zelf via bijv. FTP een xml bestand op de server zetten, dan kun je met xml.Load("path naar xml bestand") het xml bestand inladen. Als het om erg veel definities gaat en je kunt het bestand niet inlezen, dan raad ik je aan de xml boom via het adodb.stream object op te bouwen. Het gebruik ervan is eenvoudig en de performance is een stuk beter dan string bewerkingen in vbscript.

De voordelen: De Microsoft XML parser is een van de beste en snelste verkrijgbaar voor windows en je hebt in 1 stap de resultaten. Een ander voordeel is dat je zeer eenvoudig nieuwe kenmerken kunt toevoegen.

Dat is allemaal heel leuk alleen heb ik alleen de beschikking tot VBscript en geen disk's of ftp of andere databases of andere talen en die gaan er ook niet komen dus ik zit vast aan vbscript. Ik lees nu de data gewoon in van file en zet deze in een arrayen zoek daarin, dit is inefficient maar een heel stuk efficienter dan het zoeken in een file wat voorheen gebeurde.

[bigbeng]

Je hoeft een XML document helemaal niet van schijf in te lezen. Je kunt zo'n XML document prima in het geheugen in elkaar zetten. De enige vraag die je moet kunnen beantwoorden is of de machine waar je script op draait MS XML heeft en volgens mij is dat tegenwoordig altijd zo. Je kunt met een createobject heel eenvoudig een XMLDOM object aanmaken:

VBScript:

Dim myDOM
Set myDOM = CreateObject("Microsoft.XMLDOM")

Dit is ongetest, dus syntaxerrors voorbehouden

Vervolgens bij het inlezen van het bestand een xml document opbouwen. Dit hoef je niet te saven om er xpath queries op te draaien.

[Janoz]

Tja, een hele xml parser integreren lijkt me nu niet de meest efficiëntste oplossing. Ik weet niet wat de mogelijkheden zijn in vbscript, maar een eigen struct of tpe definiëren lijkt me een stuk logischer. Mocht het zoeken enkel in deze volgorde gebeuren dan lijkt mij een dictionary in een dictionary een stuk efficiënter dan een hele dom in je applicatie hangen (hoe denk je dat die van binnen werkt ).

Mocht je ook in andere volgordes willen zoeken (dus alleen op merk en kleur en dan ale types terug krijgen), dan zou ik gewoon met meerdere lookup tables werken. Eigenlijk 3 bomen die elk in hun leaves naar de auto objecten wijzen.

[sopsop]

Je zou ook je bestand als csv (comma separated) in kunnen lezen in een (ADO)recordset en daar je filtering op doen. Dit kan in VB-script, er zijn alleen wat eisen gesteld aan de geinstalleerde mdac.

Hier een voorbeeld: http://www.xtremevbtalk.com/showthread.php?t=252540

Zie de tweede post.

[bigbeng]

Eens en oneens.

Het is zo dat je het met een set dictionaries helemaal zelf kan schrijven, maar ook je zoek algoritme moet je dan helemaal zelf schrijven. Een XML parser bevat wel query functionaliteit die voldoet aan een standaard. Die kun je leren en ook nog vele andere zoekproblemen mee oplossen. Aan de andere kant is het zelf leren maken van oplossingen voor dit soort problemen ook een goede leerschool.

De TS mag fijn uitzoeken wat hij belangrijk vindt

[Janoz]

Tja, hij wil het aan gaan pakken omdat de huidige implementatie niet snel genoeg is, en iedereen komt hier met bloated oplossingen aanzetten die alleen maar meer complexiteit in het programma brengen. Wat denk je dat het toevoegen van een complete recordset functionaliteit doet met de efficientie? Hoe denk je dat die XML parser werkt? Uiteindelijk hebben zij intern ook een structuur die waarschijnlijk uit iets vergelijkbaars als de dictionary objecten bestaat.

[MrBucket]

Allereest een paar wedervragen: om welke getallen gaat het ongeveer? Hoeveel merken, types en kleuren zijn er ongeveer, en hoeveel combinaties bestaan er? Is deze data statisch, of ga je deze continue updaten? Overheersen de queries, of de updates, of zijn er van beiden ong. evenveel?
--edit: als je minder als ong. 100 combinaties hebt, dan weegt het extra implementatiewerk van een 'optimale' zoekstructuur en het bijbehorende risico dat je bugs introduceert hiermee waarschijnlijk niet op tegen de (marginale) snelheidswinst.

Deze punten hebben allemaal invloed op welke strategie je het best kunt kiezen.

Met dit in het achterhoofd heb ik tot dusver eigenlijk 2 bruikbare suggesties gezien:
- De nested dictionary. Misschien een klein beetje overhead vanwege het feit dat het COM / Automation objecten zijn, maar voor de rest waarschijnlijk optimaal qua zoektijd en updates (mits het om relatief grote aantallen auto's gaat). Als je kunt garanderen dat het Scripting.Dictionary-object aanwezig is, zou ik zonder meer voor deze oplossing gaan.
- De meerdimensionale array. Dit is de meest simpele native oplossing - je hebt geen afhankelijkheid van COM-objecten die misschien niet aanwezig zijn (ik weet niet hoe standaard dat Scripting.Dictionary object is). Is met name handig als je data niet wijzigt en als het aantal merken ong. even groot is als het aantal types. In dat geval kun je de zoektijd reduceren naar ong. wortel(n).
Oh, enne, je kunt elk van deze dimensies natuurlijk ook sorteren he, waardoor je met een binary search ipv een lineaire search erdoorheen kunt ploegen.

Als je (in verhouding tot het aantal queries) weinig updates hoeft uit te voeren, kun je natuurlijk ook gebruik maken van een gesorteerde array, die je met een binary search kunt doorzoeken. Je moet dan wel een ordening definieren over alle (merk, type, kleur) combinaties (bijv. eerst alfabetisch gesorteerd op merk, binnen hetzelfde merk alfabetisch gesorteerd op type en binnen hetzelfde type alfabetisch gesorteerd op kleur).

Verwacht je dat je ook efficient moet kunnen updaten, dan is de Skip List misschien een uitkomst (zie http://en.wikipedia.org/wiki/Skip_list en ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf). In het kort komt het erop neer dat het ong. dezelfde eigenschappen heeft als een BTree, alleen minder complex is om te implementeren.

[ Voor 7% gewijzigd door MrBucket op 09-07-2007 22:33 ]

[Verwijderd]

Het scripting object staat volgens mij vanaf win2k (of al eerder) standaard er al op en het xml object dacht ik niet.
Moet je even naar googlen om erachter te komen.
Anders is het wellicht ook een optie om via het scripting object een collection te maken en dan een tree class te schrijven. Da's best gemakkelijk en uiteindelijk erg prettig te gebruiken. Dat zou mijn voorkeur genieten boven multidimensionale arrays.

edit:
Niet helemaal goed gelezen wat MrBucket al zei.

[ Voor 7% gewijzigd door Verwijderd op 09-07-2007 23:06 ]