logisches Problem

[Bit2_Gosu]

Hallo!

Ich habe mal wieder eine Frage zu meiner Comparator Klasse
Diesmal allerdings eine logische.

Ich will eine TreeMap erstellen, die nach values sortiert ist.
Nun gibt es ja den einen TreeMap Konstruktor, der einen Comparator annimmt. Deshalb habe ich den hier geschrieben:

public class MapValueComparator <K, V extends Comparable <V>> implements Comparator <K>
{
	private Map <K, V> map;
	
	public MapValueComparator(Map <K, V> map)
	{
		this.map = map;		
	}
	
	public final int compare(K k1, K k2)
	{
		V v1 = map.get(k1);		
		V v2 = map.get(k2);		
		return v1.compareTo(v2);
	}	
}

Jetzt will ich eine TreeMap namens "players" erstellen, die nach Value geordnet ist. Dazu muss ich mir jetzt ja aber erst mal einen comparator holen:

Comparator <String> comp = new MapValueComparator <String, Integer>(players);

Tja, das geht jetzt aber nicht, weil es noch keine TreeMap "players" gibt. Wenn ich aber erst die TreeMap namens "players" erstelle, kann ich keinen eigenen Comparator übergeben...

Wie lässt sich dieses logische Problem lösen?

 

[Marco13]

Das geht erstmal nicht - nur mit einem kleinen "kniff" - schau mal hier nach "MapSortByValue2"
http://www.java-forum.org/de/viewtopic.php?p=397515&highlight=#397515
(eine LinkedList von Beiträgen.... :wink: )

 

[Bit2_Gosu]

Des hatte ich mir damals schon durchgelesen Dank dir bin ich ja überhaupt darauf gekommen, einen Comparator zu benutzen. Nur hilft mir das jetzt ja irgendwie nicht weiter.

public class MapSortByValue2 
{ 
    public static void main(String args[]) 
    { 
        final Map<String, Double> map = new HashMap<String, Double>(); 
        map.put("one", 1.0); 
        map.put("two", 2.0); 
        map.put("three", 3.0); 
        map.put("four", 4.0); 

        Comparator<String> comparator = new Comparator<String>() 
        { 
            public int compare(String a, String b) 
            { 
                return map.get(a).compareTo(map.get(b)); 
            } 
        }; 

        Map<String, Double> sortedMap = new TreeMap<String, Double>(comparator); 
        sortedMap.putAll(map); 

        for (String s : sortedMap.keySet()) 
        { 
            System.out.println(s + " -> " + sortedMap.get(s)); 
        } 
    } 

}

Hier wird ja die sortierte TreeMap ("sortedMap") ja auch erstellt, indem ein comparator benutzt wird, der allerdings Vergleiche aus einer weiteren Map (nämlich "map") zieht.
Wenn ich jetzt also nachträglich einen Eintrag in "sortedMap" einfügen möchte und ich will, dass dieser gleich in der richtigen Reihenfolge in der sortedMap ist, muss ich ja zuerst diesen Eintrag in "map" reintun. Denn ansonsten, kann der Coparator ja nicht vergleichen...

Geht das wirklich nur so umständlich?

 

[SlaterB]

anders macht es keinen Sinn, du kannst doch nicht für den Einfügevorgang verlangen, dass das Objekt schon komplett eingefügt und vefügbar ist,
ein Paradoxon,

verwende dann lieber ein höheres Objekt Entry, welches den Key und den Value enthält,
dieses Objekt dient gleichzeitig als Key und Value für die Map,
hashCode(), equals() und evtl. compare() usw. arbeiten für den Key in der Map,

für den Comparator oder direkt die compare()-Operation des Entry-Objekts greifst du dann auf den direkt referenzierten Value zurück,
so brauchst du die Map gar nicht

 

[Bit2_Gosu]

verwende dann lieber ein höheres Objekt Entry, welches den Key und den Value enthält,
dieses Objekt dient gleichzeitig als Key und Value für die Map,
hashCode(), equals() und evtl. compare() usw. arbeiten für den Key in der Map,

für den Comparator oder direkt die compare()-Operation des Entry-Objekts greifst du dann auf den direkt referenzierten Value zurück,
so brauchst du die Map gar nicht

leider verstehe ich nicht so genau, was du meinst

Jede Map enthält doch Entries? Und was meinst du mit compare() usw. arbeiten für den Key in der Map?

 

[Bit2_Gosu]

Ich habe gerade etwas furchtbares festgestellt.

Wenn ich eine TreeMap mit einem Comparator erstelle, der Values vergleicht, kann es in einer TreeMap keine 2 gleiche values geben.

Bei einer normalen TreeMap geht das ja...

Ich mein, dass eine Map keine doppelten keys habe kann is klar, aber das sich der comparator so auswirkt...


Ich brauche nämlich eine map, in der entries so sortiert sind:

("Max", 5);
("Richard", 5);
("Otto", 5);
("Paul", 6);
("Alex", 7);

usw.

Das ärgert mich ja jetzt... Kann man so eine map denn nicht auch zustandkriegen?

 

[Bit2_Gosu]

Ok, ich hab mir jetzt mal was ausgedacht, um an meine map mit sortierten values zu kommen, die aber auch mehrere gleiche values zulässt:

public class ValueOrderedMap <K, V extends Comparable <V>> extends LinkedHashMap <K, V>
{
	private static final long serialVersionUID = 1L;

	public ValueOrderedMap()
	{
		super();
	}
	
	@Override
	public final V put(K key, V value)
	{		
		super.put(key, value);
		Map <K, V> map = new LinkedHashMap <K, V>(this);
		this.clear();
		K greatestKey = null;
		
		while (map.size() != 0)
		{
			greatestKey = Container.getGreatestKey(map);			
			super.put(greatestKey, map.get(greatestKey));			
			map.remove(greatestKey);			
		}			
		return get(greatestKey);
	}	
}

Was haltet ihr davon? Klappen tut damit bis jetzt alles

 

[Marco13]

OK. Bei jeden Eingügen wird wild-würst zwischen zwei Map hin-und herkopiert, um die Elemente dann Aufsteigend sortiert in die LinkedHashMap einzufügen. Vielleicht solltest du mal "in größerem Rahmen" beschreiben, was du willst. Wenn das so eine Art Highscore-Liste werden soll, dann wäre VIELLEICHT folgende Lösung angebrachter:
Du erstellst eine Klasse "Spieler", die Name und Punktzahl enhält. Die Spieler liegen in einer Liste. Die Liste wird bei bedarf sortiert (mit einem Comparator, der Spieler nach ihrer Punkzahl vergleicht).
Anders formuliert: Bist du sicher, dass eine Map für das, was du vorhast, die geeignete Datenstruktur ist?
Wenn ja, und wenn du sicher bist, dass du eine nach Values sortierte Map haben willst, sag' bescheid, dann schau ich mal, ob man das nicht auch hinkriegt, OHNE dass das einfügen eines Elementes eine Laufzeit von O(2*n*n*log(n)) hat... :roll:

 

[Bit2_Gosu]

hi Marco!

Wenn ich eine List nehmen würde, könnte ich doch aber nur einzelne Einträge einfügen, nicht aber Paare aus Spieler und Punkten oder? Ansonsten müsste ich doch eine List mit Map.Entries machen oder sowas?

Aber die Diskussion ist eigentlich nicht so wichtig, weil ja, ich will umbedingt eine nach values sortierte Map! Mit nem Comparator bei Bedarf zu sortieren find ich net so toll.

Deshalb, wenn du es schaffst eine schnellere nach values sortierte Map hinzubekommen, als meine seeehr besondere Konstruktion dann fänd ich das super!

 

[Marco13]

Naja, jeder einzelne Eintrag könnte dann eben AUCH die Punkte enthalten.

class Spieler
{
    private String name;
    private int punkte;

    // set/get-Methoden....
}


List<Spieler> spielerListe = new ArrayList<Spieler>();
spilerListe.add(new Spieler("Bla", 4));
spilerListe.add(new Spieler("Bubb", 5));
spilerListe.add(new Spieler("Bibbl", 1));

Collections.sort(spielerListe, new EinComparatorDerDiePunkteVergleicht());

Aber ich schau' mal, was man da mit der Map machen kann....

 

[Marco13]

Ja, hier ist mal so eine "TreeMap sorted by Values", genaugenommen nurnoch "irgendeine" Map, aber das ist egal.

Wenn man keinen Comparator angibt, wird davon ausgegangen, dass die Values Comparable sind (wie bei TreeMap). Man kann aber auch einen Comparator übergeben, der auf die Values angewendet werden soll.

import java.util.*;

public class ValueSortedMap<K, V> implements Map<K, V>
{
    private Map<K, V> lookupMap = new HashMap<K, V>();

    private Map<K, V> map;


    private class KeyByValueComparator<K> implements Comparator<K>
    {
        private Comparator<? super V> valueComparator = null;

        KeyByValueComparator(Comparator<? super V> comparator)
        {
            this.valueComparator = comparator;
        }

        KeyByValueComparator()
        {
            this.valueComparator = new Comparator<V>()
            {
                public int compare(V a, V b)
                {
                    Comparable<? super V> ca = (Comparable<? super V>)a;
                    return ca.compareTo(b);
                }
            };
        }

        public int compare(K a, K b)
        {
            V va = lookupMap.get(a);
            V vb = lookupMap.get(b);

            //System.out.println("KeyByValueComparator comparing "+a+" with value "+va+" and "+b+" with value "+vb);

            int valueResult = valueComparator.compare(va, vb);
            if (valueResult != 0)
            {
                return valueResult;
            }
            else
            {
                if (a instanceof Comparable)
                {
                    Comparable ca = (Comparable)a;
                    return ca.compareTo(b);
                }
                return 1;
            }
        }
    }

    public ValueSortedMap()
    {
        map = new TreeMap<K, V>(new KeyByValueComparator<K>());
    }

    public ValueSortedMap(Comparator<? super V> c)
    {
        map = new TreeMap<K, V>(new KeyByValueComparator<K>(c));
    }

    public ValueSortedMap(Map<? extends K, ? extends V> m)
    {
        map = new TreeMap<K, V>(m);
    }

    public ValueSortedMap(SortedMap<? extends K, ? extends V> m)
    {
        map = new TreeMap<K, V>(m);
    }

    public int size()
    {
        return map.size();
    }

    public boolean isEmpty()
    {
        return map.isEmpty();
    }

    public boolean containsKey(Object key)
    {
        return map.containsKey(key);
    }

    public boolean containsValue(Object value)
    {
        return map.containsValue(value);
    }

    public V get(Object key)
    {
        return map.get(key);
    }

    public V put(K key, V value)
    {
        if (lookupMap.containsKey(key))
        {
           map.remove(key);
        }
        lookupMap.put(key, value);
        return map.put(key, value);
    }

    public V remove(Object key)
    {
        lookupMap.remove(key);
        return map.remove(key);
    }

    public void putAll(Map<? extends K, ? extends V> otherMap)
    {
        lookupMap.putAll(otherMap);
        for (K k : otherMap.keySet())
        {
            put(k, otherMap.get(k));
        }
    }

    public void clear()
    {
        lookupMap.clear();
        map.clear();
    }

    public Set<K> keySet()
    {
        return map.keySet();
    }

    public Set<Map.Entry<K, V>> entrySet()
    {
        return map.entrySet();
    }

    public Collection<V> values()
    {
        return map.values();
    }

    public boolean equals(Object o)
    {
        return map.equals(o);
    }

    public int hashCode()
    {
        return map.hashCode();
    }

    public String toString()
    {
        return map.toString();
    }
}

Hab's bisher noch nicht sooo ausführlich getestet, nur hiermit

import java.util.*;

class ValueSortedMapTest
{
    public static void main(String args[])
    {
        ValueSortedMap<String, Double> map = new ValueSortedMap<String, Double>();
        map.put("three", 3.0);
        map.put("two", 2.0);
        map.put("twoB", 2.0);
        map.put("two", 5.0);
        map.put("one", 1.0);
        map.put("four", 4.0);

        for (String s : map.keySet())
        {
            System.out.println(s+" "+map.get(s));
        }


        Comparator<String> stringLengthComparator = new Comparator<String>()
        {
            public int compare(String a, String b)
            {
                return a.length()-b.length();
            }
        };



        ValueSortedMap<String, String> map2 = new ValueSortedMap<String, String>(stringLengthComparator);
        map2.put("drei", "aaa");
        map2.put("zwei", "aa");
        map2.put("eins", "a");
        map2.put("vier", "aaaa");

        for (String s : map2.keySet())
        {
            System.out.println(s+" "+map2.get(s));
        }

    }
}

aber im großen ganzen scheint's zu funktionieren.

Vielleicht sollte ich das mal (ausführlicher kommentieren und) in die FAQ oder Codeschnipsel posten :? nach sowas wird nämlich ziemlich oft gefragt....

 

[Bit2_Gosu]

wow, super!

Da hast du dir ja einiges an Arbeit gemacht. Vielen Dank!
Ich finde auch, das muss umbedingt in Code Schnipsel aufgenommen werden!

Wie sieht es eigentlich mit der performance deiner map im vergleich zu meiner verhunzten Version aus?

PS: Die else Schleife in Zeile 44 kann weg
und sollte man das Comparable in Zeile 48 nicht parametrisieren?

 

[Marco13]

Naja, die ist jetzt auch eher noch "schnell hingeschrieben". Es gibt noch ein paar Punkte, die etwas sauberer gelöst werden können/sollten.

Wie sieht es eigentlich mit der performance deiner map im vergleich zu meiner verhunzten Version aus?

Die asymptotischen Laufzeiten sollten die gleichen sein, wie bei TreeMap, weil ja schließlich "meistens" nichts anderes gemacht wird, als die Aufrufe an die TreeMap weiterzureichen. Zusätzlich werden die Daten noch in die lookupMap eingefügt, aber das ist eine HashMap, wo alles O(1) hat, und ist in der Praxis wohl vernachlässigbar.

PS: Die else Schleife in Zeile 44 kann weg

Hmmm ... wohl nicht. Wenn man sowas macht wie
map.put("A", 1);
map.put("B", 1);
dann wird ja quasi die '1' als "key" verwendet - der Comparator liefert bei compare(1,1) also 0 zurück. Das würde eigentlich bewirken, dass der Eintrag "B" den Eintrag "A" überschreibt, und genau das wird durch das "else" verhindert: Wenn die Values gleich sind, hängt die Reihenfolge von den Keys ab (falls die irgendein Comaparable sind - das muss dazu nicht parametriesiert sein, es wird ja eh brutal mit instanceof abgefragt....). Wenn sie nicht vergleichbar sind, muss aber trotzdem "irgendwas" zurückgegeben werden, was andeutet, dass sie unterschiedlich sind. (Ob die keys "equals" sind, wurde schon direkt beim Einfügen abgefragt)

Wie gesagt, das würde ich bei Gelegenheit nochmal aufräumen + kommentieren....

 

[Bit2_Gosu]

Also, ich meinte die else Schleife kann schon weg, nicht aber das if. Wenn die if Bedingung erfüllt ist, wird returned, damit alles restliche abgebrochen. Der code in dem else {} wird also eh nur erreicht, wenn if Bedingung nicht erfüllt ist.

Also ich fände es super toll, wenn du die Klasse noch "auslieferbar" machst, wie du es gemeint hast, dann muss die echt in code schnipsel aufgenommen werden!!

 

[Marco13]

Hmja - du meinst sowas wie

        public int compare(K a, K b)
        {
...
            int valueResult = valueComparator.compare(va, vb);
            if (valueResult != 0)
            {
                return valueResult;
            }

            // ====== Und was wird hier zurückgegeben ???
           return ....
        }

Wenn man einfach das valueResult zurückgibt, dann bewirkt
map.put("A", 1);
map.put("B", 1);
eben, dass danach nurnoch ("B",1) in der map liegt, und ("A", 1) ist rausgeflogen...

Man KÖNNTE natürlich immer pauschal 1 oder -1 zurückgeben - das stimmt. Aber im Sinne einer "lexikographischen" Sortierung fand ich den Vergleich der Keys dann doch schöner...

Werde es bei Gelegenheit mal aufräumen & kommentieren, aber wann ich dafür Zeit habe ... mal sehen... bis dahin kannst du es ja so verwenden, und später ggf. durch die kommentierte Version ersetzen

 

[Bit2_Gosu]

Hm, vielleicht habe ich mich blöd ausgedrückt.

Hier meinte, dass man das ganze so schreiben sollte:

public int compare(K a, K b) 
        { 
            V va = lookupMap.get(a); 
            V vb = lookupMap.get(b); 

            //System.out.println("KeyByValueComparator comparing "+a+" with value "+va+" and "+b+" with value "+vb); 

            int valueResult = valueComparator.compare(va, vb); 
            if (valueResult != 0) 
            { 
                return valueResult; 
            } 
            if (a instanceof Comparable) 
            { 
                 Comparable ca = (Comparable)a; 
                 return ca.compareTo(b); 
            } 
            return 1; 
         } 
    }

da is jetzt nur die eine else schleife raus. sonst nix

 

[Marco13]

Ach sooo.. :idea: na sag' das doch :wink: das stimmt natürlich.
Die "else-Schleife" kann man auch in eine einfache http://if-schleife.de/ umwandeln :bae:
Das sind solche Sachen, die ich ggf. beim Code-Aufräumen machen würde ... das war ja nur so runtergeschrieben (und die Sache mit dem Vergleich der Keys bzw. dem "1" habe ich natürlich erst eingebaut, als es OHNE nicht funktioniert hat :wink: )

 

[Bit2_Gosu]

die Seite ist ja herrlich ich lach mich grad kaputt ^^

und wenn du Zeit für die Klasse findest, fänd ich das super!

 

[Marco13]

Hab' sie mal kommentiert (größtenteils Copy&Paste aus der TreeMap :roll: ) und gepostet:
http://www.java-forum.org/de/viewtopic.php?p=405336#405336