Flash missbrauchen - wie es machmal noch ein bischen schneller geht

[Janoscharlipp]

Hallo,

kürzlich brauchte ich für eine Tabelle mit Wertentwicklungen die Möglichkeit, in einem Array auf den letzten definierten Wert zuzugreifen.

Hier mal das ganze etwas veranschaulicht:
1. Die bekannten Daten: (i = Zeilen-Index; A, B = Datenfelder, - = Kein Wert bzw. letzter Wert

i | A | B
--+---+--
0 | 0 | 0
1 | 1 | -
2 | - | 2
3 | - | -

2. das gewünschte Resultat

i | A | B
--+---+--
0 | 0 | 0
1 | 1 | 0
2 | 1 | 2
3 | 1 | 2

Mir kamen drei verschiedene Lösungsvarianten in den Sinn, die zwei ausergewöhlichen musste ich aber leider wieder verwerfen, da sie, möchte man AS2-konform programmieren, zu unsauber sind.
Aufgrund dieses Threads wurde ich aber wieder an das Problem erinnert, und jetzt habe ich mal alle Varianten ausprobiert:

1. Ansatz: manuell
Der gewöhliche Ansatz ist klar; solange ein Wert undefiniert ist, siehe weiter vorne nach.
Für die Array-Einträge verwende ich eine eigene Klasse, zum Ausgeben der erzeugten Tabellen bekommen alle Einträge die von Flash verwendete Funktion toString:

stringable = function() {};
stringable.prototype.toString = function() {
    return "(" + this.a + "|" + this.b + ")";
};
 
entry = function(a, b) {
    if (a != null) this.a = a;
    if (b != null) this.b = b;
};
 
entry.prototype = new stringable(); 

Das ist nicht so sauber, da stringable noch garnicht weiß, dass es a und b besitzt, ist mir in diesem Falle aber egal.

Nun befülle ich ein Array mit n Einträgen dieser Art, zur Datengewinnung verwende ich die Funktionen a und b.

n = 100;
 
aRhythm = 10;
bRhythm = 20;
 
a = function(pos) {
    if (pos % aRhythm) {
        return undefined;
    } else {
        return pos;
    }
};
 
b = function(pos) {
    if (pos % bRhythm) {
        return undefined;
    } else {
        return pos;
    }
};
 
 
tableNormal = new Array();
 
tableNormal[0] = new Entry(0, 0);
for (i = 1; i < n; i++) {
    tableNormal[ i ] = new Entry(a(i), b(i));
} 

Nun ist das Array tableNormal unregelmäßig gefüllt, um sie jetzt so wie gewünscht auslesen zu können, schenke ich dem Array tableNormal die Funktion get:

tableNormal.get = function(pos) {
    var entry = this[pos];
 
    if ((entry.a != null) && (entry.b != null)) {
        return entry;
    }
 
    var i = pos + 1;
    var a, b;
 
    while(i-- > 0) {
        if (this[ i ].a != null) {
            a = this[ i ].a;
            break;
        }
    }
 
    i = pos + 1;
 
    while(i-- > 0) {
        if (this[ i ].b != null) {
            b = this[ i ].b;
            break;
        }
    }
 
    return (new Entry(a, b));
}; 

Sie tut nichts anderes, als für beide Werte a und b von der gefragen Position pos Schritt für Schritt weiter nach vorne zu laufen, bis sie einen Wert gefunden hat, und gibt diese dann als neuen Eintrag zurück.
Wie man sieht ist die get Funktion recht aufwendig, vielleicht fällt ja dem ein oder anderen noch eine Optimierung ein.

2. Ansatz: Vererbung
Hinsichtlich der objektorientierten Programmierung erinnert einen der Aufbau der 2. Tabelle an die Vererbung von Eigenschaften von Klasse zu Klasse. Und da dieser Mechanismus in Flash dank dem Prototyp-Konzept sehr flexibel ist, lässt er sich für dieses Problem wunderbar ausnützen.

Zuerst brauche ich eine neue erbende Klasse für die Einträge:

EntryInheriting = function(pre, a, b) {
    this.__proto__ = pre;
 
    if (a != null) this.a = a;
    if (b != null) this.b = b;
};
 
EntryInheriting.prototype = new Stringable(); 

Wie man sieht braucht der Konstruktor den Vorgänger pre, um von diesem zu erben. Mit der gewöhnlichen Vererbung bei Klassen hat das allerdings nicht mehr allzuviel zu tun, schließlich erstelle ich die Vererbungskette zur Laufzeit für Instanzen, und nicht im Voraus für Klassen (wie ich es etwa zum Erben der toString-Methode der Stringable-Klasse mache).

Wieder erstelle ich eine Tabelle anhand der Funktionen a und b:

tableInheriting = new Array();
 
tableInheriting[0] = new EntryInheriting(EntryInheriting.prototype, 0, 0);
for (i = 1; i < n; i++) {
    tableInheriting[ i ] = new EntryInheriting(tableInheriting[i - 1], a(i), b(i));
} 

Man beachte, dass dem nullten Eintrag der Eigenschaftsspeicher der EntryInheriting-Klasse übergeben wird, damit erbt der erste Eintrag wie jede gewöhnliche Instanz einer Klasse. Über diesen Schritt bekommen er, und alle nachfolgenden Einträge Zugriff auf die toString-Methode, was bei einem späten Eintrag ziemlich ungünstig ist, da dieser dann nur über hundert Ecken an sie heran kommt, das ließe sich durch eine eigene Referenz auf die toString-Methode für jeden Eintrag leicht (wenn auch unschön) lösen, soll aber hier keine Rolle spielen.

Der Zugriff auf ein Element erfolgt hier gewohnt und ohne Umwege wie eine get-Funktion durch den Array-Zugriff, allerdings muss man sich dessen bewusst sein, dass die Werte von a und b erst dann ermittelt werden, wenn man auf sie zugreift, man sollte sie also bei mehrmaliger Verwendung zwischenspeichern.
Ein unschönes Problem, das dieser Lösung das Genick brechen kann ist, dass Vererbungsketten in Flash auf eine Tiefe von 256 Schritten beschränkt sind.


3. Ansatz: __resolve
In letzter Zeit stolpere ich immer wieder über Probleme die sich mit __resolve relativ leicht lösen lassen, so auch dieses.
Wenn man versucht auf die Eigenschaft eines Objektes zuzugreifen, dann spielt sich intern folgendes ab:
1. Flash guckt, ob das Objekt selbst die Eigenschaft besitzt, wenn ja, gibt es ihren Wert zurück und ist zufrieden.
2. wenn nicht, versucht, ob das Objekt diese Eigenschaft von einer Superklasse erbt, wenn ja gibt es sie zurück, und ist zufrieden.
3. letzter Rettungsanker ist die Methode __resolve. Besitzt das Objekt eine solche (sie wird auch wieder mit 1. und 2. ermittelt), so wird sie mit dem Namen der gesuchten Eigenschaft als Parameter aufgerufen, und ihre Rückgabe wird als Wert der Eigenschaft zurückgegeben.
4. Wenn alles nichts geholfen hat, gibt Flash undefined zurück.

Wieder benötigen wir eine neue Klasse für die Einträge, auch diesmal muss jeder Eintrag wissen, welches sein Vorgänger ist:

EntryResolving = function(pre, a, b) {
    this.pre = pre;
 
    if (a != null) this.a = a;
    if (b != null) this.b = b;
};
 
EntryResolving.prototype = new Stringable();
 
EntryResolving.prototype.__resolve = function(propName) {
    return this.pre[propName];
}; 

Wie man sieht erbt jeder Eintrag die __resolve-Methode, welche nichts anderes tut, als beim vorhergehenden Eintrag nach der Eigenschaft zu fragen.

Wieder muss die Tabelle befüllt werden:

tableResolving = new Array();
tableResolving[0] = new EntryResolving(null, 0, 0);
for (i = 1; i < n; i++) {
    tableResolving[ i ] = newEntryResolving(tableResolving[i - 1], a(i), b(i));
} 

Auch hier greift man ganz normal auf die Array-Felder zu, auch hier muss man beachten, dass konkreten Werte erst beim Zugriff ermittelt werden, und deshalb bei mehrmaligem Zugriff zwischengespeichert werden sollten.
Das schöne an dieser Variante ist, dass sie, obwohl es sich um einen rekursiven Vorgang handelt, nicht auf 256 Schritte beschränkt ist, scheinbar beobachtet Flash die Tiefe von __resolve-Schritten nicht. Das ist gut für uns, kann aber in einer Endlosschleife enden, wenn man die Referenz auf den Vorgängereintrag falsch (sprich auf den Eintrag selbst) setzt.


Der Benchmark
Das interessanteste für die Anwendung ist natürlich der Geschwindigkeitsvergleich, und der sieht gut aus.
Bei 200 Tabelleneinträgen, und den Eintragsrhythmen 10 und 20 für a und b ist sind die zwei alternativen Methoden etwas schneller als 10 mal so schnell wie die manuelle Variante, das kann sich sehen lassen.
Umso spärlicher die Tabelle gefüllt ist, umso deutlicher gewinnen die beiden letzten Varianten, was auch klar ist, schließlich steigt damit der Anteil an der Rechenzeit, welcher für das Auffinden der Eigenschaften benötigt wird.

Zwischen der zweiten und der dritten Variante lassen sich keine zuverlässigen Unterschiede messen, zumal die Anzahl der Wiederholungen bei der zweiten ja auf 256 beschränkt ist. Das zeigt, das die Zeit für Interne Vorgänge wirklich zu vernachlässigen sind, schließlich setzt die dritte Variante später im Auffinden der Eigenschaft an, als die zweite.

So, ich hoffe ich konnte einigen einen kleinen Einblick in die Möglichkeiten von Flash geben, vielleicht kann sogar mal jemand davon profitieren, wenn ja, so würde ich mich brennend dafür interessieren, wofür in aller Welt man das noch gebrauchen kann.

Im Anhang findet ihr noch (spärlich kommentiert) das gesammte Script.

Gruß,

Janosch

[Janoscharlipp]

War das zu viel zum lesen?
Interessiert das keinen?
Sowiso alles kalter Kaffee?
Unverständlich ausgedrückt?

hmm … vielleicht stößt ja mal jemand in der Suche drauf

[AAI]

mir persönlich ist deine Ausführung
etwas zu abstrakt. Es geht hier um
eine Performance-Steigerung. Weiß
aber nicht wie und wo ich das an-
wenden könnte. Glaube, dass ich
zu einer Mehrheit gehöre, die das
Script nicht wirklich versteht

[Janoscharlipp]

Wo genau hapert es denn im Script?

Eigentlich ist alles, was ich sagen wollte, dass Flash noch einige wenig bekannte Möglichkeiten bietet, einige Probleme einfacher, und wesentlich schneller zu lösen, als man es von den konventionellen Lösungen erwarten könnte.

Und um diese Aussage etwas zu untermauern, dachte ich, ich zeige es am besten an einem Beispiel, mit konkreter Umsetzung, deshalb das Script.

Ich bin mir allerdings nicht sicher, ob sich der Vererbungsmechanismus, und __resolve so vielseitig ausnützenlassen, wie ich es anfangs gehofft hatte …