[PHP] Winkelmandje-recursie optimaliseren

[ACM]

De meesten van jullie kennen natuurlijk de pricewatch wel en vast ook wel de winkelmandjes-functionaliteit daarvan.
Die is onlangs aangepast om een wat betere zoektocht naar de goedkoopste shops te hebben, namelijk door alle producten die een shop niet levert als een nieuw winkelmandje te beschouwen en een nieuwe zoektocht te doen. En dat levert dus een leuke recursie op.

Meestal niet zo'n probleem, want de functie wordt sowieso maar vrij weinig aangeroepen, dus als ie wat slomer is... ach boeie.

Maar als er een wat langere lijst (een complete pc bijv) van populaire producten wordt uitgekozen, dan loopt het al heel snel tegen de execution time limits van php aan. Ik heb overigens niet de indruk dat het feit dat het in php draait erg veel uitmaakt voor de complexiteit en dus de functionaliteit in de basis, maar goed. Een configuratie uit de best buy guide van 15 producten (met in totaal 399 prijs-vermeldingen van 80 shops) loopt bijvoorbeeld al tegen de time limit aan en duurt op een verder onbelaste P4 2.8Ghz ruim 40 seconden.

Daarbij is er al een optimalisatie om reeds uitgerekende deelcombinaties te cachen en die te hergebruiken, als dat niet gebeurt gaat het voorbij de 120 seconden. Verder worden al die prijzen in één keer opgehaald (paar ms) om te voorkomen dat er een paar honderd tot duizend queries uitgevoerd worden vanwege de recursie.

Het beperken van de diepte (aantal verschillende shops waarbij een bestelling mag plaatsvinden) heeft doordat de caching minder effectief/moeilijker wordt een averechts effect. Tenzij ik dat verkeerd doe natuurlijk

In de basis is het algoritme nu zoiets (pseudo code):

code:

zoekGoedkoopsteShops($productIds)
{
  if(incache)
    return cache;
  else
    return zoekGoedkoopsteShopsVoorProducten($productIds);
}

zoekGoedkoopsteShopsVoorProducten($productIds)
{
  $shops = zoekShopsVoorProducten($productIds);
  foreach($shops as $shop)
  {
     $mandjeBijShop = telPrijsVoorShop($shop);
     if(count($mandjeBijShop['nietGeleverd']) > 0)
        $mandjeBijShop['overigeProducten'] = zoekGoedkoopsteShops($mandjeBijShop['nietGeleverd']);

     $shop['prijzen'] = $mandjeBijShop;
  }

  return sorteerEnLimiteerShops($shops);
}

Dit is overigens een nogal abstracte versie, o.a. de functies zijn niet per se een functie maar gewoon code die zo het makkelijkst samen te vatten is. Met bovenstaand getallenvoorbeeld wordt de 'zoekGoedkoopsteShops'-functie zo'n 300k x aangeroepen, en de 'zoekGoedkoopsteShopsVoorProducten'-functie zo'n 3k keer. Dus de cache heeft wel effect.

De vraag is natuurlijk:
Hoe kan het beter? Met name een reductie in het aantal recursies die ik over het hoofd zie is welkom, of uiteraard een handiger zoekalgortime. Dat is niet echt mijn sterkste punt.

Een andere optimalisatie die ik bedacht had was het limiteren van de resultaatset van 'zoekShopsVoorProducten' na de eerste stap om zo grootte van de "deelmandjes" wat te verkleinen. Alleen zal dat natuurlijk de kwaliteit van de zoektocht wat verminderen (je kan bijv alleen de shops nemen met prijzen onder de mediaan)

[EdwinG]

...Die is onlangs aangepast om een wat betere zoektocht naar de goedkoopste shops te hebben, namelijk door alle producten die een shop niet levert als een nieuw winkelmandje te beschouwen en een nieuwe zoektocht te doen...

Heeft die aanpassing ook als doel om het aantal leveranciers zo laag mogelijk te houden? Of moet de prijs echt zo laag mogelijk zijn.

Bij de tweede optie, vraag ik me af waarom die recursie nodig is. In plaats van telkens een nieuw mandje te gebruiken, zou het dan een stuk sneller zijn om 1x van elk product de laagste prijs (+ bijbehordende shop) op te halen. Vervolgens elke weergegeven shop aanvullen met informatie uit die selectie.

[ACM]

EdwinG schreef op woensdag 10 januari 2007 @ 19:17:
Heeft die aanpassing ook als doel om het aantal leveranciers zo laag mogelijk te houden? Of moet de prijs echt zo laag mogelijk zijn.

De originele oplossing was om alle leveranciers op te zoeken die minstens een product leverden en dat dan aan te vullen met de som van de laagste prijzen van de missende producten, ongeacht welke leverancier dat dan daadwerkelijk leverde.
Dat had natuurlijk met name zodra de bijkomende kosten meegenomen werden als nadeel dat het helemaal niet meer realistisch was. De variant zonder bijkomende kosten is natuurlijk sowieso niet heel erg reeel, maar met de bijkomende kosten wordt er automatisch al behoorlijk gelimiteerd op het aantal aanvullende leveranciers dat nodig is om het mandje te kunnen bestellen.
Bovendien werd de aanname dat een bezoeker zo veel mogelijk producten bij een winkelier wil bestellen dan ineens niet meer aangehouden voor de overgebleven producten.

De verandering is dus vooral bedoeld om het lijstje wat realistischer te maken.

Bij de tweede optie, vraag ik me af waarom die recursie nodig is. In plaats van telkens een nieuw mandje te gebruiken, zou het dan een stuk sneller zijn om 1x van elk product de laagste prijs (+ bijbehordende shop) op te halen. Vervolgens elke weergegeven shop aanvullen met informatie uit die selectie.

Met name zodra je de bijkomende kosten meerekent is dit eigenlijk al niet meer mogelijk. Want de kans is natuurlijk groot dat je bij de eennagoedkoopste moet zijn omdat die meer producten aanbiedt en je daardoor lagere totale kosten hebt.

Jouw afsnijding is dus wat er al was. Een beperking van het aantal shops die voorkomen is wmb ook wel wenselijk, maar dat is in wezen hetzelfde als het beperken van de diepte van de zoektocht en dat werkte dus averechts door de minder efficiente caching.

[EdwinG]

ACM schreef op woensdag 10 januari 2007 @ 17:01:...
Het beperken van de diepte (aantal verschillende shops waarbij een bestelling mag plaatsvinden) heeft doordat de caching minder effectief/moeilijker wordt een averechts effect. Tenzij ik dat verkeerd doe natuurlijk

Geldt dat averechts effect ook, indien de beperking aan de hand van de resultaten plaatsvind? Dus bijvoorbeeld als zoekShopsVoorProducten($productIds); verschillende shops met 2 of meer producten opleveren, de shops met slechts 1 product uit het resultaat gefilterd worden? (Waarmee die vertakking dus afgesloten word)

Oftewel: (regels 12 t/m 15 ingevoegd)

code:

zoekGoedkoopsteShops($productIds)
{
  if(incache)
    return cache;
  else
    return zoekGoedkoopsteShopsVoorProducten($productIds);
}

zoekGoedkoopsteShopsVoorProducten($productIds)
{
  $shops = zoekShopsVoorProducten($productIds);
  if ( shopsMetMeerdereProductenInResultaat($shops) )
  {
    verwijderShopsMet1ProductUit($shops);
  }
  foreach($shops as $shop)
  {
     $mandjeBijShop = telPrijsVoorShop($shop);
     if(count($mandjeBijShop['nietGeleverd']) > 0)
        $mandjeBijShop['overigeProducten'] = zoekGoedkoopsteShops($mandjeBijShop['nietGeleverd']);

     $shop['prijzen'] = $mandjeBijShop;
  }

  return sorteerEnLimiteerShops($shops);
}

[ACM]

EdwinG schreef op woensdag 10 januari 2007 @ 23:50:
Geldt dat averechts effect ook, indien de beperking aan de hand van de resultaten plaatsvind? Dus bijvoorbeeld als zoekShopsVoorProducten($productIds); verschillende shops met 2 of meer producten opleveren, de shops met slechts 1 product uit het resultaat gefilterd worden? (Waarmee die vertakking dus afgesloten word)

Ah, dat was een nuttige tip, bedankt. Ik heb hem in een iets conservatievere variant toegevoegd, zodat ie niet gebruikt wordt op het top-niveau (dus de eerste iteratie) en ook alleen als er in totaal meer dan 4 producten voor die ronde gevraagd werden. Dat gaf een boost van 90 naar 6 seconden, en dat vond ik wel genoeg om online te zetten. Ik had hem in een iets andere variant al eerder toegepast, maar dan leek het minder effect te hebben, dus die had ik weer ongedaan gemaakt.

De overzichten zijn voor bij het niet meenemen van de extra gevonden shops wel iets hoger van prijs, maar dat is toch niet een erg realistisch scenario, de variant waarbij de verzendkosten meegenomen worden lijkt precies hetzelfde resultaat op te leveren.