Performance-Sünden in Matrix-Klasse?

tobiii

Aktives Mitglied
Thread Starter
Dabei seit
20.05.2006
Beiträge
1.226
Reaktionspunkte
40
Hallo Leute!

Habe gerade ein paar Tage Zeit und dachte mir, ich lese mich mal in die Gründzüge von Objective-C ein. Als kleines Projekt wollte ich ein paar wissenschaftliche Algorithmen implementieren und ein bisschen mit Zellulären Automaten spielen. Die meisten Programme liegen bisher in MATLAB oder auch Python vor. Da es keine "mitgelieferte" Matrix-Klasse gibt, meine ich, dass dies eine gute Gelegenheit wäre, die erste eigene Objective-C Klasse zu schreiben.
Bevor ich jetzt aber hier noch viel mehr Zeit rein versenkte dachte ich mir, ich frage mal hier im Forum nach, ob jemand mit mehr Erfahrung vielleicht Lust hat, mal kurz über meine Implementierung drüber zu schauen und nach besonders schlimmen (Performance-) Sünden ausschau zu halten.

Hier ist meine Matrix.m:

Code:
@implementation Matrix

// generate empty matrix with size y X x
-(id)initWithY:(int)y X:(int)x{
	
	[super init];
	ymax=y;
	xmax=x;
	M = [[NSMutableArray arrayWithCapacity:y*x] init];
	return self;
}

// generate zero Matrix with size y X x
-(id)zerosWithY:(int)y X:(int)x{
	
	[self initWithY:y X:x];
	for(int i=0; i<ymax*xmax; i++){
		[M addObject:[NSNumber numberWithDouble:0]];
	}
	return self;
}

// set entry at index (y,x) to double value
-(void)set:(double)value atY:(int)y X:(int)x{
	
	[M replaceObjectAtIndex:(xmax*y+x) withObject:[NSNumber numberWithDouble:value]];
}

// get entry at index (y,x) as double value
-(double)Y:(int)y X:(int)x{
	
	double r = [[M objectAtIndex:(xmax*y+x)] doubleValue];
	return r;
}

// generate random matrix with floats [0,1) with size y X x
-(id)randomWithY:(int)y X:(int)x{
	
	[self initWithY:y X:x];
	for(int i=0; i<ymax*xmax; i++){
		double val=((double)arc4random() / ARC4RANDOM_MAX);
		[M addObject:[NSNumber numberWithDouble:val]];
	}
	return self;
}

// generate random binary matrix with doubles (0,1) and population density p
-(id)randomBinMatrixWithY:(int)y X:(int)x Density:(double)p{
	
	[self initWithY:y X:x];
	for(int i=0; i<ymax*xmax; i++){
		double val=((double)arc4random() / ARC4RANDOM_MAX);
		if(val<=p){
			[M addObject:[NSNumber numberWithDouble:1]];
		}
		else{
			[M addObject:[NSNumber numberWithDouble:0]];
		}
	}
	return self;
}

@end

Das ganze gibts etwas übersichtlicher auch hier:

http://pastie.org/private/k8tgjqviu4y3x0mrnkrrpw


Eventuell brauche ich später noch eine 3D-Matrix, ich hätte diese jetzt einfach aus einem neuen NSMutableArray gebaut, in das ich meine Matrizen rein pflanze und eine neue Zugriffs-Methode dazu schreibe, denkt ihr, dass durch diese vorgehensweise der Code zu langsam wird?

Vielen Dank schonmal im Voraus für eure Anregungen!
 
"Zu langsam" impliziert "zu langsam für x". Was ist dein x? Soll heißen: "Premature optimization is the root of all evil" (Donald Knuth)

Aber ein paar andere Anmerkungen:

a) Die Wahl der Bezeichnung ist sehr wichtig in Objective-C/Cocoa. -initWithY:X: ist nicht richtig bezeichnet. der zweite Parameter muss klein anfangen. Außerdem ist das nicht sprechend. Entweder -initWithYSize:xSize: der -initWithHeight:width: oder gleich -initWithSize:

b) -init (super) lieert einen Wert zurück. Daher muss du das an self zuweisen. Je nachdem wie du fortfährst, musst du dann auf nil prüfen. In jedem Falle ist das tunlich.

c) Deine zero-Methode sollte eine Klassenmethode sein. Wieso benötigt man bereits eine Instanz, um eine [0] zu erzeugen?

d) Die Accessoren sind auch nicht richtig bezeichnet.

Ich weiß nicht, womit du lernst, aber eigentlich steht das in allen Büchern drin. Wenn du das aus irgendwelchen Gründen für unwichtig hältst, wirst du dich noch wundern.

BTW: NSAffineTransform
 
ansonsten gibt es auch genug effiziente implementierungen für gebräuchliche datenstrukturen unter erträglich lizenzen...
 
Aber ein paar andere Anmerkungen:

c) Deine zero-Methode sollte eine Klassenmethode sein. Wieso benötigt man bereits eine Instanz, um eine [0] zu erzeugen?


BTW: NSAffineTransform

Danke fürs Feedback! Waren sehr hilfreiche Anmerkungen! Hab das soweit mal gefixt / übernommen.

Noch eine Frage zu Punkt c): ich erzeuge eine Zero-Matrix auf diese Weise:

Matrix *testMatrix = [[Matrix alloc] zerosWithYSize:100 xSize:100];

Inwiefern ist das ungeschickt? Wie sollte die Methode korrekt implementiert sein?

Den Hinweise auf NSAffineTransform verstehe ich an dieser Stelle auch nicht so recht, oder wolltest du mir damit ein Beispiel für die Syntax liefern, an die ich mich halten sollte?

Schönen Abend,


Tobi
 
Also, das Verhältnis zwischen Convenience-Allocator und Init ist iwe folgt:

Eine Methode, die eine neue Instanz initialisiert heißt stets init… Deine zeros…-Methode müsste also als Initmethode -initWithZeros… heißen. Das ist einfach Vereinbarung.

Dann kannst zusätzlich eine Klassenmethode haben, die gleich erzeugt und initialisiert. Das nennt man einen Convenience-Allocator. Der heißt dann +matrixWithZeros… oder ähnlich, so dass man sieht, dass er eine Matrix-Instanz erzeugt. Insgesamt:
Code:
- (id)initWithZerosWithWidth:(NSUInteger)width height:(NSUInteger)height {
…
}

+zeroMatrixWithZerosWithWidth:(NSUInteger)width height:(NSUInteger)width {
   return [[[self alloc] initWithZerosWithWidth:width height:height] autorelease];
}

Sei mir nicht böse, aber das sind die Basics zur Steicherverwaltung. Und da soltest du dir wirklich irgendwie einen Einstieg besorgen. Sonst wird das hier kein Forum, sondern ein Tutorial.

Mit dem Zusatz wollte ich nur sagen, dass es schon Matrizen in Cocoa gibt. Sie reichen dir bloß nicht.
 
Noch eine Frage zu Punkt c): ich erzeuge eine Zero-Matrix auf diese Weise:

Matrix *testMatrix = [[Matrix alloc] zerosWithYSize:100 xSize:100];

Inwiefern ist das ungeschickt? Wie sollte die Methode korrekt implementiert sein?

Hier musst du, obwohl du kein Objekt mit einem Zustand benötigst, ein Objekt (mit alloc) und rufst dann an diesem Objekt eine Instanzmethode. Klassenmethoden benötigen keine Instanz, du rufst sie direkt an der Klasse:

Matrix *testMatrix = [Matrix zerosWithYSize:100 xSize:100];

Das ist schneller, da für den Ruf selbst kein Speicher ausgefasst und der Konstruktor nicht durchlaufen wird.

@Armin: In meinem Design Pattern Buch nennt man deinen Convenient Allocator "Factory Pattern".
 
Zuletzt bearbeitet:
Schneller ist das in der Regel nicht. Allerdings kann man dann optimieren.

Überhaupt sollte er daran denken, eine unveränderliche Variante zu schaffen und davon eine veränderliche Subklasse – wen die überhaupt. Das Muster heißt hier Twin-Toning oder Multi-Toning. Um es kurz zu machen:

Du wirst mutmaßlich in deiner Applikation häufiger mit [0] und [E] zu tun haben. In der jetzigen Implementierung schaffst du dafür jedesmal eine neue Instanz. Wenn du die unveränderlich machst, dann kannst du die wiederverwerten. Wie aufwändig das in deinem Code ist, insbesondere weil du verschiedene Dimensionen hast, die alle eine eigene Instanz auf Vorrat benötigen, kann ich dir nicht sagen. Aber mal so auf die Schnele programmiert und daher ohne Gewähr für gar nichts:
Code:
- (NSMatrix)zeroMatrixWithWidth:(NSUInteger)width height:(NSUInteger)height {
static zeroHeap = nil;

if( !zeroHeap ) {
   // Einmalige Halde fuer alle [0]
   zeroHeap = [[NSMutableDictionary alloc] init];
}

NSString* identifier = [NSString stringWithFormat@"%d %d", width, height];
NSMatrix* twinTone = [zeroHeap objectForKey:identifier];
if( !twinTone ) {
   // hier ganz normal erzeugen
   twinTone = [[[self alloc] initWithZerosWithWidth:width height:height] autorelease];
   [zeroHeap setObject:twinTone forKey:identifier];
}
return twinTone;
}
Es wird dann also (je Größe) nur eine Instanz für alle [0] erzeugt. Das funktioniert natürlich nur, wenn die unveränderlich sind. Sonst könnte man die ja ändern – für alle im Programm. Das will man nicht. :)
 

@Armin: In meinem Design Pattern Buch nennt man deinen Convenient Allocator "Factory Pattern".
*räusper* Zunächst einmal Amin, also ohne R.

Factorys sind ja allgemeiner. Beispiel:
Code:
NSString* name = [NSString stringWithString:@"Amin"];
name = [name stringByAppendingString:@" Negm-Awad];
Beides sind Fabrikmethoden, nur das obere ist ein Convenience-Allocator.
 
Jungs, auf die Gefahr euer Fachgespräch zu unterbrechen :cake:

Hab das jetzt mal umgebastelt auf Klassenmethoden funktioniert soweit auch gut.

Unveränderliche Matrizen sind für mich eigentlich nicht interessant (zumindest nicht für meine Anwendungen, wenn sich meine Implementierung dadurch beschleunigen lassen sollte dann ist das natürlich was anderes...), meine Simulationen operieren eigentlich immer auf einer Matrix und ändern dort dann itterativ einzelne Einträge oder operieren zwischen zwei Matrizen, die dann jeweils ihre Einträge ändern.

Nachdem das jetzt soweit läuft wäre der nächste Schritt dann für mich, eine Methode zu schreiben, die die Matrix als ASCII Datei (bitte nicht schlagen..) speichert.....
 
Geil, ich verstehe kein Wort, kann es aber trotzdem nicht lassen, weiterzulesen. ;)
 
*räusper* Zunächst einmal Amin, also ohne R.

Sorry, werds mir merken. Aber für jemanden mit ner akkuten Namensschwäche wars doch gut ;)

Factorys sind ja allgemeiner. Beispiel:
Code:
NSString* name = [NSString stringWithString:@"Amin"];
name = [name stringByAppendingString:@" Negm-Awad];
Beides sind Fabrikmethoden, nur das obere ist ein Convenience-Allocator.

Nur nochmal kurz dazu: Eine Factory erzeugt bei mir ein *neues* Objekt. Deine zweite manipuliert es eher, ist in meiner Anschauung und auch in der von Holub und GoF keine Factory. Aber das führt hier doch zu weit.

@Mr. D
Dann verschaff dir ein gutes Buch und versuche zu verstehen ;) Hat noch niemandem geschadet.
 
Sorry, werds mir merken. Aber für jemanden mit ner akkuten Namensschwäche wars doch gut ;)



Nur nochmal kurz dazu: Eine Factory erzeugt bei mir ein *neues* Objekt. Deine zweite manipuliert es eher,
Nein, es erzeugt ein neues. Das wird auch sofort klar, wenn man Mutable-Instanzen hat:
Code:
NSMutableString* original = [NSMutableString stringWithString:@"Amin"];
NSString* anotherOne = [original stringByAppendingString:@" Negm-Awad];
[original replaceCharactersInRange:NSMakeRange( 0, 4 ) withString:@"Armin"];

ist in meiner Anschauung und auch in der von Holub und GoF keine Factory. Aber das führt hier doch zu weit.
Das hätte ich ganz im Gegenteil eher belegt.

(Wenn du die die formelle Bezeichnung meinst, dann sind beide keine Farbikmethoden, jedenfalls wissen wir das nicht. +++ Dann ergibt dein erster Beitrag jedoch keinen Sinn. /+++)

@Mr. D
Dann verschaff dir ein gutes Buch und versuche zu verstehen ;) Hat noch niemandem geschadet.
 
Zuletzt bearbeitet:
Bevor ich jetzt aber hier noch viel mehr Zeit rein versenkte dachte ich mir, ich frage mal hier im Forum nach, ob jemand mit mehr Erfahrung vielleicht Lust hat, mal kurz über meine Implementierung drüber zu schauen und nach besonders schlimmen (Performance-) Sünden ausschau zu halten.
Ich würde intern vermutlich keine ObjC-Datenstrukturen verwenden sondern C arrays + primitive Datentypen – wenn es dir schon um Geschwindigkeit geht.

Eventuell brauche ich später noch eine 3D-Matrix, ich hätte diese jetzt einfach aus einem neuen NSMutableArray gebaut, in das ich meine Matrizen rein pflanze und eine neue Zugriffs-Methode dazu schreibe, denkt ihr, dass durch diese vorgehensweise der Code zu langsam wird?
Ich würde generell mit einem N-dimensionalen Array planen.
 
Hab das ganze gerade mal spaßeshalber umgebaut und mit

double *M =malloc(sizeof(double)*y*x);

probiert, ein Durchlauf zum Erzeugen von 100 1000x1000 Zufalls-Matrizen dauert ziemlich exakt 1/10tel der Zeit verglichen mit dem Fall, das M als NSMutableArray verwendet wird.
 
Ja, klar, wenn du das auf einen Schwung mit C erzeugst, ist das deutlich schneller. Allerdings frage ich mich –*und da bin ich jetzt nicht mehr firm genug –, ob du die Größe so berechnen darfst. Kann das nicht mit Aligning problematisch werden? Ist wirklich etwa sizeof( char ) * N dasselbe wie sizeof( char[N] )?

Keine Ahnung mehr, vielleicht ein C-Recke?
 
Hi,

die reine C-Variante ist in Deiner Form, naja, fehleranfällig...
Wenn überhaupt, pack die Matrix in ein struct

Code:
struct _matrix
{
   int rows;
   int columns;
   double *values;
} matrix;
Dann würdest Du noch Verwaltungsfunktionen (z.B. createMatrix( int rows, int columns ) sowie deleteMatrix( struct matrix* matrixPointer ) benötigen.

Das wiederum bedeutet, dass Du es gleich in einer OO-Sprache machen solltest.
Für Matrizen und Deine Laufzeitwünsche würde sich C++ und eine Template-Lösung anbieten.
Die gibt es auch schon, z.B.hier:
http://www.boost.org/doc/libs/1_39_0/libs/numeric/ublas/doc/index.htm

Gruß, SMJ
 
Zuletzt bearbeitet:
Ich war bisher davon ausgegangen, dass er die einzelnen Arrays schon in eine Instanz gepackt hat. Die einfach so herumfliegen zu lassen, ist in der tat gefährlich!
 
Ich war bisher davon ausgegangen, dass er die einzelnen Arrays schon in eine Instanz gepackt hat. Die einfach so herumfliegen zu lassen, ist in der tat gefährlich!

Ich verwende weiterhin meine alte Klasse,

double *M =malloc(sizeof(double)*y*x);

ist eine der drei Instanz-Variablen. Funktioniert bisher erstaunlich gut, allerdings hat meine Matrix -> export nach ASCII file Routine irgendwo ein großen Speicherleck ;-)
 
Allerdings frage ich mich –*und da bin ich jetzt nicht mehr firm genug –, ob du die Größe so berechnen darfst. Kann das nicht mit Aligning problematisch werden? Ist wirklich etwa sizeof( char ) * N dasselbe wie sizeof( char[N] )?

Keine Ahnung mehr, vielleicht ein C-Recke?
Bei den Standarddatentypen sollte das egal sein, und sonst eigentlich auch, denn wenn man irgendwelche Strukturen in das Array packt, wurden die ja schon „aligned“. Aber ich kenne auch nicht jeden esoterischen Einzelfall.

Das Sumpfmonster hat natürlich recht, C++ wurde schließlich für genau solche Anwendungsfälle entwickelt, aber zum Lernen von ObjC bietet sich eine Lösung in C imo mehr an.
 
Zuletzt bearbeitet:
Zurück
Oben Unten