Algoritme voor samenvoegen positieve en negatieve integers?

[Verwijderd]

Ik heb een hele lange lijst met (miljarden) integers (32-bit signed) met omstebeurt een positief getal en dan een negatief getal, bijvoorbeeld:

code:

10
-2
10
-1
12
-59
40
-2
1
-2
34
-10
10

Wat is nu nodig heb is een algoritme om deze nummers zo veel mogelijk samen te voegen om zo groot mogelijk positieve nummers te krijgen, dus in dit voorbeeld wil ik de volgende output genereren:

code:

29
-59
71
-10
10

Is dit een veelvoorkomend probleem waar misschien standaard algoritmes voor bestaan? Of heeft iemand tips hoe ik dit het beste kan aanpakken om de beste performance te realiseren?

[armageddon_2k1]

Ik snap je voorbeeld niet helemaal, moet het geen: 29, -59, 81, -10, 10 zijn?

[Henk007]

Zou je je doel iets preciezer kunnen opschrijven met een formule? Op deze manier is het erg onduidelijk hoe je van set A naar set B in je voorbeeld komt.

[ Voor 19% gewijzigd door Henk007 op 22-08-2017 17:14 ]

[Verwijderd]

armageddon_2k1 schreef op dinsdag 22 augustus 2017 @ 17:09:
Ik snap je voorbeeld niet helemaal, moet het geen: 29, -59, 81, -10, 10 zijn?

Nee, volgens mij klopt het toch?

40 - 2 = 38
38 + 1 = 39
39 - 2 = 37
37 + 34 = 71

[armageddon_2k1]

Check, ik was niet scherp.

[Verwijderd]

Henk007 schreef op dinsdag 22 augustus 2017 @ 17:12:
Zou je je doel iets preciezer kunnen opschrijven met een formule? Op deze manier is het erg onduidelijk hoe je van set A naar set B in je voorbeeld komt.

Ik weet eerlijk gezegd niet hoe ik dit in een formule kan gieten, ben helaas niet erg goed in wiskunde. Op dit moment weet ik alleen hoe ik het handmatig kan doen en op een hele brute-force manier in code, maar dit zou heel erg traag worden.

Wat ik tot nu toe van plan was is om meerdere keren over de lijst heen te gaan en elke keer proberen om twee positieve getallen (en het tussenliggende negatieve getal) samen te voegen mits het resultaat groter is dan elk van de positieve getallen op zich.

[Henk007]

Volgens mij komt dit in de buurt:
Wiki maximum subarray problem

(Op een of andere manier lukt copy past niet in deze browser)
Het daarin genoemde algoritme is O(n)
Lees ook het wiki artikel: Subset sum problem

[ Voor 25% gewijzigd door Henk007 op 22-08-2017 17:34 ]

[Verwijderd]

Ik ga dat eens allemaal rustig doornemen, bedankt!

[emnich]

Verwijderd schreef op dinsdag 22 augustus 2017 @ 16:59:
Wat is nu nodig heb is een algoritme om deze nummers zo veel mogelijk samen te voegen om zo groot mogelijk positieve nummers te krijgen, dus in dit voorbeeld wil ik de volgende output genereren:

code:

29
-59
71
-10
10

Maar waarom kies je hiervoor en niet bijv voor:

code:

29
-59
71

m.a.w. wanneer besluit je dat het getal groot genoeg is?

[g0tanks]

emnich schreef op dinsdag 22 augustus 2017 @ 17:43:
[...]

Maar waarom kies je hiervoor en niet bijv voor:

code:

29
-59
71

m.a.w. wanneer besluit je dat het getal groot genoeg is?

-10 en +10 blijven toch gewoon over van de originele lijst? Je kan er niks mee doen om hoger uit te komen dan 71.

[Verwijderd]

Wat g0tanks zegt klopt inderdaad, ze blijven over (en moeten ook behouden blijven) en ze kunnen niet verder samengevoegd worden om tot een groter getal te komen.

[LightningBullet]

Nvm. Mijn gedachte was incorrect. Ik sloeg een belangrijke stap over...

[ Voor 135% gewijzigd door LightningBullet op 22-08-2017 19:39 ]

[Reptile209]

Uit nieuwsgierigheid: wat stellen de getallen voor? Dat helpt misschien in het kiezen van het juiste algoritme. En hoe belangrijk is het dat je de beste oplossing vindt? Mag het ook 'close enough' zijn?

En moet je dit continu/elk uur/elke dag/eenmalig doen? Bij regelmatig gebruik wil je snel zijn, maar als het eenmalig of zelden is, kan je gewoon number crunching doen, boeien dat je dan een half uurtje op het resultaat moet wachten.

Tot slot nog een vraag over je randvoorwaarde van "zo groot mogelijk". Hoe weet je dat je moet stoppen, en dat er na je voorbeeld niet een +40 komt waarmee de som van alle getallen opeens het grootst zou worden? Of zal dat pas blijken als je de hele serie gezien hebt?

[Verwijderd]

Ik kan niet echt zeggen wat de getallen voorstellen, behalve dat het komt uit afbeeldingen. Het is wel belangrijk dat de data correct is, dus geen schattingen.

In principe is het on-demand, dus hoe sneller hoe beter, omdat dit voor een prettigere user experience zorgt.

Je weet in principe pas wat de grootst mogelijke combinatie is zodra je de hele reeks hebt doorlopen.

Ik ben nu bezig om met Kadane's algoritme (via Henk007's link) een versie te maken die snel genoeg is. Deze gaat door de reeks heen, haalt elke keer de grootste range eruit, en splits vervolgens de array op in twee arrays (stuk voor en het stuk na de gevonden range) en herhaal dit vervolgens totdat alle mogelijke combinaties zijn getest. Ik hoop dat dit een beetje snel is (<1 seconde).

[Mijzelf]

Is het niet gewoon

code:

som = 0;
while( true )
{
     geltal = LeesVolgendGetal();
     nieuwe_som = som + getal;
     if( nieuwe_som < 0 )
     {
         print som
         print getal;
         som = 0;
     }
     else
     {
         som = nieuwe_som;
     }
}

[Flipull]

Mijzelf schreef op woensdag 23 augustus 2017 @ 11:27:
Is het niet gewoon[code]som = 0;
[...]

Ik denk het niet. Van elke reeks, de som getallen die het grootst zal zijn, moet volgens mij als eerst gedaan worden. Als je dat niet doet, dan kan het zijn dat je deze grootste som niet meer kan behalen, omdat je een deel van de nodige getallen al gebruikt hebt in andere (voorgaande) sommen.


De TS kan uit de lijst het kleinste en grootste getal pakken en die als minimum stellen voor de nieuwe som. Dit is voor uitzonderingssituaties waar blijkt dat 1 getal een grotere (of kleinere) som is, dan elk andere mogelijke som in de lijst.

Om alle sommen te bepalen moet je O(n^2) doen ofzo

code:

som (item 0)
kijk of het het grootst of het kleinst is, en sla het op
som (item 0 + item 1)
kijk of het het grootst of het kleinst is, en sla het op
[...]
som (item 0 + item 1 + [...] + item n-1)
kijk of het het grootst of het kleinst is, en sla het op
[...]
som (item 1)
kijk of het het grootst of het kleinst is, en sla het op
[...]
som (item 1 + [...] + item n-1)
kijk of het het grootst of het kleinst is, en sla het op
[...]
som (item n-2)
kijk of het het grootst of het kleinst is, en sla het op
som (item n-2 + item n-1)
kijk of het het grootst of het kleinst is, en sla het op
[...]
som (item n-1)
kijk of het het grootst of het kleinst is, en sla het op

(Hopelijk duidelijke uitleg waarom ik n^2 zie)


[edit]
Ow, je hebt geen negatieve antwoorden nodig, zie ik nu
En iemand die me kan uitleggen hoe je hier O(n) van maakt?

[ Voor 4% gewijzigd door Flipull op 23-08-2017 11:58 ]

[breew]

Ik zou beginnen in R, met de adagio-package..
https://cran.r-project.org/web/packages/adagio/adagio.pdf

maxsub finds a contiguous subarray whose sum is maximally positive. This is sometimes called
Kadane’s algorithm.
maxsub will use a compiled and very fast version with a running time of O(n) where n is the length
of the input vector x.
maxsub2d finds a (contiguous) submatrix whose sum of elements is maximally positive. The approach
taken here is to apply the one-dimensional routine to summed arrays between all rows of A.
This has a run-time of O(n^3), though a run-time of O(n^2 log n) seems possible see the reference
below.
maxsub2d uses a Fortran workhorse and can solve a 1000-by-1000 matrix in a few seconds—but
beware of biggere ones