Hallo liebes Forum,
für ein Projekt möchte ich vom Ursprung aus von einem Datensatz von Punkten mit x und y Koordinaten, eine Anzahl nPoints an direktionalen nächsten Nachbarn finden. Als Beispiel: Die "Richtung" der Punkte sei dadurch gegeben, in welchem Quadrant die Punkte liegen, das ist dann das "Segment" in dem der jeweilige Punkt liegt. Am liebsten hätte ich dann etwa nPoints/4 aus jedem Segment, wenn ein Segment aber weniger Punkte beinhaltet, dann muss das aus den anderen Segment geholt werden.
Meine Funktion dafür funktioniert, wird aber sehr oft augerufen und ist mit > 90% der Laufzeit das absolute Bottle Neck. Hier ist ein Auszug aus dem Code. Das in der while Schleife wird dabei mehrere Millionen mal aufgerufen und ist einfach zu lahm. Ich würde mich über neue Ansätze, die nächsten Nachbarn aus den Quadranten zu finden, sehr freuen.
Code:
% Beispieldaten erzeugen, die irgendwie um (0,0) in der Ebene liegen. Finde % die Quadranten, in denen die Punkte P liegen.
P = rand(100,2)-0.2; % Daten um (0,0) streuen
P = [P; rand(30,2)*0.1]; % künstlich den ersten Quadranten dicht besetzen
% ----- Ordne dem Punkten in Prot ihren Quadranten (ihr Segment) zu
segmentedIndices = cell(4,1);
for iQuadrant = 1:4 switch iQuadrant
case1
idx = find(P(:,1) > 0 & P(:,2) > 0);
case2
idx = find(P(:,1) < 0 & P(:,2) > 0);
case3
idx = find(P(:,1) < 0 & P(:,2) < 0);
case4
idx = find(P(:,1) > 0 & P(:,2) < 0);
end
segmentedIndices{iQuadrant,1} = idx;
end
% ----- nach euklidischem Abstand zum Ursprung sortierte Indexlisten
order = cell(size(idx));
for seg = 1:4;
[~,idx] = sort(sqrt((P(segmentedIndices{seg},1)).^2 + (P(segmentedIndices{seg},2)).^2));
order{seg,1} = segmentedIndices{seg}(idx);
end
%% ------ Ab hier ist es zu langsam ------ % Jetzt sind die vier Richtungen (Quadranten) fertig und das Sammeln der % Punkte beginnt.
nPoints = 50;
pointsgathered = 0; % bereits gesammelt
seg = 0; % welches Segment?
takenFromSeg = zeros(4,1); % wieviele aus welchem Segment genommen?
% man kann nicht mehr sammeln als da sind
totalInSeg = cellfun(@length, segmentedIndices);
nPoints = min(nPoints,sum(totalInSeg));
idxList = NaN(nPoints,1);
% ----- hier wird eingesammelt while pointsgathered < nPoints
% update segment to take point out of ...->1->2->3->4->1-> ...
seg = mod(seg,4)+1;
% if there are less taken from the segment seg, than there are points % in that segment, we take one more out of it. if takenFromSeg(seg) < totalInSeg(seg)
idxList(pointsgathered+1,1) = order{seg}(takenFromSeg(seg)+1);
pointsgathered = pointsgathered + 1;
takenFromSeg(seg) = takenFromSeg(seg)+1;
% else-- there are no more points to take from that segment, so we % carry on with the next segment end
Eine weitere Umschreibung des Problems könnte folgende sein, die beeinflusst vielleicht nicht so sehr, wie der obige Beitrag, durch vorgefertigten Code:
Ich habe 4 Töpfe, i = 1 bis 4. Dabei hat der i-te Topf Elemente und ich möchte daraus , mit folgenden Einschränkungen
1) (ich ziehe am Ende genau N Elemente)
2) alle sind natürliche Zahlen
3) (nicht mehr ziehen als da sind)
4) sollte ungefähr N/4 ergeben, im Idealfall, wenn alle Töpfe mindestens N/4 Elemente haben.
5). (Es sind genug Elemente auf die Töpfe verteilt).
Eigentlich ist es genau dieses Szenario, das ich auf irgendeine Weise gerne lösen möchte. Falls da jemand einen schnelleren Ansatz hat als den, den ich oben postete, dann wäre das dufte.
Viele Grüße,
Nras.
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