Ist Java viel schneller als C... in manchen Dingen

Computer: Software & Programmierung C/C++
#1

Hi zusammen, wollte mal wieder was andiskutieren. Hab ein Programm geschrieben, um zu berechnen, wieviele Codes einer Zahlentastatur keine Zahlenwiederholungen haben. Also zB 12454 (die 2x 4er). Nun hab ich das ganze mal mit Mrd. von for Schleifen versehen und siehe da, java scheint um vieles schneller zu sein als c Derivate. Hab ich nur den Schalter für Geschwindigkeits-Optimierung beim gcc noch nicht gefunden (im release mode war er manchmal sogar langsamer als im debug mode) oder ist da wirklich was dran?

Gefunden im Netz hab ich dazu z.B. folgendes was mir plausibel erscheint:
https://www.computerweekly.com/de/feature/Java-versus-C-Welche-Programmiersprache-ist-schneller

Quelltexte liegen hier:

Ausführungszeit bei mir bis zu 60sec, java nur ca. 16.

#2

Hallo,
ich sage es mal diplomatisch so: Man kann fast jedes Programm in jeder Programmiersprache langsamer machen. Und es kommt auf den Compiler an.

Ohne libc-Routinen läuft Dein Programm bei mir statt in 89 Sekunden in 21. Den Algorithmus noch durch ein Radix-Search ersetzt in 10 Sekunden. Die Java-Variante (IBM Semeru)

Version    gcc-7  icc-11  semeru
original      97      89      21
nolibc        22      19      21
radix         16      10      16

Hier der Radix-Code:

#include <stdio.h>
#include <stdint.h>

static int
repeats(size_t i)
{
    unsigned char counter[10U] = {0};
    do {
            if (counter[(i % 10U)]++ >= 1U) {
                    return 0;
            }
    } while (i /= 10U);
    return 1;
}

int main() {
    int counter = 0; // zaehlt Zahlen ohne Wiederholungen von Ziffern in der Zahl

    for (size_t i=1000; i<999999999; ++i) {
            counter += repeats(i);
    }
    printf("%d\n\r", counter);
    return 0;
}
3 Like
#3

Dank dir @hroptatyr für deine gewohnt tollen Antworten und die tolle Aufbereitung!
Mit dem Radix search repeats() ist das natürlich auch ziemlich cool & simpel! :slight_smile:

Ich wollte auch nicht damit sagen, dass java gut ist und die CC…s schlechter sind aber ich war schon erstaunt über das Verhalten. Findest du das konstant gute Verhalten der letzten Spalte nicht auch erstaunlich? Klar ist, dass bei vielen grafischen Sachen… natürlich java nicht anstinken kann gegen die C’s. Aber bei den Berechnungen hier hab ich eher das umgekehrte Verhalten erwartet nach landläufiger Meinung (ohne Prüfung)?

Anbei nochmal ein Beispiel, wie man das auch „undiplomatischer“ kommunizieren kann. :slight_smile:

#4

Ja, die .toString Routinen in Java scheinen hervorragend optimiert zu sein. Etwas, das ich in meinen eigenen C-Programmen immer als erstes erstes ersetze, weil es quälend langsam ist.

Ich habe keinerlei Erfahrungen mit Java und demnach auch keine Erwartungen, aber ich weiß, daß Schleifen mit komplexen Abbrüchen für heutige Prozessoren Gift sind. Leider ist mir nichts schlaueres eingefallen, als naiv alle Eingaben durchzugehen.

1 Like
#5

Ah, hallo, nochmal ich.
Ich hab’s jetzt wesentlich optimiert. Es ist ja nur ein kombinatorisches Problem: Für k-stellige Zahlen sollen genau die gezählt werden, die eine Variation der Ziffern 0 bis 9 sind. Das sind aber gerade die k-Variationen es sei denn ganz vorne steht eine 0, dann ist das definitionsgemäß keine k-stellige Zahl. Also müssen wir die (k-1)-Variationen der Ziffern 1 bis 9 abziehen. In Formeln:

count(k) = nPr(10, k) - nPr(9, k-1)

Die Gesamtaufgabe ist es dann

count(4) + count(5) + count(6) + count(7) + count(8) + count(9)

zu berechnen.

Generisch ginge das sehr schnell via exp/lgamma, aber für dieses einfache Problem reicht die Integer-Multiplikation. Bei mir hat’s 11 Nanosekunden (+/-0.5) gedauert.

Ein Speed-up in der Milliarden Größenordnung, und das wohl auch in Java.

1 Like
#6

uff @hroptatyr da muss ich mal abends noch in Ruhe drüber nachdenken, irgwie schwante mir auch was mit Variation/Kombination aber die Schulzeit ist schon etwas her… :slight_smile:

Hab grad mit meiner String Variante ein bisschen gespielt, das sprintf muss die meiste Zeit brauchen - anbei meine Zeiten:

+++

fam@Telemann:~/eclipse-workspace/Codetastatur/Debug$ time ./Codetastatur
ZahlenMitString
strlen in innerstem for:
5611032

real 1m19,823s
user 1m19,814s
sys 0m0,004s
fam@Telemann:~/eclipse-workspace/Codetastatur/Debug$ time ./Codetastatur
ZahlenMitString
strlen vor innerstem for:
5611032

real 1m16,269s
user 1m16,259s
sys 0m0,008s
fam@Telemann:~/eclipse-workspace/Codetastatur/Debug$ time ./Codetastatur
ZahlenMitString
strlen vor äußerem for:
5611032

real 1m6,504s
user 1m6,491s
sys 0m0,005s

ZahlenMitRadix
5611032

real 0m15,760s
user 0m15,759s
sys 0m0,000s

        strLen=strlen(zahl);
        for (int j=0; j<strLen; j++) {
            if (checker == false) break;
            for (int k=1+j; k<strLen; k++) {
                if (zahl[j] == zahl[k]) {
                    checker=false; break;
                }
            }
        }

#7

Da wirst Du nicht viel erreichen, hier mal die Zeiten aus dem Profiler:

_IO_vfprintf_internal          24.466s
_itoa_word                     15.544s
_IO_default_xsputn              8.667s
__strchrnul                     8.072s
main                            5.794s
[...]                          15.679s

Die ersten vier gehören rein der libc, da kannst Du mit Code-Umstellen und Co. nichts dran ändern. Also mein Tipp, das Maximum an Optimierung in der String-Variante liegt bei ca. 62 Sekunden.

Falls Du kannst, kannst Du ja mal musl (eine libc) probieren, statt der glibc. Ist auch nicht viel besser aber in der Größenordnung von 30 Sekunden.

Den sprintf selbstgeschrieben und auf das strlen verzichtet bringt nochmal 10 Sekunden (das ist, was ich eingangs als nolibc betitelt habe).

Ach übrigens, sprintf gibt bereits die String-Länge zurück. Das wollte ich auch noch erwähnen.

1 Like
#8

Hallo zusammen,
zur Kontrolle habe ich das einmal mit dem Taschenrechner berechnet. :wink:

  • Es gibt 10 einelementige Codes, nämlich 0, 1, 2, …, 9.
  • Dann gibt es im Prinzip 100 zweielementige Codes, nämlich 00, 01, …, 99. Von denen sind aber die 10 Dopplungen 00, 11, …, 99 ausgeschlossen. Bleiben also noch 90 zweielementige Codes. Auf die 90 kommt man auch durch die folgende Überlegung: Für die erste Ziffer habe ich 10 Möglichkeiten, für die zweite Ziffer dann aber nur noch neun Möglichkeiten, weil die beiden Ziffern ja verschieden sein müssen. Das gibt zusammen dann auch 10*9 = 90 Codes.
  • Als nächstes zähle ich die dreielementigen Codes. Da gibt es für die erste Ziffer 10 Möglichkeiten, für die zweite Ziffer noch 9 Möglichkeiten und für die dritte Ziffer dann noch acht Möglichkeiten, da ja schon zwei Ziffern „verbraucht“ sind. Insgesamt ergibt das 10 * 9 * 8 = 720 dreielementige Codes.

An dieser Stelle sieht man schon, wie das weitergeht. Die Gesamtzahl an gültigen Codes beträgt offensichtlich 10 + 10 * 9 + 10 * 9 * 8 + 10 * 9 * 8 * 7 + … + 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1. Der letzte Summand zählt die zehnelementigen Codes. Dann ist Schluss, weil man natürlich aus zehn Ziffern keine längeren Codes ohne Wiederholungen bilden kann.

Diesen Ausdruck kann man nun in den Taschenrechner eintippen und erhält 9 864 100.

Man kann sich die Berechnung noch etwas vereinfachen, indem man die Fakultät benutzt. Man schreibt 10! (lies: 10 Fakultät) und bezeichnet damit das Produkt 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Die Summe oben besteht also aus lauter „angefangenen Fakultäten“. Die schreibe ich als Bruch, indem ich immer 10! im Zähler schreibe und die unerwünschten Faktoren durch den Nenner wieder wegdividiere. Dann ist also 10 = 10! / 9! und 90 = 10 * 9 = 10! / 8! sowie 720 = 10 * 9 * 8 = 10! / 7! usw. Insgesamt führt das auf die Anzahl 10!/9! + 10!/8! + 10!/7! + … + 10!/1!. In dieser Summe klammere ich noch die 10! aus und erhalte kurz

N = 10! * (1/1! + 1/2! + … + 1/9!) = 9 864 100.

PS. Die Formel erscheint etwas unsymmetrisch, weil vorne 10! steht, in der Summe aber nur bis 9! summiert wird. Man hätte das natürlich lieber in der Form

10! * (1/1! + 1/2! + … + 1/9! + 1/10!) = 9 864 101.

Das ergibt mathematisch gesehen auch Sinn, wenn man nämlich die eine dazugewonnene Kombination als den einzigen nullstelligen Code, nämlich die leere Menge, interpretiert.

Liebe Grüße
vom Namenlosen

1 Like
#9

Genau. Das nennt man k-Variationen. Auf dem Taschenrechner die nPr-Taste. Aber, Du hast vergessen, daß eine führende Null ausgeschlossen ist. Daher zählst Du einige Zahlen doppelt, also 0123 und 123.

#10

Hallo @hroptatyr,
woraus geht denn hervor, dass führende Nullen verboten sind?

Wenn man diese Kombinationen unbedingt ausschließen möchte, ergeben sich nach meiner Rechnung 8 877 690 verschiedene Codes. Die Formel ist dann aber weniger symmetrisch,
N = 90 + 9 * 9! * ( 1/0! + 1/1! + … + 1/7!). Entspricht das auch deiner Berechnung?

Liebe Grüße
vom Namenlosen

#11

Aus dem Original-Quelltext geht das hervor.

Also ich habe insgesamt 5611770 ein- bis neunstellige Zahlen ohne Zifferndopplung.

#12

Danke! Das entspricht auch meinem Ergebnis, wenn ich die 3 265 920 zehnstelligen Codes ohne führende Null abziehe.
Liebe Grüße
vom Namenlosen

#13

Ja ich komme auch mit den zu Fuß Programmen (ohne Mathekenntnisse) auf:
ZahlenMitRadix
5611771
für Wertebereich:
0-999.999.999

Zählt 0 mit? Eigentlich schon???

#14

Hallo @oldy22,
die Frage, welche Kombinationen zählen, gibst du durch die Fragestellung doch selber vor. Wenn ich die Aufgabe rein als ein kombinatorisches Problem ohne weitere zusätzlichen Bedingungen betrachte, erscheint es mir am sinnvollsten, alle ein- bis zehnstelligen Kombinationen zu betrachten und somit eine führende Null generell zuzulassen und zusätzlich auch noch die eine „nullstellige Kombination“ mitzuzählen.

Liebe Grüße
vom Namenlosen

1 Like
#15

Ja, 0-10 sind alle MIT dabei in den 5.611.771!

#16

Ja, genau. Aber die Kombination 0123 ist nicht dabei.

Du erlaubst zB 1023 und 3210, aber eben nicht 0123.

#18

Noch diese Bedingung hab ich vergessen für das Ergebnis oben:
bis 9 stellige Codes aber auch mit führenden Nullen möglich und keine Ziffernwiederholungen.
Damit müsste das die Zahl sein, was mit 9 Ziffern ohne Ziffer-Wiederholungen maximal möglich ist.
Zahlen mit Strings plus führende Nullen.java:

9501220

real 0m40,082s
user 0m40,365s
sys 0m0,185s

#19

Also ich habe mit „Durchtesten“ ein anderes Ergebnis hier (Source im Link oben):

Bedingung bis 9-stellige Codes, führende Nullen erlaubt und keine Wiederholung von Ziffern:
:space_invader: :bomb:

Zahlen mit Strings plus führende Nullen:

6.235.300

real 0m30,117s
user 0m30,467s
sys 0m0,138s

(Sorry die 2 Posts drüber waren fehlerhaft.)

#20

100 Codes für 2-stellig hab ich auch!
3-stellig: 820
4-stellig: 5860
5-stellig: 36100
6-stellig: 187.300
7-stellig: 792.100
8-stellig: 2.606.500

#21

Also ich persönlich verstehe die Forderung mit der führenden Null nicht, einfacher macht sie die Sache auch nicht. Eine k-stellige Zahl mit 6 führenden Nullen ist für mich eine (k-6)-stellige Zahl.

Beim „Durchzählen“ tritt zudem die Diskepanz auf, daß 123 gezählt, 0123 ebenfalls gezählt, aber 00123 nicht gezählt wird. Andersherum ist 120 gültig, 0120 ungültig, und 00120 erst recht ungültig.