[C] Uitvoeren van if-statements in verschillende volgorden

[NinjaTuna]

Hi medetweakers,

Voor een project voor de studie heb ik een stukje code dat bestaat uit 4 if-statements achter elkaar:

C:

if (foobar1)
 foo = bar1;
if (foobar2 && !foo)
 foo = bar2;
if (foobar3 && !foo)
 foo = bar3;
if (foobar4 && !foo)
 foo = bar4;

Zoiets dus, nou werkt dat allemaal leuk en aardig, maar het zou voor mijn toepassing efficiënt zijn als ik de volgorde van die checks (er krijgt er dan één prioriteit, die komt bovenaan) aan kan passen afhankelijk van een variabele.
Nu is de enige oplossing die ik kan bedenken het vier keer herhalen van de vier if-statements, met elke keer een andere bovenaan, maar dat lijkt me niet bijster efficiënt en er zouden naar mijn idee toch betere oplossingen moeten zijn.

Iemand ideeën?

[Gropah]

Het hangt heel erg af van de context. Waarschijnlijk kun je het beste kijken of je de dat niet zo kunt forceren dat het altijd op 1 manier kan?

Anders misschien een switchcase binnen een while proberen? Niet de mooiste oplossing, maar waarschijnlijk efficienter dan wat er nu staat.

[Soultaker]

Als die foobar expressies kostbaar zijn (en ik neem aan dat dat zo is, want waar hebben we het anders over?) moet je om te beginnen ze niet allemaal uitvoeren ongeacht welke precies matcht. Als dat niet kan (omdat de side effects relevant zijn) dan valt er ook weinig te optimaliseren, lijkt me.

[Radiant]

Als !foo goedkoper is kan je die beter naar voren halen, aangezien het een &&-operatie is zal hij bij het falen van de eerste expressie de tweede al niet meer gaan controleren.

Verder ben je met embedded software bezig denk ik dat je zo tijdkritisch zit? Misschien is het handiger om het hele probleem even uit te leggen.

[NinjaTuna]

Dan geef ik je een stukje context

Het gaat hier om een rechthoekig m bij n grid, bestaande uit nodes. Het idee is dat je een route vindt tussen twee bepaalde nodes, dit doe ik met Lee's algorithm. Het komt er nu op neer dat het programma bij elke node waar hij aan komt checkt of ten eerste naar links kan, daarna rechts, daarna boven, en daarna onder. Als hij naar links kan, zal hij dus altijd naar links gaan.

Als we geen obstakels toevoegen aan de grid levert die geen probleem op, de route zal dan eerst naar een rand (eerst links, als dat niet kan rechts, etc) lopen, om vervolgens langs de randen naar de eindbestemming te komen. De route loopt dan gewoon in een hoek.

Plaatsen we echter een obstakel op die hoek dan gebeuren er andere dingen; de eerst volgende richting waar hij dan naar uit kan wijken is naar onder, en dat gebeurt dan ook. Echter daarna zal hij weer gewoon naar links gaan, omdat het kan.

Ideaal zou echter zijn als hij het in zo recht mogelijke lijnen (een robot doet langer over bochten maken dan rechtdoorrijden) zou doen, dit betekent dat ik een variabele "direction" wil gebruiken die in het vorige geval equivalent zou worden aan "bottom" oid, waarna het programma eerst controleert of hij in die richting verder kan. Dit levert een veel rechtere route op, die dus theoretisch sneller afgelegd kan worden.


Links de route zonder obstakels, deze kent maar één bocht; daarnaast de route zoals hij hem nu uitrekent (5 bochten) en rechts de route die het snelst af te leggen zou moeten zijn in de echte wereld (=optimaal: 2 bochten).

[ Voor 6% gewijzigd door NinjaTuna op 20-02-2013 17:41 ]

[NinjaTuna]

@Soultaker en Radiant,
Het gaat dus niet om de expressies die kostbaar zijn, maar om het resultaat wat ze opleveren.

Als mensen de code willen zien kan ik wel een linkje naar GitHub dm'en, laat maar even weten dan.

[Soultaker]

Ah, dat had ik inderdaad verkeerd geïnterpreteerd. Als sturen kostbaar is zou ik dat persoonlijk verwerkt hebben in de afstandsfunctie (en dan simpelweg A* of iets dergelijks gebruiken om het korstste pad daadwerkelijk te vinden). Maar dat is een high level oplossing, en niet echt een antwoord op je vraag.

Als je jouw aanpak wil gebruiken, moet je de verschillende statements relatief maken aan de richting waarin je beweegt. Bijvoorbeeld door de huidige richting mee te geven als vector (dx,dy) in een backtracking search:

C:

int search(int x, int y, int dx, int dy)
{
    int res;

    if (blocked(x, y)) return -1;
    if (goal(x, y)) return 0;

    res = search(x + dx, y + dy, dx, dy);  /* try moving forward */
    if (res == -1) res = search(x + dy, y - dx, dy, -dx);  /* try turning left */
    if (res == -1) res = search(x - dy, y + dx, -dy, dx);  /* try turning right */
    return res;
}

Ik vermoed tenminste dat je code er momenteel ongeveer zo uit ziet. Deze aanpak levert echter niet per se het kortste pad op, vandaar dat ik zou denken dat A* slimmer is.

[NinjaTuna]

Je krijgt hoe dan ook het kortste pad, zo werkt Lee's algorithm, de kracht ervan is dat het zo simpel is te implementeren.

De backtrace code is als volgt:

C:

//Keep tracing until we reach the entry node
    while (node != entryNode)
    {
        nextnode = NULL;

        if (getLeftNode(node, 1) && getLeftNode(node, 1)->label < node->label && getLeftNode(node, 1)->label >= 0)
        {
            nextnode = getLeftNode(node, 1);
        }
        if (!nextnode && getRightNode(node, 1) && getRightNode(node, 1)->label < node->label && getRightNode(node, 1)->label >= 0)
        {
            nextnode = getRightNode(node, 1);
        }
        if (!nextnode && getTopNode(node, 1) && getTopNode(node, 1)->label < node->label && getTopNode(node, 1)->label >= 0)
        {
            nextnode = getTopNode(node, 1);
        }
        if (!nextnode && getBottomNode(node, 1) && getBottomNode(node, 1)->label < node->label && getBottomNode(node, 1)->label >= 0)
        {
            nextnode = getBottomNode(node, 1);
        }

        //Add next node to path 
        path[i--] = nextnode;
        node = nextnode;
    }

Waarbij label de waarde is die toegekend wordt tijdens de "wave expansion" stap, zoals beschreven in de wikipedia-pagina die ik eerder aanhaalde. De conditie houdt dus in dat de aangrenzende node moet bestaan; dat het label van die aangrenzende node lager is dan die van de huidige (zo kom je tot het kortst mogelijke pad); en dat het label wel groter is dan -1. De laatste twee condities zou ik nog om kunnen wisselen als extra optimalisatie, maar daar zul je hoe dan ook weinig van merken.
Als al deze condities waar zijn wordt de desbetreffende node toegevoegd aan het pad en begint een nieuwe iteratie van de while met die node als uitgangspunt.

[Soultaker]

Ah, je bent al aan het backtracen. Ik zou die code dan zo herschrijven:

C:

int direction = 0;
while (node != entryNode)
{ 
    switch (direction)
    {
    case 0: nextNode = getLeftNode(node, 1); break;
    case 1: nextNode = getTopNode(node, 1); break;
    case 2: nextNode = getRightNode(node, 1); break;
    case 3: nextNode = getBottomNode(node, 1); break;
    }
    if (nextNode && nextNode->label >= 0 && nextNode->label < node->label)
    {
        path[i--] = node = nextNode;
    }
    else
    {
        direction = (direction + 1)%4;
    }
}

Bij elke iteratie stap je dus óf in de richting waar je al op ging, óf je draait een kwartslag. Dat voldoet aan jouw eis, maar het levert niet het pad op met het minste aantal bochten (wel met een minimaal aantal stappen).

Maar eigenlijk vind ik het een teken van slecht ontwerp dat er vier aparte functies zijn voor het vinden van nodes in vier richtingen, wat conceptueel vergelijkbare operaties zijn. Ik zou daar één functie van gemaakt hebben die de richting als parameter heeft. In plaats van getLeftNode(n) zou je dan getNode(n, LEFT) kunnen schrijven, en dan kun je dus ook die switch statement achterwege laten.

[ Voor 12% gewijzigd door Soultaker op 20-02-2013 18:29 ]

[NinjaTuna]

Leuk stukje code zet je daar neer, ik zal een kijken of ik dat al dan niet met switch aan de praat krijg.

Ik snap alleen niet waarom je zegt dat dit niet het pad oplevert met het minste aantal bochten, hij houdt toch dezelfde richting aan zolang hij dat kan?

[pedorus]

NinjaTuna schreef op woensdag 20 februari 2013 @ 19:37:
Ik snap alleen niet waarom je zegt dat dit niet het pad oplevert met het minste aantal bochten, hij houdt toch dezelfde richting aan zolang hij dat kan?

Dit komt omdat je alleen lokaal naar rechte stukken zoekt. Je kunt daardoor een bepaald pad inslaan, welke met weinig bochten begint, maar met meer bochten eindigt. Hiervan wijkt het algoritme vervolgens niet meer af.

Alternatief zou je de kostenfunctie moeten uitbreiden met de kosten van de bochten, en bij moeten houden vanuit welke richtingen je met welke laagste kosten kan komen. Afhankelijk van de kosten voor een bepaald soort bocht in verhouding tot de kosten van doorrijden moet je waarschijnlijk 4 waardes per cel onthouden. En de backtracking wordt dan ook ietsje ingewikkelder natuurlijk.

[Soultaker]

NinjaTuna schreef op woensdag 20 februari 2013 @ 19:37:
Ik snap alleen niet waarom je zegt dat dit niet het pad oplevert met het minste aantal bochten, hij houdt toch dezelfde richting aan zolang hij dat kan?

Ja, maar dat levert niet per se het minimaal aantal bochten op. Bijvoorbeeld in dit grid:

########b
#........
#.######.
#.#####..
#.####..#
#.###..##
#.##..###
#.#..####
a...#####

Er zijn precies twee kortste paden tussen a en b mogelijk, maar als je draaien zo lang mogelijk uitstelt, moet je door de diagonaal en dan maak je uiteindelijk veel meer bochten dan wanneer je langs de rand was gegaan.

pedorus schreef op woensdag 20 februari 2013 @ 20:20:
Alternatief zou je de kostenfunctie moeten uitbreiden met de kosten van de bochten, en bij moeten houden vanuit welke richtingen je met welke laagste kosten kan komen.

Dat suggereerde ik hier ook al.

[pedorus]

Het lijkt me enkel handiger om Lee uit te breiden, dan A* te nemen (Of bij herhalende situaties highway hierarchies uitbreiden zou helemaal mooi zijn.)

[NinjaTuna]

Ik zie het, jullie hebben gelijk. Beetje jammer, want ik moet dus eigenlijk precies niet hebben dat de robot die hoekjes gaat maken... Duurt lang.

Mijn voorkeur zou ook uit gaan naar het uitbreiden van wat ik nu heb, aangezien dat al werkt en er ook andere vakken zijn waar ik tijd aan moet besteden p:

Ik zou alleen niet weten hoe Lee uit te breiden, aangezien het algoritme alleen lokaal checks uitvoert. Of ik zou iets moeten goochelen tijdens de wave expansion...

[Soultaker]

pedorus schreef op woensdag 20 februari 2013 @ 20:41:
Het lijkt me enkel handiger om Lee uit te breiden, dan A* te nemen

Het is mij echter compleet onduidelijk op welke manier dit algoritme verschilt van een gewone breadth-first search

Breadth-first search is simpelweg Dijkstra's algoritme met constante kostenfunctie.
Dijkstra's algoritme is simpelweg A* met nulheuristiek.

Dus het komt allemaal min of meer op elkaar neer.

[NinjaTuna]

Als ik het goed begrijp zou A* in mijn geval het meest efficiënt moeten zijn, omdat ik al informatie heb over waar het doel zich bevindt, klopt dit? In dat geval lever ik mijn huidige programma wel gewoon in en zal ik me later als daar tijd voor is nog toeleggen op een programma wat gebruik maakt van A*.

In ieder geval bedankt voor jullie hulp!

[pedorus]

Soultaker schreef op woensdag 20 februari 2013 @ 21:08:
Het is mij echter compleet onduidelijk op welke manier dit algoritme verschilt van een gewone breadth-first search

Breadth-first search is simpelweg Dijkstra's algoritme met constante kostenfunctie.
Dijkstra's algoritme is simpelweg A* met nulheuristiek.

Het verschil lijkt mij zitten in het bijhouden van de lokatie waar je vandaan kwam, en de structuur van opslaan. Bij Lee sla je minder data op, namelijk niet waar je vandaan kwam. Ook is er geen priority queue/(Fibonacci) heap nodig, omdat alles steeds op afstand 1 zit. (Bij een uitbreiding van Lee krijg je wellicht wel een queue, maar dit kan waarschijnlijk een calendar queue zijn, afhankelijk van de kosten van een bocht.)

NinjaTuna schreef op woensdag 20 februari 2013 @ 21:06:
Ik zou alleen niet weten hoe Lee uit te breiden, aangezien het algoritme alleen lokaal checks uitvoert. Of ik zou iets moeten goochelen tijdens de wave expansion...

Het lijkt mij niet al te ingewikkeld, echter wel wat codeerwerk. Je moet elke cel opsplitsen in 4 'subcellen', namelijk celplek en de richting waarin de robot staat. Je bevind je dan steeds in 1 van de 4 subcellen van een cel, en kan navigeren naar 3 verschillende aangrenzende subcellen, waarbij de kosten verschillen afhankelijk van of je een bocht maakt. (Er van uitgegaan dat keren niet nodig is.)