Java Liste vom Typ "char" erstellen, wie?

4 Antworten

Erst mal vorweg: Deine Frage ist wirklich interessant! Denn sie hat mich zum grübeln darüber gebracht, wie effizient dein Vorhaben überhaupt in Java realisierbar ist.

Ich konnte mir einfach nicht vorstellen, dass der JIT-Compiler das ständige Autoboxing und Unboxing nicht irgendwie wegoptimiert.

Die Implementierung einer ArrayList aus Java entspricht im Grunde genommen einem Deque aus C++.

Ich habe dann mal folgende Java Version geschrieben:

public static List<Character> str2list(final String s) {
final int len = s.length();
ArrayList<Character> result = new ArrayList<Character>(len);

for (int i = 0; i < len; ++i) {
result.add(s.charAt(i));
}

return result;
}

Und habe diese im Profiler gegen folgende C++ Version antreten lassen:

deque<char> str2list(const string &s) {
deque<char> result;

for (const auto &c : s) {
result.push_back(c);
}

return result;
}

Diese Version war ca. ein Drittel schneller als die Java Version (2.3 Sekunden vs. 3.3 Sekunden). Allerdings hinkt dieser Vergleich, da Javas String zwar das CharSequence-Interface implementiert, dieses aber leider keine Collection ist, und somit effizientes Füllen einer ArrayList nicht möglich ist.

Da die C++ Container aber allesamt die C++ typischen Iteratoren in Form von begin() und end() implementieren, würde man eigentlich keinen Code wie den obigen schreiben, sondern eher soetwas:

inline deque<char> str2list(const string &s) {
return deque<char>(s.begin(), s.end());
}

Damit sinkt die benötigte Zeit auf ziemlich genau ein 11tel der Java Version. (3.3 Sekunden vs. 0.3 Sekunden)

Jetzt könnte man auch noch den Vektor-Container in Java und C++ vergleichen, aber das wäre totaler Quatsch, da Javas Vektor synchronisiert ist, und ein C++ vector bei den gegebenen Testdaten nochmal eine ganze Ecke flotter arbeitet. (8.3 Sekunden vs. 0.1 Sekunde) Wie gesagt, dieser Vergleich hinkt zu extrem, und deshalb lassen wir das mal weg.

Aaaaaber, worauf ich hinaus will ist: Ich hätte nicht gedacht, dass der Geschwindigkeitsunterschied zwischen Java und C++ bei vorliegender trivialer Aufgabe so enorm groß ist. Zudem ist die C++ Version deutlich kürzer, eleganter und leichter lesbar, obwohl das eigentlich immer von Java behauptet wird (was an vielen Stellen natürlich auch stimmt).

Trotzdem: 0,3 Sekunden verglichen mit 3,3 Sekunden bei einer Million Durchläufen mit jeweils einem 1-KB langen String. Ziemlich krass, ich hätte gedacht, Java sei sehr viel schneller! Selbst wenn man beachtet, dass Javas Chars 16 Bit breit sind und ein C++ Char nur 8 Bit, und diesen dann durch einen char16_t ersetzt, genauso wie die "string" Objekte durch "u16string" ... dann komme ich immer noch auf knapp 0.4 Sekunden.

Ich weiß, dass meine Antwort für den Fragensteller vermutlich ziemlich uninteressant ist, aber wollte auch nur mal den großen Unterschied aufzeigen.

Naja, schönen Abend noch an alle Mitleser und sorry für den Roman! :)

PS: Der Grund, warum ich im Java-Beispiel keine erweiterte for-Schleife genommen habe ist, dass man dafür erst ein char-Array erzeugen muss, was wieder zusätzlich RAM und Rechenzeit verbrät und nochmal langsamer wäre.

TeeTier  23.09.2016, 21:00

PS: Habe mir gerade nochmal die Implementierung von ArrayList angeschaut, und erschrocken festgestellt, dass es nur ein Wrapper um ein echtes Array ist, ohne die Zusätzlichen Features von einem C++-Deque. Da habe ich wohl zu viel erwartet.

Also ist der Vergleich der vector-Klasse von C++ doch wohl eher angebracht. Damit landen wir dann tatsächlich bei einem Verhältnis von 0,1 Sekunde zu 3,3 Sekunden, bei identischer Funktionalität.

Schade eigentlich. Ich hätte gedacht, dass der JIT-Compiler da mehr rausholt, aber ein Abstand mit mehr als Faktor 30 zu C++ ist in gewisser Weise schon bemerkenswert. Da wird einem direkt mal bildlich vor Augen geführt, warum man Game-Engines nicht in reinem Java schreiben sollte. :)

0
Unkreatiiiev  23.09.2016, 21:57

Könntest Du denselben Test mal mit der Java-8-Version machen?
Ich glaube zwar, dass die noch schlechter abschneidet, bin aber trotzdem gespannt.

final List<Integer> list = testString.chars()
.boxed()
.collect(Collectors.toList());

Die Liste enthält nun allerdings Integer statt Character. Das Ergebnist sollte aber dasselbe sein.

1
TeeTier  24.09.2016, 11:26
@Unkreatiiiev

Ehrlich gesagt hatte ich das mit getestet und kam auf etwas über 10 Sekunden.

Die Streams sind zwar mit Abstand die angesagteste Möglichkeit, aber fallen performance-technisch leider ziemlich durch. (10+ Sek. für Streams vs. ca. 0.1 Sek. für C++ vector)

Natürlich spielt das keine Rolle, wenn man mal kurz User-Eingaben umwurschteln will, aber wenn man damit über eine DB iteriert, wird es evtl. unangenehm. :)

Auf jeden Fall braucht man keine Angst haben, das der Oracle JIT Compiler schon perfekt ist, und es kein Optimierungspotential mehr gibt. So wie es aussieht, ist da noch genügend Luft nach oben. Bin sehr gespannt was da in den nächsten Jahren noch alles kommt. :)

PS: Schön, dass hier auch jemand Streams kennt! Ich hab die bewusst nicht weiter erwähnt, weil ich dachte, da kann sowieso niemand etwas mit anfangen. Aber so langsam scheinen sich die Leute an Java 8 zu gewöhnen und JavaFX für GUIs sieht man ja auch immer häufiger. :)

1
Unkreatiiiev  24.09.2016, 15:33
@TeeTier

Streams sind in manchen Situationen einfach ein Traum. Natürlich nicht, wenn jede Millisekunde zählt. ;)

1
TeeTier  24.09.2016, 15:37
@Unkreatiiiev

Streams sind vom API-Design her genial! Ich hoffe, das kam jetzt nicht anders rüber. :)

Man muss halt einfach abwägen, in welcher Situation WAS am geeignetsten ist. Und das werden in sehr vielen Fällen eben die Streams sein. :)

2
gut4fr5g4 
Fragesteller
 24.09.2016, 08:02

Danke, dass du dir die Mühe gemacht hast, so viel zu schreiben, sowas schätze ich sehr! :)

2

Du musst als Rückgabetyp List<char> nutzen. List ist eine generische Klasse, die musst du schon richtig benutzen.

Woher ich das weiß:Studium / Ausbildung – Informatikstudium
gut4fr5g4 
Fragesteller
 23.09.2016, 17:48

habe ich doch gemacht...

public List splitText(){
List list = new ArrayList();
return list;
}

geht immer noch nicht -.-

0
triopasi  23.09.2016, 17:51

Du gibst keinen Typ an. List ist GENERISCH. Google mal wie man generics richtig benutzt.

1
triopasi  23.09.2016, 17:52

edit: Wraper-Classe statt primitive benutzen. ergo List

1

Generics funktionieren nicht mit primitiven Typen. Dafür gibt's die Wrapper-Klasse Character.

List<Character> splitText() {
//...
}