Treemap

[Caeptn]

Hallo,

ich habe folgendes Problem:

Ich muss die Distanzen in einer Distanzmatrix berechnen.

Dazu verwende ich eine Treemap mit einem Index (der Übergang) und dem zugehörigen Wert als double-Zahl.

Beispielsweise so:

12 25.3

13 14.8

...

...

98 12.8

99 8.2

Die Map ist ja sortiert, aber nach dem Index.

Ich würde sie gerne umsortieren nach dem Wert, beginnend bei dem kleinsten Wert.

Für Listen gibt es die Methode: void sort(List<Typ> listname)

Kann ich eine ähnliche Methode für meine Map benutzen oder muss ich mir selber was basteln?

Vielen Dank im Voraus

[Ezra]

Das kann man nur "manuell" machen.

Hier hast Du einen Überblick über die Methoden, die Dir die Treemap liefert: klick

Ich würde sowieso empfehlen, bei solchen Fragen immer in der API nachzugucken.

Bearbeitet 30. Juni 2009 von Ezra

[flashpixx]

Hallo,

wenn Du vielleicht das Problem einmal etwas umfangreicher beschreiben würdest, dann könnte man durch einen anderen Algorithmus evtl das Problem optimieren z.B. wenn Du "kürzeste Pfade" benötigst usw.

Hierzu wären z.B. Graphenalgorithmen oder auch dynamische Programmierung (Bellman Prinzip) mögliche Ansätze

Phil

[elSusto]

bubblesort

damit könntest du ziemlich leicht sortieren.

[flashpixx]

@elSusto: Bubblesort ist O(n^2) Algorithmus und damit für große Datenmengen ungeeignet, außerdem wird in einer Treemap schon eine Sortierung anhand des Suchbaums durchgeführt.

Phil

[Caeptn]

Ich beschreib es mal etwas genauer:

Man hat eine (quadratische) Distanzmatrix mit i Spalten und j Zeilen.

Diese muss ich Zufallszahlen füllen.

Der Abstand eines Feldes zum anderen ist quasi die Differenz der absolut-Beträge.

Soweit kein Problem... das schreibe ich alles in meine Treemap.

Jetzt will ich die Map der Größe nach ordnen, beim kleinsten Wert beginnend.

Wir haben schon verschiedene Sortieralgorithmen behandelt dieses Semester, das manuell zu programmieren wäre nicht so schwer.

Aber Student ist man faul, desshalb wäre es mir lieber wenn ich diese Arbeit vermeiden kann :-).

In der Doku der Treemap habe ich eben leider nichts gefunden.

Eine Treemap ist ja eine "sortierte Map", allerdings ist sie ja nach dem Schlüssel sortiert. Jetzt würde ich gerne Wissen ob man sie nicht nach den Werten sortieren kann, oder einfach den Schlüssel zum Wert macht und den Wert zum SChlüssel als Alternative dazu.

[perdian]

Eine Treemap ist ja eine "sortierte Map", allerdings ist sie ja nach dem Schlüssel sortiert. Jetzt würde ich gerne Wissen ob man sie nicht nach den Werten sortieren kann

Das würde dem Wesen einer Map widersprechen. Eine Map wird verwendet um Einträge schnell anhand eines Index zu finden. Die Datenstruktur der Values selbst ist dabei irrelevant.

Ich würde sagen für deinen Anwendungsfall ist eine Map - so wie du die Verwendung hier beschrieben hast - der falsche Container.

[Caeptn]

hm was wäre denn am sinnvollsten um einen Wert einem Namen zuzuordnen wenn nach dem Wert sortierbar sein soll?

[flashpixx]

Der Abstand eines Feldes zum anderen ist quasi die Differenz der absolut-Beträge.

Dann mach es mit dynamischer Programmierung. Mal ganz grob der Algorithmus (es handelt sich um das Bellmann Prinzip, d.h. die Teillösungen, die Du ermittelst sind optimal, so dass die Gesamtlösung auch optimal ist - salopp formuliert):

aktuelle Position (i,j)

Zielposition (n,m)

so lange (i,j) != (n,m)

    a = ||(i,j) - (i+1,j)||

    b = ||(i,j) - (i-1,j)|| 

    a = ||(i,j) - (i,j-1)||

    b = ||(i,j) - (i,j+1)||


    (i,j) = min(a,b,c,d)

Du betrachtest immer nur die nächste Teillösung des Problems, d.h. der kürzeste Pfad ist von der aktuellen Position der Weg / das Element, das den kürzesten Abstand zum aktuellen Punkt hat.

In diesem Fall müssen Dir sowohl Start und Ziel bekannt sein und Du musst darauf achten, dass keine Schleifen entstehen, weil dann die Schleife nicht terminiert.

Wenn Du nur den kürzesten Pfad innerhalb Deiner Matrix benötigst, dann wirst Du nicht darum herum kommen alle Pfade zu durchlaufen. Das wird aber dann O(c*n*m), wobei Du das c geschickt klein halten kannst, in dem Du ähnlich wie im Algorithmus die Wege auswählst, d.h. Du betrachtest nur immer einen Weg der kürzer ist wie Dein aktueller

Phil

[Ezra]

Jetzt würde ich gerne Wissen ob man sie nicht nach den Werten sortieren kann, oder einfach den Schlüssel zum Wert macht und den Wert zum SChlüssel als Alternative dazu.

Das Umdrehen von Wert und Schlüssel kann nicht funktionieren, da Werte auch doppelt vorkommen.

In der Doku der Treemap habe ich eben leider nichts gefunden.

Ich sagte ja auch, dass es nicht geht.

Wenn Du faul sein willst, schreib alles in eine Liste und lass diese von Java sortieren.