Ich habe ein mathematisches Problem, das ich durch Versuch und Irrtum löse (ich denke, das nennt man Brute Force), und das Programm funktioniert gut, wenn es ein paar Optionen gibt, aber wenn ich weitere Variablen / Daten hinzufüge, dauert es länger und länger zu laufen.
Mein Problem ist, obwohl der Prototyp funktioniert, ist es nützlich mit Tausenden von Variablen und großen Datensätzen; Ich frage mich, ob es möglich ist, Brute-Force-Algorithmen zu skalieren. Wie kann ich es skalieren?
Ich fing an, mit Hadoop zu lernen und herumzuspielen (und HBase ); Obwohl es vielversprechend aussieht, wollte ich überprüfen, dass das, was ich versuche, nicht unmöglich ist.
Wenn es hilft, habe ich das Programm in Java geschrieben (und kann es wenn möglich verwenden), habe es aber auf Python portiert, weil ich mich damit wohler fühle.
Update: Um mehr Einblick zu gewähren, werde ich eine vereinfachte Version des Codes hinzufügen, um die Idee zu verstehen. Grundsätzlich, wenn ich weiß, dass die Summe 100 ist, versuche ich alle Kombinationen der Variablen zu finden, die ihm gleich sein könnten. Dies ist einfach, in meiner Version kann ich größere Zahlen und viele weitere Variablen verwenden. Es ist die Diophantine, und ich glaube, es gibt keinen Algorithmus, der es ohne Brute-Force-Lösung gibt.
%Vor%Ich bin neu im Programmieren, und es tut mir leid, wenn ich diese Frage nicht richtig formuliere. Dies ist eher eine allgemeine Frage.
Normalerweise können Sie quantifizieren, wie gut ein Algorithmus skaliert, indem Sie die Groß-O-Notation verwenden, um seine Wachstumsrate zu analysieren. Wenn Sie sagen, dass Ihr Algorithmus mit "roher Gewalt" arbeitet, ist unklar, in welchem Umfang er skalieren wird. Wenn Ihre "Brute-Force" -Lösung alle möglichen Teilmengen oder Kombinationen eines Datensatzes auflistet, wird sie höchstwahrscheinlich nicht skalieren (sie wird asymptotische Komplexität haben O (2 n ) oder O (n !), beziehungsweise). Wenn Ihre Brute-Force-Lösung funktioniert, indem Sie alle Elementpaare finden und jedes Element überprüfen, kann es ziemlich gut skalieren (O (n 2 )). Ohne weitere Informationen darüber, wie Ihr Algorithmus funktioniert, ist das schwer zu sagen.
Vielleicht möchten Sie diesen ausgezeichneten Beitrag über big-O ansehen als Ausgangspunkt für die langfristige Skalierbarkeit Ihres Programms. Üblicherweise skaliert alles, was eine Wachstumsrate O (n log n), O (n), O (log n) oder O (1) aufweist, extrem gut, alles mit der Wachstumsrate O (n 2) ) oder O (n 3 ) skaliert bis zu einem Punkt, und alles mit Wachstumsrate O (2 n ) oder höher wird überhaupt nicht skaliert.
Eine andere Möglichkeit wäre, das Problem, das Sie lösen möchten, nachzuschlagen, um zu sehen, wie gut es studiert wurde. Einige Probleme haben bekanntermaßen großartige Lösungen, und wenn Ihre eine davon ist, könnte es sich lohnen, zu sehen, was andere sich ausgedacht haben. Vielleicht gibt es eine sehr saubere Lösung ohne Brute-Force, die wirklich gut skaliert! Einige andere Probleme werden vermutet, um überhaupt keine skalierbaren Algorithmen zu haben (die so genannten NP-harte Probleme ). Wenn das der Fall ist, dann sollten Sie ziemlich sicher sein, dass es keinen Weg gibt, einen skalierbaren Ansatz zu bekommen.
Und schließlich können Sie bei Stack Overflow immer eine neue Frage stellen, in der Sie beschreiben, was Sie tun möchten, und nach Eingabe fragen. Vielleicht kann die Community Ihnen helfen, Ihr Problem effizienter zu lösen, als Sie ursprünglich erwartet hatten!
BEARBEITEN: Angesichts der Beschreibung des Problems, das Sie zu lösen versuchen, machen Sie jetzt einen für die Schleife pro Variable von 0 bis zu der Nummer, auf die Sie zielen möchten. Die Komplexität dieses Algorithmus ist O (U k ), wobei k die Anzahl der Variablen und U die Summe ist. Dieser Ansatz wird nicht sehr gut skalieren. Wenn Sie jede neue Variable in den obigen Fall einführen, wird der algori2thm 100-mal langsamer laufen, was definitiv nicht gut skalieren wird, wenn Sie 100 Variablen haben wollen!
Ich denke jedoch, dass es einen ziemlich guten Algorithmus gibt, dessen Laufzeit O (U 2 k) ist, der O (Uk) Speicher verwendet, um das Problem zu lösen. Die Intuition ist wie folgt: Angenommen, wir wollen 1, 2 und 4 zusammenfassen, um 10 zu erhalten. Es gibt viele Möglichkeiten, dies zu tun:
%Vor%Die Schlüsselbeobachtung ist, dass wir all dies als Summe ausgeben können, aber noch wichtiger, als Summe, bei der jeder Begriff in der Summe nicht größer ist als der vorhergehende Begriff:
%Vor% Das ergibt also eine interessante Idee, wie man alle möglichen Wege, um das Ziel zu summieren, generiert. Die Idee besteht darin, den ersten Koeffizienten festzulegen und dann alle möglichen Möglichkeiten zu generieren, um den Rest der Summe auszuarbeiten. Mit anderen Worten, wir können über das Problem rekursiv nachdenken. Wenn wir die Variablen der Reihe nach als x 1, x 2, ..., x n auflisten, können wir versuchen, einen bestimmten Koeffizienten zu bestimmen für x 1, dann Lösen des Problems des Aufsummierens von sum - c_1 x_1 unter Verwendung von nur x 2, ..., x n.
Bis jetzt scheint das alles nicht so extravagant zu sein - tatsächlich ist es genau das, was Sie oben tun - aber es gibt einen Trick, den wir verwenden können. Solange wir rekursiv über dieses Problem nachdenken, denken wir über das Problem umgekehrt nach. Anstatt mit sum zu beginnen und zu versuchen, es zu zerlegen, was wäre, wenn wir statt dessen mit 0 anfangen würden und alles versuchen würden, was wir könnten?
Hier ist die Idee. Angenommen, wir wissen bereits im Voraus alle Zahlen, die wir nur mit den Summen von x 1 erzeugen können. Dann können wir für jede Zahl k zwischen 0 und sum einschließlich k aus x 2 und x 1 aus jeder beliebigen Kombination, in der k - c & sub0; 2 2 ist etwas, das aus Kombinationen von x1 gebildet werden kann. Aber da wir dies vorausberechnet haben, können wir einfach über alle möglichen zulässigen Werte von c 2 iterieren, berechnen k - c 2 x 2 und sehen, ob wir wissen, wie man es macht. Unter der Annahme, dass wir eine gigantische U x (k + 1) -Tabelle mit booleschen Werten speichern, so dass der Tabelleneintrag [x, y] speichert "können wir die ersten y-Werte einschließlich auf eine Weise aufsummieren, die genau zu U?" Wir können die Tabelle effizient ausfüllen. Dies wird dynamische Programmierung genannt und ist ein mächtiges algorithmisches Werkzeug.
Konkreter gesagt, hier ist, wie dies funktionieren könnte.Geben Sie für k Variablen eine U x (k + 1) -Tabelle T von Werten ein. Dann setze T [0] [0] = wahr und T [x] [0] = falsch für alle x & gt; 0. Die Begründung hier ist, dass T [0] [0] bedeutet "Können wir die Summe Null mit einer linearen Kombination der ersten Nullvariablen erhalten?" und die Antwort ist definitiv ja (die leere Summe ist Null!), aber für jede andere Summe, die aus keiner linearen Kombination von Variablen besteht, können wir es definitiv nicht machen.
Nun, für i = 1 .. k, werden wir versuchen, die Werte von T [x] [i] auszufüllen. Denken Sie daran, dass T [x] [i] bedeutet "Können wir x als lineare Kombination der ersten i Variablen machen?" Nun, wir wissen, dass wir dies tun können, wenn es einen Koeffizienten c gibt, so dass k - cx unter Verwendung einer Linearkombination von x1, x
Wenn wir die Schleifen untersuchen, sehen wir, dass die äußere Schleife k mal läuft, die innere Schleife sum mal pro Iteration und die innerste Schleife auch höchstens sum mal pro Iteration. Ihr Produkt ist (mit unserer Notation von oben) O (U 2 k), was viel besser ist als der O (U k ) Algorithmus, den Sie ursprünglich hatten.
Aber wie verwenden Sie diese Informationen, um alle möglichen Wege aufzulisten, die zum Ziel führen? Der Trick hier ist zu erkennen, dass Sie die Tabelle verwenden können, um zu vermeiden, eine riesige Menge an Anstrengung zu verschwenden, die über jede mögliche Kombination sucht, wenn viele von ihnen nicht arbeiten werden.
Sehen wir uns ein Beispiel an. Angenommen, wir haben diese Tabelle vollständig berechnet und möchten alle Lösungen auflisten. Eine Idee ist, alle Lösungen aufzulisten, bei denen der Koeffizient der letzten Variablen Null ist, dann wenn die letzte Variable Eins ist usw. Das Problem mit dem Ansatz, den Sie zuvor hatten, ist, dass für einige Koeffizienten überhaupt keine Lösungen existieren . Aber mit dem Tisch, den wir oben konstruiert haben, können wir diese Zweige abschneiden. Angenommen, wir möchten sehen, ob es Lösungen gibt, die mit x k mit dem Koeffizienten 0 beginnen. Das heißt, wir fragen, ob es Möglichkeiten gibt, eine Linearkombination von erste k - 1 Variablen, so dass die Summe dieser Werte sum ist. Dies ist nur dann möglich, wenn T [Summe] [k - 1] wahr ist. Wenn es wahr ist, können wir rekursiv versuchen, Koeffizienten den restlichen Werten auf eine Weise zuzuordnen, die zu sum zusammenfasst. Wenn nicht, dann überspringen wir diesen Koeffizienten und gehen zum nächsten über.
Rekursiv sieht das ungefähr so aus:
%Vor%Dies rekursiv listet alle Lösungen auf, die funktionieren, und verwendet die Werte in der Tabelle, die wir gerade erstellt haben, um eine große Menge an verschwendeten Aufwand zu überspringen. Sobald Sie diese Tabelle erstellt haben, können Sie diese Arbeit aufteilen, indem Sie die Aufgabe an mehrere Computer verteilen, die jeweils eine Teilmenge der Gesamtlösungen auflisten und sie alle parallel verarbeiten.
Hoffe, das hilft!
Per Definition sind Brute-Force-Algorithmen dumm. Du wärst viel besser mit einem clevereren Algorithmus (wenn du einen hast). Ein besserer Algorithmus wird die Arbeit reduzieren, die getan werden muss, hoffentlich in einem Grad, dass Sie es tun können, ohne auf mehrere Maschinen "skalieren" zu müssen.
Unabhängig vom Algorithmus kommt es zu einem Punkt, an dem die erforderliche Datenmenge oder Rechenleistung so groß ist, dass Sie etwas wie Hadoop verwenden müssen. Aber normalerweise sprechen wir Big Data hier. Sie können heutzutage mit einem einzigen PC viel tun.
Der Algorithmus zur Lösung dieses Problems ist für den Prozess geschlossen, den wir für die manuelle mathematische Division erlernen oder auch von dezimal in eine andere Basis wie oktal oder hexadezimal konvertieren - außer dass zwei Beispiele nur nach einer einzigen kanonischen Lösung suchen.
Um sicherzugehen, dass die Rekursion endet, ist es wichtig, das Datenarray zu ordnen. Um effizient zu sein und die Anzahl der Rekursionen zu begrenzen, ist es auch wichtig, mit höheren Datenwerten zu beginnen.
Konkret ist hier eine rekursive Java-Implementierung für dieses Problem - mit einer Kopie des Ergebnisvektors coeff für jede Rekursion, wie es theoretisch erwartet wird.
Aber jetzt ist dieser Code in einem speziellen Fall: der letzte Wert Test für jeden Koeff ist 0, also ist die Kopie nicht notwendig.
Als Komplexitätsschätzung können wir die maximale Tiefe von rekursiven Aufrufen als data.length * min({ data }) verwenden. Sicherlich wird es nicht gut skalieren und der begrenzte Faktor ist der Stack-Trace-Speicher ( -Xss JVM-Option). Der Code kann mit einem Stapelüberlauffehler für eine große data Menge fehlschlagen.
Um diese Nachteile zu vermeiden, ist der "Derecursion" -Prozess nützlich. Es besteht darin, den Methodenaufruf-Stack durch einen programmatischen Stack zu ersetzen, um einen Ausführungskontext zu speichern, der später verarbeitet wird. Hier ist der Code dafür:
%Vor%Aus meiner Sicht ist es schwierig, in einer einzelnen Thread-Ausführung effizienter zu sein - der Stack-Mechanismus benötigt nun Koeff-Array-Kopien.
Tags und Links algorithm hadoop scalability