[Java] Efficienter varianten bitmap genereren (winkelmand)

[ACM]

Voor een stuk rekencode dat ik aan het uitwerken ben moet ik heel veel verschillende combinaties van een stel producten doorrekenen.
Die combinaties (van max 31 producten) representeer ik in Java met een bitmap dmv een int.

Een en ander bestaat uit twee lagen, waarvan de tweede laag ook nog eens recursief werkt. Die eerste laag heeft echter niet zoveel invloed op de executietijd, dus die laat ik hier buiten beschouwing.

Voor de tweede laag begin ik met een deelverzameling van die producten, dat kan dus bijvoorbeeld 0100101 zijn. Vervolgens wil ik daarvan alle mogelijke deelverzamelingen, behalve 0, genereren. Bij dit voorbeeld is dat dus:
0100101, 0000101, 0100001, 0100100, 0000001, 0000100 en 0100000

De enige manier die ik heb kunnen verzinnen/vinden om die combinaties te genereren is door domweg te tellen hoeveel bits er zij (3 hier) en dan een nieuwe bitmap te maken met die grootte. Zodat je uiteindelijk met een simpele for-loop alle (2³ - 1) combinaties kan maken door domweg van 1 t/m 7 te tellen in dit voorbeeld.
En zodra je zo'n combinatie "gegenereerd" hebt, moet je de originele bitmap weer zo vertalen dat de gekozen bits daarvan in een nieuwe bitmap verschijnen. Dus dat het getal 5 uit de kleine bitmap (101) vertaald wordt naar 0100001 uit de grote bitmap. Ik weet overigens vooraf niet hoeveel of welke bits er in het origineel geset zijn.

Ik heb daarvoor imho een redelijk efficient algoritme voor uitgewerkt, maar aangezien ik nog steeds vrij weinig bitmagic beheers, denk ik wellicht nog te veel in losse bits. Hieronder staat mijn code om een bovenstaande tekst in code-vorm nog een keertje weer te geven. Momenteel zit zo'n 20% van mijn totale executietijd (volgens een sampling profiler) in de bovenste functie en nog eens 60% in de onderste.
Deze code is uiteraard niet alles wat er is, maar wel alle statements die ik atm doe met de bitmaps. Momenteel is de methode die het grootste deel van mijn executie tijd (in het algemeen dus) opslokt de 'alternativeBitmap'-methode. Ironisch genoeg kan de hotspot-optimizer van Java het als losse methode beter optimaliseren dan in-line in de generateCombinations(), maar als de inhoud van die methode tot een of enkele statements gereduceerd kan worden, dan is dat wellicht weer een ander verhaal.

Dus is er een nog efficientere methode om die varianten te genereren?

Java:

private Some generateCombinations(int origBitmap, params...)
{
    // Use a smaller bitmap to get all possible combinations from the original.
    final int comboLimit = (1 << bitCount(origBitmap));
    
    for(int combo = 1; combo < comboLimit; combo++)
    {
        int subBitCount = bitCount(combo);
        if(subBitCount not ok)
            continue;
            
        // Get the bit-variant 
        int newBitmap = alternativeBitmap(origBitmap, comboLimit, combo);
        
        if(newBitmap == origBitmap)
            // do a little work
        else if(we can continue)
        {
            // Unset all the bits already taken in the origBitmap
            int leftOverBitmap = origBitmap & ~newBitmap;
            // And recurse and do a bit of work
        }
    }
    
    return currentEntry;
}

private static int alternativeBitmap(int origBitmap, int comboLimit, int combo)
{
    int newBitmap = 0;
    for(int combobit = 1; combobit < comboLimit; combobit <<= 1)
    {
        // Get the lowest bit set (see Integer.lowestOneBit(int)). 
        int lowestBit = origBitmap & -origBitmap;
        
        // Unset this bit in the bitmap
        origBitmap &= ~lowestBit;
        
        // See if this new combination actually requires the combobit' bit
        if((combo & combobit) > 0)
        {
            newBitmap |= lowestBit;
        }
    }
    
    return newBitmap;
}

[Soultaker]

Java:

for (int mask = init; mask > 0; mask = (mask - 1)&init)

[ACM]

Soultaker schreef op donderdag 03 december 2009 @ 15:24:

Java:

for (int mask = init; mask > 0; mask = (mask - 1)&init)

Hmm, dat is net iets minder code dan ik nu heb

Thx, nu nog kijken of ik ook begrijp waarom het werkt..

[Soultaker]

Het helpt waarschijnlijk een simpel voorbeeldje uit te schrijven:

  100100    <-- mask = init
       1 -
 --------
  100011
  100100 &
 --------
  100000    <-- mask = (init - 1)&init
       1 -
 --------
  011111
  100100 &
 --------
  000100    <-- mask = (((init - 1)&init) - 1)&init

De truc is dat als je 1 aftrekt, je altijd leent van de laagste 1-bit (waarbij de ondergelegen bits op 1 worden gezet). De nieuwe 1-bits die je niet wil hebben mask je daarna weg. Eigenlijk tel je dus (voor drie bits) nog steeds van 7 tot 0, alleen zitten er wat nullen tussen de drie bits die je ervoor gebruikt.

(Je gebruikte een soortgelijk truc trouwens op regel 34: -origBitmap is niets anders dan ~(origBitmap - 1), en (origBitmap - 1) leent van de laagste 1-bit in origBitmap.)

[ACM]

Soultaker schreef op donderdag 03 december 2009 @ 16:36:
De truc is dat als je 1 aftrekt, je altijd leent van de laagste 1-bit (waarbij de ondergelegen bits op 1 worden gezet). De nieuwe 1-bits die je niet wil hebben mask je daarna weg. Eigenlijk tel je dus (voor drie bits) nog steeds van 7 tot 0, alleen zitten er wat nullen tussen de drie bits die je ervoor gebruikt.

Ik had hem ondertussen inderdaad al met een simpel loopje laten printen wat ie deed en het was me duidelijk(er) geworden. Je uitleg bevestigd idd dat ik redelijk op de goede weg zat

Bij deze staat je nickname en een verwijzing naar dit topic dan ook in de comments in code die tzt in productie komt voor tweakers.net

Helaas had mijn gebruikte sampling profiler de boel een beetje overdreven en was de originele code al niet voor zo'n groot deel afhankelijk van mijn slomere eigen versie. Desalniettemin is de code in mijn testvoorbeeld van 2.1 naar 1.8 seconde terug gegaan, wat nog steeds geen gekke winst is als je bedenkt dat dit slechts ter ondersteuning van een for-loop was, ipv het doel van de code

[Soultaker]

ACM schreef op donderdag 03 december 2009 @ 16:44:
Bij deze staat je nickname en een verwijzing naar dit topic dan ook in de comments in code die tzt in productie komt voor tweakers.net

Een hele eer.

Helaas had mijn gebruikte sampling profiler de boel een beetje overdreven en was de originele code al niet voor zo'n groot deel afhankelijk van mijn slomere eigen versie.

Dat verbaast me niet echt, aangezien de oude code niet zo gek verzonnen was, en je waarschijnlijk ook wel wat werk bínnen de lus moet verrichten. Maar elk beetje helpt natuurlijk, zeker als je tegelijkertijd je code kunt vereenvoudigen. (Tenzij je per SLOC betaald krijgt misschien. )

[.oisyn]

Hoe is je bitCount()? Dat kan zonder loop en checks met 5 operaties door de bits slim te maskeren en op te tellen

Java:

int bitCount(int i)
{
    i = (i & 0x55555555) + ((i & 0xaaaaaaaa) >>> 1);
    i = (i & 0x33333333) + ((i & 0xcccccccc) >>> 2);
    i = (i & 0x0f0f0f0f) + ((i & 0xf0f0f0f0) >>> 4);
    i = (i & 0x00ff00ff) + ((i & 0xff00ff00) >>> 8);
    return (i & 0x0000ffff) + (i >>> 16);
}

Wat hier feitelijk gebeurt is dat je de int benadert als een vectorregister van groupjes van bits die feitelijk aangeven hoeveel bits er in dat groepje staan. Dit is natuurlijk logisch voor de originele waarde - een 32 bits int bestaat uit 32 groepjes van 1 bit, en elke bit geeft aan hoeveel bits erin staan (een 0 voor 0 bits en een 1 voor 1 bits). In de eerste stap zie je 'm als groepjes van 2-bits, en benader je 'm in twee delen. Door de een helft te maskeren met 01010101 krijg en de andere met 10101010 en dat vervolgens een op de schuiven, en die bij elkaar op te tellen, krijg je per groepje van 2 bits hoeveen bits er in dat groepje stonden. Zo wordt 11 opgedeeld in een 01 en een 10, die laatste wordt geshift naar 01, en 01 + 01 is 10. Oftewel, 2 bits .

Daarna behandel je ze als groepjes van 4-bits, bijv. 0110. Dit is het resultaat van 2 groepjes van 2, het linkergroepje had 1 bit (01) en de rechter had er 2 (10). Deze maskeer je met 0011 en 1100, die laatste schuif je nu met 2, en vervolgens tel je ze op. Oftewel: 0010 + (0100 >> 2) = 0010 + 0001 = 0011. Met andere woorden, in dat groepje van 4 zitten 3 bits.

En dit herhaal je tot je het hebt gereduceerd tot 1 groep van 32 bits.

[ Voor 41% gewijzigd door .oisyn op 03-12-2009 20:29 . Reden: | ipv + ]

[ACM]

.oisyn schreef op donderdag 03 december 2009 @ 17:32:
Hoe is je bitCount()? Dat kan zonder loop en checks met 5 operaties door de bits slim te maskeren en op te tellen

In eerste instantie gebruikte ik gewoon static Integer.bitCount(int i), die hetzelfde doet als jij post. Daarna heb ik die voor "kleine" (tot 20 bits geset) lijsten vervangen door een array waar ik alle 2^n varianten in opsla die ik tegen ga komen en is het effectief dus gereduceerd tot een enkele array-lookup. Daarboven gebruik ik toch een ander algoritme die veel minder vaak bitCount aanroept en dan dus wel gewoon de Integer-versie gebruikt.

Toen ik het dat verving was dat weer een stukje sneller aangezien ik een paar ordes van groottes vaker het aantal bits wil weten dan dat er mogelijke bitmaps voor komen, maar ik zal het weer eens testen of het nog steeds sneller is nu ik de rest van de code redelijk verder heb geoptimaliseerd.

Nuttige uitleg

Ik gebruikte het dus indirect al, maar nou begrijp ik ook nog eens wat het doet

[.oisyn]

ACM schreef op donderdag 03 december 2009 @ 17:51:
Daarna heb ik die voor "kleine" (tot 20 bits geset) lijsten vervangen door een array waar ik alle 2^n varianten in opsla die ik tegen ga komen en is het effectief dus gereduceerd tot een enkele array-lookup.

Vergis je niet, zo'n lookup is potentieel enorm veel duurder dan met wat bits rekenen als hij niet in de cache staat. 20 bits is toch een array van 1 MB, bestaande uit 16384 cache lines (van 64 bytes). Dan kun je beter een array van 10 bits gebruiken (= 1024 bytes en slechts 16 cachelines) en twee keer een lookup doen, eentje met m & 0x3ff en eentje met m >>> 10.

Ter vergelijking, die bitCount functie is op mijn core 2 quad zo'n 10 cycles. Een cache miss kost zo'n 270 cycles

[ Voor 7% gewijzigd door .oisyn op 03-12-2009 18:05 ]

[Soultaker]

Als het gaat om het tellen van de bits in je bitmap, dan heb je geen algemene bitcount nodig, aangezien je de bitcount eenvoudig in de lus kan bijhouden:

Java:

int bits = bitCount(init), n = (1<<bits) - 1;
for (int mask = init; mask > 0; mask = (mask - 1)&init)
{
    // doe iets met mask en bits:
    System.out.println(mask + "," +bits);

    // bitcount updaten:
    for (int m = 1; (n&m) == 0; m += m) ++bits;
    --bits; --n;
}

De lus in regel 8 lijkt lelijk, en dat is 't ook aangezien veel CPU's bitscan operaties supporten, maar helaas hebben de meeste talen daar geen constructies voor. In C met GCC kun je dit doen:

C:

bits += __builtin_ctz(n);

Die builtin compileert naar een bsr instructie. Maar het lusje is in absolute zin niet zo heel slecht, aangezien je gemiddeld maar één iteratie van de loop uitvoert. Wellicht is dat sneller dan een bitcount uitvoeren. (Hangt er een beetje vanaf hoe alles uitpakt; de bitcount heeft meer instructies, maar geen branches.)

[ Voor 8% gewijzigd door Soultaker op 03-12-2009 18:53 ]

[Matis]

De term die jij volgens mij zoekt is Hamming distance.
Ik heb een keer een berekening gemaakt/gejat voor het uitrekenen van de Wikipedia: Hamming distance :

C++:

unsigned hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0, val = x ^ y;
 
  // Count the number of set bits (Knuth's algorithm)
  while(val)
  {
    ++dist; 
    val &= val - 1;
  }
 
  return dist;
}

Hij telt dus het aantal logische 1en in je uint. Ik weet niet of dit is wat je zoekt, maar efficiënter kan het niet in een hogere programmeertaal Mocht je er niets aan hebben, dan spijt het me

edit; Ik raad je aan om deze code inline op te nemen, ik verloor (door deze functiecall 1 miljoen keer uit te voeren) ongeveer 10% door het aanroepen van deze functie. Het inline opnemen van rekenintensieve taken is dus wel aan te raden

[ Voor 24% gewijzigd door Matis op 03-12-2009 19:18 ]

[ACM]

.oisyn schreef op donderdag 03 december 2009 @ 17:58:
Vergis je niet, zo'n lookup is potentieel enorm veel duurder dan met wat bits rekenen als hij niet in de cache staat.

Ik heb mijn 17-bit testaanroep losgelaten op mijn array-versie, die had gemiddeld 2,120 seconde nodig, gewoon weer Integer.bitCount() gebruiken vereiste 2,075 seconde en Soultakers bijhoud-methode vereiste 2,139 seconde voor de totale procedure. (2x 10 opwarm aanroepen, gemiddelde is de gemiddelde tijd over 4x 10 aanroepen daarna).

Het lijkt er dus inderdaad op dat de bitCount-versie nu wint. Dat scheelt me iig twee verschillende varianten onderhouden, dus de aanpak met twee halve integers met array-lookups laat ik dan maar zitten

[ACM]

Matis schreef op donderdag 03 december 2009 @ 19:13:
Hij telt dus het aantal logische 1en in je uint. Ik weet niet of dit is wat je zoekt, maar efficiënter kan het niet in een hogere programmeertaal Mocht je er niets aan hebben, dan spijt het me

In mijn geval zou ik dan de hamming distance van "een int" tot 0 willen weten lijkt me? En dat kan uiteraard wel efficienter met de aanpak van .oisyn. Tenzij ik jou niet goed begrijp?

edit; Ik raad je aan om deze code inline op te nemen, ik verloor (door deze functiecall 1 miljoen keer uit te voeren) ongeveer 10% door het aanroepen van deze functie. Het inline opnemen van rekenintensieve taken is dus wel aan te raden

Dat is dan weer het aardige van Java's hotspot-optimalisaties. Toen ik nog met de code in de topicstart werkte had ik gewoon "int lowestBit = Integer.lowestOneBit(originalMap);" staan en ik zag geen verschil in executietijd (hoewel ook niet heel goed getest) met later gewoon "int lowestBit = originalMap & -originalMap;" in de code te zetten. En de functie met die loop werd zelf al 69M keer aangeroepen. De Integer-functie werd dus nog wat vaker aangeroepen... Ik heb geen idee van het precieze aantal, maar waarschijnlijk in de orde van grootte van 69M * 2^7.

[Matis]

ik zie nu dat Soultaker in "[Java] Efficienter varianten op bitmap g..." exact hetzelfde is als Knuth's algorithm alleen anders uitgeschreven

Het enige verschil zit hem in het feit dat je (in het geval van soultaker) niet weet hoeveel bitjes er gezet zijn, dit zou je wel weer kunnen doen door een counter in de forloop op te hogen.

edit; een hamming distance van een integer tot 0 is dus gewoon de hammingdistance van de integer zelfve.

als je 0xff ^ 0x00 doet, dan komt daar 0xff uit , de XOR dus

[ Voor 19% gewijzigd door Matis op 03-12-2009 19:51 ]

[.oisyn]

Matis schreef op donderdag 03 december 2009 @ 19:13:
De term die jij volgens mij zoekt is Hamming distance.
Ik heb een keer een berekening gemaakt/gejat voor het uitrekenen van de Wikipedia: Hamming distance :

C++:

unsigned hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0, val = x ^ y;
 
  // Count the number of set bits (Knuth's algorithm)
  while(val)
  {
    ++dist; 
    val &= val - 1;
  }
 
  return dist;
}

Hij telt dus het aantal logische 1en in je uint. Ik weet niet of dit is wat je zoekt, maar efficiënter kan het niet in een hogere programmeertaal

*kuch*

C++:

unsigned hamdist2(unsigned x, unsigned y)
{
    unsigned i = x ^ y;
    i = (i & 0x55555555) + ((i & 0xaaaaaaaa) >> 1); 
    i = (i & 0x33333333) + ((i & 0xcccccccc) >> 2); 
    i = (i & 0x0f0f0f0f) + ((i & 0xf0f0f0f0) >> 4); 
    i = (i & 0x00ff00ff) + ((i & 0xff00ff00) >> 8); 
    return (i & 0x0000ffff) + (i >> 16); 
}

time  Matis: 4645000
time  oisyn: 1664688

.edit: ik zie trouwens dat ik in een eerdere post een foutje heb gemaakt door | te gebruiken ipv +

[ Voor 5% gewijzigd door .oisyn op 03-12-2009 20:29 ]

[Matis]

Hmm, ik snap ff niet wat je code doet Je werkt met een masker oid welke de bits van de vorige overneemt en maskeerd middels een aantal logisch geplaatste bits?

Welke waardes hebben je gebruikt voor het unsigned i? Alle van 0 tm 2^32?

Dat knuth's algoritme heeft theoretisch maar 1 klokslag nodig om te detecteren dat er 0 bit hoog zijn, de jouwe moet wel wat meer berekeningen doen. Dat is voor 32 bits natuurlijk precies andersom

Wat zijn precies die timings?

edit; heej waarom heb je dat tabelletje met die tijden nu veranderd/verwijderd?

[ Voor 12% gewijzigd door Matis op 03-12-2009 20:30 ]

[.oisyn]

Matis schreef op donderdag 03 december 2009 @ 20:29:
Hmm, ik snap ff niet wat je code doet Je werkt met een masker oid welke de bits van de vorige overneemt en maskeerd middels een aantal logisch geplaatste bits?

.oisyn in "[Java] Efficienter varianten op bitmap g..."

Welke waardes hebben je gebruikt voor het unsigned i? Alle van 0 tm 2^32?

yup

Dat knuth's algoritme heeft theoretisch maar 1 klokslag nodig om te detecteren dat er 0 bit hoog zijn, de jouwe moet wel wat meer berekeningen doen.

Jammer alleen dat een compare en een jump niet maar 1 klokslag is . Zoals ik al zei, dit algoritme kost 10 cycles. Ja nu een paar meer door het extra parameters en de xor operatie.

Wat zijn precies die timings?

Aantal cycles voor 100.000 iteraties. Ik heb een 3.2GHz CPU dus je moet delen door 3200000000 voor het aantal seconden

Matis schreef op donderdag 03 december 2009 @ 20:29:
edit; heej waarom heb je dat tabelletje met die tijden nu veranderd/verwijderd?

Die totalen waren de uitkomsten van alle hamdist() aanroepen bij elkaar opgeteld, zodat de compiler dat niet wegoptimized en ik tevens de uitvoer kon verifieren. Was voor de post niet echt nuttige info ofzo . Verder had ik tijden gepost van een debug versie ipv een release versie

[ Voor 27% gewijzigd door .oisyn op 03-12-2009 20:36 ]

[pedorus]

Hoewel ik denk dat dit voor het genereren van combinaties een vrij efficiënte oplossing is, vraag ik me af of dat nu het grootste probleem was. Als je een soort knapsack-probleem bij de pricewatch (?) wil oplossen, dan zijn er waarschijnlijk betere oplossingen... Wat gaat er komen?

[ACM]

Overigens heeft Java's Integer.bitCount een iets andere manier van werken, met zo te zien iets minder operaties (ik tel er 15 en bij .oisyn's manier 19):

Java:

    public static int bitCount(int i) {
        // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
    }

[.oisyn]

Cool Die is nog iets sneller

time  Matis: 4644192
time  oisyn: 1656104
time   java: 1467808

[Matis]

Het duizelt mij

[pedorus]

In het kader van microoptimalisaties: Hoe is deze?

quote: http://stackoverflow.com/...-bits-in-a-32-bit-integer

Java:

int NumberOfSetBits(int i)
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

[.oisyn]

't Stomme is, ik zat net te denken dat een paar van die ANDs niet nodig zijn omdat ze toch overflowen in een gedeelte waar je niet meer in geïnteresseerd bent. De Java implementatie maakt daar nou net gretig gebruik van

.edit: wow

time  Matis: 4658664
time  oisyn: 1659672
time   java: 1443944
time     so: 1122176

[ Voor 20% gewijzigd door .oisyn op 03-12-2009 20:48 ]

[ACM]

pedorus schreef op donderdag 03 december 2009 @ 20:34:
Hoewel ik denk dat dit voor het genereren van combinaties een vrij efficiënte oplossing is, vraag ik me af of dat nu het grootste probleem was. Als je een soort knapsack-probleem bij de pricewatch (?) wil oplossen, dan zijn er waarschijnlijk betere oplossingen... Wat gaat er komen?

Het is een poging tot herimplementatie van het bepalen van de beste groep winkels voor een 'winkelmandje'. Maar dit keer dus in Java en met wat nieuwe functionaliteit om na te gaan of je bijv beter af bent om bij winkelmand A,B,C,D bij een winkel die ze allevier kan leveren toch beter af bent om een of meerdere van die producten elders te bestellen.
Het stukje code dat je hier ziet is een deel van dat 'een of meerdere' bepalen.

Ik weet zelf niet heel goed hoe dit te vertalen naar een echt knapsack, noch welk algoritme daar dan de beste uitkomst gaat bieden (of of ik toevallig een van die algoritmes al heb gekozen). Er zitten echter wat randvoorwaarden bij die - voor zover ik kon zien - in alle algoritmes niet echt goed passen. Ik wil namelijk meerdere resultaten kunnen geven en dat moeten dan wel resultaten zijn die voor de gebruiker logisch zijn. Dus niet vijf resultaten die in wezen minieme varianten op de elkaar zijn met slechts een product verschillend ofzo
Afgezien daarvan heb ik een aspect dat ik sowieso in geen van de algoritmes die ik bekeken had terugzag, bij mij moet ik rekening houden dat de totale kosten van een groep producten afhangt van of er meerdere producten bij een winkel worden besteld. Het kan zelfs zo zijn dat de toevoeging van een extra product betekent dat de totale kosten ineens afnemen en je dus niet eens domweg de prijs van het product bij een andere deelverzameling op kan tellen.

[Wolfboy]

De meeste beschikbare algorithmen geburiken een vorm van backtracking, dus als je (een aantal van) de tussenliggende oplossingen opslaat dan is het prima mogelijk om de bestaande algoritmen te gebruiken.

Het enige probleem is dat veel van de algoritmen de optimum direct als afkappunt gebruiken, daardoor zijn ze natuurlijk niet direct geschikt aangezien dat je een subset van de oplossingen levert. Maarja... die controle kan je natuurlijk prima verwijderen. Al ontkom je dan niet snel meer aan alle oplossingen berekenen

[pedorus]

De combinatie van meerdere resultaten, en het toepassen van de kostenstructuur (oa verzendkosten), zorgt ervoor dat hier bijna zeker geen bestaand algoritme voor is, behalve algemene dingen zoals evolutionary computing enzo.

Ik bestel zelf meestal maar 1 product, maar ik gok dat vooral oplossingen met zo min mogelijk winkels interessant zijn, als ik kijk hoe mensen bestellen. De huidige weergave suggereert al snel dat je bij een winkel 1 product moet gaan bestellen, zelfs als die winkel voor dat product niet eens de goedkoopste is. Een tabelletje met winkels, prijs per product incl. percentuele opslagen (of/met kleurtje), en aditionele (verzend)kosten als je daar zoveel mogelijk bestelt zal al veel inzicht verschaffen, ook voor het bedenken van goede heuristieken. Beginnen met winkels die (een groot deel van de) producten goedkoop aanbieden, en vervolgens voor de overige producten hetzelfde deelprobleem oplossen (soort dynamisch programmeren) zou goed kunnen werken.

Voor een zo goedkoop mogelijke oplossing kun je waarschijnlijk al snel vele combinaties uitsluiten, bijvoorbeeld als [prijs-extra korting]>[prijs+kosten andere winkel]. Winkels die vanaf bedrag x korting geven, daar kun je nog suggereren om een (of meer) onzinproduct(en) erbij te bestellen, dat doe ik zelf in de praktijk ook wel eens. Aangezien het bepalen van die onzinproducten NP-compleet is, kun je het beste suggereren om voor bedrag y extra te kopen..

Kortom, hier is geen pasklare oplossing voor, maar ik denk dat je met een paar goede heuristieken wel snel (<0.1s) tot een aantal goede oplossingen kan komen..

[ACM]

pedorus schreef op vrijdag 04 december 2009 @ 14:47:
De combinatie van meerdere resultaten, en het toepassen van de kostenstructuur (oa verzendkosten), zorgt ervoor dat hier bijna zeker geen bestaand algoritme voor is, behalve algemene dingen zoals evolutionary computing enzo.

Dat was idd ook mijn conclusie

Ik bestel zelf meestal maar 1 product, maar ik gok dat vooral oplossingen met zo min mogelijk winkels interessant zijn, als ik kijk hoe mensen bestellen.

Ik heb nu twee sturingsparameters, waarvan een het maximum aantal winkels is dat teruggegeven wordt per keuze-mogelijkheid. En dat zorgt dan uiteraard ook voor een beperking van de benodigde hoeveelheid berekeningen, want als je max 4 terug mag geven, dan ga je uiteraard bij een incomplete subset niet alsnog de diepte verder in.

De huidige weergave suggereert al snel dat je bij een winkel 1 product moet gaan bestellen, zelfs als die winkel voor dat product niet eens de goedkoopste is.

Die weergave gaat sowieso op de schop, je krijgt iig altijd eerst de winkel te zien die de meeste producten levert. En er worden in principe geen dubbele - maar omgekeerde volgordes - combinaties gegenereerd, mede door betere interne stopvoorwaarden; Als je een combinatie probeert met 4 van 10 producten, dan weet je zeker dat in een vorige iteratie die overgebleven 6 ook al eens als 6+0 zijn geprobeerd (en de 5+1 varianten ook), dus die combinatie kan iig overgeslagen worden. Hoef je alleen nog maar naar 4+4+2 enzo te kijken.

Beginnen met winkels die (een groot deel van de) producten goedkoop aanbieden, en vervolgens voor de overige producten hetzelfde deelprobleem oplossen (soort dynamisch programmeren) zou goed kunnen werken.

Dat was al de basis van de werking van de huidige code, maar ik heb dat nu met deze nieuwe implementatie beter en efficienter aangepakt.

Voor een zo goedkoop mogelijke oplossing kun je waarschijnlijk al snel vele combinaties uitsluiten, bijvoorbeeld als [prijs-extra korting]>[prijs+kosten andere winkel].

En zoiets zit er inderdaad ook al in

Winkels die vanaf bedrag x korting geven, daar kun je nog suggereren om een (of meer) onzinproduct(en) erbij te bestellen, dat doe ik zelf in de praktijk ook wel eens.

Mja, dat soort suggesties ga ik maar niet proberen. Er is geen kennis van het feit dat als de persoon 1 euro meer zou besteden, dat ie dan 9 euro goedkoper uit is doordat de 10 euro verzendkosten dan vervallen. Wel is het zo dat sommige deelcombinaties dan dus 10 euro verzendkosten erbij kunnen krijgen en een anderen 0.

Kortom, hier is geen pasklare oplossing voor, maar ik denk dat je met een paar goede heuristieken wel snel (<0.1s) tot een aantal goede oplossingen kan komen..

Binnen 0.1 seconde lukt met kleine mandjes inderdaad prima. Vanaf 15 ofzo begint het toch wel lastiger te worden hoewel ik met jullie help en nog wat eigen tweaks ondertussen op mijn core2duo nog "maar" 1.3 seconde nodig heb om met mijn standaardparameters 17 producten te combineren. We hebben het namelijk dan al snel over 60+ winkels waarvan gelukkig slechts een klein deel grote deelverzamelingen kunnen leveren. Maar niettemin krijg je aardig wat potentiele combinaties.

[Nick The Heazk]

Ik denk niet dat het zinvol is om dit soort problemen exact op te lossen. Met een goed heuristisch algoritme kom je waarschijnlijk al een heel eind.

Zelf zou ik het volgende proberen:

Bepaal voor elk product de winkel met de laagste prijs
Zolang je zin hebt, doe:
Bepaal de winkel die het minste aantal producten aanlevert uit het winkelmandje. Indien er zo meerdere zijn, neem dan degene die de volgende stap de kost minimaliseert.
Plaats bestellingen voor alle producten bij de andere winkels in je huidige lijst van winkels (steeds bij de goedkoopste)


Op deze manier kun je eenvoudig winkelmandjes genereren die bij steeds minder winkels aangekocht kunnen worden. Met een aanvaardbare implementatie haal je hier een tijdscomplexiteit van O(n lg n) met n = max{ #producten, #winkels}.

[ Voor 7% gewijzigd door Nick The Heazk op 04-12-2009 18:01 ]

[ACM]

Ik begrijp niet zo goed hoe jouw algoritme werkt en vooral niet hoe je uiteindelijk het aantal leverende winkels minimaliseert en toch volledig gevulde order-voorstellen krijgt.

Daarbij komt nog dat we juist een voorkeur hebben voor zoveel mogelijk producten per winkel en dat de verzendkosten doorgaans juist doorslaggevend kunnen zijn voor welke winkel gekozen zou moeten worden, gezien het feit dat de prijzen van de individuele producten over het algemeen niet zo heel veel verschillen.

[Nick The Heazk]

Misschien is onderstaand skelet wat duidelijker.

code:

// Initial distribution of products
Pair<Shop, Product>[] shopOrderMapping = {};
Product[] productBasket = getUserSelection();
for(Product p : productBasket) {
   shopOrderMapping.add( Pair<Shop,Product>(p, getBestShopForProduct(p)) );
}

// Greedily improve
while( numberDifferentShops(shopOrderMapping) > whateverYouWant ) {
   // Apply heuristics in the selection here; for example if ultimately the price rose 
   // too much by selecting this shop, try to backtrack.
   Shop fewest = selectShopDeliveringFewestItemsToClient(shopOrderMapping);
   for( Product p : productsDeliveredByShop(fewest, shopOrderMapping) ) {
      // The best shop here can be heuristically defined.
      Shop bestForProduct = getBestShopToDeliverProductInSetOfActiveShops(shopOrderMapping, p);
      shopOrderMapping.add( Pair<Shop,Product>(p, bestForProduct) );
   }
   shopOrderMapping.deleteAllFromShop(fewest);
}

Dat dit het aantal winkels minimaliseert is nogal vrij wiedes. In elke stap neemt het aantal winkels waarbij je bestellingen plaats namelijk af met 1. Op deze manier genereer je #producten mogelijke manieren om je bestellingen te plaatsen (of meer, als je eventueel wil backtracken over winkels).

Men kan correct opmerken dat bovenstaand algoritme gevoelig is voor de initiële selectie van winkels. Dat klopt. Je kan dit eenvoudig remediëren door te vertrekken van een willekeurige initiële verdeling, waarbij de kans om een winkel te selecteren omgekeerd evenredig is met de gemiddelde prijs die hij voor elk product aanbiedt. Op die manier is het waarschijnlijker om winkels te selecteren die producten goedkoper aanbieden. Een verdere generalisatie van dit idee is om bovenstaand skelet te incorporeren in een genetisch algoritme. Op die manier zul je vast en zeker meer dan behoorlijke resultaten bekomen met relatief weinig rekenwerk.

Het berekenen van de exacte oplossing door alle combinaties te berekenen zou ik snel uit je hoofd zetten. Stel dat je p producten koopt en er N winkels zijn, dan is het aantal combinaties gelijk aan (met de vereenvoudiging dat elke winkel elk product kan leveren):

sum_{i=1}^{p} bincoeff(p,i) * bincoeff(N,i)

De verklaring hiervoor is als volgt. Je kunt het aantal winkels waarbij je wilt bestellen kiezen (i). Voor een vast aantal winkels i, heb je nog eens keuze uit N winkels waarbij je kunt bestellen. Je kunt deze op bincoeff(N,i) manieren combineren. Van zodra je de winkels gekozen hebt, kun je ook nog eens kiezen hoe je de producten verdeeld. Je kunt op nog eens bincoeff(p,i) manieren p producten verdelen over i winkels.

Om 15 producten te verdelen over pakweg 7 winkels heb je dus
bincoeff(15,7) * bincoeff(60,7) = (15! * 60! ) / (8!7! * 53!*7!) ~= 2,4852e12
mogelijke combinaties.

Maar om heel eerlijk te zijn is het niet echt waarschijnlijk dat iemand bij meer dan pakweg 5 winkels wilt bestellen natuurlijk . Dat geeft nog een erg aanzienlijk aantal combinaties, maar met slimme technieken is het nog wel haalbaar om het (bijna) exact uit te rekenen.

[ Voor 22% gewijzigd door Nick The Heazk op 05-12-2009 17:25 ]

[ACM]

Nick The Heazk schreef op zaterdag 05 december 2009 @ 16:56:
Misschien is onderstaand skelet wat duidelijker.

Ahzo, je vervangt uit de uiteindelijke uitleverende combinatie net zolang "kleine winkels" totdat je niet meer teveel winkels hebt.
Ook voor dit algoritme geldt dan dat het als nadeel heeft dat je maar 1 uiteindelijk resultaat terugkrijgt en dus de gebruiker in kwestie geen keuzemogelijkheden meer biedt

Stel dat je p producten koopt en er N winkels zijn, dan is het aantal combinaties gelijk aan (met de vereenvoudiging dat elke winkel elk product kan leveren):

Een van de redenen dat het redelijk te doen is om, binnen zekere grenzen, de beschikbare combinaties door te rekenen, is simpelweg dat niet alle winkels alle producten leveren.

[quoteOm 15 producten te verdelen over pakweg 7 winkels heb je dus
bincoeff(15,7) * bincoeff(60,7) = (15! * 60! ) / (8!7! * 53!*7!) ~= 2,4852e12
mogelijke combinaties.[/quote]
Ik geloof niet dat ik er zoveel uitrekenen voor 15 producten

Maar om heel eerlijk te zijn is het niet echt waarschijnlijk dat iemand bij meer dan pakweg 5 winkels wilt bestellen natuurlijk . Dat geeft nog een erg aanzienlijk aantal combinaties, maar met slimme technieken is het nog wel haalbaar om het (bijna) exact uit te rekenen.

Ik maak inderdaad vrij intensief gebruik van het feit dat men bij feedback over het algemeen aangeeft een voorkeur te hebben voor winkels die alle producten leveren. Daarom zijn de defaults bij mijn "alle combinaties doorrekenen"-code ook zodanig dat ik lang niet alle combinaties ook daadwerkelijk doorneem. Een groot deel valt af doordat dan domweg te veel winkels nodig gaan zijn om de gebruiker tevreden te stellen (ik begin dan ook aan de andere kant, met een zo vol mogelijke (deel)verzameling en kijk dan of het goedkoper kan).

Niettemin kan het vast handiger en/of (nog) efficienter, maar helaas ontbreekt het mij op zulk soort momenten dan toch wel een beetje aan wiskundige achtergrond. Misschien dat we het een keer als programmeerwedstrijd moeten brengen, heeft het gelijk nog een real-life gebruiksscenario ook

[momania]

Volgens mij kan je voor dit soort berekeningen/verdelingen ook een andere aanpak nemen: http://jgap.sourceforge.net/

Ik weet niet in hoeverre het echt bruikbaar zal zijn, maar ik zie er wel mogelijkheden in. Zelf zou ik het bv (gezien mijn vakgebied) wel eens op portfolio verdelingen en auto-hedging technieken willen toepassen.

[ACM]

momania schreef op zondag 06 december 2009 @ 09:14:
Volgens mij kan je voor dit soort berekeningen/verdelingen ook een andere aanpak nemen: http://jgap.sourceforge.net/

Ik weet niet in hoeverre het echt bruikbaar zal zijn, maar ik zie er wel mogelijkheden in. Zelf zou ik het bv (gezien mijn vakgebied) wel eens op portfolio verdelingen en auto-hedging technieken willen toepassen.

Uit hun beschrijving mbt genetic algoritms:

quote: http://jgap.sourceforge.net/doc/gaintro.html

However, in order for genetic algorithms to work effectively, a few criteria must be met:
* It must be relatively easy to evaluate how "good" a potential solution is relative to other potential solutions.
* It must be possible to break a potential solution into discrete parts that can vary independently. These parts become the "genes" in the genetic algorithm.
* Finally, genetic algorithms are best suited for situations where a "good" answer will suffice, even if it's not the absolute best answer.

Punt 1 en 3 is waar, maar punt 2 is door de manier waarop de kostenregels toegepast worden nog best lastig... als het uberhaupt mogelijk is.
[edit]
Hmm, daar is de fitness natuurlijk voor.

[Macros]

Ik zou pas naar genetische algoritmes gaan kijken wanneer een volledige oplossing niet meer snel genoeg kan worden doorgerekend. Genetische algoritmes gaan nogal slordig om met geheugen en cpu's en er is geen garantie dat de beste oplossing wordt gevonden.

[Wolfboy]

Macros schreef op zondag 06 december 2009 @ 17:53:
Ik zou pas naar genetische algoritmes gaan kijken wanneer een volledige oplossing niet meer snel genoeg kan worden doorgerekend. Genetische algoritmes gaan nogal slordig om met geheugen en cpu's en er is geen garantie dat de beste oplossing wordt gevonden.

Mee eens, genetische algoritmes zijn imho alleen een oplossing als je met een echt langdurig probleem zit of met veel voorkomende vergelijkbare oplossingen zodat je de oude resultaten direct kan hergebruiken.

Met een beetje slim afbakenen moet het ook brute force prima te doen zijn, alle opties uitrekenen is misschien ondoenlijk. Maar een slim algoritme zal al snel een aantal goede oplossingen kunnen "gokken" zonder alles te hoeven proberen.

[ACM]

Macros schreef op zondag 06 december 2009 @ 17:53:
Ik zou pas naar genetische algoritmes gaan kijken wanneer een volledige oplossing niet meer snel genoeg kan worden doorgerekend. Genetische algoritmes gaan nogal slordig om met geheugen en cpu's en er is geen garantie dat de beste oplossing wordt gevonden.

Ik heb net een basisimplementatie met een genetisch algoritme, op basis van momania's link, gemaakt. Echt heel veelbelovend is het vooralsnog niet. Het is in de gevallen dat mijn eigen code 'snel genoeg is' sowieso langzamer en het lijkt ook nog eens niet heel erg mogelijk om af te dwingen dat een resultaat ook daadwerkelijk geldig is, de fitness is daar niet helemaal geschikt voor zo lijkt het.
Bovendien is de grootte van de populatie nogal van invloed op het resultaat (en de tijd die ervoor nodig is) en heb je dan ook nog eens maar een resultaat... Ik geloof niet dat ik deze weg verder ga proberen uit te werken

Wolfboy schreef op zondag 06 december 2009 @ 19:27:
Maar een slim algoritme zal al snel een aantal goede oplossingen kunnen "gokken" zonder alles te hoeven proberen.

Je hebt in mijn geval sowieso de beschikking over zaken als de laagste prijs van een product, daardoor kan je vrij snel al met zekerheid stellen dat een bepaalde deelverzameling je geen nieuwe laagste combinatie gaat kunnen opleveren. Dat gecombineerd met een handige sortering van de mogelijke deelverzamelingen heeft me iig alweer 75% van de tijd bespaard in mijn test
Tenzij ik nog meer van dat soort ideeen krijg, geloof ik dat ik het voorlopig ook maar zo moet laten.

[ Voor 26% gewijzigd door ACM op 06-12-2009 19:42 ]

[Nick The Heazk]

ACM schreef op zondag 06 december 2009 @ 19:38:
[...]

Ik heb net een basisimplementatie met een genetisch algoritme, op basis van momania's link, gemaakt. Echt heel veelbelovend is het vooralsnog niet. Het is in de gevallen dat mijn eigen code 'snel genoeg is' sowieso langzamer en het lijkt ook nog eens niet heel erg mogelijk om af te dwingen dat een resultaat ook daadwerkelijk geldig is, de fitness is daar niet helemaal geschikt voor zo lijkt het.

In dit geval wil dat zeggen dat je implementatie niet erg goed is. Je kunt heel eenvoudig enkel individuen genereren die geldig zijn.

Stel bijvoorbeeld dat je als genetische data een mapping gebruikt van producten naar winkels. Om willekeurig een individu te maken kun je bijvoorbeeld alle bestelde producten overlopen. Je kijkt dan naar de lijst van winkels die het product kunnen aanleveren. Elk van deze winkels geef je een kans om geselecteerd te worden (omgekeerd evenredig met de prijs die je moet betalen voor het product bij die winkel--op deze manier is het waarschijnlijker om winkels te kiezen die het product goedkoop aanbieden). Vervolgens genereer je een uniform verdeeld willekeurig getal en selecteer je de overeenkomstige winkel. Op deze manier kun je eenvoudig geldige individuen genereren.

Ook het combineren (crossover) van twee individuen kan in dit geval op een logische wijze. Stel dat je bij twee goede individuen (hoge fitness) dezelfde mapping van product naar winkel tegenkomt voor een bepaald product. Het is duidelijk dat als twee goede individuen voor bepaalde items bij dezelfde winkel bestellen, dat je misschien best bij de offspring van die twee individuen de gemeenschappelijke mappings bewaart. Dus als individu 1 item I1 bestelt bij winkel W1 en individu 2 ook I1 bij W1 bestelt, dan laat je de kinderen ook best item I1 bij winkel I1 bestellen. Voor alle niet-gemeenschappelijke items zou je weer bovenstaande procedure kunnen gebruiken voor het willekeurig toekennen van de overgebleven producten.

Mutaties kun je ook heel eenvoudig toepassen zonder de geldigheid van een individu te schenden. Je gaat gewoon een of meerdere producten bij andere winkels bestellen (weer op de manier die helemaal boven beschreven staat).

Maw, als je zegt dat je GA niet werkt omdat je ongeldige individuen krijgt, dan heb je in dit geval niet zo'n slim GA ontworpen (en zou ik bijgevolg ook niet afgaan op zijn prestaties).

ACM schreef op zaterdag 05 december 2009 @ 23:32:
[...]
Ahzo, je vervangt uit de uiteindelijke uitleverende combinatie net zolang "kleine winkels" totdat je niet meer teveel winkels hebt.
Ook voor dit algoritme geldt dan dat het als nadeel heeft dat je maar 1 uiteindelijk resultaat terugkrijgt en dus de gebruiker in kwestie geen keuzemogelijkheden meer biedt

En

Nick The Heazk schreef op zaterdag 05 december 2009 @ 16:56:
Dat dit het aantal winkels minimaliseert is nogal vrij wiedes. In elke stap neemt het aantal winkels waarbij je bestellingen plaats namelijk af met 1. Op deze manier genereer je #producten mogelijke manieren om je bestellingen te plaatsen (of meer, als je eventueel wil backtracken over winkels).

[ACM]

Nick The Heazk schreef op maandag 07 december 2009 @ 11:04:
In dit geval wil dat zeggen dat je implementatie niet erg goed is. Je kunt heel eenvoudig enkel individuen genereren die geldig zijn.

Ik zal het vast niet heel goed gedaan hebben. Maar mijn basis-implementatie was een kwestie van per Gene een integer-bereik van 0 tot "#productprices - 1" wat dan correspondeerde met de verschillende prijzen die bij dat product mogelijk zouden moeten zijn.

Daarbij kreeg je natuurlijk ook combinaties die niet voldoen aan het criterium "maximaal 4 winkels" of waar winkels bij zitten die die combinatie van producten niet kunnen leveren door hoe de regels zijn opgesteld. De enige manier die ik zo snel zag om dat uberhaupt te communiceren was door domweg te stellen dat de fitness heel beroerd is.
Het kan natuurlijk zijn dat ik e.e.a. over het hoofd zag. Verder gaf ik de totaalprijs van de combinatie als fitness (met een DeltaFitnessEvaluator om een hogere fitness beroerder te laten zijn).
En dan kon er alsnog af en toe na met een populatie van 5000 en mijn fitnessmonitor die dan keek of de minimale fitness nog met minstens 0.1 (cent) verbeterde kreeg blijkbaar alsnog regelmatig dan niks beters dan enkel combinaties die niet konden...

Stel bijvoorbeeld dat je als genetische data een mapping gebruikt van producten naar winkels. Om willekeurig een individu te maken kun je bijvoorbeeld alle bestelde producten overlopen. Je kijkt dan naar de lijst van winkels die het product kunnen aanleveren. Elk van deze winkels geef je een kans om geselecteerd te worden (omgekeerd evenredig met de prijs die je moet betalen voor het product bij die winkel--op deze manier is het waarschijnlijker om winkels te kiezen die het product goedkoop aanbieden). Vervolgens genereer je een uniform verdeeld willekeurig getal en selecteer je de overeenkomstige winkel. Op deze manier kun je eenvoudig geldige individuen genereren.

Dit is dus wel ongeveer hoe ik het geimplementeerd had, met dien verstande dat ik het hele uitzoeken van varianten aan JGAP overliet en er dus ook (nog) geen waarschijnlijkheid was gekoppeld aan de prijs van de winkel.

Mutaties kun je ook heel eenvoudig toepassen zonder de geldigheid van een individu te schenden. Je gaat gewoon een of meerdere producten bij andere winkels bestellen (weer op de manier die helemaal boven beschreven staat).

Ik zag zo snel niet hoe ik bij JGAP kan afdwingen dat een bepaalde variant ook daadwerkelijk geldig is, maar wellicht dat dat dan een eigen Gene en/of Chromosome vereist. Daar had ik nog geen moeite in gestoken.

Maw, als je zegt dat je GA niet werkt omdat je ongeldige individuen krijgt, dan heb je in dit geval niet zo'n slim GA ontworpen (en zou ik bijgevolg ook niet afgaan op zijn prestaties).

Dat zal zeker, het was sowieso mijn eerste poging Niettemin blijft het zo dat GA niet echt ontworpen is om 'meerdere varianten' die voor de gebruiker logisch zijn aan te bieden; je wil tenslotte niet twee keer bijna dezelfde combinatie van W1, W2 en W3 zien die enkel verschillen omdat een product toevallig verschoven is van aanbieder en ze daardoor respectievelijk de beste en eenna beste gevonden combinatie waren.

Hoedanook, het blijft een interessante uitdaging dus wellicht dat ik de code nog een keer afstof en een variant bedenk waarbij per winkel een goede Chromosome eruit komt en ik vooraf al aan kan geven dat een Chromosome geldig is, zodat de FitnessFunction daar niet voor misbruikt hoeft te worden.

[pedorus]

Nick The Heazk schreef op maandag 07 december 2009 @ 11:04:
Maw, als je zegt dat je GA niet werkt omdat je ongeldige individuen krijgt, dan heb je in dit geval niet zo'n slim GA ontworpen (en zou ik bijgevolg ook niet afgaan op zijn prestaties).

In zijn algemeenheid staan evolutionaire algoritmes nou niet bekend om hun real-time prestaties, dus ik zou er evengoed niet al te veel tijd aan besteden... Daarnaast is puur EA een black-box methode, en kun je juist tijd besparen door te kijken hoe die box van binnen werkt. En dan heb je op het einde alsnog het probleem welke oplossingen je wilt tonen.

---

Ik denk dat het grootste probleem in de kostenstructuur zit. Als er alleen bij elke winkel altijd verzendkosten zijn, is het probleem zeer makkelijk. Als je winkels hebt geselecteerd, kies je gewoon overal de laagste prijs. Aangezien je maximaal bij zo'n 4 winkels besteld, en zo'n 60 winkels hebt, heb je dus slechts zo'n 500.000 combinaties om af te gaan (bereken hier). Als je de winkels nog een beetje handig sorteert, kom je al snel tot hele goede resultaten. Eventueel kun je ook nog een algoritme als dat van Nick hierboven gebruiken om ook een soort allergoedkoopste oplossing te berekenen. Of juist een soort winkel-toevoegen algoritme.

Hoeveel winkels zijn er met echt gekke regels, nu 4allclients failliet is? Welke regels zijn er allemaal? Het lijkt me het beste om die regels zoveel mogelijk in het algoritme te krijgen. Een soort black-box aanpak is architectonisch wel leuk, maar in de praktijk niet zo snel.

Edit: Hou je trouwens ook rekening met levertijden?

[ACM]

pedorus schreef op maandag 07 december 2009 @ 12:29:
Hoeveel winkels zijn er met echt gekke regels, nu 4allclients failliet is? Welke regels zijn er allemaal? Het lijkt me het beste om die regels zoveel mogelijk in het algoritme te krijgen. Een soort black-box aanpak is architectonisch wel leuk, maar in de praktijk niet zo snel.

Er zijn er helaas nog wel een paar, Zercom rekent bijvoorbeeld 1 euro per product bovenop de vaste kosten. Verder zijn er winkels die bijvoorbeeld tot 250 euro een bepaald bedrag aan verzendkosten rekenen en daarboven gratis zijn. Daarnaast heb je vooral voor creditcard- en remboursbetalingen vaak percentages van de totaalprijs met een bepaalde startwaarde.
Kortom het toevoegen van een specifiek product is niet altijd even duur

Edit: Hou je trouwens ook rekening met levertijden?

Nee. Sowieso levert nog lang niet elke winkel levertijdindicaties aan.

[Wolfboy]

Eventueel zou je het geheel zelfs nog om kunnen schrijven naar een standaard minilaiseringsprobleem waarmee je gewoon de simplexmethode zou kunnen gebruiken. Het probleem is natuurlijk alleen dat je zo'n enorme hoeveelheid variabelen kan krijgen dat het in sommige gevallen niet meer berekenbaar is (in een redelijke hoeveelheid tijd).

Levertijden zouden overigens wel een erg fijne feature zijn hierbij, als je dat meeneemt kan je het probleemgebied nog heel wat verder beperken

[pedorus]

ACM schreef op maandag 07 december 2009 @ 12:56:
[...]

Er zijn er helaas nog wel een paar, Zercom rekent bijvoorbeeld 1 euro per product bovenop de vaste kosten.

Dat is niet zo erg: voordat het algoritme plaatsvind, gewoon overal 1 euro bij optellen..

Verder zijn er winkels die bijvoorbeeld tot 250 euro een bepaald bedrag aan verzendkosten rekenen en daarboven gratis zijn.

Dit zijn interessante gevallen. Ik zou bijhouden per winkel of dit gehaald wordt. Als dit niet gehaald wordt, maar gezien de totaalprijs wel gehaald had kunnen worden, dan opslaan in een (gesorteerd) lijstje/boompje met eventueel later te onderzoeken gevallen.

Daarnaast heb je vooral voor creditcard- en remboursbetalingen vaak percentages van de totaalprijs met een bepaalde startwaarde.

Ook gewoon gelijk optellen bij de productprijzen als dit is geselecteerd. Het wordt pas vervelend als je iets hebt als max(2% verkoopprijs, 10) ofzo.

Nee. Sowieso levert nog lang niet elke winkel levertijdindicaties aan.

Zou evengoed een leuke functie kunnen zijn, en een reden voor bedrijven om die informatie wel aan te leveren. Lijkt me belangrijker dan creditcard/rembours. En als je simpelweg combinaties uitsluit, is dit nog eenvoudig te implementeren ook (net als het uitsluiten van bepaalde winkels).

Maar snap ik nu goed dat alle data voor dit probleem als volgt op te slaan is?

Java:

//alle prijzen in centen; Integer.MAX_VALUE bij niet beschikbaar
int [#winkels][#producten] prijs; //incl. vaste (percentuele) opslagen/product
int [#winkels] verzendkosten;
int [#winkels] geenVerzendkostenVanaf;
int [#winkels] overigeKosten; //oa rembours, creditcard

Of zijn er nog meer dingen om rekening mee te houden?

Wolfboy schreef op maandag 07 december 2009 @ 13:33:
Eventueel zou je het geheel zelfs nog om kunnen schrijven naar een standaard minilaiseringsprobleem waarmee je gewoon de simplexmethode zou kunnen gebruiken.

Ik gok dat dit dan evengoed de NP-complete variant wordt met branch-and-bound als je alle constraints erin zet... Maar dan nog komt er sowieso maar 1 oplossing uit.

[Wolfboy]

pedorus schreef op maandag 07 december 2009 @ 14:00:
Ik gok dat dit dan evengoed de NP-complete variant wordt met branch-and-bound als je alle constraints erin zet... Maar dan nog komt er sowieso maar 1 oplossing uit.

Waarschijnlijk, maar het branch-and-bound algoritme is prima om de mogelijke oplossingen op te slaan

[ACM]

pedorus schreef op maandag 07 december 2009 @ 14:00:
Dat is niet zo erg: voordat het algoritme plaatsvind, gewoon overal 1 euro bij optellen..

Per voorbeeld is het inderdaad simpel te bepalen wat er precies moet gebeuren Maar alle mogelijke situaties voorspellen maakt het lastiger.
Overigens heb ik - in de complete variant voor max 16 producten - het uitrekenen van de kosten en het proberen van varianten van de originele mandjes opgesplitst in mijn huidige algoritme. Worst case levert dat tenslotte "maar" #winkels * 2^#producten aan "kosten-berekeningen" op, die ik dan gelijk kan opslaan als goedkoopste leverancier voor een gegeven combinatie van producten. In de praktijk is het veel minder dan die worst-case.
Bij een 16-producten testcase gaat het dan om minder dan 100 milliseconde voor dat deel, inclusief het ophalen van de prijsdata uit de database.

Daarna heb ik in de tweede stap van mijn algoritme alleen nog maar met die goedkoopste en reeds opgenomen winkels te maken. Als zo'n goedkoopste winkel voor een deelverzamleling ook reeds opgenomen was... dan is dat een combinatie die reeds in een iteratie een niveau hoger toch al aan bod is gekomen.
Die stap hangt helaas heel erg sterk af van de hoeveelheid producten die de grootste deelverzameling moet bevatten. De tijd nam ruwweg 5x toe bij een testcase van 16 producten voor elk product extra. Dat begint met 14 uit 16 in 15 milliseconde, maar liep naar 40 minuten op bij 5 uit 16. Desalniettemin veranderde de combinatie met de laagste prijs toen al een tijdje niet meer en gaan de overige varianten steeds meer op die ene goedkoopste lijken, dus echt zinvol is het niet om zo ver te gaan.

Ook gewoon gelijk optellen bij de productprijzen als dit is geselecteerd. Het wordt pas vervelend als je iets hebt als max(2% verkoopprijs, 10) ofzo.

In principe is dat ook mogelijk... Hoewel ik geen idee heb of dat ook voorkomt. Er zijn iig vrij complexe situaties mogelijk met de diverse kostenregels.

Zou evengoed een leuke functie kunnen zijn, en een reden voor bedrijven om die informatie wel aan te leveren. Lijkt me belangrijker dan creditcard/rembours. En als je simpelweg combinaties uitsluit, is dit nog eenvoudig te implementeren ook (net als het uitsluiten van bepaalde winkels).

Klopt, maar het icoontje bij producten is natuurlijk al een aardige indicator. Overigens zou een triviale variant natuurlijk kunnen zijn om een harde grens op te laten geven, zodat je gewoon de prijzen niet ophaalt waarbij bekend is dat het te lang gaat duren. Scheelt ook weer in de rekentijd

Of zijn er nog meer dingen om rekening mee te houden?

Nou... Rembours wordt bijvoorbeeld vaak maar tot een bepaald maximumbedrag gedaan (1000 euro ofzo). Het is bovendien mogelijk dat regels wel over de losse productprijzen gaan, maar niet over de verder gemaakte kosten - of juist wel. Of dat we transportkosten-data vanuit de aangeleverde feeds inlezen en die gebruiken ipv de vaste regels. Het is overigens wel zo dat voor de standaard verzend- en betaalmethodes het meestal vrij eenvoudig is.
Verder worden de regels per groep op volgorde verwerkt en zodra er een matched wordt de rest niet meer gedaan. Waardoor het ook niet altijd triviaal is om de regels tot een stel simpele integerwaarden om te zetten.
Zoals eerder al genoemd kan een en ander vrij complex worden en dan is deze berekencode zelfs al wat vereenvoudigd tov wat er werkelijk allemaal mogelijk is.
Overigens optimaliseer ik de code intern al zodat ie er voor de kostenberekeningen meestal niet heel veel rekenwerk gedaan hoeft te worden. De belangrijkste reden dat die berekeningen tijd kosten is omdat ze domweg heel erg vaak gedaan moeten worden (wat dus redelijk beperkt wordt door bovenstaande opsplitsing).

Ik gok dat dit dan evengoed de NP-complete variant wordt met branch-and-bound als je alle constraints erin zet... Maar dan nog komt er sowieso maar 1 oplossing uit.

Op zich is 1 oplossing nog niet zo erg, mits het dan maar enigszins efficient en bruikbaar voor "elke winkel" opnieuw te doen is. Als ik altijd in 0.01 seconde een "optimale variant waarbij winkel Wx de boventoon voert" krijg.. ben ik ook tevreden. Dan is het geen probleem om dat tot 60x te doen om vervolgens die optimale resultaten te vergelijken

[pedorus]

ACM schreef op maandag 07 december 2009 @ 14:46:
Per voorbeeld is het inderdaad simpel te bepalen wat er precies moet gebeuren Maar alle mogelijke situaties voorspellen maakt het lastiger.

Dat klopt, maar ik heb toch het vermoeden dat een simpel model makkelijker optimaliseert dan een black-box model op de winkelkostenstructuur. Op zich hoeft het simpele model niet altijd te kloppen, zolang het maar een zeer goede indicatie geeft. Voor de meeste gevallen lijkt me dit niet zo moeilijk.

Overigens heb ik - in de complete variant voor max 16 producten [...]

De BBG's gaan enkel al zomaar naar 18 producten, dus ik vrees dat dit lastig schaalt. Wel een originele invalshoek overigens om de product-combinaties/winkel voor te berekenen; ik dacht al waar komen die bits vandaan.

Overigens zou een triviale variant natuurlijk kunnen zijn om een harde grens op te laten geven, zodat je gewoon de prijzen niet ophaalt waarbij bekend is dat het te lang gaat duren. Scheelt ook weer in de rekentijd

Precies, 2x winst.

Nou... Rembours wordt bijvoorbeeld vaak maar tot een bepaald maximumbedrag gedaan (1000 euro ofzo).

offtopic:
1000 euro cash klaarhebben..

Tsja, dit lijkt me een losstaand probleem met die betaalmethode. Dan moet je 2 bestellingen bij dezelfde winkel gaan aanraden ofzo, of het juist opsplitsen over meerdere winkels? Lijkt me allemaal veel moeite voor iets dat weinig voorkomt.

Het is bovendien mogelijk dat regels wel over de losse productprijzen gaan, maar niet over de verder gemaakte kosten - of juist wel. Of dat we transportkosten-data vanuit de aangeleverde feeds inlezen en die gebruiken ipv de vaste regels.

Deze 2 zaken lijken me nog net te modeleren in het door mij voorgestelde model.

Verder worden de regels per groep op volgorde verwerkt en zodra er een matched wordt de rest niet meer gedaan. Waardoor het ook niet altijd triviaal is om de regels tot een stel simpele integerwaarden om te zetten.

Een lastig probleem inderdaad: het huidige model is eigenlijk te luxe uitgevoerd. Toch denk ik dat versimpeling enigszins onvermijdelijk is als je snelle resultaten wil hebben. Het lijkt me het handigst dat de versimpeling altijd somber uitpakt, waarna je op het allerlaatst de boel nog even narekent en het echte antwoord laat zien.

Op zich is 1 oplossing nog niet zo erg, mits het dan maar enigszins efficient en bruikbaar voor "elke winkel" opnieuw te doen is. Als ik altijd in 0.01 seconde een "optimale variant waarbij winkel Wx de boventoon voert" krijg.. ben ik ook tevreden. Dan is het geen probleem om dat tot 60x te doen om vervolgens die optimale resultaten te vergelijken

Ik heb het sterke vermoeden dat 0.01 seconden bij lange na niet gehaald zal worden, ook niet als je het model eerst hebt versimpelt, wat dan evengoed zal moeten gebeuren. Overigens heeft Wolfboy gelijk dat je met een aangepast branch-and-bound-algoritme zelfs meerdere oplossingen kan genereren; ik weet enkel niet of er bestaande libraries zijn die dit ook doen en of er dan wat zinnigs uit zal komen. Normaal worden de meeste 'branches' niet geheeltallig en zijn ze daardoor niet valide.

[ACM]

pedorus schreef op maandag 07 december 2009 @ 22:20:
Op zich hoeft het simpele model niet altijd te kloppen, zolang het maar een zeer goede indicatie geeft. Voor de meeste gevallen lijkt me dit niet zo moeilijk.

Klopt. Maar dan moet je wel weer goed kunnen weten wanneer je geen grote fouten gaat maken

De BBG's gaan enkel al zomaar naar 18 producten, dus ik vrees dat dit lastig schaalt. Wel een originele invalshoek overigens om de product-combinaties/winkel voor te berekenen; ik dacht al waar komen die bits vandaan.

Dat zijn er voor mij 17, een product dat meerdere keren voorkomt zie ik niet als meerdere losse En rara waar komen mijn hiervoor genoemde testcases met 17 vandaan?

Lijkt me allemaal veel moeite voor iets dat weinig voorkomt.

Doe ik dan ook niet, uiteindelijk zal er wel een advies uitkomen waarbij je in veelvouden van maximaal 1000 euro bij verschillende winkels de boel koopt...

Een lastig probleem inderdaad: het huidige model is eigenlijk te luxe uitgevoerd.

Klopt, helaas is het gemodeleerd op basis van het feit dat elke winkel weer wat anders kan verzinnen en het in sommige gevallen ook daadwerkelijk doet.

Ik heb het sterke vermoeden dat 0.01 seconden bij lange na niet gehaald zal worden, ook niet als je het model eerst hebt versimpelt, wat dan evengoed zal moeten gebeuren.

Sja, helaas is het bedoeld om als onderdeel van een webpagina te worden getoond... Dus dan zit je gewoon met "harde" grenzen waarbij men er niet meer op wil wachten en/of er zelfs browsertimeouts optreden. Een algoritme dat een minuut aan het rekenen is, is gewoon niet zo goed bruikbaar voor het beoogde publiek

Bij voorkeur zet je binnen een seconde een compleet resultaat op het scherm.

[pedorus]

ACM schreef op dinsdag 08 december 2009 @ 13:56:
Dat zijn er voor mij 17, een product dat meerdere keren voorkomt zie ik niet als meerdere losse En rara waar komen mijn hiervoor genoemde testcases met 17 vandaan?

Stel we willen 17 verschillende producten kopen, waarvan product 1 twee keer. We hebben 2 winkels:
winkel 1: product 1 kost 100 euro, alle andere producten kosten 1 euro; verzendkosten 10 euro alleen bij bedrag<100 euro.
winkel 2: alle producten kosten 95 euro, geen verzendkosten
Het is nu natuurlijk vrij duidelijk dat de goedkoopste oplossing een opsplitsing zal worden, en dat lukt alleen als je het als 18 producten ziet.

Bij voorkeur zet je binnen een seconde een compleet resultaat op het scherm.

Het kan wel, maar met optimale resultaten en alle mogelijke kostenregels meenemen wordt het enigszins onmogelijk. Persoonlijk zou ik dus, op basis van mijn eigen ervaringen, gaan voor een zo simpel mogelijk kostenmodel, dat dan maar niet altijd klopt. Een andere mogelijkheid is het om wel een global search-algoritme te gebruiken op het volledige model, maar redelijk snel te stoppen met zoeken, waardoor je vanwege de tijd alsnog sub-optimale resultaten krijgt, waarschijnlijk zelfs slechter.

Overigens denk ik dat het al heel mooi is als je snel (zeg 0.1-1 sec) een aantal mogelijkheden kan bekijken. Dat het dan niet optimaal is vanwege rare bijkomende kostenstructuren bij sommige winkels lijkt me minder relevant. Desnoods laat je die gekke winkels geheel buiten beschouwing behalve bij alles-bij-1-winkel resultaten; gezien de resultaten uit het verleden is het toch al geen aanbeveling..

[Juup]

ACM schreef op dinsdag 08 december 2009 @ 13:56:
Bij voorkeur zet je binnen een seconde een compleet resultaat op het scherm.

Bij voorkeur zet je binnen 100ms nuttige info op het scherm (de winkelmand zelf) en vul je dat later aan met je winkeladvies.

Niets zo irritant als steeds 2 seconden te moeten wachten terwijl je alleen wilt weten of je al een harddisk in je winkelmans hebt zitten.

[ACM]

pedorus schreef op dinsdag 08 december 2009 @ 14:44:
Stel we willen 17 verschillende producten kopen, waarvan product 1 twee keer. We hebben 2 winkels:
winkel 1: product 1 kost 100 euro, alle andere producten kosten 1 euro; verzendkosten 10 euro alleen bij bedrag<100 euro.
winkel 2: alle producten kosten 95 euro, geen verzendkosten
Het is nu natuurlijk vrij duidelijk dat de goedkoopste oplossing een opsplitsing zal worden, en dat lukt alleen als je het als 18 producten ziet.

Zegt de persoon die de kostenregels zelf dan maar wil vereenvoudigen... Gelukkig is het scenario dat je schetst zeer ongebruikelijk, de prijzen liggen zelden (verhoudingsgewijs) zo ver uit elkaar.
Mijn algoritme zou dus inderdaad op die 15*1 + 2x100 of 15*1+10 + 2x95 uitkomen en dus 5 euro duurder dan het absoluut goedkoopste voorstel komen.

Persoonlijk zou ik dus, op basis van mijn eigen ervaringen, gaan voor een zo simpel mogelijk kostenmodel, dat dan maar niet altijd klopt. Een andere mogelijkheid is het om wel een global search-algoritme te gebruiken op het volledige model, maar redelijk snel te stoppen met zoeken, waardoor je vanwege de tijd alsnog sub-optimale resultaten krijgt, waarschijnlijk zelfs slechter.

Ik hou het voorlopig bij mijn huidige algoritme dat met de meest gebruikte "kleine mandjes" behoorlijk snel (<1s) resultaten weet te produceren en daarboven een alternatief algoritme dat meer een algemene indicatie geeft. Misschien dat ik nog probeer dat algoritme voor de grotere manden te vervangen door een van de voorstellen zoals hier.

Desnoods laat je die gekke winkels geheel buiten beschouwing behalve bij alles-bij-1-winkel resultaten; gezien de resultaten uit het verleden is het toch al geen aanbeveling..

Hehe, ik geloof niet dat ik dat kan maken Maar er komt sowieso een optie om specifieke winkels uit te sluiten, dus je kan het als gebruiker iig makkelijker sturen.

Juup schreef op dinsdag 08 december 2009 @ 16:09:
Niets zo irritant als steeds 2 seconden te moeten wachten terwijl je alleen wilt weten of je al een harddisk in je winkelmans hebt zitten.

Eens, ik overweeg nog om de initiele interne time-out korter te zetten. Afgezien daarvan is het straks sowieso (weer) mogelijk om de inhoud van je winkelmand te bekijken, los van de kostenberekening. Dus je hoeft niet per se naar die bestelkostenpagina om die check te doen.

[TheWickedD]

ACM schreef op dinsdag 08 december 2009 @ 18:40:
Eens, ik overweeg nog om de initiele interne time-out korter te zetten. Afgezien daarvan is het straks sowieso (weer) mogelijk om de inhoud van je winkelmand te bekijken, los van de kostenberekening. Dus je hoeft niet per se naar die bestelkostenpagina om die check te doen.

Volgens mij zeg je het hier al, maar dit lijkt mij een goed idee:
maak een knop "bereken optimale productverdeling" ofzo en voer alleen de berekening uit als men op die knop klikt. Dan kun je ook laten weteen dat het een paar seconden duurt en die paar seconden heb je dan ook omdat je je zwaardere serverbelasting per berekening kunt veroorloven wanneer die berekening minder vaak wordt uitgevoerd (knop i.p.v. altijd).