Greedy Faerbungsalgorithmus für eine Variablenreduktion

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von bobpcur » Di Jan 10, 2017 2:05 pm

Hallo,
ich möchte für mein Projekt einen "Compiler" Optimierer schreiben, welcher mir die benutzten Variablen im erzeugten Code reduziert. Dazu parse ich die erzeugten Codezeilen und trenne die Variablen zeilenweise, die nur beschrieben werden, von denen, die nur gelesen werden. Der erzeugte Code ist eine Assembler artige Zwischensprache, welche jede Zeile zu einem Zeitpunkt abarbeitet. Deswegen, wenn eine Variable in einer Zeile nur noch gelesen wird und nie wieder beschrieben, ´wird der Name dieser Variable frei und somit reduziert sich die Gesamtanzahl der Variablen.

Ich habe etwas recherchiert und festgestellt, solche Probleme werden mit Hilfe der Graphentheorie, speziell Faerbungsproblem gelöst. Leider ist das Finden der optimalen chromatischen Zahl ein NP vollständiges Problem, deswegen möchte ich erstmal auf den Greedy Algorithmus zurueckweichen.

Zunächst muss ich meinen erzuegten Code und meine beiden Variablenlisten als einen Graphen repräsentieren. Dabei bilden meine Variablennamen und Anweisungen Knoten. Und schon komme ich nicht klar, im Output des Algorithmus möchte ich einen neuen erzeugten Code mit weniger verwendeter Variablen, ich bin mir aber absolut nicht sicher wie ich den Algorithmus anweden soll.

Ich frage nicht nach einem fertigem Code oder aehnlichem, ich schreibe je in Matlab und das ist glaube ich diesem Forum etwas fremd. Ich braeuchte lediglich Hilfe bei dem Übertragen meines spezifischen Problems auf ein allg. graphentheoretisches Problem.

Viele Grüße, bob.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von cloidnerux » Di Jan 10, 2017 2:55 pm

Zunächst muss ich meinen erzuegten Code und meine beiden Variablenlisten als einen Graphen repräsentieren. Dabei bilden meine Variablennamen und Anweisungen Knoten. Und schon komme ich nicht klar, im Output des Algorithmus möchte ich einen neuen erzeugten Code mit weniger verwendeter Variablen, ich bin mir aber absolut nicht sicher wie ich den Algorithmus anweden soll.
Ich hatte bisher nichts mit Compilerbau zu tun, XIN aber, er kann dir sicherlich weiterhelfen.

Ansonsten mal eine allgemeine Anmerkung:
Eine Variable und damit der verknüpfte Speicher wird "Frei", wenn ihr Inhalt nicht mehr benötigt wird. Dabei musst du aber beachten, dass es "indirekte" Zugriffe auf eben diesen Speicher geben kann, z.B über Pointer, Strukturen oder spezielle Assemblerbefehle.
Weiterhin gibt es Speicher, über den du keine Kontrolle hast, dieser ist dynamischer, vom System angeforderter Speicher.

Effektiv bedeutet das, dass du keine Liste aller Variablen brauchst, sondern eine Liste mit den Variablenzugriffen zu Programmlaufzeit "t". Der letzte Punkt t, an dem auf eine Variable zugegriffen wird in dieser Liste, kennzeichnet das Ende der Lebenszeit dieser Variable.
Um aber diese Liste zu erstellen, müsstest du dein Programm komplett durchlaufen und das für alle möglichen Eingaben, da es ja auch Verzweigungen geben kann. Offensichtlich hat dies zum Problem, dass du hier mit dem Halteproblem zu tun hast, was passiert wenn dein Programm ewig läuft.

Weiter Hürden sind auch schlechte Abläufe. Folgender Fall:
Es wird eine Variable angelegt, eine Berechnung mit einer weiteren Variable durchgeführt und das Ergebnis in der neu angelegten Variable gespeichert. Die "alte" Variable wird ab diesem Zeitpunkt nicht mehr benötigt. Würde man erst die Berechnung durchführen, könnte man es sich sparen, eine neue Variable anzulegen.

Die Lösung mit dem Graphen wird wohl innerhalb einer Sprache wie C/C++ mehr sinn machen, da du hier "Scopes" hast, damit Gültigkeitsbereiche. Hier wird es leichter, die Notwendigkeit einer Variable zu determinieren.
Redundanz macht wiederholen unnötig.
quod erat expectandum

bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von bobpcur » Di Jan 10, 2017 3:19 pm

Eine Variable und damit der verknüpfte Speicher wird "Frei", wenn ihr Inhalt nicht mehr benötigt wird. Dabei musst du aber beachten, dass es "indirekte" Zugriffe auf eben diesen Speicher geben kann, z.B über Pointer, Strukturen oder spezielle Assemblerbefehle.
Von meinem Betreuer wurde mir versichert, dass es in dieser Assemblersprache keine Spruenge, Iterationen, sonstwas gibt. Das einzige "speziell" es gibt MOV Anweisungen, welche den Wert einer Variable zuweisen, abhängig davon, ob der Wert positiv, negativ oder 0 ist.
Effektiv bedeutet das, dass du keine Liste aller Variablen brauchst, sondern eine Liste mit den Variablenzugriffen zu Programmlaufzeit "t". Der letzte Punkt t, an dem auf eine Variable zugegriffen wird in dieser Liste, kennzeichnet das Ende der Lebenszeit dieser Variable.
Der verwendete Assemblercode rechnet jede Zeile zu einem Zeitpunkt durch, kann ich den Index meiner erzeugten Codezeilen als Zeitstempel nehmen?
Um aber diese Liste zu erstellen, müsstest du dein Programm komplett durchlaufen und das für alle möglichen Eingaben, da es ja auch Verzweigungen geben kann. Offensichtlich hat dies zum Problem, dass du hier mit dem Halteproblem zu tun hast, was passiert wenn dein Programm ewig läuft.
Um festzustellen, welche Variablen in der Zeile gelesen und welche geschrieben werden, laufe ich den Code in umgekehrter Reihenfolge beim Parsen durch, bzw. kann die Reihenfolge gefundener Variablen ändern.
Die Lösung mit dem Graphen wird wohl innerhalb einer Sprache wie C/C++ mehr sinn machen, da du hier "Scopes" hast, damit Gültigkeitsbereiche. Hier wird es leichter, die Notwendigkeit einer Variable zu determinieren.
Naja, Matlab ist C aehnlich, da kann ich zum Bsp. ueber die Cells auch auf jede einzelne erzeugte Zeile zugreifen oder auf eine Variable in der Liste. Ist schon ganz cool.

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von cloidnerux » Di Jan 10, 2017 3:25 pm

Gerade nochmal darüber nachgedacht.

Du hast in deinem Programm eine Liste an "logischen Variablen", i.e du hast eine Variable in einem bestimmten Kontext(Algorithmus).
Die Knoten eines Graphen sind die logischen Variablen dieses Programmes. Alle Kanten stellen eine "Gleichzeitigkeit" dar. Daher eine Verbindung zwischen zwei Knoten bedeutet, dass sie im Programmablauf gleichzeitig Gültig sein müssen.
Wenn du nun als Einfärbungsregel festlegst, dass keine zwei Verbundenen Knoten die gleiche Farbe haben dürfen, ist die Gesamtheit der Farben und die Zuordnung zu den Knoten die anzahl und Zuordnung der physikalisch notwendigen Variablen.

Um aber diesen Graphen zu erstellen, stößt du weiterhin auf die Probleme, die ich vorher schon geschildert habe. Je nach dem wie viele Verzweigungen, Sprünge und Pointer du in deinem Programm hast, wirst du Probleme haben, deinen Graphen zu erstellen.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3079
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von cloidnerux » Di Jan 10, 2017 3:30 pm

Ich beantworte das einfach mal in einem extra Beitrag.
Von meinem Betreuer wurde mir versichert, dass es in dieser Assemblersprache keine Spruenge, Iterationen, sonstwas gibt. Das einzige "speziell" es gibt MOV Anweisungen, welche den Wert einer Variable zuweisen, abhängig davon, ob der Wert positiv, negativ oder 0 ist.
Ahh, das macht vieles einfacher. Es geht hier also eher um ein synthetisches Problem.
Der verwendete Assemblercode rechnet jede Zeile zu einem Zeitpunkt durch, kann ich den Index meiner erzeugten Codezeilen als Zeitstempel nehmen?
Ja.
Um festzustellen, welche Variablen in der Zeile gelesen und welche geschrieben werden, laufe ich den Code in umgekehrter Reihenfolge beim Parsen durch, bzw. kann die Reihenfolge gefundener Variablen ändern.
Dadurch das du keine Sprünge oder Verzweigungen hast, ist dies sehr viel einfacher. Dann ist deine Vorgehensweise Anwendbar.
Naja, Matlab ist C aehnlich, da kann ich zum Bsp. ueber die Cells auch auf jede einzelne erzeugte Zeile zugreifen oder auf eine Variable in der Liste. Ist schon ganz cool.
Ja, Matlab als Programmiersprache ist ähnlich zu C.
Dein pseudo Assembler hat aber entscheidend andere Eigenschaften. Wenn du keine Sprünge oder Verzweigungen hast, wird jeder dieser Codes halten und ist strikt deterministisch.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8472
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von Xin » Mi Jan 11, 2017 7:06 pm

bobpcur hat geschrieben:Hallo,
ich möchte für mein Projekt einen "Compiler" Optimierer schreiben, welcher mir die benutzten Variablen im erzeugten Code reduziert. Dazu parse ich die erzeugten Codezeilen und trenne die Variablen zeilenweise, die nur beschrieben werden, von denen, die nur gelesen werden. Der erzeugte Code ist eine Assembler artige Zwischensprache, welche jede Zeile zu einem Zeitpunkt abarbeitet. Deswegen, wenn eine Variable in einer Zeile nur noch gelesen wird und nie wieder beschrieben, ´wird der Name dieser Variable frei und somit reduziert sich die Gesamtanzahl der Variablen.
Das lässt sich über Scopes abbilden.
Alle Variablen werden beschrieben und gelesen:

Code: Alles auswählen

int func( int par )
{  // Scope 1
  int b = func();
  int c;  // still unused;

  if( condition() )
  {  // Scope 2
     c = func();
     something( par, c );
     return par;
  }  // benutzt c, par; muss par kennen

  something( par, b );
  return b;
}  // deklariert par, b, c; benutzt par, b, muss par und b kennen, nicht aber c.
par wird überall benutzt, c nur in scope 2, b nur in scope 1.
Da c in Scope 1 nicht benutzt wird, kann man es nach Scope 2 schieben.

Code: Alles auswählen

int func( int par )
{  // Scope 1
  int b = func();

  if( condition() )
  {  // Scope 2
     int c = func();
     something( par, c );
     return par;
  }  // deklariert c, benutzt c, par

  something( par, b );
  return b;
}  // deklariert par, b; benutzt par, b
In Scope 2 stellt sich die Frage, wo man c nun hinlegt. Der bisherige Stack hat [par, b] - par wird benutzt, b wird nie wieder benutzt, da dieser Scope (2) den Scope verlässt, der b deklariert hat (1). Der Platz von b wird innerhalb dieses Scopes nicht benutzt, kann also überschrieben werden, b ist auch groß genug, um c zu speichern.
bobpcur hat geschrieben:Ich habe etwas recherchiert und festgestellt, solche Probleme werden mit Hilfe der Graphentheorie, speziell Faerbungsproblem gelöst. Leider ist das Finden der optimalen chromatischen Zahl ein NP vollständiges Problem, deswegen möchte ich erstmal auf den Greedy Algorithmus zurueckweichen.
Ich schreibe zwar einen Compiler und entwickle eine Sprache, muss allerdings sagen, dass ich mich mit Optimierung noch nicht groß auseinander gesetzt habe. Ich persönlich würde hier ehrlich gesagt auf Dauer den Ansatz wählen, beim Funktionsaufruf den Bedarf des größten Scope zu alloziieren und fertig: Erstens kostet die Allokation Zeit (da ich noch Scopeweise alloziiere, will ich davon weg), zweitens ist Speicher billig und drittens ist die Optimierung nicht mein Hauptanliegen, wenn ich erstmal was lauffähiges haben möchte.
Ich transpiliere dann nach LLVM-Assembler, dort kann ich die LLVM-Optimizer die Arbeit überlassen.

Du hast aber offenbar eine Hausaufgabe vor Dir?
bobpcur hat geschrieben:Zunächst muss ich meinen erzuegten Code und meine beiden Variablenlisten als einen Graphen repräsentieren. Dabei bilden meine Variablennamen und Anweisungen Knoten. Und schon komme ich nicht klar, im Output des Algorithmus möchte ich einen neuen erzeugten Code mit weniger verwendeter Variablen, ich bin mir aber absolut nicht sicher wie ich den Algorithmus anweden soll.
Zu "Dem Algorithmus" kann man nicht viel sagen, denn "Greedy" ist nicht unbedingt ein klare Ansage, welcher Algorithmus überhaupt gemeint ist? ^^

bobpcur hat geschrieben:Von meinem Betreuer wurde mir versichert, dass es in dieser Assemblersprache keine Spruenge, Iterationen, sonstwas gibt.
Hausaufgabe. ^^
Bei "dieser Sprache" komme ich zum gleichen Problem wie bei "dem Algorithmus".
Und unter Sonstwas verstehe ich dann auch mal Bedingungen, da es schließlich keine Sprünge gibt.
bobpcur hat geschrieben:Das einzige "speziell" es gibt MOV Anweisungen, welche den Wert einer Variable zuweisen, abhängig davon, ob der Wert positiv, negativ oder 0 ist.
Was genau meinst Du, wenn Du "Bahnhof" sagst? ;)
bobpcur hat geschrieben:Um festzustellen, welche Variablen in der Zeile gelesen und welche geschrieben werden, laufe ich den Code in umgekehrter Reihenfolge beim Parsen durch, bzw. kann die Reihenfolge gefundener Variablen ändern.
Du brauchst im Prinzip die Lebensdauer von Variablen:
Erste Benutzung bis letzte Benutzung. Wird eine Variable erstmalig benutzt, nachdem eine andere letztmalig genutzt wurde, kann sie auf dem Speicherplatz abgelegt werden, den die alte Variable hat - falls sie darein passt, was ich bei einer Hausaufgabe mal einfach so annehme ;)

Um in dem Beispiel zu bleiben: par lebt über die komplette Funktion. b lebt über die komplette Funktion, wird aber in Scope 2 nicht mehr benutzt. Die Funktion teilt sich aufgrund der zwei möglichen Pfade. Der zweite Pfad geht durch Scope 2, also endet die Lebensdauer mit Eintritt in Scope 2 und der Speicher, den b besetzte wird frei. c wird erstmals verwendet, braucht also Platz und findet ihn da, wo vorher b war. c lebt also von Beginn bis Ende von Scope 2.
Ist condition() falsch, durchläuft die Funktion den Standardpfad. Hier existiert b bis zum Ende der Funktion und c niemals, weil sie weder gelesen, noch geschrieben wird.

Aber das Beispiel ist ja eigentlich schon zu groß, weil Du keine Springe hast, also auch nicht mögliche Ablaufpfade der Funktion berücksichtigen müsstest, womit wir dann nämlich bei einem Graphen wären.

Das hier hat dann nix mehr mit der Hausaufgabe zu tun, also bei Nicht-Verstehen einfach komplett ignorieren.
In der Realität wird das dann noch verschönert durch Objekte, die konstruierbar bzw. dekonstruierbar sind und während der Konstruktion oder Destruktion zu Seiteneffekten neigen. Seiteneffekte verhindern auch b beispielsweise unter Scope 2 zu schieben, da der Aufruf von func() sich ja auch auf die Funktion von condition() auswirken könnte, der Aufruf von func() nach condition() also das Programm fehlerhaft verändern könnte.
Das ganze kann man also beliebig verkomplizieren. :)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von bobpcur » Mo Jan 16, 2017 10:00 am

Hausaufgabe ist gut, es ist ein Teil der Masterarbeit xD. Vielen lieben Dank fuer die aufschlussreiche Antwort, alles ist mir noch nicht klar, aber das mit den Scpopes ist ein guter Tio.

Das mit der Lebensdauer der Variablen habe ich mittlerweile verstanden und genau dazu brauche ich die Aussage ueber die generierten Zeilen, in denen diese Variablen gefunden werden. Diese Lebensdauer wollte ich ueber die Graphentheorie finden. Dabei habe ich zuerst gedacht, dass wenn ich meinen generierten Code irgendwie als einen Baumgraph repräsentieren, wo die Knoten entweder Variablen oder die verknüpfenden Anweisungen sind, dass dabei die chromatische Zahl des erstellten Graphen die minimale Anzahl der benötigten Variablen seien wird. Und wusste dabei nicht, dass ich die Lebensdauer jeder einzelnen Variable beachten soll.

Witzigerweise wollte ich mit der Reduktion noch vor Weihnachten fertig sein, habe aber den Aufwand massiv unterschaetzt :oops:

bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von bobpcur » Mo Jan 16, 2017 1:55 pm

Entschuldigung fuer den Doppelpost, ich hatte jetzt ein Treffen mit dem Betreuer, was tatsaechlich mal weiter geholfen hat.
Es hat sich herausgestellt, dass das Problem deutlich einfacher ist, als gedacht, da eine der Eigenschaften der Assemblerzwischensprache ist, dass tatsaehclich zu jedem Zeitpunkt nur eine Anweisung ausgeführt wird, ich muss mir nur darueber Gedanken machen, dass die Variablen in den entsprechenden Zeilen richtig ersetzt werden. Also, keine NP Vollstaendiogkeit, keine Graphenfaerben.

Folgendes habe ich mir ueberlegt:

1) Ich erstelle mir eine Liste von Variablen, die in den erzeugtem Code verwendet werden.
2) Für jede Variable erstelle ich mir eine Zaehlvariable
3) Ich geh den erzeugten Code Zeile fuer Zeile durch, und suche nach der ersten Variable aus der Liste
4)Falls eine Variable in der Zeile gefunden wurde, erhoeht sich die Zaehlvariable countvar, die countvar kann folgende Werte einnehmen: 0, 1, 2, 3. Countvar ist die Enstcheidungsvariable, was mit der generierten Codezeile gemacht werden muss.
5)Merke die Zeilennummer t, wo die Variable gefunden wurde ->schwerster Schritt fuer mich bis jetzt, kein Plan wie ich das in Matlab machen soll
6)Entscheide ob die Variable in der Zeilennumer t gelesen oder geschrieben wird (ich habe hier schon meine Lese- und Schreibelisten, könnte ich einfach mit den Eintraegen in diesen Listen vergleichen)
7)Falls die Variable nur gelesen wird, und ab da nicht mehr geschrieben, markiere die nächste generierte Zeile t+1
8)ersetze in der t+1 den Variablennamen, der in t+1 geschrieben wird, mit dem Variablennamen, nach dem gesucht wurde. Merke ersetzten Namen
9)suche alle Codezeile t+rest nach den ersetzten Namen aus t+1 und ersetze diesen mit dem Variablennamen aus 8).
10)geh zu 3), nimm nächste Variable.
11)End, wenn Variablenliste durch ist.


Der Algorithmus sollte so eigentlich funktionieren, habe ich vllt. etwas vergessen? Wie wuerdet ihr daran gehen?
EDIT: Die Berechnungszeit dürfte wohl so aussehen: O(n) = 3*n*(n-m) ~ 3*n^2, wobei n Anzahl meiner Variablen ist und m Anzahl der Codezeilen´, die 3, weil in einer Codezeile max 3 Variablen vorkommen duerften.
Grüße, bob.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8472
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von Xin » Mi Jan 18, 2017 1:26 pm

So, ich glaube, dritter Versuch... ^^
Bleibt immer mittendrin liegen und dann ist die Antwort weg.
bobpcur hat geschrieben:Entschuldigung fuer den Doppelpost, ich hatte jetzt ein Treffen mit dem Betreuer, was tatsaechlich mal weiter geholfen hat.
Es hat sich herausgestellt, dass das Problem deutlich einfacher ist, als gedacht, da eine der Eigenschaften der Assemblerzwischensprache ist,
Du schreibst, es handelt sich um eine Masterarbeit, es klingt für mich ein wenig so, als würdest Du ein Ziel anstreben, dass Deinem Betreuer bereits bekannt ist, Du also entsprechend einer Prüfung zeigen musst, dass Du den gewünschten Weg dorthin findest!?
bobpcur hat geschrieben:dass tatsaehclich zu jedem Zeitpunkt nur eine Anweisung ausgeführt wird, ich muss mir nur darueber Gedanken machen, dass die Variablen in den entsprechenden Zeilen richtig ersetzt werden. Also, keine NP Vollstaendiogkeit, keine Graphenfaerben.
Wieviele Anweisungen führt ein Assemblerprogramm denn sonst so im Schnitt zu einem Zeitpunkt durch?!
bobpcur hat geschrieben: Folgendes habe ich mir ueberlegt:

1) Ich erstelle mir eine Liste von Variablen, die in den erzeugtem Code verwendet werden.
2) Für jede Variable erstelle ich mir eine Zaehlvariable
3) Ich geh den erzeugten Code Zeile fuer Zeile durch, und suche nach der ersten Variable aus der Liste
4)Falls eine Variable in der Zeile gefunden wurde, erhoeht sich die Zaehlvariable countvar, die countvar kann folgende Werte einnehmen: 0, 1, 2, 3. Countvar ist die Enstcheidungsvariable, was mit der generierten Codezeile gemacht werden muss.
5)Merke die Zeilennummer t, wo die Variable gefunden wurde ->schwerster Schritt fuer mich bis jetzt, kein Plan wie ich das in Matlab machen soll
Woher die Fixierung auf Matlab und wo ist das Problem?
Es ist ein Vektor. (Variablennummer, Zeilennummer).
bobpcur hat geschrieben: 6)Entscheide ob die Variable in der Zeilennumer t gelesen oder geschrieben wird (ich habe hier schon meine Lese- und Schreibelisten, könnte ich einfach mit den Eintraegen in diesen Listen vergleichen)
7)Falls die Variable nur gelesen wird, und ab da nicht mehr geschrieben, markiere die nächste generierte Zeile t+1
8)ersetze in der t+1 den Variablennamen, der in t+1 geschrieben wird, mit dem Variablennamen, nach dem gesucht wurde. Merke ersetzten Namen
9)suche alle Codezeile t+rest nach den ersetzten Namen aus t+1 und ersetze diesen mit dem Variablennamen aus 8).
10)geh zu 3), nimm nächste Variable.
11)End, wenn Variablenliste durch ist.
Klingt kompliziert.
Was spricht dagegen, die Lebensdauer der Variablen zu nehmen und sie so zu stapeln, dass sie sich nicht überlagern, aber möglichst wenig Raum einnehmen?

Man muss Probleme nicht kleinklopfen, um sie zu lösen. Es ist manchmal aber praktisch.
bobpcur hat geschrieben: Der Algorithmus sollte so eigentlich funktionieren, habe ich vllt. etwas vergessen? Wie wuerdet ihr daran gehen?
EDIT: Die Berechnungszeit dürfte wohl so aussehen: O(n) = 3*n*(n-m) ~ 3*n^2, wobei n Anzahl meiner Variablen ist und m Anzahl der Codezeilen´, die 3, weil in einer Codezeile max 3 Variablen vorkommen duerften.
Grüße, bob.
*Augenbraue heb*

Nehmen wir 1 Zeile mit einem 1 Variablen.
Dein Laufzeitverhalten beträgt dann O(N) = -3n^2.

Wenn ich das richtig interpretiere, ist Dein Programm also fertig, bevor die Berechnung startet.

Und je länger das Programm ist, umso früher wird es fertig? Also umso mehr Zeit kann ich mir lassen, die Berechnung zu starten, wenn ich das Ergebnis in der Hand halte.

Ich stelle fest, das Posting hätte ich früher fertig stellen können. Die Auseinandersetzung damit braucht gar nicht soviel Text. Es gibt eher ein fundamentales Argument, als eine Abwägung von mehreren, wie ich zunächst vermutete. ;)
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

bobpcur
Beiträge: 13
Registriert: Mi Nov 30, 2016 10:03 am

Re: Greedy Faerbungsalgorithmus für eine Variablenreduktion

Beitrag von bobpcur » Fr Jan 20, 2017 1:30 pm

Natuerlich habe ich m und n vertauscht, bei jeder Iteration des Algorithmus muss er weniger Zeilen durchgehen, weil es immer weniger geben wird, die man optimieren kann.

Matlab, weil das Vorprojekt in Matlab geschrieben wurde, ich bau den Optimierer dafuer. ´Habe auch schon erste Erfolge. Ich habe eine Trennung der geschriebenen, gelesenen und deklarierten Variablen erstellt, mit dazugehörigen Zeilennummern und habe jetzt auch eine Liste von Variablen estellt, die gelöscht werden können (im jetzig gepostetem Beispiel dann, ab den Zeilennummern die in L_del stehen, vorausgesetzt der Beispielcode wuerde laenger gehen).
Ich habe mal meine Ergebnisse in der Matlab Commano Zeile rausgegeben, und eine .txt mit dem zu optimierendem Beispielcode.

Code: Alles auswählen

L_read = 

    [13]    [13]    [14]    [15]    [15]


Var_read = 

    't_6'    't_5'    't_5'    't_2'    't_1'


L_write = 

    [11]    [12]    [13]    [14]    [15]


Var_write = 

    't_2'    't_6'    't_5'    't_2'    't_1'


L_dq = 

    [7]    [8]    [9]    [10]


Var_dq = 

    'v=t_1;'    'v=t_2; '    'v=t_5; '    'v=t_6; '


var_del = 

    'v=t_2;'    'v=t_6; '    'v=t_5; '    'v=t_2; '


L_del = 

    [15]    [13]    [14]    [15]
Also, so langsam komme ich vorwaerts, wobei ich an dieser Stelle gerne vor 6 Wochen waere :D.

Aufjedenfall muss ich jetzt irgendwie den nächsten Schritt machen, und Variablen, die in den Zeilen, welche nach L_del stehen mit den Namen aus var_del zu ersetzen. Und anschließend, alle Variablen, welche entfernt wurden, auch aus Var_dq entfernen.

Grueße.
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.

Antworten