Wann sind zwei Elems gleich, größer oder kleiner?

Ich hab eine Liste an Produkten. Die neueren Datums sind wichtiger - also nach oben sortieren. Die des Herstellers siemens sind besser - also nach oben sortieren. Die, die in der Gebrauchsanweisung mehr Sprachen haben, sind besser als die, die weniger Sprachen haben - also nach oben sortieren. Aber jetzt hab ich auch ein Problem. Jedes Produkt hat eine (sortierte) Liste an Kategorien, in die dieses Produkt passt. Sind Datum, Hersteller und Sprachenanzahl gleich, so soll nach Kategorien sortiert werden…

        int gc1 = 0;
        int gc2 = 0;
        for (String string : genere) {
            if (Arrays.binarySearch(o.genere, string) != -1) {
                gc1++;
            }
        }
        for (String string : o.genere) {
            if (Arrays.binarySearch(genere, string) != -1) {
                gc2++;
            }
        }
        int gc = gc1*100/genere.length >= 50 ? gc2*100/o.genere.length >= 50 ? 0 : -1 : gc2*100/o.genere.length >= 50 ? +1 : 0;

gc steht für Genre-Count. Sortiere ich jetzt nach gc, dann sieht das Ergebnis gewürfelt aus.

Wie bestimme ich gc so, dass bei „hoher Kategoriegleichheit“ 0, bei „niedriger Kategoriegleichheit“ entweder -1 oder +1?

Mich verwirrt das. :confused:

Weiß zwar nicht wie, aber ich hab’s hinbekommen:

        int gc = 0;
        if (genere.length >= o.genere.length) {
            for (String string : genere) {
                if (Arrays.binarySearch(o.genere, string) != -1) {
                    gc++;
                }
            }
            gc = gc * 100 / genere.length - 100;
        } else {
            for (String string : o.genere) {
                if (Arrays.binarySearch(genere, string) != -1) {
                    gc++;
                }
            }
            gc = -gc * 100 / o.genere.length + 100;
        }

Ein Wert zwischen -100 und +100, das Ergebnis sieht richtig aus, und ließe sich vielleicht so beschreiben: Gruppiere Produkte bei denen Kategorien “oft” übereinstimmen.

Bitte löscht das Thema, ich hab ja selber die Lösung gefunden.

Ich würde sagen, das, was du da vorhast, ist schon im Ansatz abenteuerlich. Für Elemente, die mehr als 3 Elemente haben, würde ich eine ComparatorChain verwenden. Eine solche erlaubt es sogar, die Reihenfolge der einzelnen Comparatoren zu variieren - je nachdem in welcher Reihenfolge man sie in die Liste einfügt.

[code]import java.util.Comparator;
import java.util.LinkedList;

public class ComparatorChain extends LinkedList<Comparator> implements Comparator {
private static final long serialVersionUID = -7124429108682324592L;

@Override
public int compare(K o1, K o2) {
int v = 0;
for(Comparator c : this) {
v = c.compare(o1, o2);
if(v != 0) {
break;
}
}
return v;
}
}[/code]

1 Like

Konzeptuell ist das von Spacerat genau richtig. Aber bei

extends LinkedList<Comparator<K>>

rollen sich mir gelinde gesagt die Fußnägel hoch. Also, an der Implementierung könnte man noch etwas feilen, und da gibt es verschiedene Freiheitsgrade, aber grundsätzlich: Jedes Vergleichskriterium sollte ein Comparator sein.

1 Like

Im compareTo sieht es ‘schließlich’ so aus:

        //...
        if (dc == 0) {
            if (uc == 0) {
                if (lc == 0) {
                    return gc;
                } else {
                    return lc;
                }
            } else {
                return uc;
            }
        } else {
            return dc;
        }

Das ist korrekt, es ist ja auch nur ein KSKB. Die Liste muss eigentlich ein Set sein, um doppelte Comparatoren zu vermeiden. man könnte das Set (oder dann auch beliebige andere Collections) auch noch kapseln und dann nur Add- und Removedelegatoren bauen, aber all dies ist nicht Sinn eines KSKBs.

Also ich häte hier mal das Dekorator Patern eingeworfen:

class abstract MyProductComparator implements Comparator<Product>{
   public static final Comparator<Product> UNSORTESD = new Comparator<Product> (){
      public void int compare(Product  p1, Product  p2) { return 0; }
  }
  privat final Comparator<Product> nextLevel
  MyProductComparator(Comparator<Product> nextLevel){
     this.nextLevel=nextLevel;
  }
  
  public void int compare(Product  p1, Product  p2) { 
     int thisDiff = thisCompare(p1,p2);
     if(0==thisDiff) 
        return nextLevel.compare(p1,p2);
     else
        return thisDiff ; 
  }

   protected abstract int  thisCompare(Product  p1, Product  p2);


  public static class MyProductComparatorDate extends MyProductComparator {
      public MyProductComparatorDate(){ super(UNSORTESD);}
      public MyProductComparatorDate(Comparator<Product> nextLevel){ super(nextLevel);}
      protected int  thisCompare(Product  p1, Product  p2){
          return p1.getDate().compareTo(p2.getDate());
     }     
  }

  public static class MyProductComparatorManufactorer extends MyProductComparator {
      public MyProductComparatorManufactorer(){ super(UNSORTESD);}
      public MyProductComparatorManufactorer(Comparator<Product> nextLevel){ super(nextLevel);}
      protected int  thisCompare(Product  p1, Product  p2){
          return p1.getManufactorer().compareTo(p2.getManufactorer()); // oder wie auch immer....
     }     
  }    
}

Anwendung:

Collections.sort(productList, 
          new MyProductComparatorManufactorer(
                   new MyProductComparatorDate()));


Collections.sort(productList, 
          new MyProductComparatorDate(
                   new MyProductComparatorManufactorer()));

Hier sei mal die komplette compareTo()-Methode:

    @Override
    public int compareTo(Elem o) {
        int dc = o.date.compareTo(date);
        int uc = hrs.equals("siemens") ? o.hrs.equals("siemens") ? 0 : -1 : o.hrs.equals("siemens") ? +1 : 0;
        int lc = o.langs.length - langs.length;
        int gc = 0;
        if (genere.length >= o.genere.length) {
            for (String string : genere) {
                if (Arrays.binarySearch(o.genere, string) != -1) {
                    gc--;
                }
            }
            gc = gc * 100 / genere.length + 100;
        } else {
            for (String string : o.genere) {
                if (Arrays.binarySearch(genere, string) != -1) {
                    gc++;
                }
            }
            gc = gc * 100 / o.genere.length - 100;
        }

        //...
        if (dc == 0) {
            if (uc == 0) {
                if (lc == 0) {
                    return gc;
                } else {
                    return lc;
                }
            } else {
                return uc;
            }
        } else {
            return dc;
        }
    }

Ihr ahnt es, durch binarySearch() wird’s geringfügig langsamer (bei bis jetzt 10 Elems geht es noch).

  • Ist bS richtig?
  • Wie heißt diese Art der Kategoriensortierung?

Ich gebe euch ein Beispiel:

a
a
b, c
d, e
b, a
b, f
f, a
f, a
f
b, f, a, e, g
  • Wurde richtig sortiert?
  • b, c und d, e stehen doch i-wie an der falschen Stelle?

###Edit
Ich muss in die Doc schauen, es muss >= 0 heißen. Aber er sortiert immer noch falsch.

Das kann so nicht funktionieren (jetzt mathematisch wird…). Die Reflexivität, Antisymmetrie und Transitivität ist nicht gegeben. Z. B. (a, b) und (a, c). Beide haben dieselbe Länge, aber (a, b) und (a, c) = +50 UND (a, c) und (a, b) = +50, d. h., (a, b) <= (a, c) UND (a, c) <= (a, b), ABER (a, b) != (a, c). Dadurch ist (mindestens) die Antisymmetrie nicht gegeben ( https://de.wikipedia.org/wiki/Ordnungsrelation#Totalordnung )…

Frage: Kann man eine Ordnungsrelation daraus “zaubern”?

Irgendwo ist gerade ein “übler” Denkfehler, die Kategorien sind ja sortiert, dann kann ich daraus auch Strings machen. Aber ich möchte, dass kürzere Strings bei Gleichheit oben stehen, bei compareTo() ist das nicht der Fall. Für SO fand ich nicht den richtigen Suchbegriff. Mein Versuch:

        String g1 = Arrays.toString(genere), g2 = Arrays.toString(o.genere);
        for (int i = 0;; i++) {
            if (i == g1.length()) {
                if (i == g2.length()) {
                    gc = 0;
                } else {
                    gc = -1;
                }
                break;
            }
            if (i == g2.length()) {
                gc = +1;
                break;
            }
            if (g1.charAt(i) < g2.charAt(i)) {
                gc = +1;
                break;
            }
            if (g1.charAt(i) > g2.charAt(i)) {
                gc = -1;
                break;
            }
        }

Sortiert wie gewünscht, aber o steht jetzt vor e und e vor a.

Wenn beide gleichlang sind 0, wenn g1 kürzer ist -1, wenn g2 kürzer ist +1. Soweit macht das sinn, aber was ist, wenn ein Zeichen kleiner anderes ist?

Gebt mir doch mal einen Wink mit dem Zaunpfahl - jeder Hinweis ist gerne willkommen, dann ist das Thema auch durch.

String sortiert bereits cc vor allen anderen Strings die mit cc beginnen oder hast du ein Gegenbeispiel?
freilich bbb vor cc, aber das willst du anscheinend auch, wobei nicht ganz klar,

beim Buchstabenvergleich kannst du ja auch einfach -1 zurückgeben wo im Moment +1 usw., muss das erst jemand anders sagen?

Blick auf Implementierung in String hätte auch nicht geschadet, Suche ‘java String grepcode’

Schleife: char c1 = .. char c2 = .. if (c1 != c2) { return c1 - c2; }

Zunächst erstmal würde ich ganz klar fragen, wer wann Produkte überhaupt nach einer Kategorieliste sortiert, zumal man davon ausgehen kann, dass wenn zwei Produkte sonst inhaltlich gleich sind, diese wohl auch in die selben Kategorien gehören, die Kategorielisten - in welcher Form auch immer - also identisch sein dürften.

Warum sollte man seine Kategorielisten dann auch noch alphabetisch ordnen? Das macht ja nur dann Sinn, wenn die Anzahl der Kategorien (nahezu) unbegrenzt ist, bzw. theoretisch jedes Produkt eine Liste mit eigenen Kategorien mitbringen kann.
Normalerweise hält man sich Kategorien in einer Enumeration und jede einzelne setzt ein bestimmtes Bit in einem BitSet. Dieses Bitset bildet dann einen Wert, in welchem man - je nachdem in welchen Kategorien man sucht - einzelne Bits isolieren und logisch verknüpfen oder aber auch über welchen man Kategorielisten sortieren kann.

@Timothy_Truckle: Das mit deinem „Comparator-Multiplexer“ halte ich deswegen für eine schlechte Idee, weil man erstens Immer Comparatoren neu instanzieren muss, die eigentlich irgendwo konstant zur Verfügung stehen sollten und zweitens man nicht daran gehindert wird (ähnlich, wenn ich LinkedList verwende :wink: ), Dubletten darin einzufügen.

Für die JVM sind viele kurzlebige Objekte besser als wenige langlebige…

Das ist natürlich ein gutes Argument.

bye
TT

[quote=“Timothy_Truckle, post:13, topic:19095”]
Für die JVM sind viele kurzlebige Objekte besser als wenige langlebige…
[/quote]Wir weichen da zwar vom Thema ab, aber das gilt hauptsächlich für flüchtige bzw. veränderbare Objekte. Comparatoren aber beinhalten im Idealfall nur eine Methode und die ist sicher nicht flüchtig oder veränderbar.
Und der Weisheit letzter Schluß ist deine Aussage auch nicht… Wenn man z.B. die Vertices von Morphobjekten für jeden Frame neu instanziert, statt sie wiederzuverwenden, sinkt die Framerate gewaltig. Das Beispiel ist zwar nicht mehr ganz so aktuell, aber es gibt da sicher außerhalb meines Stehgreifs noch weitere, bei denen die Verarbeitung schneller geht, als Objekte neu erstellt werden können.

Ach, ich war zu dumm… Arrays#toString() stellt Klammern dazu… eine schließende eckige Klammer ist immer größer als ein normaler Buchstabe, deshalb wird der kürzere String nach unten sortiert… Und ich hab String#compareTo() infrage gestellt…
(das ist mir nach deinem Post aufgefallen)


Dennoch die Frage, ob man aus zwei Kategorienlisten eine Ordnungsrelation (reflexiv, antisymmetrisch u. transitiv) herstellen kann?

Wann ist welches Produkt größer respektive kleiner, wenn die Kategorienliste nicht genau übereinstimmt?

Oder anders gefragt, ist eine Aussage dazu dann theoretisch generell möglich?

Kategorien sind vorher nicht bekannt. Ich hab eine Menge mit ungefähr 20 Elems, zu denen später neue Elems hinzukommen können.


Ich kann diese Daten nur abrufen, ich erstelle die Daten nicht, aber sie sind verfügbar (aber ungeordnet :smiley: ). Frage wäre, wie man aus Kategorienlisten eine lineare Ordnung herstellt. Bsp.:
Spülmaschine
Waschmaschine
Gläser-Spülmaschine, Spülmaschine
Trommel (also: Wäscheschleuder)

Perfekt wäre:
Spülmaschine
Gläser-Spülmaschine, Spülmaschine
Trommel
Waschmaschine

Hatte ich doch oben schon angedeutet.

[code]public enum Category {
CAT_1,CAT_2,CAT_N,;

public static long toBitSet(Category… cats) {
long rc = 0;
for(Category c : cats) {
rc |= (1 << c.ordinal());
}
return rc;
}
}[/code]Das zeigt nicht nur eine legitime Vervendung der [Enum].ordinal()-Methode, sondern auch eine Lösung für deine gesuchte Ordnungsrelation.

Natürlich hätte ich ja gleich von Anfang an BitSet statt long verwendet, nur leider ist BitSet nicht Comparable und auf Anhieb wüsste ich nicht, wie man zwei BitSets miteinander vergleichen kann. Sicher ist das recht einfach, wenn man es sich überlegt… z.B. welches BitSet setzt die höchste Bitstelle bei einer Exclusiv-Oder-Verknüpfung von zweien oder so…

[quote=“CyborgBeta, post:16, topic:19095”]
Kategorien sind vorher nicht bekannt. Ich hab eine Menge mit ungefähr 20 Elems, zu denen später neue Elems hinzukommen können.
[/quote]Auch dafür gibt es Möglichkeiten. Die Klasse Enumeration z.B. Dann ist aber sicher, dass du bei der Erstellung von BitSets auch solche verwenden musst, denn long dürfte recht schnell zu kurz werden.

Ok… Vor dem Sortieren erst alle Kategorien „sammeln“ - oder in der compareTo möglich? Ich hab die Vorgehensweise noch nicht ganz nachvollzogen :blush:


Und, wenn ihr möchtet, kann ich auch echte Daten geben, wir sind ja hier unter uns :smiley: , falls das nützlich sein könnte

Dann wäre aber auch ersichtlich, von welcher Seite die Daten kommen


Jedenfalls danke an alle, welche geantwortet hatten - welches Designmuster/Architektur man anwendet, kann ich ja immer noch, wenn die ‚logische inhaltliche‘ Vorgehensweise bekannt ist

Ich drücke jetzt nicht überall auf ‚Gefällt mir‘ :wink:

Du sammelst vorher natürlich alle Kategorien. Produkte bekommen dann nicht irgendwelche Kategorielisten, in denen sie vertreten sind, sondern nur noch das entsprechende BitSet. In der Compare-Methode musst du dann nur noch einen Weg finden, die BitSets zu vergleichen, deswegen hatte ist Eingangs ja auch long verwendet, weil BitSet nun mal nicht Comparable ist. Dachte, die Intention dafür war offensichtlich.

Funktioniert nicht:

// Konstruktor... gens ist eine statische Liste
        Arrays.sort(genere);
        for (String string : genere) {
            if (!gens.contains(string)) {
                gens.add(string);
            }
        }
        Collections.sort(gens);
// compareTo()...
        int gc1 = 0;
        for (String string : genere) {
            gc1 |= 1 << gens.indexOf(string);
        }
        int gc2 = 0;
        for (String string : o.genere) {
            gc2 |= 1 << gens.indexOf(string);
        }
        int gc = Integer.compare(gc1, gc2);

Das Ergebnis sieht i-wie (wiedermals) gewürfelt aus.


Wirklich zur Vereinfachung können wir davon ausgehen, dass es nicht mehr als 10 Kategorien gibt.


Edit: Mit höherem Anfangsbuchstaben hat doch auch höhere Priorität…