4. Vector/Liste (Eingabe/Ausgabe) - Beschleunigung gewünscht, Algorithmus gesucht

Vector/Liste (Eingabe/Ausgabe) - Beschleunigung gewünscht, Algorithmus gesucht

  • S

    Hi ihr,

    mich plagt ein vorweihnachtliches Problem, und zwar sind

    Gegeben:
    - Menge A enthält alle n Punkte,
    - Menge B enthält k Punkte aus A, (0 ≤ k ≤ n) (in B landen alle Werte zwischen zwei Grenzwerten)
    - erfolgte an allen Punkten aus B eine Berechnung, werden in B Punkte entfernt und ergänzt

    Gesucht:
    Da B weniger Punkte enthält als A, soll die Berechnung an diesen wenigen Punkten natürlich um einiges schneller vonstatten gehen, als die Berechnung an allen Punkten aus A.

    Bisher:
    Ich hab es in etwa, wie unten angegeben implementiert und mußte leider feststellen, dass die Berechnung über B ca. 4x so lang dauert, wie über alle Punkte aus A. Ich tüftel nun an einer sinnvollen Lösung und weil mir so langsam die Ideen ausgehen, habe ich beschlossen, hier mal anzufragen. Fände es supertoll, wenn Ihr mir ein paar Tipps geben könntet. Vielleicht noch ein kleiner Anhaltpunkt bzgl. der Werte: |A| = n = 500.000 und |B| = 150.000

    Im Voraus tausend Dank,
    Stefan

    PS: Ich wünsch allen schonmal schöne Weihnachtsfeiertage und einen fleißigen :xmas1: !!!
    PPS: Und hier der

    + Berechnung einer Startlösung & Füllen von B (StdLib:Vector)
+ Wiederhole (
    + Berechnung über alle Punkte B
    + Schreibe alle Punkte, deren Werte zwischen den Limites liegen in einen temporären Vektor
    + Leere B
    + Füge alle Punkte aus dem temporären Vektor & alle unmittelbare Nachbarn in B 
    + Leere temporären Vektor
  )

    bzw.

    std::vector<int> viActiveNodes;       // Aktive Punkte (B)
std::vector<int> viTmpActiveNodes;    // Temporärer Vektor
std::vector<int>::iterator vitANCnt;  // Iterator

double* adLimits;                     // Limites
adLimits[0] = -5.0
adLimits[1] = 5.0               

int n;                                // Anzahl aller Punkte
double* adValues;                     // Vektor der Werte an allen Punkten
int neighbour;                        // Temporär (Benachbarter Punkt)

// [..]

for (int i=0;i<n;i++) {
  adValues[i] = StartSolution(i);

  if ((adValues[i] > adLimits[0]) and (adValues[i] < adLimits[1])) {
    viActiveNodes.push_back(i);
  }
}

for (int z=0; z<=100; z++) {
  for (vitANCnt = viActiveNodes.begin(); vitANCnt != viActiveNodes.end(); vitANCnt++) {
    i = *vitANCnt
    adValues[i] = F(adValues[i]);

    if ((adValues[i] > adLimits[0]) and (adValues[i] < adLimits[1])) {
      viTmpActiveNodes.push_back(i);
    }
  }

  viActiveNodes.clear();

  for (vitANCnt = viTmpActiveNodes.begin(); vitANCnt != viTmpActiveNodes.end(); vitANCnt++) {
    i = *vitANCnt;

    for (int j=-1; j<=1; j++) {
      neighbour = getneighbour(i,j);
      // Wenn Punkt noch nicht in "B" vorhanden, füge hinzu
      if (!(find(viActiveNodes.begin(),viActiveNodes.end(),neighbour) != viActiveNodes.end())) {            
        viActiveNodes.push_back(neighbour);
      }
    }
  }

  viTmpActiveNodes.clear();
}
    0
  • C

    Die Punkte, die bei der Berechnung neu hinzukommen, waren doch vorher nicht in B - also mußt du auf jeden Fall alle Punkte in A aktualisieren. Und da dürfte es einfacher sein, direkt mit allen Punkten zu arbeiten.

    PS:

    double* adLimits;                     // Limites
adLimits[0] = -5.0
adLimits[1] = 5.0

    Autsch - das solltest du besser nicht machen, wenn dir dein System lieb ist. (im günstigsten Fall schmiert dein Programm sofort ab, wahrscheinlicher ist aber, daß du irgenetwas tiefgreifenderes zerstörst)

    0
  • S

    CStoll schrieb:

    Die Punkte, die bei der Berechnung neu hinzukommen, waren doch vorher nicht in B - also mußt du auf jeden Fall alle Punkte in A aktualisieren. Und da dürfte es einfacher sein, direkt mit allen Punkten zu arbeiten.

    Naja, ich berechne mir ja die Startlösung über alle Punkte aus A. Mit der Zeit nähern sich alle Werte einem der Limites. Sobald die Werte also die Unter- oder Obergrenze erreicht haben, müssen Sie eigentlich nicht mehr berücksichtigt werden. Daher suche ich nach einer Lösung, die nur die relevanten Punkte berechnet. Ich denke, es muß auch einen Weg geben, die 150.000 Punkte wesentlich schneller zu berechnen, als die 500.000.

    CStoll schrieb:

    PS: [..] Autsch - das solltest du besser nicht machen, wenn dir dein System lieb ist. (im günstigsten Fall schmiert dein Programm sofort ab, wahrscheinlicher ist aber, daß du irgenetwas tiefgreifenderes zerstörst)

    Ähm, Danke, ich hab mir den Code aus einigen Klassen zusammen gesucht, da hab ich wahrscheinlich nicht ALLES übernommen, es muß natürlich heißen:

    double* adLimits;                     // Limites
adLimits = new double[2];
adLimits[0] = -5.0
adLimits[1] = 5.0

    Besser? 😃

    0
  • C

    serialize schrieb:

    CStoll schrieb:

    Die Punkte, die bei der Berechnung neu hinzukommen, waren doch vorher nicht in B - also mußt du auf jeden Fall alle Punkte in A aktualisieren. Und da dürfte es einfacher sein, direkt mit allen Punkten zu arbeiten.

    Naja, ich berechne mir ja die Startlösung über alle Punkte aus A. Mit der Zeit nähern sich alle Werte einem der Limites. Sobald die Werte also die Unter- oder Obergrenze erreicht haben, müssen Sie eigentlich nicht mehr berücksichtigt werden. Daher suche ich nach einer Lösung, die nur die relevanten Punkte berechnet. Ich denke, es muß auch einen Weg geben, die 150.000 Punkte wesentlich schneller zu berechnen, als die 500.000.

    Besteht denn überhaupt die Möglichkeit, daß ein Punkt irgendwann nachträglich in den relevanten Bereich (zurück)kommt? Oder sind alle Punkte außerhalb der Limits definitiv "aus dem Rennen"?

    Ansonsten: Das ständige Umkopieren der Punkte (entweder beim Übergang zwischen deinen Vector<>en oder beim Löschen der Punkte aus der Aktiv-Liste) benötigt natürlich Zeit. Da wäre es eventuell günstiger, eine list<> für die Datenverwaltung zu verwenden (und die Punkte mit splice() zwischen Aktiv-Liste und temporärer Liste zu verschieben).

    PS: Für zwei Werte (die nichtmal gemeinsam verwendet werden) ein dynamisches Array anzulegen halte ich für etwas Overkill - was spricht gegen double LimitMin=-5.0,LimitMax=5.0; ?

    0
  • S

    CStoll schrieb:

    Besteht denn überhaupt die Möglichkeit, daß ein Punkt irgendwann nachträglich in den relevanten Bereich (zurück)kommt? Oder sind alle Punkte außerhalb der Limits definitiv "aus dem Rennen"? [..]

    Naja, nehmen wir an, die Gleichung konvergiert gegen das obere Limit, dann sind alle Punkte, die das obere Limit erreicht haben, definitiv aus dem Rennen. Die Punkte mit dem unteren Limit werden irgendwann relevant für die Berechnung, durchlaufen den Bereich zwischen den Limites, erreichen das obere und fallen schließlich wieder raus. Das mit der Liste schau ich mir mal an, klingt gut, Thx.

    CStoll schrieb:

    PS: Für zwei Werte (die nichtmal gemeinsam verwendet werden) ein dynamisches Array anzulegen halte ich für etwas Overkill - was spricht gegen double LimitMin=-5.0,LimitMax=5.0; ?

    Stimm ich vollkommen zu, weiß auch nicht, was mich da geritten hat 🤡.

    0
  • S

    Sodelle, also die Liste war mir nicht genug, bin eben darauf gestossen, dass es ja auch noch einen Set gibt. Die Einträge werden per insert() an passender Stelle in einen binären Baum eingefügt und doppelte Einträge werden vermieten. Der binäre Baum hat den Vorteil, dass die Suche recht schnell vonstatten geht.

    Ich lasse die Berechnungen gerade zum Vergleich durchlaufen, auf den ersten Blick gewinnt man bereits ein paar Sekunden, so ganz zufrieden bin ich jedoch noch nicht, das sollte eigtl. noch schneller gehen. Die Testergebnisse poste ich, sobald ich sie hab.

    Meßwerte:

    \begin{tabular}{|r|c|c|c|c|} \hline $\mbox{Schritte}$&n&\mbox{alle Punkte [sec]}&$k$&\mbox{Punkte dynamisch [sec]}\\ \hline 1&531441&35,3&14965&22,2\\ 5&531441&177,3&42213&114,3\\ 10&531441&354,8&95465&243,5\\ 15&531441&492,2&178069&362,6\\ \hline \end{tabular}

    Verbesserter

    std::set<int> siActiveNodes;       // Aktive Punkte (B)
std::set<int> siTmpActiveNodes;    // Temporäres Set
std::set<int>::iterator sitANCnt;  // Iterator

double dLimitMin;                  // Limites
double dLimitMax;                  // Limites
dLimitMin = -5.0
dLimitMax = 5.0              

int n;                                // Anzahl aller Punkte
double* adValues;                     // Vektor der Werte an allen Punkten

// [..]

for (int i=0;i<n;i++) {
  adValues[i] = StartSolution(i);

  if ((adValues[i] > dLimitMin) and (adValues[i] < dLimitMax)) {
    siActiveNodes.insert(i);
  }
}

for (int z=0; z<=100; z++) {
  for (sitANCnt = siActiveNodes.begin(); sitANCnt != siActiveNodes.end(); sitANCnt++) {
    i = *vitANCnt
    adValues[i] = F(adValues[i]);

    if ((adValues[i] > dLimitMin) and (adValues[i] < dLimitMax)) {
      siTmpActiveNodes.insert(i);
    }
  }

  siActiveNodes.clear();

  for (sitANCnt = siTmpActiveNodes.begin(); sitANCnt != siTmpActiveNodes.end(); sitANCnt++) {
    i = *sitANCnt;

    for (int j=-1; j<=1; j++) {
      siActiveNodes.insert(getneighbour(i,j));
      }
    }
  }

  siTmpActiveNodes.clear();
}
    0
Anmelden zum Antworten