WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

  
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Suche nach Wertepaaren in n x 2 Matrix beschleunigen
 

Muck
Forum-Newbie

Forum-Newbie

Beiträge: 5
Anmeldedatum: 12.06.12
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.06.2012, 16:08     Titel: Suche nach Wertepaaren in n x 2 Matrix beschleunigen
  Antworten mit Zitat      
Hallo,

leider bin ich noch etwas ungeübt mit Matlab. In einem Unterprogramm möchte ich feststellen wie oft sich Wertepaare (jeweils in einer Zeile) innerhalb eines Wertebereiches (std) in einer n x 2 Matrix wiederholen. Mein Unterprogramm funktioniert zwar, jedoch ist die Rechenzeit propotional zu n^2. Da ich sehr große Matrizen bis ca. 88000000x2 überprüfen will sollte ich einen Rechenzeitaufwand realiseren der deutlich geringer ist. Ich bin mir sicher dass ihr mir bestimmt hilfreiche Ideen geben könnt Smile

Grüße und vielen Dank im Voraus !!!

Code:
%

g = uint32(zeros(n,1));
std=2e-004;
j = randn(n,2)

 for i=0:n,
   
 
    a = j(:,1)-j(i+1,1);
    b = j(:,2)-j(i+1,2);
   
     e = abs(a);
     e(e<std&e>0)=1;
     e(e<1|e>1)=0;
     
       f = abs(b);
       f(f<std&f>0)=1;
       f(f<1|f>1)=0;
 
         g(i+1,:) = sum(e&f);
   
end

 
Private Nachricht senden Benutzer-Profile anzeigen


Sirius3
Forum-Guru

Forum-Guru

Beiträge: 441
Anmeldedatum: 11.11.11
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.06.2012, 17:49     Titel:
  Antworten mit Zitat      
Hallo Muck,

zuerst ein paar allgemeine Anmerkungen:
Matlab zählt Indizes von 1 bis n. Deine Schleife läuft von 0 ab,
wobei immer auf i+1 zugegriffen wird. Im letzten Schleifenschritt
läuft also i+1 über das Ende der j-Matrix hinaus, und müßte
eigentlich mit einem
Index exceeds matrix dimensions.
abbrechen.
Besser die For-Schleife von 1:n laufen lassen.
Die Zeilen
Code:
e = abs(a);
     e(e<std&e>0)=1;
     e(e<1|e>1)=0;

haben ein paar seltsame Nebeneffekte.
Ist ein Element a(k)==a(i+1) zählt es nicht als gleich (e>0-Abfrage)
hat es aber den Abstand 1: a(k)+1==a(i+1) zählt es als gleich (e<1|e>1-Abfrage)
Kürzer gehts mit:
Code:
g(i+1,:) = sum(abs(a)<std&abs(b)<std);


Nun zur Komplexität:
Wenn Du die Wertepaare sortierst
Code:
[k,idx]=sort(j(:,1)^2+j(:,2)^2)

dann mußt Du nur in einer Umgebung k(a)+sqrt(2)*std>k(i)>k(b)-sqrt(2)*std
die Paar-Gleichheit überprüfen und hast effektiv wahrscheinlich O(n*log(n)).

Grüße
Sirius
Private Nachricht senden Benutzer-Profile anzeigen
 
Muck
Themenstarter

 Forum-Newbie

Forum-Newbie

Beiträge: 5
Anmeldedatum: 12.06.12
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.06.2012, 09:13     Titel:
  Antworten mit Zitat      
Hallo Sirius,

Vielen Dank für die schnelle Antwort und die Tipps. Den Code werde ich mir gleich einmal ansehen. Ich hatte vergessen zur erwähnen dass ich die Matrix "j" zuvor auch mit einer for-Schleife erzeugt hatte bei der "i" ebenso bei 0 startete.

Grüße,

Sebastian
Private Nachricht senden Benutzer-Profile anzeigen
 
Muck
Themenstarter

 Forum-Newbie

Forum-Newbie

Beiträge: 5
Anmeldedatum: 12.06.12
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 13.06.2012, 12:34     Titel:
  Antworten mit Zitat      
Hallo Sirius,

leider habe ich zum Thema Komplexität noch nicht den gesamten Durchblick.
Damit die Sortierung funktioniert muss ich bei der quadrierung noch einen Punkt setzen (skalare quadrierung der Matrixwerte).

Code:
%

[k,idx]=sort(j(:,1).^2+j(:,2).^2)

 


Was ist mit der Indizierung von k(a),k(i) und k(b) hier gemeint ?

k(a)+sqrt(2)*std>k(i)>k(b)-sqrt(2)*std

Grüße,

Sebastian
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

 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
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.