# Sortierreihenfolge festlegen im ArrayList



## chriss_2oo4 (23. Jun 2008)

Hi,

ich habe ein Problem mit der Implementierung einer Sortierreihenfolge und zwar möchte ich das das Zeichen * die niedrigste Priorität bekommt wie im folgenden Beispiel:

DU BIST EIN ROBOTER
DU BIST JA LUSTIG
DU BIST JA *
DU BIST *
DU LUEGST
DU *
HALLO
*

Das * muss immer zuletzt und "Du bist ja *" muss vor "Du bist *" kommen.

Ich habe bereits eine Klasse die das Interface Comparator implementiert, leider ist die ArrayList nach der Sortierung immer noch nicht richtig sortiert.


```
class StarComparator implements Comparator<Object> 
{	
	public int compare(Object o1, Object o2)
	{
		int iRet = 0;

		String s1 = o1.toString();
	        String s2 = o2.toString();

	    
	    if (s1.intern() == s2)
	    {
	      iRet = 0;
	    }
	    else
	    {
	      char a, b;
	      for (int i = 0, n = Math.min(s1.length(), s2.length()); i < n; i++)
	      {
	        a = s1.charAt(i);
	        b = s2.charAt(i);
	        if (a != b)
	        {
		        if (b == '*')
		        {
		          iRet = 1;
		          break;
		        }
		        else if (a < b)
		        {
		          iRet = -1;
		          break;
		        }
		        else
		        {
		          iRet = 1;
		          break;
		        }
	        }
	      }
	    }
	    return iRet;
	  }
}
```

Was mache ich falsch?

lg chriss


----------



## SlaterB (23. Jun 2008)

zunächst mal solltest du deine Operation mit einem ganz normalen Aufruf wie
compare(testString1,testString2) 
testen

und zweitens musst du noch den Rest deines Programmes posten,
so weiß man ja gar nicht, ob du den Comparator korrekt beim Sortieren einsetzt,


----------



## SebiB90 (23. Jun 2008)

ich würd sagen wenn b == '*' dann muss iRet -1 sein und nicht 1.
Weil b ja das zweite Element ist und und wenn da ein * ist, soll es ja nach dem ersten element sein.
1 gibt an, das aber das erste element größer ist, also nach dem zweiten kommt. das willst du ja genau andersrum deswegen -1.


----------



## chriss_2oo4 (23. Jun 2008)

Hi,

zunächst mal vielen Dank für eure Antworten.


@SlaterB

Getestet hab ich das ganze natürlich schon -> kann den ganzen Quelltext nicht posten, da er viel zu lang ist.

Sortieren mit folgender Methode: 


```
Collections.sort(myList, new StarComparator());
```


@SebiB90
Das mit den Rückgabewerten hab ich nicht so ganz verstanden, also wenn ich a= "Hallo" und b="Hallo *" eingebe, muss die methode -1 zurückgeben -> da Hallo vor Hallo * stehen soll?

Des Weiteren wird es bei folgendem Texten immer 0 zurückgeben:


* Hallo
*

Da nur das erste Zeichen beachtet wird (siehe for-Schleife)


Wie kann man soetwas besser lösen? <- bin echt am verzweifeln



Lg Chriss


----------



## SlaterB (23. Jun 2008)

>  kann den ganzen Quelltext nicht posten, da er viel zu lang ist. 

was ist an 
List x = ..;
x.add(..);
x.add(..);
x.add(..);
x.add(..);
Collections.sort(..)


so lang? 6 Zeilen
+ Ausgabe, kann man aber auch in einer Zeile schaffen:
 System.out.println("sortiert: "+x);

------------

> Da nur das erste Zeichen beachtet wird (siehe for-Schleife) 

das ist doch einfach, wenn am Ende noch der Vergleich 0 ist, dann vergleichst du die Längen der beiden Strings, und dieses Ergebnis entscheidet,

wie Elfmeterschießen im Fussball


----------



## chriss_2oo4 (23. Jun 2008)

Hi, 

nochmals danke für deine Antwort!

Ich fülle die ArrayLists aus einer XML-Datei und somit ist der Code, doch etwas länger.





> das ist doch einfach, wenn am Ende noch der Vergleich 0 ist, dann vergleichst du die Längen der beiden Strings, und dieses Ergebnis entscheidet,
> 
> wie Elfmeterschießen im Fussball



Aber ich verstehe nicht ganz


Bei folgenden zwei Eingaben:

a = *
b = * Hallo

Mein oben beschriebener Algorithmus gibt in dem Fall keine 0 zurück, da b ein * enhtählt und somit -1 zurückgegeben wird.

Oder verstehe ich da was falsch?


Lg Chriss


----------



## SebiB90 (23. Jun 2008)

nein tut er nicht. denn die überprüfung ob b=='*' ist wird erst nach a!=b gemacht.
da aber a und b * sind, wird die überprüfung auf b=='*' nicht durchgeführt.


----------



## SlaterB (23. Jun 2008)

> Ich fülle die ArrayLists aus einer XML-Datei

und genau sowas ist das Ende jedes guten Testens,

gutes Testen beginnt dagegen mit Teststring "a", "b" usw.


----------



## chriss_2oo4 (1. Jul 2008)

Hi,

der Algorithmus hab bisher immer gut funktioniert:


```
public int compare(Object o1, Object o2)
	{
		int iRet = 0;
		
		String s1 = o1.toString();
	        String s2 = o2.toString();
		
	    
	    if(s2.compareTo("*") == 0)
	    {
	    	iRet = -1;
	    }
	    else if (s1.intern() == s2)
	    {
	      iRet = 0;
	    }
	    else if(s1.compareTo("*") == 0)
	    {
	    	iRet = 1;
	    }
	    else
	    {
	      char a, b;
	      for (int i = 0, n = Math.min(s1.length(), s2.length()); i < n; i++)
	      {
	        a = s1.charAt(i);
	        b = s2.charAt(i);
	        if (a != b)
	        {
		        if (b == '*')
		        {
		          iRet = -1;
		          break;
		        }
		        else if (a == '*')
		        {
		        	iRet = 1;
		        	break;
		        }
		        else if (a < b)
		        {
		          iRet = -1;
		          break;
		        }
		        else
		        {
		          iRet = 1;
		          break;
		        }
	        }
	      }
	      if(iRet == 0)
	      {
	    	  if(s1.length() > s2.length())
	    	  {
	    		  return 1;
	    	  }
	    	  else
	    	  {
	    		  return -1;
	    	  }
	      }
	    }
	    return iRet;
	  }
```

Aber es funktioniert nicht für folgenden Fall :

IN * 
IN * JAHREN

Das IN * müsst weiter unten stehen.
Der Algorithmus vergleicht bis zu IN * dann bricht der Vergleich ab und der längere String steht weiter unten

Wie könnte man das Problem lösen?


Ich möchte einfach das die Liste so durchsucht wird:

- Zuerst Prüfen ob es ein Passendes Muster zur Benutzereingabe gibt (Also ohne *)
- Ist dies nicht der Fall, sollte Geprüft werden ob eine Eingabe mit Jokerzeichen vorhanden ist, dabei sollte wie im Beispiel oben immer das am bensten passende verwendet werden ( z. B. nicht DU * sonder DU BIST * für die Eingabe DU BIST LUSTIG)
- Wird dann nichts passendes gefunden, sollte das * verwendet werden.

Lg Chriss


----------



## SlaterB (1. Jul 2008)

> Der Algorithmus vergleicht bis zu IN * dann bricht der Vergleich ab und der längere String steht weiter unten 

das liegt offensichtlich am Code 

> if(iRet == 0) 
>         { 
>            if(s1.length() > s2.length()) 
>            { 
>               return 1; 
>            } 
>            else 
>            { 
>               return -1; 
>            } 
>         } 

wenn du das umdrehen willst, vertausche doch einfach 1 und -1,
oder ist die derzeitige Sortierung korrekt und du willst nur in besonderen Situationen einen anderen Einfluß der Länge, z.B. wenn das letzte Zeichen * ist?
dann prüfe doch die jeweilige Situation ab und entscheide daraufhin anders

--------

> Ich möchte einfach das die Liste so durchsucht wird

'eine Liste durchsuchen' klingt anders als das bisherige 'einfach nur zwei Strings vergleichen',
was genau du willst habe ich nicht eindeutig verstanden und möchte ich zunächst mal nicht umständlich hineininterpretieren

ideal wäre nach wie vor ein komplettes Testprogramm und Testaufrufe a la

List x = ..; 
x.add(..); 
x.add(..); 
x.add(..); 
x.add(..); 
tuWasMitList(x);
pruefeAufErwartetesErgebnis(y)


----------



## Guest (1. Jul 2008)

chriss_2oo4 hat gesagt.:
			
		

> und zwar möchte ich das das Zeichen * die niedrigste Priorität bekommt


Welches Zeichen hat denn normalerweise die "niedrigste Priorität"? char ist 16 Bit breit, also das Zeichen mit dem Unicode ffff. Das kann man doch schön ausnutzen. Außerdem sollte StarComparator Comparator<String> implementieren, dann spart man sich manuelles Casten.

```
public class StarComparator implements Comparator<String>
{
	public int compare(String s1, String s2)
	{
		String t1 = s1.replace('*', '\uffff');
		String t2 = s2.replace('*', '\uffff');
		return t1.compareTo(t2);
	}
}

class Test
{
	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("DU LUEGST");
		list.add("DU BIST JA LUSTIG");
		list.add("*");
		list.add("DU BIST JA * ");
		list.add("DU * ");
		list.add("HALLO");
		list.add("DU BIST EIN ROBOTER");
		list.add("DU BIST *");
		
		Collections.sort(list, new StarComparator());
		
		for (String s: list)
			System.out.println(s);
	}
}
```
Ich hab die Testeingaben mal munter durcheinandergewürfelt, nach der Sortierung kommt genau das raus, was Du willst.

Fred


----------



## SlaterB (1. Jul 2008)

zu bedenken ist, dass dabei potentiell viel zu oft unnötig Strings erzeugt werden,

etwas performanter: einmalig eine Liste mit neuen Strings erzeugen
und diese dann normal sortieren, am Ende zurückumwandeln

bzw. wahrscheinlich muss man recht umständlich die Originalliste neu befüllen


----------



## Guest (1. Jul 2008)

Interessanter Einwand, dann könnte man das ganze auch so abwandeln und auf den Comparator verzichten:

```
class Test
{
	private static void replace(List<String> list, char x, char y)
	{
		for (int i = 0, n = list.size(); i < n; ++i)
			list.set(i, list.get(i).replace(x, y));
	}

	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("DU LUEGST");
		list.add("DU BIST JA LUSTIG");
		list.add("*");
		list.add("DU BIST JA * ");
		list.add("DU * ");
		list.add("HALLO");
		list.add("DU BIST EIN ROBOTER");
		list.add("DU BIST *");

		replace(list, '*', '\uffff');
		Collections.sort(list);
		replace(list, '\uffff', '*');

		for (String s: list)
			System.out.println(s);
	}
}
```
Ist vielleicht sogar leichter verständlich. Das replace bitte nicht für LinkedLists verwenden, da ist get(i) zu langsam. Über Iteratoren habe ich es nicht hinbekommen, weil man da ja nur eine Kopie des Listeneintrags bekommt und die Originalreferenz nicht verändern kann.

Fred


----------



## Guest (1. Jul 2008)

Wobei, am saubersten scheint es mir doch zu sein, den Comparator besser zu implementieren:

```
public class StarComparator implements Comparator<String>
{
	public int compare(String s1, String s2)
	{
		final int minlen = Math.min(s1.length(), s2.length());
		for (int i = 0; i < minlen; ++i)
		{
			char c = s1.charAt(i);
			if (c == '*') c = '\uffff';

			char d = s2.charAt(i);
			if (d == '*') d = '\uffff';

			if (c < d) return -1;
			else if (d < c) return 1;
		}
		final int deltalen = s1.length() - s2.length();
		return deltalen < 0 ? -1 : deltalen > 0 ? 1 : 0;
	}
}

class Test
{
	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("DU LUEGST");
		list.add("DU BIST JA LUSTIG");
		list.add("*");
		list.add("DU BIST JA * ");
		list.add("DU * ");
		list.add("HALLO");
		list.add("DU BIST EIN ROBOTER");
		list.add("DU BIST *");

		Collections.sort(list, new StarComparator());

		for (String s: list)
			System.out.println(s);
	}
}
```

Fred


----------



## Guest (1. Jul 2008)

Hm, eigentlich gefällt mir mein erster Ansatz doch am besten... das unnötige Erzeugen der Strings kann man ja durch Caching verhindern:

```
public class StarComparator implements Comparator<String>
{
	private final Map<String, String> cache = new HashMap<String, String>();
	
	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}
}

class Test
{
	public static void main(String[] args)
	{
		List<String> list = new ArrayList<String>();
		list.add("DU LUEGST");
		list.add("DU BIST JA LUSTIG");
		list.add("*");
		list.add("DU BIST JA * ");
		list.add("DU * ");
		list.add("HALLO");
		list.add("DU BIST EIN ROBOTER");
		list.add("DU BIST *");

		Collections.sort(list, new StarComparator());

		for (String s: list)
			System.out.println(s);
	}
}
```

Fred


----------



## tfa (1. Jul 2008)

Anonymous hat gesagt.:
			
		

> Hm, eigentlich gefällt mir mein erster Ansatz doch am besten... das unnötige Erzeugen der Strings kann man ja durch Caching verhindern:


Warum? Das macht die Sache nur komplizierte und wahrscheinlich nicht mal schneller.


----------



## SlaterB (1. Jul 2008)

> wahrscheinlich nicht mal schneller.

bei nur 5 Strings in der Liste ist es klar, für 1xxx kannst du das aber nicht ernst meinen,
da bitte wirklich differenzieren, 
String-Erzeugung ist eines der wenigen Dinge, die man sogar in einfachen Programmen langsam machen kann


----------



## Guest (1. Jul 2008)

tfa hat gesagt.:
			
		

> Das macht die Sache [...] wahrscheinlich nicht mal schneller.


Oh doch, und zwar erheblich. Dabei geht es gar nicht um die Stringerzeugung an sich (Objekterzeugung ist nicht teuer in Java), sondern um das Durchiterieren, welches replace erledigen muss (lineare Komplexität). Das Suchen in einer Map hat dagegen konstante Komplexität.

Das ganze wäre nur dann nicht wirklich schneller, wenn String.equals sich jedes Zeichen einzeln anschauen müsste. In meiner Implementierung passiert das aber nicht, sofern IDENTISCHE String-Objekte benutzt werden, und das ist hier ja der Fall:

```
public final class String
{
    // ...
    public boolean equals(Object anObject)
    {
        if (this == anObject) return true;
    // ...
}
```

Fred


----------



## SlaterB (1. Jul 2008)

> Dabei geht es gar nicht um die Stringerzeugung an sich (Objekterzeugung ist nicht teuer in Java), sondern um das Durchiterieren, welches replace erledigen muss 

gewagt, was versteht du denn unter einer reinen Stringerzeugung?
gleich mal getestet, ein replace statt new String(statisches char-Array) ist 2x langsamer,
das dürfte vor allem daran liegen, dass beim replace ein neues char-Array angelegt wird, weniger am Durchlauf,
bei sehr langen Strings kann sich das natürlich verschieben,

aber eigentlich eh alles egal wenn es um den Faktor 1000 und mehr beim Cachen geht

> lineare Komplexität). Das Suchen in einer Map hat dagegen konstante Komplexität

hmm, vergleichst du da Äpfel mit Birnen?

bei beiden gilt lineare Komplexität, es müssen alle chars durchlaufen werden, 
nur ist das für die hashCode-Berechnung eben bedeutend schneller,
da keine neuen Objekte erzeugt werden


----------



## tfa (1. Jul 2008)

OK, ich streiche das "wahrscheinlich nicht mal schneller". 
Worauf es mir eigentlich ankommt ist folgendes: wenn du eine gut funktionierende, klare Implementierung für eine Funktion hast, nimm die und versuche nicht, sie durch eine vermeintlich schnellere Lösung zu ersetzen. Löse keine (Performance-)Probleme, die du (noch) gar nicht hast!
Wenn der Anwender eben 25 Millisekunden länger auf sein Ergebnis warten muss, was soll's? 
Wenn sich später herausstellt, dass es doch zu langsam ist, kannst du optimieren. Aber da erscheint mir die vorletzte Lösung doch besser, als das Caching.



> Dabei geht es gar nicht um die Stringerzeugung an sich (Objekterzeugung ist nicht teuer in Java)



Richtig, Stringerzeugung ist kein Problem, wenn die Objekte nur sehr kurzlebig sind. Gecachete String in einer Map sind aber langlebig. Die Wahrscheinlichkeit, dass sie deinen GC belasten, ist hoch. Besonders wenn du sehr viele Strings sortieren willst und den Speicher mit einer Riesen-Map zukleisterst.



> sondern um das Durchiterieren, welches replace erledigen muss (lineare Komplexität). Das Suchen in einer Map hat dagegen konstante Komplexität.


Bedenke, dass das Errechnen der String-Hashcodes ebenfalls nötig ist und Zeit kostet (werden glücklicherweise gecachet). Beim Suchen in der Map kann es auch zu Kollisionen kommen, die iterativ aufgelöst werden müssen.


----------



## Guest (1. Jul 2008)

SlaterB hat gesagt.:
			
		

> gewagt, was versteht du denn unter einer reinen Stringerzeugung?


Man muss Speicher aufm Heap reservieren.



			
				SlaterB hat gesagt.:
			
		

> bei beiden gilt lineare Komplexität, es müssen alle chars durchlaufen werden, nur ist das für die hashCode-Berechnung eben bedeutend schneller, da keine neuen Objekte erzeugt werden


Die gleiche Befürchtung hatte ich ja erst bei equals, ist aber nicht so. hashCode wird nie öfter als einmal pro String aufgerufen!

```
public int hashCode()
{
	int h = hash;
	if (h == 0)
	{
		// Hash-Wert berechnen
		hash = h;
	}
	return h;
}
```



			
				tfa hat gesagt.:
			
		

> OK, ich streiche das "wahrscheinlich nicht mal schneller".
> Worauf es mir eigentlich ankommt ist folgendes: wenn du eine gut funktionierende, klare Implementierung für eine Funktion hast, nimm die und versuche nicht, sie durch eine vermeintlich schnellere Lösung zu ersetzen. Löse keine (Performance-)Probleme, die du (noch) gar nicht hast!


Volle Zustimmung.



			
				tfa hat gesagt.:
			
		

> Wenn der Anwender eben 25 Millisekunden länger auf sein Ergebnis warten muss, was soll's?
> Wenn sich später herausstellt, dass es doch zu langsam ist, kannst du optimieren. Aber da erscheint mir die vorletzte Lösung doch besser, als das Caching.


Jo, aus reiner Performancesicht würde ich auch die vorletzte Lösung wählen.



			
				tfa hat gesagt.:
			
		

> > Dabei geht es gar nicht um die Stringerzeugung an sich (Objekterzeugung ist nicht teuer in Java)
> 
> 
> Richtig, Stringerzeugung ist kein Problem, wenn die Objekte nur sehr kurzlebig sind.


Die gecachten Strings leben, solange die Map lebt, also solange wie der StarComparator lebt, also solange die Sortierung läuft. Ob das ein Performanceproblem ist oder nicht kann ich nicht beurteilen, dazu müsste man einen Benchmark mit mehreren 1000 Strings bauen und dann messen.

Gecachete String in einer Map sind aber langlebig. Die Wahrscheinlichkeit, dass sie deinen GC belasten, ist hoch. Besonders wenn du sehr viele Strings sortieren willst und den Speicher mit einer Riesen-Map zukleisterst.



> Beim Suchen in der Map kann es auch zu Kollisionen kommen, die iterativ aufgelöst werden müssen.


Klar, und theoretisch kann Quicksort zu quadratischer Komplexität degenerieren. Die hashCode() Methode aus der Klasse String ist aber schon ziemlich gut, da wird es selten zu Kollisionen kommen, die die Performance drastisch beeinträchtigen würden.


----------



## Guest (1. Jul 2008)

Anonymous hat gesagt.:
			
		

> hashCode wird nie öfter als einmal pro String aufgerufen!


Schlecht formuliert. Ich meinte, dass die Berechnung des hashcodes nie öfter als einmal pro String stattfindet.

Fred


----------



## SlaterB (1. Jul 2008)

ah, das ist ja gut gemacht,
hoffentlich meckert jetzt keiner über diese String-Performanz


----------



## tfa (1. Jul 2008)

Anonymous hat gesagt.:
			
		

> Die gecachten Strings leben, solange die Map lebt, also solange wie der StarComparator lebt, also solange die Sortierung läuft.


Wie gesagt: langlebig.


> Ob das ein Performanceproblem ist oder nicht kann ich nicht beurteilen, dazu müsste man einen Benchmark mit mehreren 1000 Strings bauen und dann messen.


Dann initialisier deine Hash-Tabelle aber entsprechend. Die hat am Anfang eine Größe von 16 mit Load-Faktor 0,75. Jedes Rehashing verdoppelt die Größe, das dauert entsprechend und erzeugt viel Müll.


----------



## tfa (1. Jul 2008)

DOPPELPOST


----------



## tfa (1. Jul 2008)

Grmpf. Schon wieder Doppelpost!


----------



## Guest (1. Jul 2008)

So, ich habe mal einen Test geschrieben. Ergebnis:
- Die direkte Variante (Strings selbst vergleichen) liegt mit großem Abstand vorne
- Das Cachen ist langsamer(!) als das Nicht-Cachen
- Das Initalisieren der HashMap mit einer großen Kapazität bringt keinen messbaren Vorteil

```
class Direct implements Comparator<String>
{
	public int compare(String s1, String s2)
	{
		final int minlen = Math.min(s1.length(), s2.length());
		for (int i = 0; i < minlen; ++i)
		{
			char c = s1.charAt(i);
			if (c == '*') c = '\uffff';

			char d = s2.charAt(i);
			if (d == '*') d = '\uffff';

			if (c < d)
				return -1;
			else if (d < c) return 1;
		}
		final int deltalen = s1.length() - s2.length();
		return deltalen < 0 ? -1 : deltalen > 0 ? 1 : 0;
	}
}

class Uncached implements Comparator<String>
{
	public int compare(String s1, String s2)
	{
		String t1 = s1.replace('*', '\uffff');
		String t2 = s2.replace('*', '\uffff');
		return t1.compareTo(t2);
	}
}

class Cached implements Comparator<String>
{
	private final Map<String, String> cache = new HashMap<String, String>();

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}
}

class Capacity implements Comparator<String>
{
	private final Map<String, String> cache;

	public Capacity(int capacity)
	{
		cache = new HashMap<String, String>(capacity);
	}

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}
}

public class Test
{
	private static final int tests = 10;

	private static final int size = 100000;
	private static final int maxlen = 50;
	private static final int seed = 0;

	private static List<String> createList()
	{
		List<String> list = new ArrayList<String>(size);
		Random random = new Random(seed);
		for (int i = 0; i < size; ++i)
		{
			int n = 1 + random.nextInt(maxlen);
			char[] a = new char[n];
			for (int k = 0; k < n; ++k)
				a[k] = (char) (97 + random.nextInt(26));
			if (random.nextBoolean()) a[n - 1] = '*';
			list.add(new String(a));
		}
		return list;
	}

	public static void main(String[] args)
	{
		test(new Direct(), "direct");
		test(new Uncached(), "uncached");
		test(new Cached(), "cached");
		test(new Capacity(2 * size), "capacity");
	}

	public static void test(Comparator<String> comparator, String name)
	{
		for (int i = 0; i < tests; ++i)
		{
			List<String> list = createList();
			Benchmark bm = new Benchmark(name);
			bm.start();
			Collections.sort(list, comparator);
			bm.stop();
			System.out.println(bm);
		}
		System.out.println();
	}
}

class Benchmark
{
	private final String name;
	private boolean running;
	private long start;
	private long sum;

	public Benchmark(String name)
	{
		this.name = name;
		running = false;
	}

	public void start()
	{
		assert !running;
		running = true;
		start = System.nanoTime();
	}

	public void stop()
	{
		long stop = System.nanoTime();
		assert running;
		sum += stop - start;
		running = false;
	}

	public String toString()
	{
		long l = sum;
		String s = "ns";
		if (l > 9999)
		{
			l /= 1000;
			s = "µs";
			if (l > 9999)
			{
				l /= 1000;
				s = "ms";
			}
		}
		return String.format("%s: %d %s", name, l, s);
	}
}
```
Ergebnis:

```
direct: 138 ms
direct: 131 ms
direct: 131 ms
direct: 127 ms
direct: 128 ms
direct: 164 ms
direct: 129 ms
direct: 128 ms
direct: 128 ms
direct: 128 ms

uncached: 586 ms
uncached: 595 ms
uncached: 590 ms
uncached: 589 ms
uncached: 591 ms
uncached: 590 ms
uncached: 588 ms
uncached: 585 ms
uncached: 593 ms
uncached: 591 ms

cached: 448 ms
cached: 923 ms
cached: 815 ms
cached: 811 ms
cached: 818 ms
cached: 816 ms
cached: 917 ms
cached: 819 ms
cached: 807 ms
cached: 809 ms

capacity: 372 ms
capacity: 815 ms
capacity: 816 ms
capacity: 826 ms
capacity: 813 ms
capacity: 817 ms
capacity: 830 ms
capacity: 813 ms
capacity: 823 ms
capacity: 819 ms
```
Man beachte, dass das Cachen im ersten Test noch etwas schneller ist, in allen folgenden Tests dagegen langsamer. Liegt wahrscheinlich am erzeugten Müll.

Fred


----------



## Guest (1. Jul 2008)

Anonymous hat gesagt.:
			
		

> - Das Cachen ist langsamer(!) als das Nicht-Cachen


Ah moment, das war "Messfehler", man betracht folgenden Code:


```
public static void test(Comparator<String> comparator, String name)
	{
		for (int i = 0; i < tests; ++i)
		{
			List<String> list = createList();
			Benchmark bm = new Benchmark(name);
			bm.start();
			Collections.sort(list, comparator); // <--- hier
			bm.stop();
			System.out.println(bm);
		}
		System.out.println();
	}
}/[code]
Die markierten Zeile wird ja 10x durchlaufen, aber es wird immer dasselbe Comparator-Objekt verwendet. Man muss hier aber mit einem frischen Comparator anfangen, sonst sind die Tests ja nicht unabhängig voneinander. Jetzt implementieren die Comparatoren ein neues Interface, das das Erzeugen eines frischen Objekts polymorph ermöglicht:
[code]interface Vergleich extends Comparator<String>
{
	public Vergleich neuerVergleich();
}

class Direct implements Vergleich
{
	public int compare(String s1, String s2)
	{
		final int minlen = Math.min(s1.length(), s2.length());
		for (int i = 0; i < minlen; ++i)
		{
			char c = s1.charAt(i);
			if (c == '*') c = '\uffff';

			char d = s2.charAt(i);
			if (d == '*') d = '\uffff';

			if (c < d)
				return -1;
			else if (d < c) return 1;
		}
		final int deltalen = s1.length() - s2.length();
		return deltalen < 0 ? -1 : deltalen > 0 ? 1 : 0;
	}

	public Vergleich neuerVergleich()
	{
		return this;
	}
}

class Uncached implements Vergleich
{
	public int compare(String s1, String s2)
	{
		String t1 = s1.replace('*', '\uffff');
		String t2 = s2.replace('*', '\uffff');
		return t1.compareTo(t2);
	}

	public Vergleich neuerVergleich()
	{
		return this;
	}
}

class Cached implements Vergleich
{
	private final Map<String, String> cache = new HashMap<String, String>();

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}

	public Vergleich neuerVergleich()
	{
		return new Cached();
	}
}

class Capacity implements Vergleich
{
	private final Map<String, String> cache;
	private final int capacity;
	
	public Capacity(int capacity)
	{
		cache = new HashMap<String, String>(capacity);
		this.capacity = capacity;
	}

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}

	public Vergleich neuerVergleich()
	{
		return new Capacity(capacity);
	}
}

public class Test
{
	private static final int tests = 10;

	private static final int size = 100000;
	private static final int maxlen = 50;
	private static final int seed = 0;

	private static List<String> createList()
	{
		List<String> list = new ArrayList<String>(size);
		Random random = new Random(seed);
		for (int i = 0; i < size; ++i)
		{
			int n = 1 + random.nextInt(maxlen);
			char[] a = new char[n];
			for (int k = 0; k < n; ++k)
				a[k] = (char) (97 + random.nextInt(26));
			if (random.nextBoolean()) a[n - 1] = '*';
			list.add(new String(a));
		}
		return list;
	}

	public static void main(String[] args)
	{
		test(new Direct(), "direct");
		test(new Uncached(), "uncached");
		test(new Cached(), "cached");
		test(new Capacity(2 * size), "capacity");
	}

	private static void test(Vergleich vergleich, String name)
	{
		for (int i = 0; i < tests; ++i)
		{
			List<String> list = createList();
			Vergleich neuerVergleich = vergleich.neuerVergleich();
			Benchmark bm = new Benchmark(name);
			bm.start();
			Collections.sort(list, neuerVergleich);
			bm.stop();
			System.out.println(bm);
		}
		System.out.println();
	}
}

class Benchmark
{
	private final String name;
	private boolean running;
	private long start;
	private long sum;

	public Benchmark(String name)
	{
		this.name = name;
		running = false;
	}

	public void start()
	{
		assert !running;
		running = true;
		start = System.nanoTime();
	}

	public void stop()
	{
		long stop = System.nanoTime();
		assert running;
		sum += stop - start;
		running = false;
	}

	public String toString()
	{
		long l = sum;
		String s = "ns";
		if (l > 9999)
		{
			l /= 1000;
			s = "µs";
			if (l > 9999)
			{
				l /= 1000;
				s = "ms";
			}
		}
		return String.format("%s: %d %s", name, l, s);
	}
}
```
Jetzt sind die Testergebnisse konsistener, etwa 130 zu 580 zu 370 zu 380.

Schon witzig, wie die Garbage Collection die Messergebnisse beeinflusst... für mich ist die gecachte Variante irgendwie trotzdem langsamer, weil ja zwischendurch offenbar Zeit fürs Aufräumen draufgeht, aber das passiert halt zwischen den Messungen... naja, einfach die direkte Variante verwenden und gut is 

Fred


----------



## Guest (1. Jul 2008)

Anonymous hat gesagt.:
			
		

> - Das Cachen ist langsamer(!) als das Nicht-Cachen


Ah moment, das war "Messfehler", man betracht folgenden Code:


```
public static void test(Comparator<String> comparator, String name)
	{
		for (int i = 0; i < tests; ++i)
		{
			List<String> list = createList();
			Benchmark bm = new Benchmark(name);
			bm.start();
			Collections.sort(list, comparator); // <--- hier
			bm.stop();
			System.out.println(bm);
		}
		System.out.println();
	}
}
```
Die markierten Zeile wird ja 10x durchlaufen, aber es wird immer dasselbe Comparator-Objekt verwendet. Man muss hier aber mit einem frischen Comparator anfangen, sonst sind die Tests ja nicht unabhängig voneinander. Jetzt implementieren die Comparatoren ein neues Interface, das das Erzeugen eines frischen Objekts polymorph ermöglicht:

```
interface Vergleich extends Comparator<String>
{
	public Vergleich neuerVergleich();
}

class Direct implements Vergleich
{
	public int compare(String s1, String s2)
	{
		final int minlen = Math.min(s1.length(), s2.length());
		for (int i = 0; i < minlen; ++i)
		{
			char c = s1.charAt(i);
			if (c == '*') c = '\uffff';

			char d = s2.charAt(i);
			if (d == '*') d = '\uffff';

			if (c < d)
				return -1;
			else if (d < c) return 1;
		}
		final int deltalen = s1.length() - s2.length();
		return deltalen < 0 ? -1 : deltalen > 0 ? 1 : 0;
	}

	public Vergleich neuerVergleich()
	{
		return this;
	}
}

class Uncached implements Vergleich
{
	public int compare(String s1, String s2)
	{
		String t1 = s1.replace('*', '\uffff');
		String t2 = s2.replace('*', '\uffff');
		return t1.compareTo(t2);
	}

	public Vergleich neuerVergleich()
	{
		return this;
	}
}

class Cached implements Vergleich
{
	private final Map<String, String> cache = new HashMap<String, String>();

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}

	public Vergleich neuerVergleich()
	{
		return new Cached();
	}
}

class Capacity implements Vergleich
{
	private final Map<String, String> cache;
	private final int capacity;
	
	public Capacity(int capacity)
	{
		cache = new HashMap<String, String>(capacity);
		this.capacity = capacity;
	}

	private String lookup(String s)
	{
		String t = cache.get(s);
		if (t == null)
		{
			t = s.replace('*', '\uffff');
			cache.put(s, t);
		}
		return t;
	}

	public int compare(String s1, String s2)
	{
		return lookup(s1).compareTo(lookup(s2));
	}

	public Vergleich neuerVergleich()
	{
		return new Capacity(capacity);
	}
}

public class Test
{
	private static final int tests = 10;

	private static final int size = 100000;
	private static final int maxlen = 50;
	private static final int seed = 0;

	private static List<String> createList()
	{
		List<String> list = new ArrayList<String>(size);
		Random random = new Random(seed);
		for (int i = 0; i < size; ++i)
		{
			int n = 1 + random.nextInt(maxlen);
			char[] a = new char[n];
			for (int k = 0; k < n; ++k)
				a[k] = (char) (97 + random.nextInt(26));
			if (random.nextBoolean()) a[n - 1] = '*';
			list.add(new String(a));
		}
		return list;
	}

	public static void main(String[] args)
	{
		test(new Direct(), "direct");
		test(new Uncached(), "uncached");
		test(new Cached(), "cached");
		test(new Capacity(2 * size), "capacity");
	}

	private static void test(Vergleich vergleich, String name)
	{
		for (int i = 0; i < tests; ++i)
		{
			List<String> list = createList();
			Vergleich neuerVergleich = vergleich.neuerVergleich();
			Benchmark bm = new Benchmark(name);
			bm.start();
			Collections.sort(list, neuerVergleich);
			bm.stop();
			System.out.println(bm);
		}
		System.out.println();
	}
}

class Benchmark
{
	private final String name;
	private boolean running;
	private long start;
	private long sum;

	public Benchmark(String name)
	{
		this.name = name;
		running = false;
	}

	public void start()
	{
		assert !running;
		running = true;
		start = System.nanoTime();
	}

	public void stop()
	{
		long stop = System.nanoTime();
		assert running;
		sum += stop - start;
		running = false;
	}

	public String toString()
	{
		long l = sum;
		String s = "ns";
		if (l > 9999)
		{
			l /= 1000;
			s = "µs";
			if (l > 9999)
			{
				l /= 1000;
				s = "ms";
			}
		}
		return String.format("%s: %d %s", name, l, s);
	}
}
```
Jetzt sind die Testergebnisse konsistener, etwa 130 zu 580 zu 370 zu 380.

Schon witzig, wie die Garbage Collection die Messergebnisse beeinflusst... für mich ist die gecachte Variante irgendwie trotzdem langsamer, weil ja zwischendurch offenbar Zeit fürs Aufräumen draufgeht, aber das passiert halt zwischen den Messungen... naja, einfach die direkte Variante verwenden und gut is 

Fred

P.S. kann jemand den falsch formatierten Post von vor 1-2 Minuten bitte löschen? Danke.


----------



## SlaterB (1. Jul 2008)

meld dich doch einfach wieder an 

nun gut, die HashMap ist also viel langsamer als ich dachte,
bzw. die Stringerzeugung ist so schnell wie auch gesagt wurde,
was neues für mich




			
				Anonymous hat gesagt.:
			
		

> Die gleiche Befürchtung hatte ich ja erst bei equals, ist aber nicht so. hashCode wird nie öfter als einmal pro String aufgerufen!



die HashMap macht damit allerdings noch ein bisschen, zum einen:

static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }

und außerdem müssen ja die Strings beim Fund per equals vergleichen werden, was auch nochmal einem kompletten linearen Durchlauf entspricht,

aber ich hab extra die HashMap-Klasse kopiert und das rausgenommen, macht praktisch keinen Unterschied,
irgendwo muss es im System haken, bei so kleiner Stringerzeugung lohnt sich die Map nicht


----------



## SchonWiederFred (1. Jul 2008)

SlaterB hat gesagt.:
			
		

> meld dich doch einfach wieder an


Da muss man neuerdings so komplizierte Grundrechenarten beherrschen (was ist 10+2?)... aber ich hab's geschafft 



			
				SlaterB hat gesagt.:
			
		

> nun gut, die HashMap ist also viel langsamer als ich dachte,
> bzw. die Stringerzeugung ist so schnell wie auch gesagt wurde,
> was neues für mich


Hast Du es auch auf Deinem Rechner getestet? Vergleichbare Ergebnisse?



			
				SlaterB hat gesagt.:
			
		

> und außerdem müssen ja die Strings beim Fund per equals vergleichen werden, was auch nochmal einem kompletten linearen Durchlauf entspricht


Es gibt in String.equals eine Optimierung, die zuerst prüft, ob es sich um DASSELBE Objekt handelt. Hatte ich irgendwo schon gepostet, kannst ja auch selbst nachprüfen. Das macht die Sache also nicht langsamer.

Klar, bei Kollisionen muss man sich vielleicht erst durch ein paar falsche Strings durchwühlen, bis man zum richtigen gelangt, aber diese Tests sind ja sehr schnell, weil zwei verschiedene Strings sich ja ziemlich wahrscheinlich bereits in den ersten zwei, drei Zeichen unterscheiden. Da muss man fast nie komplett durch den String wandern. Aber wenn man den richtigen String gefunden hat, dann erkennt man das bereits beim Überprüfen der Referenz, dazu muss man sich den String überhaupt nicht näher anschauen.

Ich denke, dass sich das ganze durch "Mehr Speicherbedarf -> langsamer" erklären lässt (Von-Neumann-Flaschenhals). Schau Dir mal die Optimierungen in replace an. Wenn das merkt, dass der neue String gleich dem alten ist, gibt es eine Referenz auf den Originalstring raus und so Geschichten


----------



## SlaterB (1. Jul 2008)

SchonWiederFred hat gesagt.:
			
		

> Es gibt in String.equals eine Optimierung, die zuerst prüft, ob es sich um DASSELBE Objekt handelt. Hatte ich irgendwo schon gepostet, kannst ja auch selbst nachprüfen. Das macht die Sache also nicht langsamer.


man ey, die denken auch an alles und ich nicht,
nun gebe ich aber Ruhe 

ja, hatte bei mir die gleichen Ergebnisse


----------



## SchonWiederFred (1. Jul 2008)

Ja, ist schon fast erschreckend, wie performant Java mittlerweile geworden ist... :applaus:

Was ich lustig finde: die Java Leute benutzen oft lokale Kopien von Exemplarvariablen in Schleifen. Wahrscheinlich ist hier für den Compiler einfacher beweisbar, dass sich die Werte zwischendurch nicht ändern...?


```
public boolean equals(Object anObject)
{
	if (this == anObject)
	{
		return true; // Optimierung "derselbe String"
	}
	if (anObject instanceof String)
	{
		String anotherString = (String) anObject;
		int n = count; // lokale Kopie von Exemplarvariable
		if (n == anotherString.count)
		{
			char v1[] = value; // lokale Kopie von Exemplarvariable
			char v2[] = anotherString.value;
			int i = offset;
			int j = anotherString.offset;
			while (n-- != 0)
			{
				if (v1[i++] != v2[j++]) return false;
			}
			return true;
		}
	}
	return false;
}
```


----------



## chriss_2oo4 (1. Jul 2008)

Hi,

find ich super, dass ihr mir so viele hilfreiche Antworten gebt! Werd das bis morgen mal versuchen mit einzubauen.

Lg Chriss


----------



## SchonWiederFred (1. Jul 2008)

chriss_2oo4 hat gesagt.:
			
		

> Werd das bis morgen mal versuchen mit einzubauen.


Jo, und nimm am besten die folgende Lösung, die ist mit Abstand am schnellsten ;-)

```
class StarComparator implements Comparator<String>
{
	public int compare(String s1, String s2)
	{
		final int minlen = Math.min(s1.length(), s2.length());
		for (int i = 0; i < minlen; ++i)
		{
			char c = s1.charAt(i);
			if (c == '*') c = '\uffff';

			char d = s2.charAt(i);
			if (d == '*') d = '\uffff';

			if (c < d) return -1;
			if (d < c) return +1;
		}
		return s1.length() - s2.length();
	}
}
```


----------



## tfa (1. Jul 2008)

Jetzt lass noch das signum() weg und es ist perfekt.


----------



## SchonWiederFred (1. Jul 2008)

tfa hat gesagt.:
			
		

> Jetzt lass noch das signum() weg und es ist perfekt.


Danke, ich denke immer, dass nur -1/0/+1 erlaubt sind, aber das ist ja gar nicht so. Sehr schön!


----------

