Finden der nächstmöglichen Werte von zwei Wörterbücher

Nehmen wir an, Sie haben zwei vorhandene Wörterbücher A und BFinden der nächstmöglichen Werte von zwei Wörterbücher

Wenn Sie bereits einen ersten zwei Elemente aus Wörterbücher A und B mit Werten A1 = 1.0 und B1 = 2.0 wählen bzw. ist es eine Möglichkeit, um zwei verschiedene existierende Elemente in den Wörterbüchern A und B zu finden, die jeweils unterschiedliche Werte haben (dh A2 und B2) von A1 und B1, und würde auch den Wert (A2-A1)**2 + (B2-B1)**2 minimieren?

Die Anzahl der Elemente im Wörterbuch ist nicht festgelegt und kann 100.000 überschreiten.

Bearbeiten - Das ist wichtig: die Schlüssel für A und B sind die gleichen, aber die Werte für diese Schlüssel in A und B sind entsprechend unterschiedlich. Eine bestimmte Schlüsselwahl führt zu einem geordneten Paar (A1, B1), das sich von jedem anderen möglichen Paar (A2, B2) unterscheidet - verschiedene Schlüssel haben unterschiedliche Reihenfolgepaare. Zum Beispiel können sowohl A und B den Schlüssel 3,4 haben und dies wird einen Wert von 1.0 für dict A und 2.0 für B ergeben. Dieser eine Schlüssel wird dann mit jedem anderen Schlüssel verglichen, der möglich ist, das andere geordnete Paar zu finden (d. H. Sowohl den Schlüssel als auch die Werte der Gegenstände in A und B), der die quadrierten Unterschiede zwischen ihnen minimiert.

Quelle

2016-09-09 Mathews24

Ihre Frage ist nicht vollständig. Kümmert es Sie, was die entsprechenden Schlüssel zu A2 & B2 sind? Brauchst du nur die Werte? Wenn A2 & B2 mehr als einmal angezeigt werden, müssen Sie eine Liste aller Schlüssel zurückgeben? Ozgur (der seinen Kommentar anscheinend gelöscht hat) ist jedoch auf dem richtigen Weg, Sie werden nach Werten sortieren. –

@MaxWen Ich gebe nicht unbedingt an, was die Schlüssel selbst sind, da sie variieren können.Sie werden normalerweise Paare der Form "j, k" sein, wobei j und k ganze Zahlen sind, aber das ist keine strenge Voraussetzung für meine Frage. Ein allgemeinerer Ansatz wäre wünschenswert. Die Hauptaufgabe besteht darin, Elemente in den Wörterbüchern mit nahe - aber nicht denselben Werten zu finden. Es wird eine Rückkehr der zwei Schlüssel von "A" und "B" mit dem nächsten Wert zu "A1" und "B1" gesucht. Ja, ich dachte, eine Art Sortiermethode wäre notwendig, aber jede besonders effiziente Methode wäre sehr hilfreich. – Mathews24

@MaxWen Zum Hinzufügen sind alle Schlüssel im Wörterbuch bereits bekannt. Obwohl das Element (d. H. Sowohl sein Schlüssel als auch sein Wert) mit dem Wert, der A1 und B1 am ähnlichsten ist, wie oben spezifiziert, wird gesucht. Ich habe auch eine Änderung vorgenommen, so dass keine Auswahl von Schlüsseln die gleichen zwei Werte wie A2 und B2 geben kann, da die Schlüssel, die während eines Vergleichs berücksichtigt werden, gleich sind. Ich könnte ein Beispiel geben, wenn das klarer wäre. – Mathews24

Sie benötigen eine spezialisierte Datenstruktur, kein Standard-Python-Wörterbuch. Suchen Sie Quad-Tree oder Kd-Tree. Sie minimieren effektiv den euklidischen Abstand zwischen zwei Punkten (Ihre Zielfunktion ist nur eine Quadratwurzel von der Euklidischen Entfernung entfernt, und Ihr Wörterbuch A speichert X-Koordinaten, B y -Koordinaten.). Computational-Geometrie Menschen haben dies seit Jahren studiert.

Nun, vielleicht verstehe ich Ihre Frage falsch und mache es schwerer als sie ist. Sie sagen, dass Sie irgendein Wert von A und irgendein Wert von B wählen können, unabhängig davon, ob ihre Schlüssel die gleichen sind? Zum Beispiel könnte die Auswahl von A K: V (3,4): 2,0 sein, und die Auswahl von B könnte (5,6): 3,0 & le; Oder muss es (3,4) sein: 2,0 von A und (3,4): 6,0 von B? Bei ersterem ist das Problem einfach: Durchlaufen Sie einfach die Werte von A und finden Sie den A1 am nächsten; dann laufe durch die Werte von B und finde den nächsten zu B1. Wenn Letzteres, mein erster Absatz war die richtige Antwort.

Ihr Kommentar sagt, dass das härtere Problem das ist, das Sie lösen möchten, also hier ist ein wenig mehr. Sedgewicks Folien erklären, wie das statische Gitter, der 2D-Baum und der Quad-Baum funktionieren. http://algs4.cs.princeton.edu/lectures/99GeometricSearch.pdf. Die Folien 15 bis 29 erklären hauptsächlich den 2d-Baum, wobei 27 bis 29 die Lösung des nächsten Nachbarproblems abdecken. Da Sie die Einschränkung haben, dass der vom Algorithmus gefundene Punkt weder die X- noch die Y-Koordinate mit dem Abfragepunkt teilen muss, müssen Sie den Algorithmus möglicherweise selbst implementieren oder eine vorhandene Implementierung ändern. Eine alternative Strategie besteht darin, eine kNN-Datenstruktur (k nächste Nachbarn, im Gegensatz zum nächsten Nachbarn) zu verwenden, mit k zu experimentieren und zu hoffen, dass Ihr gewähltes k immer groß genug ist, um mindestens einen Nachbarn zu finden, der Ihre Bedingung erfüllt.

Quelle

2016-09-09 03:27:09

Es ist das letztere - die Schlüssel müssen gleich sein. Es ist im wesentlichen ein uneinheitliches 2-dimensionales Gitter, auf dem ich versuche, den nächstliegenden Punkt im Gitter zu einem anfänglich spezifizierten zu finden. – Mathews24

Bekam es. Ich fügte meiner Antwort einen dritten Absatz hinzu. –

Sie haben meinen Fall fast genau verstanden. Dies ist ein kleiner Punkt, aber für jedes geordnete Paar (An, Bn) muss nur Bn von jedem anderen geordneten Paar Bm verschieden sein. Ein anderes geordnetes Paar (Am, Bm) kann oder kann nicht immer Am = An haben, aber immer Bn! = Bm. Ich lese immer noch den Link, den Sie mir geschickt haben, dachte aber, ich würde diesen Punkt klären. – Mathews24

Finden der nächstmöglichen Werte von zwei Wörterbücher

Antwort

Verwandte Themen