Wieso fällt dieser Test durch (Java)?
Hallo!
Im Rames des Moduls Algorithmen und Datenstrukturen, gibt es manchmal online so Programmieraufgaben. Da müssen wir dann einen Algorithmus mit einer vorgegebenen Laufzeit schreiben. Dieses sieht die Aufgabe so:
Hier mein Code dazu:
Mein Code dazu funktioniert auch. Nur fällt er bei einem Test durch und ich weiß nicht genau wie ich es deutet soll und was ich anpassen muss, damit er nicht durchfällt:
Mein Code sollte auch in O(n+m) laufen, denn die erste for-Schleife ist O(n) und die zweite O(m). In den Schleifen, passieren nur konstante Dinge. Der Test, welcher fehlschlägt erstellt zwei Random Arrays der Länge 9.500.000 und schaut sich an, ob es alles geklappt hat. Das ganze wird drei mal gemacht. Die Ausgabe Strings berechne ich auch richtig, was man an den drei ok's sehen kann. Aber trotzdem steht da dann irgendwas von Zeitbegrenzung überschritten...
Danke und LG
3 Antworten
In der Aufgabe steht's doch: Timelimit 1 CPU-Sekunde.
Dein Code ist einfach viel zu langsam. Lass ihn mal mit großen Datenmengen im Profiler laufen, dann siehst Du genau, wo's klemmt (vermutlich überall).
- Warum baust Du ein neues Array C? B tut's doch auch.
- Warum iterierst Du über die Indizes von A? Du brauchst doch nur die Werte.
- Warum addierst Du 1 zu C[A[i]]? Das Ergebnis landet doch wieder an derselben Stelle.
- ...
Vielen Dank für die Antwort! Ich versuche mal das ganze zu reduzieren
Die Oracle-Dukumentation sagt
sb.append(x) has the same effect as sb.insert(sb.length(), x)
Über die Laufzeit schweigt sich die Doku allerdings aus. Grundsätzlich kann insert() nicht in 𝓞(1) sein. Allerdings hätte ich erwartet, dass ein Einfügen am Ende dennoch flott geht. Vielleicht ist append() nur deshalb schneller, weil die Indexprüfung entfällt?
Aber so oder so: Da Du die Länge des Ergebnisses kennst, wäre byte[] wohl wesentlich schneller als StringBuffer().
Mein Code sollte auch in O(n+m) laufen, denn die erste for-Schleife ist O(n) und die zweite O(m)
Stimmt zwar, aber Du darfst die übrigen Anweisungen nicht einfach ignorieren:
- new int[m] ist in 𝓞(m)
- new StringBuffer("") ist zwar in 𝓞(1), führt aber dazu, dass append() vermutlich in 𝓞(log m) liegt. (Mit new StringBuffer(m) kannst Du das vermeiden.)
- res.toString() ist mindestens in 𝓞(m).
- C[A[i]] ist zwar in 𝓞(1), aber sehr teuer:
- prüfe A==null
- berechne die Adresse von A.length
- prüfe i < A.length
- prüfe i >= 0
- berechne die Adresse von A[i]
- prüfe C==null
- berechne die Adresse von C.length
- prüfe A[i] < C.length
- prüfe A[i] >= 0
- berechne die Adresse von C[A[i]]
In der Schleife machst Du das sogar zweimal. Der Java-Compiler optimiert zwar vieles weg, aber ich bin mir nicht sicher, ob er hier noch effizienten Code produzieren kann.
So wäre es für den Compiler und für Menschen leichter zu lesen:
for ( int a : A )
++C[a];
Und noch was:
sb.append('0') ist möglicherweise als sb.append(Character.toString('0')) implementiert. Dann wäre sb.append("0") deutlich schneller.
Wunderbar! Danke für die ganzen Tipps, ist wirklich nett von Ihnen!
Ein paar Ideen, wie du den Code schneller kriegen kannst:
- Anstatt ein neues Array C zu bauen, in dem du hochzählst, kannst du auch einfach in B runterzählen und am Ende prüfen, ob die Zahl >= 0 ist
- Benutze ++C[A[i]] anstatt C[A[i]] = C[A[i]] +1. (Bzw. wenn du den ersten Punkt befolgst --B[A[i]] )
- Beim prüfen gehst du die Felder des Arrays in ihrer Reihenfolge durch. Du brauchst die Ergebnisse also nicht mit res.insert einfügen, sondern kannst res.append benutzen, was deutlich schneller gehen müsste.
Keine Ahnung ob es daran liegt, aber du darfst den Substring "sol_calc" nicht verwenden, aber das tust du. Sonst keine Ahnung
Es hat tatsächlich schon gereicht statt mittels .insert(int,char) einen character an den StringBuilder zu hängen, dies mit .append(char) zu machen. Danke nochmal!