Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Meine Lösung wurde angenommen, allerdings ist sie mit 0.21s ca. fünfmal langsamer als die schnellste Lösung in Python.
(Link zur Aufgabe: http://www.spoj.com/problems/ADDREV/)
def rev(n):
reverse=[]
reverse_int=0
list_n=list(str(n))
for i in range(len(list_n),0,-1):
reverse.append(list_n[i-1])
l_r=len(reverse)
for k in range(l_r):
reverse_int=reverse_int+int(reverse[k])*10**(l_r-k-1)
return reverse_int
def pop_zeros(n):
if n%10 == 0:
n = int(n/10)
return pop_zeros(n)
else:
return n
cases=0
ausgabe=[]
cases = int(input())
for i in range(cases):
eingabe=input()
l_input=eingabe.split()
zahl_1=rev(pop_zeros(int(l_input[0])))
zahl_2=rev(pop_zeros(int(l_input[1])))
ausgabe.append(rev(zahl_1+zahl_2))
for i in ausgabe:
print(i)
#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import print_function
from platform import python_version_tuple as version
if int(version()[0]) < 3:
input = raw_input
def add_reversed(values_str):
return str(sum(map(lambda x: int(x[::-1]), values_str)))[::-1]
if __name__ == "__main__":
for _ in range(int(raw_input("number of cases: "))):
print(int(add_reversed([input("reversed number %d: " % cnt) for cnt in range(2)])))
„gcc finds bugs in Linux, NetBSD finds bugs in gcc.“[Michael Dexter, Systems 2008] Bitbucket, Github
@hulkhomer:
Ich habe mal meinen alten code für dieses Problem erneut auf SPOJ hochgeladen (Python 3.4 kannte ich dort als Option noch gar nicht). Damit liege ich auf Anhieb bei den Top-Zeiten.
Unterschiede zu Deinem Code:
Umkehren rein über String-Slicing [::-1]
Eliminieren der (führenden) Nullen rein über int-Wandlung (Auch wenn Typ-Konvertierungen eigentlich "teuer" sind)
SPOJ-Typisch: Sammeln der Zwischenergebnisse und nur eine einzige Augabe am Ende. Noch weiter treiben kann man das mit sys.stdout.write, das lohnt sich aber bei der Ausgabemenge in diesem Problem noch nicht
line = input()
a, b = line.split()
a = a[::-1]
b = b[::-1]
sum = str(int(a) + int(b))
result = (int(sum[::-1]))
Und wie das so ist, wenn man sich seinen alten Code anschaut, selbst dieser Schnipsel ist hinsichtlich DRY und hinsichtlich *guter* Namen verbesserungswürdig
Jepp. Die "Nicht-Nachdenk-Lösung" mit den Typkonvertierungen macht zwar weniger Spaß, löst das Problem unter Python 2.7 in meinem Fall aber innerhalb von 0,05 Sekunden. Wenn man einigermaßen fit in solchen Dingen ist, dann sollte man auch eine Lösung errechnen können, die sogar ohne tatsächliches Umkehren der Strings auskommt. Aber im Falle von Python würde es mich nicht wundern, wenn eine solche Lösung eine längere Laufzeit hätte als die billige Variante ("billig" bezogen auf den Code).
EDIT: Wobei ich gerade sehe, dass etliche Lösungen mit einer Laufzeit von 0,00 Sekunden (auch unter Python) dabei sind. Wie geht denn sowas...?
EDIT2: 0,03 Sekunden sind auch noch relativ leicht machbar...
@hulkhomer: In deinem Code sind zuviele Dinge ausprogrammiert, die Python intern schon mit optimiertem Code in C für dich löst. Es ist bezogen auf Laufzeit und Korrektheit meistens besser, das Rad in solchen Fällen nicht neu zu erfinden, sondern stattdessen diese bereits vorhandene Funktionalität geschickt auszunutzen. Ich denke auch, dass du schneller unterwegs bist, wenn mehr auf Iteratoren arbeitest, weil du dann z.B. die Ausgabe der Ergebnisse in einem Rutsch mittels ``.join()`` erledigen könntest.
Vielleicht mal als Denkanstoß: Die Umkehrung eins Strings kann man direkt über Slicing durchführen lassen ohne die Verwendung einer neuen Liste. Das wurde ja schon gezeigt. Und wenn du dann mit einbeziehst, dass die am Ende stehenden Nullen durch die Umkehrung an den Anfang rutschen und wiederum am Anfang stehende Nullen durch eine ``int``-Umwandung gekillt werden, dann sind das schon zwei solcher Punkte, wo Python dir Arbeit abnehmen kann.
snafu hat geschrieben:
EDIT: Wobei ich gerade sehe, dass etliche Lösungen mit einer Laufzeit von 0,00 Sekunden (auch unter Python) dabei sind. Wie geht denn sowas...?
Die Zeitmessung auf SPOJ ist etwas ... eigenwillig. Das schwankt schon bei identischem Code bei wiederholtem Einsenden. Und wenn zwischenzeitlich die Infrastruktur bei SPOJ umgebaut worden ist, werden natürlich Äpfel mit Birnen vergleichen. Code, den ich vor 2 Jahren doert mit 0.0 sec laufen lassen konnte, läuft heute (bei identischem Code) auch 0.05 sec. Die Ergebnisse, die heute als Python 2.7-Submission auf SPOJ angezeigt werden sind tatsächlich mal Python 2.5 oder 2.6 gewesen - das Problem "ADDREV" ist seit 2004 online
#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import print_function
from platform import python_version_tuple as version
if int(version()[0]) < 3:
input = raw_input
def add_reversed(values_str):
return str(sum(map(lambda x: int(x[::-1]), values_str)))[::-1]
if __name__ == "__main__":
collector = []
for _ in range(int(input("number of cases: "))):
collector.append(int(add_reversed(input("reversed numbers: ").split())))
print("".join(["%d\n" % item for item in collector]))
Erledigt, 0.07s.
Zuletzt geändert von darktrym am Montag 22. Dezember 2014, 17:04, insgesamt 1-mal geändert.
„gcc finds bugs in Linux, NetBSD finds bugs in gcc.“[Michael Dexter, Systems 2008] Bitbucket, Github
Das wird nicht nur von SPOJ als Ausgabe ”interpretiert”, das *ist* Ausgabe. Das ist etwas das auf der Standardausgabe ausgegeben wird und vom empfangenen Programm nicht unterscheidbar ist von den Ergebnissen die auch darüber ausgegeben werden.
Genau danach hab ich ja gesucht wie denn die Auswertung stattfindet, offensichtlich stdin/stdout, nur ist das nirgends spezifiziert.
Das macht auch die Zeitmessung völlig sinnlos, weil schon der zus. Import aus Platform Zeit kostet wie auch Funktionen, sprich hier frickelt man fleißig vor sich hin nur um nicht im unteren Feld zu liegen.
Schaut man sich dann die Beispiele an, matchen garantiert keine 10% der Programme mit dem Ausgabeformat. Schon die Leerzeile ist irreführend, normalerweise würde man eine Funktionssignatur erwarten statt einer widersprüchlichen Beschreibung(schon die Beispielausgabe widerspricht der Beschreibung).
„gcc finds bugs in Linux, NetBSD finds bugs in gcc.“[Michael Dexter, Systems 2008] Bitbucket, Github
darktrym hat geschrieben:Genau danach hab ich ja gesucht wie denn die Auswertung stattfindet, offensichtlich stdin/stdout, nur ist das nirgends spezifiziert.
Das ist doch wirklich offensichtlich. Außerdem gibt es zu jeder Aufgabe eine Beispielein- und ausgabe.
darktrym hat geschrieben:Das macht auch die Zeitmessung völlig sinnlos, weil schon der zus. Import aus Platform Zeit kostet wie auch Funktionen, sprich hier frickelt man fleißig vor sich hin nur um nicht im unteren Feld zu liegen.
Es geht nicht vorrangig um die schnellste Zeit, sondern um das finden einer Lösung. Die Dauer der Berechnung hängt eh von vielen Faktoren ab. Anzahl der aktiven Benutzer, Updates und wahrscheinlich von einem bellenden Hund in Sibirien.
Lies doch mal was ich geschrieben habe. Die Ausgabe ist nicht spezifiziert weil die dem Beispiel widerspricht. Ist ja nicht zuviel verlangt, den Teil der Ein- und Ausgabe hervorzuheben und die Hinweiswörter und Leerzeilen davon zu trennen. Wozu gibts denn HTML Tags?
Wäre dem so, würde der Punkt Best Solution nicht Zeit, Alter und Speicherverbauch als Metrik nutzen. Im Übrigen reichen die 0.06 nicht aus um unter den 800 besten zu landen. Einen Mehrwert hätte das ganze wenn man den Bescheid bekäme, wie denn einige getrickst haben. Es tauchen ja teilweise Speicherverbrauchszahlen von über 30MB auf!
def add_reversed(values_str):
return str(int(values_str[0][::-1]) + int(values_str[1][::-1]))[::-1]
collector = []
for _ in xrange(int(raw_input(""))):
collector.append(int(add_reversed(raw_input("").split())))
print "\n".join([str(item) for item in collector])
Damit sind es immer noch 0.04s!
Zuletzt geändert von darktrym am Montag 22. Dezember 2014, 22:47, insgesamt 1-mal geändert.
„gcc finds bugs in Linux, NetBSD finds bugs in gcc.“[Michael Dexter, Systems 2008] Bitbucket, Github
@darktrym: Heulst Du jetzt echt rum weil Du die Beispiele falsch gelesen hast? Klar gibt es HTML-Tags, es gibt auch auch so'ne graue Masse zwischen den Ohren. Die braucht man zum lösen der Aufgaben sowieso schon, also kann man die auch auf die gezeigten Beispieldaten anwenden.
Wenn ich eine Aufgabe stelle dann schaffe es auch Beispiele zu liefern die nicht der Beschreibung widersprechen. Man braucht keine Intelligenzbestie zu sein um einfach mal die Leerzeilen und Sample Input, Output weglassen und trotzdem bleibt der Kontext erhalten.
Wenn der Parser sich an zusätzlichen Zeichen stört und korrekte Ergebnisse verwirft, ist das dann ärgerlich.
„gcc finds bugs in Linux, NetBSD finds bugs in gcc.“[Michael Dexter, Systems 2008] Bitbucket, Github
@darktrym: Man braucht auch keine Intelligenzbestie zu sein um sich denken zu können das 'sample input:' und 'sample output:' nicht zu den Ein- und Ausgaben gehören. Im Gegenteil. Ich wäre nie auf die Idee gekommen *das* das zu den Ein- und Ausgabedaten gehört.
@darktrym: Du solltest dich vielleicht mal mit dem Stichwort ``yield`` in Bezug auf Generator-Funktionen beschäftigen. Ich benutze eine solche Funktion, um die einzelnen Ergebnisse zu errechnen. Es gibt zudem noch eine ``main()``-Funktion, welche die Eingabe ein bißchen vorbereitet und die Ergebnisse des Generators ausgibt. Wie gesagt: Ist offenbar in 0,02 Sekunden möglich und beinhaltet sogar nen Import.
DaftWullie hat geschrieben:Die Zeitmessung auf SPOJ ist etwas ... eigenwillig.
In der Tat. Aus Neugierde habe ich eine einfache Lösung hochgeladen, die mit 0,06 Sekunden durchlief. Anschließend habe ich etwas optimiert, so dass es knapp doppelt so schnell lief, jedenfalls bei mir lokal. Freudig hochgeladen und — langsamer ...
darktrym hat geschrieben:Wäre dem so, würde der Punkt Best Solution nicht Zeit, Alter und Speicherverbauch als Metrik nutzen. Im Übrigen reichen die 0.06 nicht aus um unter den 800 besten zu landen.
Mit den Zeiten kann die Komplexität und damit auch die Qualität des eingesetzten Algorithmus in etwa abgeschätzt werden. Es gibt eben kluge Lösungen die viele Nicht-Lösungen bei der Berechnung ausschließen und nahe an der optimalen Komplexität liegen und schlechte Lösungen, welche mittels Brute-Force alles durchrechnen. Wer noch an hundertstel Sekunden optimieren möchte, der kann das natürlich tun.
darktrym hat geschrieben:Wenn ich eine Aufgabe stelle dann schaffe es auch Beispiele zu liefern die nicht der Beschreibung widersprechen. Man braucht keine Intelligenzbestie zu sein um einfach mal die Leerzeilen und Sample Input, Output weglassen und trotzdem bleibt der Kontext erhalten.
Dir ist aber klar, was "sample input" und "sample input" übersetzt heißen? Ich käme nie auf den Gedanken, dass "Beispieleingabe" und "Beispielausgabe" Teil der Kommunikation sein sollte.
