Performanceeinbruch beim Finden von Partitionen

Nicht nur die Schleifenanzahl an sich ist ein Problem.

Die Gesamtkosten müssten 50^8 * 10 * 5 * 50^8 * (50^8/2) für findVec(8, 10, 50) sein. Sprich 10^42. Das ist schon ne ganze Menge.

Sagen wir, meine CPU würde 4 x 10^9 Instruktionen pro Sekunde schaffen, dann reden wir von 10^27 Tagen.

Für findVec(8, 10, wären es aber nur 8^8 * 10 * 5 * 8^8 * (8^8/2) = 10^23, das müsste in 10^8 bis 10^9 Tagen machbar sein. Nur gibt es logischerweise dafür gar keine Lösung...

@Fragender sagte in Performanceeinbruch beim Finden von Partitionen:

Die Gesamtkosten müssten 50^8 * 10 * 5 * 50^8 * (50^8/2) für findVec(8, 10, 50) sein.

Wohlgemerkt, im worst case!

So, jetzt nochmal genauer zu den Zeiten. Zumindest für i=5 habe ich nun ein Ergebnis:

1
1 
Runtime: 0 milliseconds.
2
1 4 
Runtime: 0 milliseconds.
3
1 4 13 
Runtime: 27 milliseconds.
4
1 4 13 32 
Runtime: 3040 milliseconds.
5
1 4 13 32 71
Runtime: 326936 milliseconds.

#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;

struct VectorHash
{
    size_t operator()(const vector<int> &v) const
    {
        hash<int> hasher;
        size_t seed = 0;
        for (int i : v)
        {
            seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

void incrementVecp(vector<int> &vecp, int *ip, const int n1, const int n2)
{
    vecp[*ip]++;
    if (vecp[*ip] == n2)
    {
        while (*ip >= 0 && vecp[*ip] == n2)
        {
            vecp[*ip] = 0;
            (*ip)--;
            if (*ip >= 0)
            {
                vecp[*ip]++;
            }
        }
        if (*ip >= 0)
        {
            *ip = n1 - 1;
        }
    }
}

bool isConfictFree(vector<int> &gramm, const int n)
{
    for (int n1 = 1; n1 <= n; n1++)
    {
        for (int n2 = n1; n2 <= n; n2++)
        {
            vector<int> v1(n1, 0);
            vector<int> v2(n2, 0);
            for (int i1 = n1 - 1; i1 >= 0;)
            {
                for (int i2 = n2 - 1; i2 >= 0;)
                {
                    vector<int> v3 = v1;
                    vector<int> v4 = v2;
                    sort(v3.begin(), v3.end());
                    sort(v4.begin(), v4.end());
                    if (v3 != v4)
                    {
                        int sum1 = 0;
                        int sum2 = 0;
                        for (int v : v3)
                        {
                            sum1 += gramm[v];
                        }
                        for (int v : v4)
                        {
                            sum2 += gramm[v];
                        }
                        if (sum1 == sum2)
                        {
                            return false;
                        }
                    }
                    incrementVecp(v2, &i2, n2, gramm.size());
                }
                incrementVecp(v1, &i1, n1, gramm.size());
            }
        }
    }
    return true;
}

void findVec(const int n1, const int n2, const int maxVal)
{
    vector<int> v(n1, 0);
    for (int i = n1 - 1; i >= 0;)
    {
        if (isConfictFree(v, n2))
        {
            for (int j : v)
            {
                cout << j << " ";
            }
            cout << endl;
            return;
        }
        incrementVecp(v, &i, n1, maxVal);
    }
}

uint64_t timeSinceEpochMillisec()
{
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}

int main(int argc, char const *argv[])
{
    uint64_t startTime, endTime, totalTime;
    for (int i = 1; i <= 5; i++)
    {
        cout << i << endl;
        startTime = timeSinceEpochMillisec();
        findVec(i, 3, 75);
        endTime = timeSinceEpochMillisec();
        totalTime = endTime - startTime;
        cout << "Runtime: " << totalTime << " milliseconds." << endl;
    }
    return 0;
}

Wenn man einfach mal davon ausgehen würde, dass sich die Reihe nach dem Muster fortsetzt, also dass eine Erhöhung von i um 1 (i+1) 100-mal so viel Zeit in Anspruch nehmen würde, dann wäre man für i=8 bei 83 Tausend Stunden.

Für i=8 müsste man maxVal aber wahrscheinlich sehr viel höher als nur 75 wählen ...

Ich hoffe, das Problem ist nun zumindest einigermaßen klar beschrieben.

E: Und dann noch was, 1 4 13 32 sieht immer gleichbleibend aus, aber das muss so nicht sein, das ist nur eine mögliche Lösung ... 1 4 15 24 wäre ebenso eine denkbare Lösung für i=4.

@ all : Ich hab ein bisschen optimiert und bin jetzt schon bei i=7!:

#include <algorithm>
#include <numeric>
#include <unordered_set>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;

// struct VectorHash
// {
//     size_t operator()(const vector<int> &v) const
//     {
//         hash<int> hasher;
//         size_t seed = 0;
//         for (int i : v)
//         {
//             seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
//         }
//         return seed;
//     }
// };

void incrementVecp(vector<int> &vecp, int *ip, const int n1, const int n2)
{
    vecp[*ip]++;
    if (vecp[*ip] == n2)
    {
        while (*ip >= 0 && vecp[*ip] == n2)
        {
            vecp[*ip] = 0;
            (*ip)--;
            if (*ip >= 0)
            {
                vecp[*ip]++;
            }
        }
        if (*ip >= 0)
        {
            *ip = n1 - 1;
        }
    }
}

bool areVecsNotEquals(const vector<int> &v1, const vector<int> &v2)
{
    if (v1.size() == v2.size())
    {
        vector<int> v3 = v1;
        vector<int> v4 = v2;
        sort(v3.begin(), v3.end());
        sort(v4.begin(), v4.end());
        return v3 != v4;
    }
    return true;
}

bool isNotEqualsAndEqualWeighted(const vector<int> &v1, const vector<int> &v2, const vector<int> &gramm)
{
    if (areVecsNotEquals(v1, v2))
    {
        int sum1 = 0;
        int sum2 = 0;
        for (int v : v1)
        {
            sum1 += gramm[v];
        }
        for (int v : v2)
        {
            sum2 += gramm[v];
        }
        return sum1 == sum2;
    }
    return false;
}

bool isConfictFree(vector<int> &gramm, const int n)
{
    for (int n1 = 1; n1 <= n; n1++)
    {
        for (int n2 = n1; n2 <= n; n2++)
        {
            vector<int> v1(n1, 0);
            vector<int> v2(n2, 0);
            for (int i1 = n1 - 1; i1 >= 0;)
            {
                for (int i2 = n2 - 1; i2 >= 0;)
                {
                    if (isNotEqualsAndEqualWeighted(v1, v2, gramm))
                    {
                        return false;
                    }
                    incrementVecp(v2, &i2, n2, gramm.size());
                }
                incrementVecp(v1, &i1, n1, gramm.size());
            }
        }
    }
    return true;
}

void findVec(const int n1, const int n2, const int maxVal)
{
    vector<int> v(n1, 1);
    v[0] = 1;
    v[1] = 4;
    v[2] = 13;
    v[3] = 32;
    v[4] = 71;
    for (int i = n1 - 1; i >= 0;)
    {
        if (isConfictFree(v, n2))
        {
            for (int j : v)
            {
                cout << j << " ";
            }
            cout << endl;
            return;
        }
        incrementVecp(v, &i, n1, maxVal);
    }
}

uint64_t timeSinceEpochMillisec()
{
    using namespace std::chrono;
    return duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count();
}

int main(int argc, char const *argv[])
{
    uint64_t startTime, endTime, totalTime;
    for (int i = 5; i <= 7; i++)
    {
        cout << i << endl;
        startTime = timeSinceEpochMillisec();
        findVec(i, 3, 555);
        endTime = timeSinceEpochMillisec();
        totalTime = endTime - startTime;
        cout << "Runtime: " << totalTime << " milliseconds." << endl;
    }
    return 0;
}

5
1 4 13 32 71 
Runtime: 9 milliseconds.
6
1 4 13 32 71 124 
Runtime: 112 milliseconds.
7
1 4 13 32 71 124 218
Runtime: 58180 milliseconds.

Der Trick war: Nicht mit 0,0,... anzufangen, sondern zumindest mit 1,1,...

Bleibt natürlich noch das Problem, dass 1, 4, 13, 32 usw. zwar valide, aber nicht optimal sein muss (wie weiter oben bereits erwähnt).

Jockelx

@Fragender Das ist alles so wirr....
Ich dachte i wäre n1 und das ist die maximale Anzahl der Münzen?
Wie kann denn dann 1 und 4 zur Lösung gehören?
Du hast 4 Gramm..welche Münzen hast du?

Hier noch eine alternative Lösung für i=7.

7
1 4 13 32 74 127 195 
Runtime: 52999 milliseconds.

@Jockelx sagte in Performanceeinbruch beim Finden von Partitionen:

@Fragender Das ist alles so wirr....
Ich dachte i wäre n1 und das ist die maximale Anzahl der Münzen?
Wie kann denn dann 1 und 4 zur Lösung gehören?
Du hast 4 Gramm..welche Münzen hast du?

n1=Anzahl der Münzen, für die jeweils eine Grammanzahl gefunden werden soll
n2=Anzahl der Münzen, bis zu der ich Münzen auf die Waage legen kann
maxVal=Maximales Gewicht einer Münze in Gramm

1 und 4 gehört zur Lösung, wenn n2=3 gilt...

1 =1
4 =4
1 1 =2
1 4 =5
4 4 =8
1 1 1 =3
1 1 4 =6
1 4 4 =9
4 4 4 =12

Das wären die unterschiedlichen Kombinationen für n2=3 ... (du siehst, jedes Gesamtgewicht ist eindeutig).

Jockelx

~~Okay, aber dann wäre doch eine triviale Lösung sowas:~~

Hier stand quatsch. Langsam verstehe ich das Problem erst.

@Jockelx Ich hab mal etwas gegoogelt:

https://oeis.org/search?q=1%2C4%2C13%2C32&language=german&go=Suche

https://oeis.org/A051912

a(n) is the smallest integer such that the sum of any three ordered terms a(k), k <= n, is unique.

Aber nur für "three ordered terms"...

Ich suche ja bis zu "ten" "ordered terms" für n=8...

Eine praktische Anwendung wäre: Ich suche an der Supermarktkasse "Klein"geld heraus, lege es der/dem Kassierer:in auf eine Waage und es wird sofort der Gesamtbetrag, der gegeben wurde, angezeigt.

*john 0

Das ganze hört sich verdächtig nach dem Rucksackproblem an, und das ist doch NP-vollständig. Falls Du keinen Fehler gemacht haben solltest, wird man zwar die Geschwindigkeit einzelner Abschnitte verbessern können, aber die schlechte Skalierung über N ist typisch für NP-vollständige Probleme.

Ja, gut, es ist eins der Rucksackprobleme. Ich hatte mich vor Jahren schon mal mit dem Rucksackproblem "beschäftigt", es aber dann ruhen lassen, weil mich zu viele Leute abgelenkt hatten.

Zwei (Pardon: drei) Fragen hab ich aber noch:

A) Wieso gibt es zwei n-Parameter, also n1 und n2? Haben klassische Rucksackprobleme nicht nur einen Größe-Parameter?
\B) Kann ich den Algo noch weiter optimieren, oder ist das nun endoptimiert? Abgesehen von heuristischen Ansätzen und so natürlich.
C) Ist das wirklich ein NP-vollständiges Problem? Oder sieht das nur so aus?^^

E: Ich persönlich gehe davon aus, dass p!=np tatsächlich gilt, aber beweisen möchte ich das natürlich net.

Also, ich lasse das nun ruhen ... Eigentlich hatte ich heute eh meinen digital detox Tag ... daraus ist auch nicht viel geworden. Außerdem kann man bei den Temperaturen nicht wirklich sehr produktiv sein. 21.5 °C wäre im Sommer optimal, aber eine Klimaanlage hab ich auch net.

Bin dann mal off, by by.