Wieso fällt dieser Test durch (Java)?

3 Antworten

Vom Beitragsersteller als hilfreich ausgezeichnet
ralphdieter
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Computer, Informatik
07.12.2021, 18:38

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.
  • ...
ralphdieter  08.12.2021, 08:16
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:
  1. prüfe A==null
  2. berechne die Adresse von A.length
  3. prüfe i < A.length
  4. prüfe i >= 0
  5. berechne die Adresse von A[i]
  6. prüfe C==null
  7. berechne die Adresse von C.length
  8. prüfe A[i] < C.length
  9. prüfe A[i] >= 0
  10. 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];
ralphdieter  08.12.2021, 08:26
@ralphdieter

Und noch was:

sb.append('0') ist möglicherweise als sb.append(Character.toString('0')) implementiert. Dann wäre sb.append("0") deutlich schneller.

xam193 
Beitragsersteller
 08.12.2021, 09:40
@ralphdieter

Wunderbar! Danke für die ganzen Tipps, ist wirklich nett von Ihnen!
xam193 
Beitragsersteller
 07.12.2021, 22:12

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!

ralphdieter  08.12.2021, 07:54
@xam193

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().
xam193 
Beitragsersteller
 07.12.2021, 18:41

Vielen Dank für die Antwort! Ich versuche mal das ganze zu reduzieren
daCypher
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Computer, programmieren
08.12.2021, 08:24

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.
xam193 
Beitragsersteller
 08.12.2021, 09:42

Danke für die Antwort!

imsonoah
07.12.2021, 17:53

Keine Ahnung ob es daran liegt, aber du darfst den Substring "sol_calc" nicht verwenden, aber das tust du. Sonst keine Ahnung

Woher ich das weiß:Hobby – Studium (und Hobby seit Jahren)