getal zoeken in optelling van max. 3 getallen uit verzam.

[remvs]

Beste wiskundigen,

Ik ben software ontwikkelaar in bedrijfsautomatiseringen.
Ik werk aan een systeem dat o.a. binnenkomende betalingen van klanten matched met uitstaande facturen.
Als gevolg van heel specifieke eisen, ik zal de functionele aspecten hier achterwege laten, heb ik het volgende probleem waarvoor ik een wiskundige oplossing zoek.

ik heb een bedrag A. en ik heb een verzameling bedragen V.
Ik wil weten of bedrag A te vormen is uit een optelling van 1,2 of 3 bedragen uit verzameling V.

Voorbeeld:
bedrag A:
2,13

verzameling B:
1,09
3,00
1,45
0,68
1,13

Hierbij is de uitkomst dus TRUE, omdat 1,45 en 0,68 samen 2,13 vormen.

Omdat vervameling V erg groot kan zijn en de berekening vele duizenden keren uitgevoerd moet worden wil ik niet dmv brute computer rekenkracht alle mogelijke combinaties aflopen.

Is er een manier om de hoeveelheid computer rekenwerk significant te verminderen door een wiskundig slimmigheidje erop los te laten? het zou erg helpen wanneer we de verzameling V link kunnen inperken bijvoorbeeld.

Zelf heb gespeeld met het meest rechtse getal van bedrag A, in dit geval dus 3 (2,13). Er zijn maar een beperkt aantal bedragen uit verzameling V die in een sequentie van 1,2 of 3 een rusultaat kunnen hebben eindigend op 3. ( naar mijn idee 0,1,3,4, ahh helaas, je moet ook combinaties zoeken die 13 of 23 opleveren).... Dit is dus niet een heilzame oplossing, maar mijn gevoel zegt dat er wellicht wel een andere oplossing is.

Ik ben benieuwd of iemand me opweg kan helpen met een denkrichting of wiskundige benadering!

alvast bedankt!

remvs

[arie]

Ik zou in eerste instantie eens experimenteren met een gesorteerde lijst V.
Als V nog niet gesorteerd is kan dit snel doen met quicksort: http://nl.wikipedia.org/wiki/Quicksort,
is V eenmaal gesorteerd kan je daarin snel zoeken (en zo nodig ook nieuwe openstaande rekeningen toevoegen) via een binary search: http://en.wikipedia.org/wiki/Binary_search_algorithm.

Het binaire zoeken gaat erg snel (orde log(N)) en wil je vervolgens zo veel mogelijk benutten.
Maak daarbij voor A onderscheid in 1, 2 of 3 bedragen.

[1] A bestaat uit 1 bedrag: dat bedrag kan je nu direct zoeken via een binaire search op V

[2] A bestaat uit 2 bedragen: a1 en a2. Neem aan dat a1<=a2
Dan kan a1 maximaal de helft zijn van A, in jouw voorbeeld:
a1<=1.06
a2>=1.07.
Kijk dan waar deze grens ligt in je gesorteerde lijst V:
0.68
1.09
1.13
1.45
3.00
In dit geval ligt de grens tussen 0.68 en 1.09 (ook weer te vinden met een binary search),
en splitst V in V1=[0.68] en V2=[1.09, 1.13, 1.45, 3.00]
Zoek dan het kleinste gedeelte (hier V1) af met een lineaire search, de 2e waarde is hier dan a2=A-a1 die je kan zoeken met een binaire search in V2 (de grootste deellijst).
Zou A gelijk zijn aan 3.68, dan is a1<=1.84 en a2>=1.84, splitst V in V1=[0.68, 1.09, 1.13, 1.45] en V2=[3.00], waardoor V2 de kleinste verzameling is en je die lineair gaat doorzoeken op a2, en vervolgens V1 binair op a1=A-a2.

[3] A bestaat uit 3 bedragen: a1, a2 en a3. Neem aan dat a1<=a2<=a3
Het kleinste bedrag=a1 kan maximaal gelijk zijn aan een derde van A, in dit geval a1<=0.71.
Het grootste bedrag=a3 moet groter of gelijk zijn aan A/3, hier is dus a3>=0.71.
Je krijgt dan: a1 in V1=[0.68] en a3 uit V3=[1.09, 1.13, 1.45, 3.00], waardoor je lineair gaat zoeken op a1.
Voor elke mogelijke waarde van a1 (hier alleen 0.68) bereken je dan A-a1 = 2.13-0.68 =1.45.
En dit kan weer op de manier van situatie [2] met als nieuw streefbedrag (A-a1).
Let daarbij wel op dat a2 ook in V1 kan liggen, maar dat nog wel a2>=a1 moet gelden.
Als V3 kleiner is dan V1 kan je a3 lineair zoeken in V3 en situatie [2] toepassen op V tot aan a3 met streefbedrag (A-a3).
Bijvoorbeeld: A=4.77, dan moet a1<=1.59 dus in V1=[0.68, 1.09, 1.13, 1.45] en a3>=1.59 dus in V3=[3.00].
Lineair zoeken in V3, in dit geval alleen a3=3.00, dus A-a3=1.77, zoek dit vervolgens in V tot aan 3.00 (a2 kan ook in V2 liggen). Je weet nu a1<=1.77/2 dus a1<=0.88, waarna a1 in V1'=[0.68] en a2 in V2=[1.09, 1.13, 1.45]. Doorzoek nu V1' lineair en V2 binair.

Kom je hiermee verder?

[remvs]

Beste Arie,

Dank voor je uitgebreide uitleg!

Het sorteren is geen probleem. Je uitleg is helder en lijk m.i. op het binair zoeken.
De stelling dat bij 2 bedragen, 1 van die bedragen maximaal de helft van dat bedrag kan zijn is een hele goeie en zeker wel bruikbaar.

Wanneer ik me deze oplossing voorstel in code vraag ik me af of, en hoe groot het netto runtime voordeel gaat zijn. de tijd die ik bespaar met minder loopjes, weegt die nog wel op tegen de sortering en het binaire zoeken in de (sub)sets? Tijd voor een empirisch experimentje achter de knoppen dus!

Dank voor de input en ik houd je op de hoogte

remvs

[remvs]

LS,

Heb vanavond een test programma in elkaar gedraaid dat bovenstaande methode implementeerd.
Ik heb een iets afwijkende logica toegpast, voor details zie het commentaar (beginnend met een *) in onderstaande code)

- Als verzameling V heb ik 1000 random getallen genomen (bedragen met 2 decimalen)
- met name de stap waarbij 2 getallen het bedrag moeten vormen heb ik getest

Hierop heb ik wat metingen gedaan, met de volgende resultaten;
- een gemiddelde 'hit' kost minder dan 10000 cycles.
- 10000 cycles kost netto (enkel het zoeken in de tabel gemeten) ongeveer 0,3 seconden.

Daarna heb ik de niet geopitmaliseerde methode getest.
Het aantal bendodigde cycles was een factor 2 tot 3 hoger, maar....
De netto runtime hierovoor was beduidend lager; voor 20000 cycles was slechts 0,01 seconde nodig.

de gebruikte variabelen in mijn test komen redelijk overeen met de werkelijke aantallen.
In het 'eggie' word deze berekening dagelijks ongeveer 3000 keer uitgevoerd in een nachtelijk batch verwerking. dit resultaaerd in een looptijd van maximaal 0,3 * 3000 = een kwartiertje. Dit is ruim acceptabel.

Samenvattend; De geoptimaliseerde methode is wiskundig beter maar geeft in CPU geen voordeel.
De variant waarbij 3 getallen de combinatie maken is gevoelsmatig wel significant meer werk.
Echter staat hier tegen over dat (en dit heb ik verzuimd te melden in mn eerste bericht) ik de verzameling V ook opgesplitst kan aanleveren in 3 verzamelingen waarbij uit elke verzameling 0 of 1 waarde gekozen dient te worden. Dit verzacht de pijn weer dermate waardoor ik verwacht dat het uiteindelijk niet veel meer effort kost.

Ik zal later bezien welke methode ik toepas; wiskundige schoonheid kan het nl. niet persee winnen van heldere, goed onderhoudbre code.

Dank Arie, voor je hulp. Het was leuk en leerzaam!
remvs


Voor de code-nerds onder ons;
hieronder de code. Het is een programeertaal welke voor de meeste exotisch zal zijn, maar wel te begrijpen. Ofschoon de gebruikte hardware meer CPU's heeft dan ik IQ punten draait onderstaand op 1 CPU/thread.
metingen zijn dus redelijk hardware onafhankelijk te noemen

Code: Selecteer alles

*&---------------------------------------------------------------------*
*& Report  ZZ_VERZAMELING
*&
*&---------------------------------------------------------------------*
*&
*&
*&---------------------------------------------------------------------*

REPORT  zzjoris_verzameling.
TYPES lt_f TYPE packed10.

CONSTANTS lc_100 TYPE packed10 VALUE '100.00'.
CONSTANTS lc_getal TYPE packed10 VALUE '36.34'.

DATA lt_verzameling TYPE STANDARD TABLE OF packed10.
FIELD-SYMBOLS <ls_verzameling> LIKE LINE OF lt_verzameling.
FIELD-SYMBOLS <ls_helft> LIKE LINE OF lt_verzameling.
DATA ls_verzameling LIKE LINE OF lt_verzameling.
DATA l_i TYPE i.
DATA l_f TYPE packed10..

DATA l_time TYPE timestampl.
DATA l_time_pre TYPE timestampl.
DATA l_time_diff TYPE timestampl.
DATA l_output  TYPE string.


GET TIME STAMP FIELD l_time.
l_time_pre = l_time.

DO 10000 TIMES.
* Random getal < 9999
  CALL FUNCTION 'QF05_RANDOM_INTEGER'
    EXPORTING
      ran_int_max = 9999
      ran_int_min = 1
    IMPORTING
      ran_int     = l_i.

* Delen door 100 en opslaan als float in tabel
  l_f = l_i.
  ls_verzameling = l_f / lc_100.
  APPEND ls_verzameling TO lt_verzameling.

ENDDO.


SORT lt_verzameling.

********************************************
**  Routine 1 getal
********************************************
READ TABLE lt_verzameling WITH KEY lc_getal ASSIGNING <ls_verzameling>
                                            BINARY SEARCH.
IF sy-subrc = 0.
* Gevonden!
  WRITE: / 'Korting in 1 bedrag gevonden op. ', <ls_verzameling>,
           ' op index ', sy-tabix.
  RETURN.
ENDIF.

*PERFORM time.

********************************************
*  Routine 2 getallen.
********************************************
DATA l_idx_helft TYPE i.
DATA l_idx_2 TYPE i.
DATA l_vlag TYPE c.
DATA l_aant_subreads TYPE i.
* Indien lc_getal gevormd moet worden uit twee getallen,
* dan is zeker dat 1 van beide kleiner is of gelijk aan
* de helft van dat getal (en de andere dus groter).
* vb: LC_GETAL = 37, dan kan het kleinste van de twee getallen
* A maximaal 37/2 = 18 zijn In dat geval kun je volstaat het
* dus om voor het kleine getal A1 dus slechts de eerste
* helft van de gesorteerde tabel te doorlopen (in dit geval alles <= 18)
* en daarbij op zoek te gaan naar getal A2 in slehts de tweede
* helft van de tabel ( > 18) 

* helft van Getal bepalen
l_f = lc_getal / 2.

* Positie van deze 'helft' in tabel
* (waar pos. -1 < helft en pos. + 1 > 'helft')
READ TABLE lt_verzameling ASSIGNING <ls_verzameling> INDEX 1.
WHILE <ls_verzameling> < l_f.
  READ TABLE lt_verzameling INDEX sy-index ASSIGNING <ls_verzameling> .
ENDWHILE.
IF sy-subrc = 0.
* Index van 'helft' in tabel
  l_idx_helft = sy-tabix.
ENDIF.

* Main loop over eerste helft van tabel
WHILE sy-index <= l_idx_helft AND l_vlag = abap_false.

  READ TABLE lt_verzameling INDEX sy-index ASSIGNING <ls_verzameling>.
* Sub-loop; Zoek in tweede helft naar match
  LOOP AT lt_verzameling ASSIGNING <ls_helft> FROM l_idx_helft.
*   Het te zoeken getal in tweede helft (impliciet, eerste helft foorloopt ie ook)
    l_f = lc_getal - <ls_verzameling>.
    READ TABLE lt_verzameling WITH KEY l_f  TRANSPORTING NO FIELDS BINARY SEARCH.
    l_aant_subreads = l_aant_subreads + 1.
    IF sy-subrc = 0.
*    gevonden!!!
      WRITE: / '2 getallen gevonden ', <ls_verzameling>,  ' en ', l_f, ' maken samen ', lc_getal.
      PERFORM time.
      l_vlag  = abap_true.
      EXIT.
    ENDIF.
  ENDLOOP.

ENDWHILE.
WRITE:/ l_aant_subreads.
PERFORM time.





*BREAK-POINT.






*&---------------------------------------------------------------------*
*&      Form  time
*&---------------------------------------------------------------------*
*       text
*----------------------------------------------------------------------*
FORM time.
  GET TIME STAMP FIELD l_time.
  l_time_diff = l_time - l_time_pre.
  l_output =  |{ l_time_diff TIMESTAMP = USER TIMEZONE = 'UTC   ' }|.
  l_time_pre = l_time.
  WRITE: / l_output.
ENDFORM.                    "time

[Sjoerd Job]

Even een vraag:

Sorteer je eerst de lijst, en dan meerdere malen een zoek opdracht, of doe je meerdere malen (sorteren, dan zoekopdracht).

De efficientie vraagt natuurlijk om het eerste.

[remvs]

Sjoerd,

Ik sorteer eenmalig. De tabel V is namelijk niet aan verandering onderhevig. Meerdere malen sorteren is derhalve zinloos.

groet
remvs