Verfasst am: 21.10.2010, 11:48
Titel: Werte zählen in einer Zx2 Matrix
Hallo Leute,
ich steh da vor einem kleinen Problem zu dem mir keine Lösung einfällt. Ich hab eine Matrix der Dimension 1600x2. Die Einträge entsprechen Koordinaten von Punkten (Spalte1 = X-Koordinate, Spalte2 = Y-Koordinate, Zeilen entsprechen den einzelnen Punkten).
Ich würde nun gerne zählen, wie oft der selbe Punkt vorkommt. Die Ausgabe sollte so aussehen, dass eine Zx3 Matrix entsteht, in der wieder in Spalte1 die X-Koordinate, in Spalte 2 die Y-Koordinate und in Spalte 3 die Anzahl dieses Punktes steht.
UNIQUE und ISMEMBER beinhalten neben den versteckten Schleifen auch noch zwei Sortierungen. Deswegen könnte man das deutlich beschleunigen, wenn man aus den beiden Spalten für X- und Y-Koordinaten eine einizge erzeugen könnte. Dann wäre HISTC anwendbar, man bräucht für die Edge-Werte aber doch UNIQUE.
Wenn X und Y z.B. ganzzahlig ist und zwischen 0 und 255 liegt, wäre X*256+Y hilfreich. Aber eine allgemeine Lösung gibt es da nicht und für Floatingpoint-Zahlen ist das Problem der Rundungsfehler sehr hinderlich.
Folglich wäre dies ein idealer Kandidat für ein C-Mex-Programm, wenn es denn wirklich zeitkritisch ist.
UNIQUE und ISMEMBER beinhalten neben den versteckten Schleifen auch noch zwei Sortierungen. Deswegen könnte man das deutlich beschleunigen, wenn man aus den beiden Spalten für X- und Y-Koordinaten eine einizge erzeugen könnte. Dann wäre HISTC anwendbar, man bräucht für die Edge-Werte aber doch UNIQUE.
Gruß, Jan
Und? Ich habe diese aber nicht verschachtelt. ISMEMBER ist auf Zahlen sehr schnell, Schleifen braucht es nur für Strings um Indexen zu erzeugen, danach geht es zu einer C-Funktion.
@Sco du hast 2 Schleifen. BSXFUN gehört zu der versteckten Schleifen
Jan S hat Folgendes geschrieben:
UNIQUE und ISMEMBER beinhalten neben den versteckten Schleifen auch noch zwei Sortierungen
denny hat Folgendes geschrieben:
Und? Ich habe diese aber nicht verschachtelt. ISMEMBER ist auf Zahlen sehr schnell, Schleifen braucht es nur für Strings um Indexen zu erzeugen, danach geht es zu einer C-Funktion.
Wenn Du sagst, dass BSXFUN eine versteckte Schleife ist, obwohl es in eine Builtin-Funktion ist, erwähne ich, dass dies für UNIQUE und ISMEMBER auch zutrifft.
Ich habe nicht den Eindruck, dass ISMEMBER schnell ist. Die zugrunde liegende MEX-Funktion ISMEMBC ist recht fix, aber das Sortieren kann das sehr leicht zunichte machen.
Ohne Frage würde ich die von Dir angegebene Lösung empfehlen, wenn das Problem nicht arg zu zeitkritisch ist. Falls aber doch, ist der Overhead deutlich:
1. Sortieren der Daten in UNIQUE(rows)
==> ISMEMBER(rows):
2. Aufruf von UNIQUE für beide Inputs, also nochml 2 Sortierungen
3. SORTROWS([au;su]): Noch eine Sortierung, und dabei wird noch nicht einmal ein MergeSort verwendet, das ausnutzen würde, dass beide Inputs schon sortiert sind.
4. Da ISMEMBER mit mehr als einem Output aufgerufen wird, wird intern nochmals ISMEMBER aufgerufen für "Find repeats among original list". Das sortiert die Indices noch einmal, falls es weniger als 1000 sind. Andernfalls hilft ein zeitraubender ISSORTED-Test das Sortieren zu vermeiden - das ist aber nicht unbedingt schneller.
Eine naive Implementierung als C-Mex, die ganz banal jedes Element aus einem Array mit allen Elementen aus einem zweiten Array vergleicht ist etwa 2 bis 4 mal schneller für kleine Vektoren (etwa NUMEL=100), und bei größeren Vektoren (~1000 Elemente) kommt es auf den Grad der Sortierung an, ob das naive C-Mex oder ISMEMBER schneller ist. Für > 10^5 Elemente ist das Suchen auf jeden Fall aufwändiger als das Sortieren. Ein einmaliges Sortieren wäre aber auf alle Fälle sinnig.
Wenn Du sagst, dass BSXFUN eine versteckte Schleife ist, obwohl es in eine Builtin-Funktion ist, erwähne ich, dass dies für UNIQUE und ISMEMBER auch zutrifft.
Das ist mir klar, überall wo Sortieren/ Suchen vorkommt, sind Schleifen nötig. Ich wollte bloß damit sagen, dass Sco hat BSXFUN in eigenen verschachtelt, also hat er in schlimmsten Fall schon Laufzeit von O(n³), ich habe zwar auch Schleifen, habe aber in schlimmsten Fall Laufzeit etwa von O(2n²+n)=O(n²)
Ich will damit sagen, dass Vorschachtelung ist der Oberkiller, mag sein die Befehle führen doppelte Operationen aus und die Laufzeit verdoppelt sich dadurch. Aber dass ist halt wie ich es mit Matlab internen Funktionen zu Lösung komme.
Ich glaube schon, dass du bei Cell viel rausholen kannst, bei Zahlen-Matrizen bin ich da skeptischer. Matlab ist ja auf Matrizen optimiert. Da bin ich auf deine Mex-Lösung gespannt.
Mich hätte aber noch mehr interessiert, wie du es mit Matlab mitteln gelöst hättest, das wäre für viele hier die mit C/C++ nicht arbeiten bestimmt interessanter.
Ich glaube schon, dass du bei Cell viel rausholen kannst, bei Zahlen-Matrizen bin ich da skeptischer.
Ich auch.
Zitat:
Mich hätte aber noch mehr interessiert, wie du es mit Matlab mitteln gelöst hättest, das wäre für viele hier die mit C/C++ nicht arbeiten bestimmt interessanter.
Das ist ja immerhin auch ein Matlab-Forum. Also:
Code:
% VERSION 1
x = fix(rand(16, 2) * 4); % Small test data to check results [a, b, c] = unique(x, 'rows');
[u, v] = histc(c, 1:max(c));
Z = [x, u(v)];
Ein ISMEMBER(rows) kann man sparen, wenn man UNIQUE(rows) mit drei Outputs benutzt. HISTC ist als built-in (C-Mex) Funktion schneller als eine Schleife und "sum(pos==k)" (aus Dennies Lösung).
Nun ist HISTC noch ziemlich flexibel und würde auch Werte zwischen den ganzzahligen Schritten akzeptieren. ACCUMARRAY ist etwas einfacher gestrickt und damit auch schneller:
Code:
% VERSION 2 [a, b, c] = unique(x, 'rows');
f = accumarray(c, 1);
Z = [x, f(c)];
40% schneller als mit HISTC. Aber ziemlich unübersichtlich. Ehrlich gesagt ist es optisch gesehen sogar richtig häßlich. Wenn also irgend jemand verstehen möchte, was genau geschieht, wird das sicherlich mehr Zeit kosten, als die tolle Laufzeit jemals wieder einbringen wird. Deshalb empfehele ich:
- Version1 für alte Matlab Versionen (kein ACCUMARRAY),
- Version2 für interessierte Nutzer eines neuen Matlab,
- Version3 falls die Laufzeit wirklich wichtig wird und niemand das Programm später debuggen muss.
Gerne. Ich habe alle drei Möglichkeiten ausprobiert, um zu testen, was eigentlich schneller ist - das kann aber je nach Matlab-Version anders ausfallen: Manchmal kann der JIT-Compiler einer neuen Version genau erkennen, was der Programmierer eigentlich wollte, und das drastisch beschleunigen.
Und als ich nun schon drei Versionen eingetippt hatte, konnte ich sie auch gleich posten.
Gruß, Jan
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS