Algorithme suggesties?

Scan A en B en maak een tabel met alle mogelijke waarden van O.
En tegelijk tel hoevaak elke O voorkomt.
Dan scan de O lijst.

Goeie! Met de lijstlengtes veel kleiner dan het aantal mogelijke "O" waardes, is dat VEEL beter. Nu gaat het wel hard. Als dit goed werkt doe ik het mogelijk voortaan ook met A-lijsten van duizenden. Met in dit geval een B-lijst van 46k zit je dan ook al snel met miljoenen mogelijke O-waardes. En als je een eenvoudige "O-lijst" als lijst implementeert is dat dus voor iedere mogelijke O-waarde een scan van de lijst om het record te vinden. Kwadratisch met het aantal O-waardes. Oeps. Dat loopt uit de klauwen. Een array met de telling van de O-waardes is dan sneller.

Ja, wel lastig dat je verschillende algoritmes moet gebruiken, afhankelijk van de grootte van de lijsten.

Daarom had ik direct de "huidige aantallen" genoemd zodat opties die bij die aantallen slecht werken uitgefilterd kunnen worden.

De sets van A en B waarbij A+O=B hebben de eigenschap dat de verschillen tussen de getallen van beide sets gelijk moeten zijn, of een veelvoud van een constante over beide sets.

Ik zou beide sets sorteren en de verschillen tussen de opvolgende getallen bepalen, dat weer sorteren en bekijken of er een gemene factor zit in die getallen.

Het lastige is dat twee getallen die een veelvoud van een gemene factor uit elkaar liggen, niet perse een geldige oplossing vormen; stel dat A = 10, B = 13 dus O = 3, dan zou A = 13 en B = 19 en mogelijke oplossing lijken (allebei een verschil van een veelvoud van 3), maar niet zijn.

Ik denk dat dit een mogelijke oplossing kan zijn, maar daar is nog wel wat werk voor nodig. Het voordeel is dat dit lineair schaalt, en niet als het product van A en B, zoals het verschil tussen elke combinatie bepalen.

Als je weet dat O relatief klein is, kun je wellicht de zoekruimte beperken.

Op 7 februari 2021 19:11:35 schreef SparkyGSX:
De sets van A en B waarbij A+O=B hebben de eigenschap dat de verschillen tussen de getallen van beide sets gelijk moeten zijn, of een veelvoud van een constante over beide sets.

Ik zou beide sets sorteren en de verschillen tussen de opvolgende getallen bepalen, dat weer sorteren en bekijken of er een gemene factor zit in die getallen.

Het probleem is dat als

A =   23      25      36  40  55
B =  123 124 125 130 136 140 155

Dan is O=100 een "perfecte" oplossing (alle elementen in A hebben een match). Maar door dat er in B een waarde tussen zit, worden "2" en "11" als verschil tussen opeenvolgende waardes in B niet gevonden.

Maar je hebt gelijk. Mogelijk is dit in de praktijk voldoende zeldzaam dat deze strategie werkt.

Oh... Nu snap ik hem. Jij dacht dat die extra 256 een gemeenschappelijke factor in alle getallen is geweest. Nee dat is niet zo! Die factor die was er wel (4096) maar had ik al met de had er uitgedeeld.

Als je weet dat O relatief klein is, kun je wellicht de zoekruimte beperken.

Nee, Ik weet dat O minder dan 200 miljoen is. ("Relatief klein" voor relatief grote waardes van "klein". Er is een getal dat heet "The monster". Da's pas een groot getal.).

Yay, Conway!

--
Meester (strikvraag): 'Wat denk je dat het grootste getal is?'
Jantje: 'Ehmmm... honderdduizendmiljoen?'
Meester (triomfantelijk): 'Ah! Maar wat denk je dan van... honderdduizendmiljoen en één?'
Jantje: 'Nou, dan zat ik er in elk geval toch dicht bij.'

Sorteer A en B.

Dan voor iedere mogelijke O:

Kijk hoeveel elementen B heeft tussen min(A)+O en max(A)+O.

Dat is de score voor die O.

Je kunt je lookups versnellen doordat je weet dat ze incrementeel zijn met toenemende O.

Je kunt het ook pipelinen:
-Bepaal posities in B van min(A)+n (=PBmin(n))
-Bepaal posities in B van max(A)+n (=PBmax(n))
-Bepaal PBmax(n)-PBmin(n).

Omdat opeenvolgende waarden van PMMin(n) en PBmax(n) dicht bij elkaar zullen liggen, zal waarschijnlijk leuk werken op een CPU met een cache.

Oke, dit werkt niet want er kunnen heel veel niet matchende elementen in dat stuk van de set zitten.
Hooguit kan het helpen in bepalen welk stuk van B je moet bekijken.

[Bericht gewijzigd door blurp op maandag 8 februari 2021 02:26:42 (14%)

Na een dagje puzzelen... Ik DENK dat dit probleem om te schrijven is naar "knapsack" en dat ie dus "NP compleet" is. Zodra deze stelling bewezen is, dan is degene die een efficient algorithme vind wereldberoemd. (en heb je dus een "efficient algorithme" gevonden voor een HELE hoop andere problemen waar de afgelopen 50 jaar niemand een efficient algorithme voor heeft kunnen vinden).

Dat wil niet zeggen dat er geen "redelijke" oplossingen zijn.

Een bekend NP compleet probleem is het "traveling salesman problem": Een handelsreiziger wil een aantal plekken bezoeken en terwijl alle afstanden tussen ieder paar plekken bekend is, wil ie een rondreis langs alle plekken maken en liefst zo min mogelijk afstand afleggen. Formeel zijn alle NP complete problemen als ja/nee vraag gesteld, dus formeel is de vraag kan het in minder dan XXX afstand. Als de kortste route 75.000 km is en ik vraag: "kan het in minder dan 75.001 km?" dan is de ja/nee vraag equivalent met het vinden van die 75.000 route.

Ik heb in 1987 een algorithme geschreven wat gebruik maakte van de geometrische eigenschap dat in de gezochte route geen kruisingen zitten. Op mijn 8086 deed die er zo'n 60 sec over op de voorbeeld-case achter in het boek. Dit leverde precies de juiste oplossing op, maar niet een bewijs dat het de beste oplossing was. De schrijvers van het boek hadden een 60 sec op een cray gehuurd om dat bewijs te leveren.

Ik denk dat er met heuristieken hier ook heel snel een behoorlijke oplossing te vinden valt.

Dit zoekt "soort van binair". Eerst alles met de onderste n bitjes gelijk aan nul, dan pas met alle getallen met maar n-1 laagste bitjes nul:

  for (p=0;p<63;p++)
    if ( (1<<p) > maxO) break;
  p--;
  calcO (1 << p);
  for (p--;p>=0;p--) {
    for (o=1<<p; o < maxO;o+= 2*(1<<p))
      calcO (o);
  }

Dit is redelijk algemeen dat ie "calcO" aanroept met alle getallen tussen 0 (oeps! Vergeten! nul komt niet aan de beurt!) en maxO. Niet "wiskundig mooi" is dat er 1 calcO, en voor nul moet er nog een extra, buiten de loop staat.

Dit had mijn O in 0.4% van wat ie nu heeft staan rekenen zullen vinden omdat mijn O een 256-voud bleek te zijn.