Challenge! (Leerzeichen in Strings zählen)

Hallo Freunde, (bitte mit Gronks Stimme vorstellen)

neben dem Quiz thread fände ich einen challenge thread sehr reizvoll. Über die Regeln hab ich mir noch nicht viele Gedanken gemacht, aber so in etwa:
0. Jeder darf eigene Regeln einbringen, Details klärt immer der Herausvorderer.

  1. eine Challenge geht n Wochen
  2. alles was auf der JVM läuft darf verwendet werden (Hallo Scalla, etc), aber kein JNI, sollte das Ziel sein Code so kurz wie möglich zu bekommen, nur pure Java
  3. Der Gewinner stellt die neue Aufgabe oder delegiert.

Sollte es sich bei der Herausvorderung um ein “schreibe den schnellsten Code” handeln gilt noch:
4. eseiden es wird explizit erlaubt: keine Parallelisierung.
5. am Ende wird der Code jedes Teilnehmers vom letzten Herausvorderer einheitlich mithilfe eines Benchmark Tools und von uns standartisierten Bedingungen getestet.
6. der Schnellste, der nicht der Herausvorderer ist, gewinnt.

über standartisierte Benchmarks und den Wert von n darf gerne noch diskutiert werden (ersteres besonders von Leuten die Ahnung von sowas haben).

Auch wenn die formalitäten noch nicht klar sind würde ich mal mit einer schreibe-den-schnellsten-Code-Challenge beginnen:

Aufgabe:
Schreibe ein Programm, dass in einem beliebigen String (zu Referenzzwecken würde ich hier den Wiki Artikel über unsere Lieblingsinsel nehmen) alles was kein Leerzeichen ist zählt. Gemessen wird nicht das Einlesen des Strings (darf auch gerne hartkodiert sein, beim einheitlichen Benchmark würde ich das dann alles anpassen) sondern nur die Zeit die benötigt wird, die Nichtleerzeichen zu zählen.

Wer will hier mal ein kleines Gerüst zum experimentieren (ja, es wird wirklich nur die letzte “Runde” gemesse, meinen Tests zu folge ist das der stabilste Weg vergleichbare Resultate zu erzielen, da der JIT dann schon warmgelaufen ist und sich die verschiedenen Methoden nicht gegenseitig beschleunigen):
[SPOILER]

import java.util.LinkedList;
import java.util.Collections;

public class foo {

	private static String s = " By assuming the subtraction would need to be executed less times than the addition I changed it to check whether or not the character was a white-space character. The logic was better, but using the Character.isWhitespace boolean call on every character the execution time was horrendous. This was pretty slow as it was computing the stringToParse.length() on every iteration, also the charAt doesn't seem to be very optimal. (excluding the 3.7 million on the island of Madura which is administered as part of the province of East Java), Java is the world's most populous island, and one of the most densely populated places in the world. Java is the home of 57 percent of the Indonesian population. The Indonesian capital city, Jakarta, is located on western Java. Much of Indonesian history took place on Java. It was the center of powerful Hindu-Buddhist empires, the Islamic sultanates, and the core of the colonial Dutch East Indies. Java was also the center of the Indonesian struggle for independence during the 1930s and 40s. Java dominates Indonesia politically, economically and culturally.";

	public static void main(String[] args) {
		
		LinkedList<Counter> list = new LinkedList<Counter>();
	
		// Test 1
		list.add(new Counter("addition") {
			public int count() {
				int count = 0;
				for(int i = 0; i < s.length(); i++){
					if(s.charAt(i) != ' ') {
						count++;
					}
				}
				return count;
			}
		});
		// Test 2
		list.add(new Counter("replace") {
			public int count() {
				String s2 = s.replaceAll(" ","");
				return s.length() - s2.length();
			}
		});

		for(int i=0; i<26; i++) // startup JIT with 25 rounds and messure the 26th
		for(Counter c : list) {
			c.compute();
		}  
		Collections.sort(list);
		System.out.println(list);
	}

	private static abstract class Counter implements Comparable<Counter> {
		private static final int ROUNDS = 100000;
		private String name;
		private long duration;
		private int amount;

		public Counter(String name) {
			this.name = name;
		}		

		public int compareTo(Counter c) {
			return (int) (duration - c.duration);
		}
		public String toString() {
			return "
 counted:"+amount+ "chars in:" + duration +"ns by:"+name+"
";

		}
		public void compute() {
			long before = System.nanoTime();
			for(int i=0; i<ROUNDS; i++) {
				amount = count();
			}
			long after = System.nanoTime();
			duration = (after-before)/ROUNDS;
		}
		public abstract int count();
	}
}

[/SPOILER]

Viel Spaß beim mikrooptimieren!
Jemand der schonwieder sein Passwort vergessen hat.

P.S.: ich bin echt gespannt, auf was für Ideen die Cracks hier kommen.
P.P.S: ja die Aufgabe ist aus einem anderen Forum geklaut, ich finde die Idee mit den Challenges aber wirklich gut und glaube dass sie der Community hier auch einiges bringen wird. Außerdem glaub ich, dass die Qualität der Antworten hier ziemlich hoch sein wird.

Vielleicht nicht am effizientesten, aber kurz:


public static int count(String s) {
         return s.split(" ").length - 1;
}

         return s.replace(" ", "").length();
}```Ich meine gelesen zu haben, dass er (im Gegensatz zu dem, was im Titel steht) die nicht Leerzeichen addiert haben will...
@TO: Sag bescheid, wenn der Titel geändert werden soll.

Ich denke, dass das Erzeugen des leerzeichenfreien Strings ein Zeit-Fresser ist. Daher wäre mein Vorschlag dieser:private static final Pattern NON_SPACE_PATTERN = Pattern.compile("[^ ]"); public static int count(String s) { Matcher nonSpaceMatcher = NON_SPACE_PATTERN.matcher(s); int nonSpaceCounter =0; while(nonSpaceMatcher.find()) {nonSpaceCounter++;} return nonSpaceCounter; }
bye
TT

Moin,

auf Heise gab es vor kurzem einen einsteigerfreundlichen Artikel zum Thema Microbenchmarking.

Damit sähen die bisherigen “Lösungen” etwa so aus:


import java.util.regex.Matcher;
import java.util.regex.Pattern;

import org.openjdk.jmh.annotations.GenerateMicroBenchmark;


public class Counter {


    private static String s = " By assuming the subtraction would need to be executed less times than the addition I changed it to check whether or not the character was a white-space character. The logic was better, but using the Character.isWhitespace boolean call on every character the execution time was horrendous. This was pretty slow as it was computing the stringToParse.length() on every iteration, also the charAt doesn't seem to be very optimal. (excluding the 3.7 million on the island of Madura which is administered as part of the province of East Java), Java is the world's most populous island, and one of the most densely populated places in the world. Java is the home of 57 percent of the Indonesian population. The Indonesian capital city, Jakarta, is located on western Java. Much of Indonesian history took place on Java. It was the center of powerful Hindu-Buddhist empires, the Islamic sultanates, and the core of the colonial Dutch East Indies. Java was also the center of the Indonesian struggle for independence during the 1930s and 40s. Java dominates Indonesia politically, economically and culturally.";


    @GenerateMicroBenchmark
    public int countUnregistriert1() {

        int count = 0;
        for (int i = 0; i < s.length(); i++)
            if (s.charAt(i) != ' ')
                count++;

        return count;

    }


    @GenerateMicroBenchmark
    public int countUnregistriert2() {

        final String s2 = s.replaceAll(" ", "");
        return s.length() - s2.length();

    }


    @GenerateMicroBenchmark
    public int countBene() {

        return s.split(" ").length - 1;

    }


    @GenerateMicroBenchmark
    public int countSpacerat() {

        return s.replace(" ", "").length();

    }

    
    private static final Pattern NON_SPACE_PATTERN = Pattern.compile("[^ ]");


    @GenerateMicroBenchmark
    public int countTimothy_Truckle() {

        final Matcher nonSpaceMatcher = NON_SPACE_PATTERN.matcher(s);
        int nonSpaceCounter = 0;

        while (nonSpaceMatcher.find())
            nonSpaceCounter++;

        return nonSpaceCounter;

    }


    @GenerateMicroBenchmark
    public int countFancy() {

        return 923;

    }

}```

Und im Ergebnis:


Run complete. Total time: 00:48:26

Benchmark Mode Samples Score Score error Units
n.b.Counter.countBene thrpt 200 98.734 1.146 ops/ms
n.b.Counter.countFancy thrpt 200 595048.500 10129.891 ops/ms
n.b.Counter.countSpacerat thrpt 200 28.295 0.345 ops/ms
n.b.Counter.countTimothy_Truckle thrpt 200 25.923 0.472 ops/ms
n.b.Counter.countUnregistriert1 thrpt 200 1070.932 26.372 ops/ms
n.b.Counter.countUnregistriert2 thrpt 200 40.372 0.826 ops/ms



Sauber wäre es imho, wenn der Aufgabensteller ein zu implementierendes Interface und ein Unit-Test stellt, dann wäre klar, was eine Lösung ist und was nicht.

Viele Grüße
Fancy

Unit-Tests halte ich in dieser Beziehung für eine gute Idee. Ich bin in dieser Beziehung leider immer recht lustlos und nicht besonders einfallsreich. Glücklicherweise hat mich TT ja gerinfügig geschlagen. Herzlichen Glückwunsch. :wink:

@Fancy eine ähnliche Lösung hatte ich auch im Kopf. Allerdings hätte ich das Ergebnis bei der Klasseninitialisierung berechnet und dann zurückgegeben. Das dürfte der JIT nach ein paar Durchläufen zu deinem Code machen :wink:

Ist die banalste Lösung auch die schnellste?

	public int countNonBlanks() {
		int count = 0;
		for (char ch : s.toCharArray())
			if (ch != ' ')
				count++;
		return count;
	}```

Edit: Ich sehe gerade ... Lösung countUnregistriert1 ist ja fast das selbe :)

Wenn sich Programmierer langweilen. Ich würde die Zeichenkette char für char durchgehen und in einer if-Abfrage nach 64 schauen, wenn true, zaehler++.
Da sehe ich grad, @freezly hat dafür auch schon den Code geliefert.
@Fancy deine Lösung ist… hinten durch die Brust ins Auge