[C++] Meest efficiente wijze om vectoren in elkaar te voegen

[Knakker]

** Edit: omdat ik merk dat context wel degelijk belangrijk is, heb ik dat in mijn derde post uitgelegd ... wellicht handig als je dat eerst leest. Alvast bedankt **

Ik ben bezig met het schrijven van een implementatie van een wiskundig algoritme. Ik heb al eerder wat vragen gesteld specifiek gerelateerd aan C++, maar dit is meer een algemene vraag. Theoretische snelheid van een algoritme is natuurlijk mooi, maar uiteindelijk is het toch de snelheid van de computerimplementatie waar het om draait. Probleem is dat ik weliswaar redelijk wat programmeerervaring heb, maar wanneer ik een op-en-top efficiente implementatie moet schrijven (nu het geval ) schiet mijn kennis gewoonweg tekort.

(Voor de mensen met wat kennis van combinatorisch optimaliseren: ik heb N cycles die ik één voor één aan elkaar wil plakken.)

Stel dat ik op een gegeven moment N vectoren heb van wisselende lengte. Van elke mogelijke combinatie van elementen uit twee verschillende vectoren heb ik een waarde berekend; deze zijn opgeslagen in drie dimensionale vector PatchCosts[I][J][K]; eerste twee indices geven de betreffende vectoren aan, K is de index. Voor twee vectoren C1 en C2 van lengte drie is de dimensie van PatchCosts dus negen. Ik houd er uiteraard rekening mee dat de waarden tussen C1 en C2 dezelfde zijn als C2 en C1 en dus niet berekend hoeven te worden, en PatchCosts is een soort bovendriehoeksmatrix (de waarden van cycles 4 en 6 staan in PatchCosts[4][1]).

Aan de hand van een bepaalde criteria, gebaseerd op deze waarden, besluit ik om één vector (C2) in een andere (C1) in te voegen. Ik kan nu natuurlijk de hele array PatchCosts opnieuw berekenen, maar dat is natuurlijk onnodig: de waarden tussen alle vectoren anders dan C1 en C2 blijven onveranderd en de waarden van vectoren gerelateerd aan C2 dienen alleen op de juiste posities ingevoegd te worden in de waarden gerelateerd aan C1. Nu heb ik een code geschreven waarbij ik gebruik maak van de container-class vector, en ik ben er ingeslaagd om het ‘updaten’ van de vector PatchCosts foutloos te laten verlopen. Hoewel deze code uiteindelijk nog geeneens 20 regels is, was dat behoorlijk complex om te maken en heeft een hóóp tijd gekost (geklooi met dimensies en posities in vectoren etc…).

Probleem: ik maak véél gebruik van het commando ‘insert’, en dat is een operatie met complexiteit N (volgens mij). Hoewel de huidige implementatie sneller is dan in het geval dat alles opnieuw berekend wordt, is het nog veel te traag. Op dit moment voeg ik elementen één voor één in; je begrijpt dat als ik een vector met dimensie 100 bij een andere vector met dimensie 150 invoeg, dat ik dus 100 keer (gemiddeld genomen) 75 elementen één positie opschuif.

Nu kan ik switchen naar een andere container-class, maar het probleem is dat de waarden PatchCosts[I][J][K] bij wijze van spreken net zo vaak opgevraagd worden in berekeningen, als dat ik inserts gebruik. Random access is dus net zo belangrijk als random insert.

Ik zou graag willen weten wat een efficientere aanpak is. Eén daarvan is de dimensie van C1 in één keer vergroten, de elementen van C1 verplaatsen naar het einde en C2 invoegen. Een andere is het één voor één schrijven van alle waarden naar een dummy vector om die vervolgens in één klap te kopieren naar PatchCosts met de juiste index. Zo zijn er vast nog wel wat alternatieven. Ik kan ze natuurlijk één voor één proberen maar zoiets implementeren vergt best veel tijd; ik hoop dat jullie hier je licht op kunnen laten schijnen.

Bedankt!

[ Voor 3% gewijzigd door Knakker op 18-11-2005 12:25 ]

[Soultaker]

Ik heb je verhaal een aantal keer moeten lezen om 't te kunnen begrijpen, waarschijnlijk omdat ik wat contextinformatie mis, maar als ik het goed begrijp heb je een aantal cykels van een bepaald soort elementen, en heb je een functie die gegeven twee van die elementen een zekere 'cost' uitrekent (de kosten om een pad toe te voegen daartussen ofzo ).

Als ik het goed heb begrepen reken je eerst de kosten uit voor alle paren van elementen in verschillende cykels en ga je in een latere stap cykels samenvoegen; bij dat samenvoegen moeten de kosten verplaatst worden (om dat je de elementen uit bijvoorbeeld cykel A naar cykel B verplaatst), maar je hoeft ze nooit opnieuw uit te rekenen. Klopt dat?

In die situatie vraag ik me af waarom je een 3D-vector gebruikt. Het lijkt me dat je in principe alleen een functie wil die gegeven twee elementen de bijbehorende kosten oplevert; die berekening is dan (denk ik) onafhankelijk van de cykels waarin die elementen zitten; klopt dat ook? Dan zou je simpelweg een map<pair<Element, Element>, Kosten> kunnen gebruiken om je waarden in te cachen.

Als je geheugen wil besparen en je access time wil verlagen, kun je de elementen nummeren vanaf 0 en een 2D matrix van kosten maken, maar het principe veranderd daar niet door.

Zit ik een beetje in de goede richting te denken? Zo niet, kun je dan misschien wat pseudocode geven van hoe je algoritme in elkaar steekt?

[Knakker]

Als ik het goed heb begrepen reken je eerst de kosten uit voor alle paren van elementen in verschillende cykels en ga je in een latere stap cykels samenvoegen; bij dat samenvoegen moeten de kosten verplaatst worden (om dat je de elementen uit bijvoorbeeld cykel A naar cykel B verplaatst), maar je hoeft ze nooit opnieuw uit te rekenen. Klopt dat?

Klopt! Nou ja, bij elke samenvoeging moeten de kosten van twee nieuwe elementen betrekking tot de rest van de cycles berekend worden; maar dat stelt niet veel voor.

In die situatie vraag ik me af waarom je een 3D-vector gebruikt. Het lijkt me dat je in principe alleen een functie wil die gegeven twee elementen de bijbehorende kosten oplevert; die berekening is dan (denk ik) onafhankelijk van de cykels waarin die elementen zitten; klopt dat ook? Dan zou je simpelweg een map<pair<Element, Element>, Kosten> kunnen gebruiken om je waarden in te cachen.

Het klopt dat de kosten van de elementen onafhankelijk zijn van de cycles waartoe ze behoren. Wel is het natuurlijk zo dat als twee elementen in dezelfde cycle terecht komen, de kosten tussen die twee irrelevant zijn geworden.

Maar ga je me nou vertellen dat datgene waar ik láng naar gezocht heb ook daadwerkelijk bestaat? Neemt zo'n 'map' niet meer geheugen in dan het aantal elementen dat erin zitten (geheugen is écht een issue bij grote netwerken), en is de random access ook efficient? Bij een list bijvoorbeeld moet je vanaf het begin de list doorlopen om een element te vinden, dus daar heb ik niks aan.

Ik heb overigens te maken met vier elementen per twee cycles in plaats van twee, alleen omdat dat verder niet relevant was (dacht ik) heb ik dat weggelaten; ik neem aan dat ik nog steeds gebruik kan maken van zo'n 'map'? Hoe werkt dat?

Als je geheugen wil besparen en je access time wil verlagen, kun je de elementen nummeren vanaf 0 en een 2D matrix van kosten maken, maar het principe veranderd daar niet door.

De elementen zijn genummerd, gewoon van 0 tot 2634 (bijvoorbeeld).

Ik snap dat het verwarrend voor je kan zijn, maar als je me op de weg kunt helpen ben ik (en de wetenschap ) je erg erkentelijk

[ Voor 6% gewijzigd door Knakker op 18-11-2005 00:40 ]

[writser]

Ik heb je verhaal een paar keer doorgelezen, maar snap nog niet precies wat de bedoeling is. Toch zal ik een poging wagen.

Je wil twee vectoren samenvoegen, op basis van een bepaalde ordening. Wat ik niet kan opmaken uit je post is of C1 en C2 ook al gesorteerd zijn, maar omdat je de ene vector wil 'mergen' met andere ga ik er vanuit dat dat zo is. In dat geval kun je beide vectoren 'ritsen'. Je initialiseert twee iterators, eentje voor C1[0] en eentje voor C2[0]. Je kiest dan steeds het kleinste element van beide en gooit deze in de nieuwe vector. Als je vantevoren genoeg ruimte in deze vector reserveert en push_back gebruikt kan dat wel efficient.

Gooi je een element van C1 in de nieuwe vector, dan verhoog je de iterator van C1, idem voor C2. Op deze manier ga je door tot je zowel C1 als C2 helemaal hebt doorgewerkt.

Als C1 en C2 niet gesorteerd zijn gaat dit natuurlijk niet op. Hopelijk heb je hier wat aan, ik ben benieuwd!

[writser]

Overigens ben ik wel benieuwd waar je precies mee bezig bent. Je werkt met cykels, maar wat doe je? Een minimum spanning tree maken?

[Soultaker]

Knakker schreef op vrijdag 18 november 2005 @ 00:38:
Het klopt dat de kosten van de elementen onafhankelijk zijn van de cycles waartoe ze behoren. Wel is het natuurlijk zo dat als twee elementen in dezelfde cycle terecht komen, de kosten tussen die twee irrelevant zijn geworden.

Uiteraard, maar die kun je bij het samenvoegen vrij makkelijk weggooien. (Of lekker laten staan; daar kom ik later op terug.)

Maar ga je me nou vertellen dat datgene waar ik láng naar gezocht heb ook daadwerkelijk bestaat? Neemt zo'n 'map' niet meer geheugen in dan het aantal elementen dat erin zitten (geheugen is écht een issue bij grote netwerken), en is de random access ook efficient? Bij een list bijvoorbeeld moet je vanaf het begin de list doorlopen om een element te vinden, dus daar heb ik niks aan.

Het is een beetje implementatieafhankelijk, maar ik ga er doorgaans vanuit dat een vector gemiddeld ~1.5 keer zoveel geheugen alloceert als z'n elementen; een vector<X> zal dus ongeveer 1.5*sizeof(X) bytes innemen. Een map is meestal geïmplementeerd als een soort semi-gebalanceerde binaire boom (vaak een AVL of red&black tree) en heeft dan twee pointers en een extra byte ofzo extra informatie. Op een 32-bits processor zou ik uitgaan van maximaal 16 bytes per element extra (hangt er vanaf hoe het uitkomt met alignment); dat is dus niet zo efficiënt als het datatype dat je er in opslaat klein is. (Verder komt er nog meer overhead bij als je de standaard C++ allocator gebruikt.)

Qua tijd doet een vector look-up in O(1) en insertion in O(N) (behalve aan het einde); een map heeft O(log N) voor beide operaties. Als je dus veel look-ups doet én je voegt veel elementen in het midden toe (door het samenvoegen van de cykels) dan is de vector dus gemiddeld nog iets van O(N) en dan is de kans aanwezig dat de map het beter doet. Of dat echt zo is hangt af van een aantal factoren waaronder de verhouding tussen look-ups en insertions/deletions in het midden.

Ik heb overigens te maken met vier elementen per twee cycles in plaats van twee, alleen omdat dat verder niet relevant was (dacht ik) heb ik dat weggelaten; ik neem aan dat ik nog steeds gebruik kan maken van zo'n 'map'? Hoe werkt dat?

Hoe bedoel je die vier elementen; bedoel je dat je twee elementen uit de ene cykel vergelijkt met twee elementen uit de andere cykel? (Met elementen dacht ik aan de 'dingen' die op je pad liggen; die nu dus in een vector die een cykel representeert worden opgeslagen.)

De elementen zijn genummerd, gewoon van 0 tot 2634 (bijvoorbeeld).

De vraag is meer hoe groot je cykels in het begin zijn. Als je begint met allemaal 1-cykels en vanaf daar gaat opbouwen, dan zul je in het begin toch álle kosten moeten uitrekenen en dan kun je net zo goed een kostenmatrix maken.

Sowieso lijkt me gaandeweg geheugen vrijgeven niet zo'n zinnig idee. Als ik het goed begrijp heb je in het begin veel geheugen nodig en voeg je later heel weinig toe. Dan kun je beter je berekening afmaken en dan het geheugen in één keer vrijgeven dan dat je processortijd gaat gebruiken om je oude data op te ruimen. (Denk bijvoorbeeld aan SQL databases: die gaan ook niet elke keer vrijgekomen data pages opruimen, omdat dat traag en relatief zinloos zou zijn.)

Het lijkt me al met al een typische geheugen-tegen-processortijd trade-off. Wat je in zo'n situatie het beste kan doen hangt nogal van je invoer af en je testresultaten in de praktijk. Duurt de berekening te lang, maar heb je nog geheugen over? Dan gewoon een map gebruiken. Passen de gewenste test sets niet in het geheugen, maar zou je ze anders wel door kunnen rekenen? Dan zijn compressietrucs zoals met die vectors misschien wél zinnig.

[ Voor 6% gewijzigd door Soultaker op 18-11-2005 04:06 ]

[.oisyn]

Soultaker schreef op vrijdag 18 november 2005 @ 04:03:
Qua tijd doet een vector look-up in O(1) en insertion in O(N) (behalve aan het einde);

En vergeet niet dat bij een vector<vector<T>> van elke vector een copy wordt gemaakt op het moment dat de interne buffer niet lang genoeg is bij insertion aan het eind, wat dus leidt tot N geheugenallocaties en -deallocaties, plus nog N copies van M elementen in die interne vectoren.

[ Voor 14% gewijzigd door .oisyn op 18-11-2005 11:23 ]

[Knakker]

Je wil twee vectoren samenvoegen, op basis van een bepaalde ordening. Wat ik niet kan opmaken uit je post is of C1 en C2 ook al gesorteerd zijn, maar omdat je de ene vector wil 'mergen' met andere ga ik er vanuit dat dat zo is. In dat geval kun je beide vectoren 'ritsen'.

Nee, ze zijn niet geordend; sterker nog, de volgorde is compleet willekeurig en vooraf niet te bepalen. Maar toch bedankt

Overigens ben ik wel benieuwd waar je precies mee bezig bent. Je werkt met cykels, maar wat doe je? Een minimum spanning tree maken?

Ik heb het in eerste instantie weggelaten omdat ik dacht dat het in feite niet ter zake doet, maar ik merk dat context toch belangrijk is. En omdat je ernaar vraagt, bij deze

Stel, je hebt een netwerk met N nodes. Tussen elk paar nodes zitten bi-directionele verbindingswegen, arcs genaamd. Aan elk van deze arcs zijn kosten verbonden, en die zijn te vinden in de kostenmatrix C. Verder is het netwerkasymmetrisch, hetgeen in dit geval betekent dat C(i, j) ongelijk is aan C(j, i) voor elke i ongelijk aan j.

Mijn probleem is nu als volgt: gegeven het netwerk van verbindingswegen, wat is de snelste route, zodanig dat ik alle nodes exact éénmaal bezoek, alvorens terug te keren naar mijn startpositie? Dit staat bekend als het handelsreizigersprobleem (TSP); een eeuwenoud probleem dat (toegepast) wiskundigen al even zoveel eeuwen bezig houdt. Voor dit probleem bestaat geen oplossing.

Verwant aan het TSP is een ander probleem, het Linear Assignment Problem (LAP). Het LAP is het probleem van het toewijzen van taken aan machines, zodanig dat de totale verwerkingstijd minimaal is. Voor dit probleem bestaat wél een oplossing, wat ook voor matrices van 3000 bij 3000 binnen een paar seconden berekend kan worden.

Aan de hand van een klein (triviaal) voorbeeldje zal ik de link tussen LAP en TSP verduidelijken, en uitleggen waar ik mee bezig ben. Stel, ik heb de volgende matrix:

code:

Taak         1  2  3  4  5

Machine 1    9  1  9  9  9
Machine 2    9  9  1  9  9
Machine 3    1  9  9  4  9
Machine 4    9  9  9  9  1
Machine 5    4  9  9  1  9

Er zijn 5 taken, en elke machine kan elke taak uitvoeren tegen een bepaalde 'kost'. Het is duidelijk dat machine 1 taak 2 moet doen, 2 moet 3 doen, 3 moet 1 doen, 4 moet 5 doen en 5 moet 4 doen. Dit is de optimale toewijzing.

Goed, nu terug naar het TSP. Ik zei dat voor het TSP geen algemene oplossing bestaat dat in 'polynomial-time' uitgerekend kan worden. Wel bestaan er benaderingsmethodes, heuristieken genaamd, die binnen korte tijd een oplossing genereren (simpel voorbeeldje is Nearest Neighbour). Enkele van die heuristieken zijn gepaseerd op het 'patchen' van cycles voortkomende uit de LAP-oplossing. Plaatsen we de bovenstaande oplossing voor het LAP in de context van het TSP, dan zien we dat we 2 cycles hebben: 1 - 2 - 3 - 1 en 4 - 5 - 4. Door uit elk van deze twee cycles één arc te verwijderen - (p, q) en (r, s) - en twee anderen toe te voegen - (p, s) en (r, q) - kunnen we ze 'patchen', ofwel aan elkaar plakken. Bijvoorbeeld (2, 3) en (4, 5), resulterende in 1 - 2 - 5 - 4 - 3 - 1. De optimale patching is trouwens (3, 1) en (5, 4), resulterende in 1 - 2 - 3 - 4 - 5 - 1.

Je voelt al aankomen dat ik dus exact met dit laatste bezig ben. Door aan de hand van een bepaald criterium te bepalen hoe en welke cycles je één voor één aan elkaar plakt, kun je dus een (behoorlijke) oplossing genereren. De eerste stap van mijn code is dus het vertalen van de LAP oplossing naar reeksen die de cycles bevatten, om die vervolgens aan elkaar te plakken.

Hoe bedoel je die vier elementen?

Uit mijn verhaal hierboven kun je opmaken dat ik dus niet twee nodes patch, maar twee arcs. Twee arcs zijn gerelateerd aan vier nodes. Omdat ik echter een aparte vector heb met alle cycles, bepaal ik aan de hand daarvan welke node door een andere wordt opgevolgd en hoef ik dat dus niet op te slaan.

Qua tijd doet een vector look-up in O(1) en insertion in O(N) (behalve aan het einde); een map heeft O(log N) voor beide operaties. Als je dus veel look-ups doet én je voegt veel elementen in het midden toe (door het samenvoegen van de cykels) dan is de vector dus gemiddeld nog iets van O(N) en dan is de kans aanwezig dat de map het beter doet. Of dat echt zo is hangt af van een aantal factoren waaronder de verhouding tussen look-ups en insertions/deletions in het midden.

Okee. Maar als ik hier gebruik van kan maken zal dit een énorme tijdswinst opleveren, omdat de combinaties van arcs op zichzelf niet veranderen. Als ik twee cycles patch worden er twee arcs verwijderd en twee toegevoegd; ik moet de kosten tussen de twee toegevoegde en alle andere arcs in de overige cycles berekenen en die aan de mapping toevoegen.

De reden dat ik in mijn implementatie alles moet verschuiven is omdat de volgorde van de elementen PatchCosts dezelfde is als in Cycles. Als ik simpelweg aan ze kan refereren aan de hand van de arcs (of startnodes, ik kan de eindnodes opzoeken in Cycles), hoef ik ze helemaal niet te verschuiven! Ik hoef alleen de elementen in Cycles te verschuiven en PatchCosts kan ik met rust laten.

De vraag is meer hoe groot je cykels in het begin zijn. Als je begint met allemaal 1-cykels en vanaf daar gaat opbouwen, dan zul je in het begin toch álle kosten moeten uitrekenen en dan kun je net zo goed een kostenmatrix maken.

Dat klopt. Maar je weet niet hoe groot de cycles zijn; dat hangt helemaal van het type netwerk af. Sommige type netwerken genereren stapels cycles met lengte twee, anderen maar heel weinig. Eén van 's wereld's beste heuristieken, genaamd 'Contract Or Patch', breekt eerst alle cycles met kleine lengte op door de duurste arc te verwijderen en trekt ze vervolgens samen (contraction); hoe dat werkt is vrij ingewikkeld, maar geeft aan dat men dus inderdaad begrijpt dat veel kleine cycles niet alleen een geheugenintensief, maar ook bijzonder rekenintensief zijn.

Ik dacht dat mijn enige alternatief op mijn huidige aanpak was dat ik inderdaad een extra matrix aan moest maken en dat is iets dat ik niet wou.

Ik ben het met je eens dat je normaalgesproken tussentijds niet dingen moet gaan verwijderen. Ik móest alleen wel, omdat ik dus met die specifieke volgorde te maken had. Als ik van die specifieke volgorde af ben, laat ik ze lekker staan.

Ik ga me nu even verdiepen in die mappings; in de tussentijd zijn alle verdere ideeën, tips en trucks natuurlijk welkom. In ieder geval alvast bedankt voor de reacties tot dusver!

[ Voor 4% gewijzigd door Knakker op 18-11-2005 12:19 ]

[Soultaker]

Aha, gewoon een TSP-algoritme; moest je daar nu zo geheimzinnig over doen.

Het lijkt mij het makkelijkst programmeren als je gewoon die kostenmatrix in je geheugen kunt houden. Tot de 5000 elementen moet dat geen probleem zijn (als je kosten in een double zitten, dan komt het nog maar op 8*5000*5000 ~ 190 MB).

Ik vraag me nu toch af hoe je ueberhaupt die eerste cykels opbouwt, zonder kostenmatrix te gebruiken? Verder vraag ik me af wat de complexiteit van je huidige algoritme is; het zal minimaal O(N²) zijn, maar je huidige implementatie is veel complexer (omdat je allerlei data gaat zitten schuiven) waardoor je de 5000 elementen toch al niet haalt. (Echt een typische rekentijd/geheugengebruik trade-off. )

[Knakker]

Aha, gewoon een TSP-algoritme; moest je daar nu zo geheimzinnig over doen.

Het zou je verbazen hoeveel mensen niet weten wat dat is, al had ik natuurlijk kunnen bedenken dat in P&W dat percentage erg laag is

Het lijkt mij het makkelijkst programmeren als je gewoon die kostenmatrix in je geheugen kunt houden. Tot de 5000 elementen moet dat geen probleem zijn (als je kosten in een double zitten, dan komt het nog maar op 8*5000*5000 ~ 190 MB).

De kostenmatrix blijft de hele tijd in mijn geheugen, dat klopt. Alleen ik wil dus geen tweede maken, zeg maar.

Ik vraag me nu toch af hoe je ueberhaupt die eerste cykels opbouwt, zonder kostenmatrix te gebruiken?

Ik analyseer de oplossing van het LAP. Dat is een vector met dimensie N, die voor elke vertex aangeeft wat de volgende vertex is. Door gewoon de hele vector de doorlopen kun je heel makkelijk een vector opbouwen waarin alle cycles opgeslagen zijn. Ik doe het waarschijnlijk zelfs nog omslachtig :

code:

    for (I = 0; I < N; I++) {
        if (RowChecked[I] == 1) { continue; }
        Cycles.resize(Cycles.size()+1);
        StartVertex = I; CurrentVertex = I; 
        while (1) {
              RowChecked[CurrentVertex] = 1;  
              Cycles[Cycles.size()-1].push_back(CurrentVertex);           
              CurrentVertex = APSolution[CurrentVertex];
              if (CurrentVertex == StartVertex) {
                 Cycles[Cycles.size()-1].push_back(StartVertex);
                 break;          
                 }
              }
        }

Verder vraag ik me af wat de complexiteit van je huidige algoritme is; het zal minimaal O(N²) zijn, maar je huidige implementatie is veel complexer (omdat je allerlei data gaat zitten schuiven) waardoor je de 5000 elementen toch al niet haalt. (Echt een typische rekentijd/geheugengebruik trade-off. )

Als ik de implementatie gereed heb, zal ik dat eens bepalen.

Ik ben nu bezig de implementatie om te vormen door maps te gebruiken; het gaat me lukken

[ Voor 5% gewijzigd door Knakker op 18-11-2005 16:46 ]

[Soultaker]

Als je inderdaad echt het assignment problem oplost om die cykels te vinden, dan is dat sowieso al minimaal een O(N³) algoritme en dan is volgens mij het mergen van die cykels verhoudingsgewijs piece of cake.

[Knakker]

Als je inderdaad echt het assignment problem oplost om die cykels te vinden, dan is dat sowieso al minimaal een O(N³) algoritme en dan is volgens mij het mergen van die cykels verhoudingsgewijs piece of cake.

Je hebt gelijk, minimaal O(n³). Als je bedenkt dat mijn implementatie nog vele malen trager was dan het oplossen van het LAP alleen, dan is er iets góed fout

[Knakker]

Okee, ik ben praktisch klaar. Ik heb nog één probleem (technisch) een theoretische vraag.

Eerst het probleem waar de fout niet van snap (af en toe een segmentation fault). Ik heb een map genaamd PC van type PC_m (map<pair<int, int>, int>) en een vector LPC van type vector<vector<vector<PC_m::iterator> > >. Idee achter de triple vector is dat voor elke combinatie van cycles bijhoudt wat de twee laagste waarden in PC zijn.

Goed, nu patch ik op een gegeven moment twee cycles aan elkaar; dat lukt allemaal, updaten van de relevante vectoren gaat allemaal soepel. Stel dat ik iets van 10 cycles heb en ik bijvoorbeeld cycle 3 uit LPC wil verwijderen, dus ik doe (bedenk dat tweede dimensie relatief is aan de eerste):

code:

for (I = 0; I < 3; ++I) { LPC[I].erase(LPC[I].begin()+3-I-1); }

Ik weet zéker dat de LPC[I]'s bestaan en dat de dimensies daarvan groot genoeg zijn (geverifieerd met een cout << LPC[I].size(); ). Toch resulteert dit (soms) in een segmentation fault. Wat is mijn probleem?


Verder:
De vector LPC houdt van elke twee cycles de twee laagste patchcosts bij (heb ik nodig voor mn patchingcriterium). Bij het patchen van twee cycles verwijder ik echter twee arcs; het is heel goed mogelijk dat een van de twee kleinste waarden in een andere combinatie van cycles (waarbij één een gepatchte is) diezelfde arc betreft. Nou verwijder ik niets uit de mapping (waarom zou ik?) dus de iterator is nog steeds geldig, maar ik moet de iterator wel naar een nieuwe arc verwijzen die wél in de cycle voorkomt.

Op dit moment doe ik dat door alle mogelijke combinaties van arcs binnen die twee cycles af te lopen, waarbij ik dus (lengte cycle 1 * lengte cycle 2) keer een .find operatie moet doen binnen de mapping. Dat kost tijd; als je bedenkt dat je op een gegeven moment cycles van lengte 1000 hebt dan is dat gewoon heel vervelend

Nu kan ik in plaats van de kleinste twee de kleinste drie waardes bijhouden, maar zoiets maakt natuurlijk helemaal niets uit. Ook is de cycles 'sorten' niet een optie, dat is nog tijdsrovender - de vector Cycles bestaat namelijk alleen uit een rijtje vertices waarbij ik met een combinatie van twee opeenvolgende vertices de kosten op kan zoeken in de mapping.

Iemand die er een licht op kan schijnen?

[ Voor 3% gewijzigd door Knakker op 23-11-2005 18:21 ]

[Soultaker]

Knakker schreef op dinsdag 22 november 2005 @ 22:59:

code:

for (I = 0; I < 3; ++I) { LPC[I].erase(LPC[I].begin()+3-I-1); }

Ik weet zéker dat de LPC[I]'s bestaan en dat de dimensies daarvan groot genoeg zijn (geverifieerd met een cout << LPC[I].size(); ). Toch resulteert dit (soms) in een segmentation fault. Wat is mijn probleem?

Die code ziet er wel heel wazig uit. Je wist achtereenvolgens het derde, tweede en eerste element. Ik kan niet verklaren waarom het zou crashen (want het lijkt me correct, aangenomen dat LPC[I].size() >= 3), maar ik zou dan gewoon [i]LPC[i].erase(LPC[i].begin(), LPC.begin()+3) doen om ze in één keer alledrie te verwijderen. Dat neemt niet weg dat het inefficiënt blijft om aan het einde te verwijderen.

Om de seg fault te kunnen achterhalen heb ik meer code (en voorbeelddata) nodig. Heb je zelf al eens een stacktrace bekeken als 'ie crasht?

Op dit moment doe ik dat door alle mogelijke combinaties van arcs binnen die twee cycles af te lopen, waarbij ik dus (lengte cycle 1 * lengte cycle 2) keer een .find operatie moet doen binnen de mapping. Dat kost tijd; als je bedenkt dat je op een gegeven moment cycles van lengte 1000 hebt dan is dat gewoon heel vervelend

Nu kan ik in plaats van de kleinste twee de kleinste drie waardes bijhouden, maar zoiets maakt natuurlijk helemaal niets uit. Ook is de cycles 'sorten' niet een optie, dat is nog tijdsrovender - de vector Cycles bestaat namelijk alleen uit een rijtje vertices waarbij ik met een combinatie van twee opeenvolgende vertices de kosten op kan zoeken in de mapping.

Hier ga ik als ik morgen wat wakkerder ben iets dieper over na denken. Ik heb namelijk het vage gevoel dat het veel simpeler moet kunnen.

Wat is je patchingscriterium trouwens? Toch gewoon: hoe kan ik twee cycles patchen zo dat de totale kosten zo min mogelijk stijgen? (Dat betekend dus als je een cykel (a,b,c) en (d,e,f) hebt en je verbind ze bij a resp. d, de kosten gelijk zijn aan: C(a,d) + C(e,b) - C(a,b) - C(d,e)).

edit:
Ik bedenk me net dat je cykels ook kruislings kunt patchen trouwens; hou je daar al rekening mee?
Dit is waarschijnlijk niet aan de orde, omdat het een asymmetrische kostenmatrix is (dus je kunt niet zomaar alle paden omdraaien).

[ Voor 5% gewijzigd door Soultaker op 24-11-2005 18:29 ]

[Soultaker]

Ok, een voorstel voor een algoritme in O(N³) tijd en O(N²) ruimte. Dat lijkt me redelijk, omdat invoer tot ongeveer 10.000 punten dan een paar honderd megabyte ruimte kost en de berekening enkele (tientallen?) minuten duurt.

Uitgaande van N punten, heb je een NxN kostenmatrix C (C[i][j] zijn de kosten van een pad van i naar j), een opvolgerlijst S (S[n] is de opvolger van punt n). Verder heb je een union-find structuur waarin je registreert welke punten tot dezelfde cykel behoren.

Stap 1: je begint met een aantal cykels (die zijn afgeleid uit de oplossing van het assignment problem) en dus moet je S en de union-find structuur initialiseren. (Voor een cykel 1,2,3 geldt bv. dat S[1]==2, S[2]==3 en S[3]==1). Dat is makkelijk genoeg.

Stap 2: bekijk elk paar van punten (a,b); als a en b deel uitmaken van verschilende cykels, dan kun je eenvoudig uitrekenen (met behulp van de kostenmatrix en de opvolgers van a en b) wat het kost om de cykels bij die punten te patchen. Deze stap kost O(N²) tijd.

Stap 3: voer de goedkoopste patch uit die je in stap 2 hebt gevonden, door de successors van a en b aan te passen. Zolang er meer dan één cykel over zijn herhaal je stap 2; dit zal maximaal N keer voorkomen.

Volgens mij is dit in de basis heel simpel en heb je er helemaal geen ingewikkelde datastructuren zoals driedimensionale vectoren met map-iterators voor nodig.

[ Voor 9% gewijzigd door Soultaker op 24-11-2005 18:34 ]

[Knakker]

Soultaker, bedankt voor je hulp zover. Het probleem is alleen niet dat ik niet een simpelere manier kan verzinnen om een dergelijke tour te construeren.

Als onderdeel van mijn afstudeerscriptie heb een heuristiek ontworpen op basis van GKS, Greedy Karp-Steele Patching; ik ben hieraan gebonden. Een hoop academici mijden GKS alleen omdat het schrijven van een efficiente implementatie erg lastig is - althans, voor niet-informatici zoals ik

Voordat het iteratieproces begint, berekent GKS alle mogelijke patchcombinaties. In het iteratieproces wordt iedere keer de patching met de laagste kosten gekozen, worden de cycles aan elkaar gepatcht en worden de patchkosten geüpdate (alternatief voor dit updaten is het iedere keer opnieuw berekenen van alle mogelijke kosten).

Als ik staat ben om zo'n efficiente implementatie wél te schrijven, dan is GKS superieur aan andere patchingalgoritmes, simpelweg omdat ik over volledige informatie beschik (je bekijkt alle mogelijke combinaties). Daarom wil ik het toch proberen.

Mijn heuristiek is TBGKS; TB staat voor 'Tolerance Based'. In plaats van de patching met de laagste kosten te kiezen, kies ik degene waarvoor zijn tolerantie het hoogst is. In dit geval is tolerantie gedefinieerd als het verschil tussen de kosten van de twee goedkoopste patchings. Ik kies dus de patching met de hoogste 'oppurtunity cost', om het maar even in economische termen te gooien. De redenering waarom dit tot een beter resultaat zou kunnen leiden in bepaalde gevallen laat ik achterwege omdat het er niet toe doet; geloof me als ik zeg dat dat gefundeerd is - ik probeer dus niet 'zomaar iets'.

Een getallenvoorbeeldje.

Stel dat ik mijn huidige oplossing drie cycles heb: 1 - 2 - 3 - 1, 4 - 5 - 6 - 4 en 7 - 8 - 7. De patchcosts tussen alle mogelijke combinaties van arcs zijn gegeven door:



De goedkoopste patchings voor cycles 1 & 2 zijn (2,3) en (5,6) en (2,3) en (6,4); bieden kosten 10. De tolerantie van de goedkoopste patching is 10 - 10 = 0. Voor cycles 1 & 3 is dit (3,1) en (8,7), en (1,2) en (7,8), respectievelijk 4 en 11. De tolerantie van (3,1) en (8,7) is dus 11 - 4 = 7. Idem voor cycles 2 & 3, tolerantie van 12 - 10 = 2.

Ik kies er dus voor om (3,1) en (8,7) te verwijderen en cycles 1 & 3 aan elkaar te plakken; deze heeft de hoogste tolerantie. Ik heb nu cycles 1 - 2 - 3 - 7 - 8 - 1 en 4 - 5 - 6 - 4. De mogelijke patchcosts zijn nu:



Je ziet dat er een 6 nieuwe combinaties zijn bijgekomen. De overigen hoef ik niet opnieuw te berekenen, dat heb ik immers al eens gedaan. Omdat er nog maar 2 cycles over zijn, kies ik de patching met de laagste kosten, en krijg ik uiteindelijk 1 - 2 - 3 - 7 - 8 - 6 - 4 - 5 - 1.

De rekencomplexiteit die hier bij komt kijken als je 500 cycles hebt, hoef ik niet uit te leggen.

Laat je licht hier maar op schijnen, en alvast bedankt

[ Voor 13% gewijzigd door Knakker op 24-11-2005 20:11 ]

[Soultaker]

Die achtergrondinformatie vind ik sowieso wel leuk.

Knakker schreef op donderdag 24 november 2005 @ 20:05:
Mijn heuristiek is TBGKS; TB staat voor 'Tolerance Based'. In plaats van de patching met de laagste kosten te kiezen, kies ik degene waarvoor zijn tolerantie het hoogst is. In dit geval is tolerantie gedefinieerd als het verschil tussen de kosten van de twee goedkoopste patchings. [..] De redenering waarom dit tot een beter resultaat zou kunnen leiden in bepaalde gevallen laat ik achterwege omdat het er niet toe doet; geloof me als ik zeg dat dat gefundeerd is - ik probeer dus niet 'zomaar iets'.

Ik kan me er intuïtief wel iets bij voorstellen: als je twee even goedkope opties hebt om te patchen, dan kun je daar later ook nog wel één nemen, maar als het verschil tussen de goedkoopste en op-één-na goedkoopste groot is, dan wil je graag nu de goedkoopste doen voordat 'ie niet meer mogelijk is (het is immers een greedy algoritme dus je kunt later niet terug gaan) en je gedwongen bent de dure te kiezen.

De rekencomplexiteit die hier bij komt kijken als je 500 cycles hebt, hoef ik niet uit te leggen.

Eigenlijk denk ik dat de complexiteit van stap 2 in het algoritme wat ik hierboven beschreef hetzelfde blijft: O(N³). Je kunt dat doen door bij het vergelijken van paren per cykel bij te houden wat de laagste gevonden waarde is, en wat de huidige tolerantie is. Als je dan een nieuwe waarde vind kun je de tolerantie of het minimum bijstellen. Bij het bijstellen van de tolerantie kun je gelijk de beste (tot nu toe gevonden)

Dan kun je in stap 3 direct patchen en de boel herhalen. Dat blijft O(N³) en dat lijkt me voor aantallen als 500 cykels snel zat. (Maar er zijn wel wat optimalisaties denkbaar; al denk ik dat je dat altijd extra geheugen gaat kosten, bijvoorbeeld door een priority queue te maken van de nog te beschouwen punten kun je waarschijnlijk wel in de buurt van O(N²) komen.)

De vraag is dus: is O(N³) (met een vrij lage constante) goed genoeg - neem ook mee dat je al een, waarschijnlijke tragere, O(N³) assignment stap hebt - of wil je het nog sneller krijgen? Dan zou ik als ik jouw was sowieso eerst heel goed over de werking van je algoritme gaan nadenken voordat je 'm daadwerkelijke schrijft, want als ik zie wat je allemaal voor ingewikkelde datastructuren gebruikt dan kan ik me moeilijk voorstellen dat 'ie efficiënter is dan een simpele aanpak.

[ Voor 16% gewijzigd door Soultaker op 25-11-2005 00:10 ]

[Knakker]

Ik kan me er intuïtief wel iets bij voorstellen: als je twee even goedkope opties hebt om te patchen, dan kun je daar later ook nog wel één nemen, maar als het verschil tussen de goedkoopste en op-één-na goedkoopste groot is, dan wil je graag nu de goedkoopste doen voordat 'ie niet meer mogelijk is (het is immers een greedy algoritme dus je kunt later niet terug gaan) en je gedwongen bent de dure te kiezen.

Precies; dat is ook de reden dat mijn 'simpele' versie (zonder al dat moeilijke gedoe ) van het algoritme heeft aangetoond dat TBGKS slechts voor een beperkt aantal typen netwerken een verbetering oplevert t.o.v. GKS. Ik ga nu eens kijken naar selectie op basis van tolerance/cost; als je nog andere suggesties hebt: laat gerust komen!

Eigenlijk denk ik dat de complexiteit van stap 2 in het algoritme wat ik hierboven beschreef hetzelfde blijft: O(N³). Je kunt dat doen door bij het vergelijken van paren per cykel bij te houden wat de laagste gevonden waarde is, en wat de huidige tolerantie is. Als je dan een nieuwe waarde vind kun je de tolerantie of het minimum bijstellen. Bij het bijstellen van de tolerantie kun je gelijk de beste (tot nu toe gevonden).

Precies; de vraag is dus alleen hóe ik dat het beste bij kan houden.

De vraag is dus: is O(N³) (met een vrij lage constante) goed genoeg - neem ook mee dat je al een, waarschijnlijke tragere, O(N³) assignment stap hebt - of wil je het nog sneller krijgen?

Ik gebruik de AP-oplossing van Jonker & Volgenant (UvA, 1996); deze is theoretisch O(N³) maar in de praktijk (veel) sneller dan het Hongaarse algoritme. Ik gebruik gewoon de C++ implementatie van Jonker (beetje 'black box'-idee dus).

Dan zou ik als ik jouw was sowieso eerst heel goed over de werking van je algoritme gaan nadenken voordat je 'm daadwerkelijke schrijft, want als ik zie wat je allemaal voor ingewikkelde datastructuren gebruikt dan kan ik me moeilijk voorstellen dat 'ie efficiënter is dan een simpele aanpak.

Ik weet precies hoe ik het wil hebben; ik ben alleen niet in staat dat wat ik in mijn hoofd heb te vertalen naar een efficiente C++ implementatie. En je hebt absoluut gelijk dat wat ik aan het produceren ben veel trager kan zijn dan de simpele, alles overnieuw berekenende, aanpak.

Ik moet er sowieso over nadenken over het schrijven van de 'meest efficiente' implementatie wel mijn prioriteit is; het gaat uiteindelijk om het testen kwaliteit van de oplossing. In beginsel is het maken van een efficiente implementatie meer een taak voor informatici, die waarschijnlijk een veel betere implementatie in veel minder tijd kunnen maken.

Maar toch, advies is altijd welkom

[Soultaker]

Knakker schreef op vrijdag 25 november 2005 @ 15:37:
Precies; de vraag is dus alleen hóe ik dat het beste bij kan houden.

Hmm, ik dacht dat ik een redelijk overzichtelijk algoritme had geschetst, maar óf ik moet 'm nog wat nader toelichten, óf je wil gewoon liever je eigen implementatie bijschaven in plaats van opnieuw te beginnen (waar ik me ook wel iets bij kan voorstellen). In het tweede geval kan ik je niet echt helpen, ben ik bang.

Ik gebruik de AP-oplossing van Jonker & Volgenant (UvA, 1996); deze is theoretisch O(N³) maar in de praktijk (veel) sneller dan het Hongaarse algoritme. Ik gebruik gewoon de C++ implementatie van Jonker (beetje 'black box'-idee dus).

Hmm, moet ik die maar eens opzoeken. Ik heb wel een implementatie van de Hongaarse methode maar die is eigenlijk gewoon kut om te programmeren. Ik ben benieuwd of het algoritme dat jij noemt ook 'makkelijker' is.

Ik weet precies hoe ik het wil hebben; ik ben alleen niet in staat dat wat ik in mijn hoofd heb te vertalen naar een efficiente C++ implementatie. En je hebt absoluut gelijk dat wat ik aan het produceren ben veel trager kan zijn dan de simpele, alles overnieuw berekenende, aanpak.

Ik moet er sowieso over nadenken over het schrijven van de 'meest efficiente' implementatie wel mijn prioriteit is; het gaat uiteindelijk om het testen kwaliteit van de oplossing. In beginsel is het maken van een efficiente implementatie meer een taak voor informatici, die waarschijnlijk een veel betere implementatie in veel minder tijd kunnen maken.

Inderdaad; daar hebben wiskundigen wel vaker moeite mee (niet omdat programmeren te ingewikkeld voor ze is, maar ze een heleboel ervaring missen). Als het je alleen om de kwaliteit van de oplossingen gaat zou ik inderdaad gewoon een ad-hoc methode implementeren (dan maar wat langer wachten) en de 'echte' implementatie na publicatie van je algoritme aan iemand anders overlaten.

In de informatica telt (zeker voor heuristieke algoritmen) de efficiëntie in de praktijk ook wel mee, maar je kunt niet alles tegelijk doen.

[ Voor 8% gewijzigd door Soultaker op 25-11-2005 16:24 ]

[Knakker]

Hmm, ik dacht dat ik een redelijk overzichtelijk algoritme had geschetst, maar óf ik moet 'm nog wat nader toelichten, óf je wil gewoon liever je eigen implementatie bijschaven in plaats van opnieuw te beginnen (waar ik me ook wel iets bij kan voorstellen). In het tweede geval kan ik je niet echt helpen, ben ik bang.

Sorry, ik had mijn reactie iets uitgebreider moeten maken; de aanpak die jij beschrijft is de aanpak die ik volg op dit moment - per combinatie bijhouden en bij een verandering aanpassen.

Het niet weten hóe slaat erop hoe ik dat implementatie-technisch gezien moet het beste kan realiseren.

[ Voor 7% gewijzigd door Knakker op 25-11-2005 16:50 ]

[Soultaker]

In pseudo-code zat ik aan zoiets te denken (dit is mijn 'stap 2'), hoewel ik niet zeker weet of mijn kostenberekening enzo klopt:

code:

min_kost[x]      = oneindig
min_patch[x]     = -
tolerantie[x]    = -

Voor elk combinatie van punten (a,b):
  Als cykel(a) <> cykel(b):
    c = C(a, S[b]) + C(b, S[a]) - C(a, S[a]) - C(b, S[b])
    Als c < min_kost[cykel(a)]:
      tolerantie[cykel(a)] = min_kost[cykel(a)] - c
      min_kost  [cykel(a)] = c
      min_patch [cykel(a)] = (a,b)
    Als c - min_kost[cykel(a)] < tolerantie[cykel(a)]:
      tolerantie[cykel(a)] = c - min_kost[cykel(a)]

gekozen_patch = min_patch[x] voor x zo dat tolerantie[x] maximaal is

Daarvoor is het nodig dat je een cykel kunt identificeren (dat kan vrij makkelijk met de union-find structuur) en de drie variabelen min_kost, min_patch en tolerantie zijn gewoon vectors (van respectievelijk int, pair<int,int> en int).