SPOJ 42 - Gelöst, aber langsam

[hulkhomer]

Danke für eure Antworten! Das mit dem slicing "von hinten" habe ich versucht, war aber wohl zu doof. Und dass man dann die führenden Nullen mit int() wegmacht leuchtet ein. Das hätte mir auch einfallen können

Wie ich sehe, gibt es noch viel zu lernen. Aber dafür ist ja jetzt auch genug Zeit.

edit: Bin jetzt bei 0,06s. Das reicht mir

[DaftWullie]

Es tauchen ja teilweise Speicherverbrauchszahlen von über 30MB auf!

Die Speicherverbräuche vom 30 MB weisen darauf hin, dass der Einsender psyco benutzt hat. Zu einer Zeit als das bei SPOJ noch funktioniert hat.

SPOJ Probleme weisen eine sehr große Schwankungsbreite auf. Sowohl im Hinblick auf die Genauigkeit der Aufgabenstellung als auch im Hinblick auf die Schwierigkeit. Und auf die Lösbarkeit mit Python. Tendenziell sind neuere Probleme eher drauf abgestimmt, dass ein guter Algorithmus auch in Python zum Erfolg führt. Bei den älteren Problemen war Python oft durch riesige Ein- / Ausgabemengen benachteiligt, was zu vielen - IMHO "unpythonischen" - Optimierungs-Notwendigkeiten geführt hatte.

[hulkhomer]

Ich häng das mal hier dran, damit ich nicht ständig neue Themen aufmache.

Meine Lösung wird akzeptiert, ist aber wieder langsamer. product_sum in eine Liste speichern und dann die items ausgeben habe ich versucht, ist auch nicht schneller. Liegt es an der häufigen Umformung in int()?

@sirius3 Danke für den Hinweis mit den list-comprehensions!

Code: Alles auswählen

# SPOJ 1025 Fashion Shows
# http://www.spoj.com/problems/FASHION/

t = input()         
output = ""
for i in range(int(t)):
    n = input()     
    hot_m_sort = sorted([int(x) for x in input().split()])
    hot_f_sort = sorted([int(x) for x in input().split()])
    product_sum = 0
    for k in range(int(n)):
        product_sum += hot_m_sort[k] * hot_f_sort[k]
    output += str(product_sum)+"\n"
print(output)

[BlackJack]

@hulkhomer: Keine Ahnung welche Auswirkungen das auf die Geschwindigkeit hat, aber das ``for k in range(int(n)):`` ist in Python eigentlich Igitt. Dafür gibt es `zip()` beziehungsweise `itertools.izip()`. Und warum verwendest Du für `product_sum()` nicht die `sum()`-Funktion? Die kennst Du doch bereits.

Bitte nicht wiederholtes ``+=`` mit Zeichenketten in einer Schleife. Auch wenn Du das keinen Zeitunterschied messen kannst, wenn der da ist, dann wird der schnell sehr heftig, denn die Sprache garantiert da nun mal nicht dass das effizient gemacht wird/werden kann. Der Trick den aktuelle CPython-Implementierungen da machen funktioniert so nur bei der Art wie CPython Objekte im Speicher verwaltet. Bei Jython, IronPython, oder anderen alternativen Implementierungen geht das nicht und auch bei CPython ist nicht sicher das das in alle Zukunft gehen wird. Ein (Traum)Ziel ist ja bei CPython da „global interpreter lock” (GIL) loszuwerden, und dann steht wahrscheinlich auch die Speicherverwaltung zur Disposition.

Ein Funktion kann eventuell helfen. Also einfach das ganze in eine `main()`-Funktion stecken. Lokale Namen in Funktionen können nämlich zur Laufzeit schneller aufgelöst werden als welche auf Modulebene.

[hulkhomer]

@BlackJack Ich habe das so verstanden, dass sum() nur auf einer Liste funktioniert. Hier muss ich ja die jeweils n-ten Einträge multiplizieren und davon die Summe bilden. Damit sum() funktioniert, müsste ich (nach meinem Verständnis) die Produkte in eine Liste parken und diese dann aufsummieren.

Und um ehrlich zu sein, habe ich keine Ahnung wie ich (schnell) aus

Code: Alles auswählen

liste_von_tupeln = [(1,2), (3,4)...]

die Produkte von den einzelnen Tupeln finde. Zumindest nicht mit wenigen Zeilen.

Der "Trick" mit main(), hat was gebracht, ich bin nicht mehr letzter

[Sirius3]

@hulkhomer: Tuple multiplizieren und aufsummieren

Code: Alles auswählen

product_sum = sum(m*k for m,k in zip(hot_m_sort, hot_k_sort))

[hulkhomer]

@sirius3 Das geht aber anscheinend nur, wenn die Einträge in der Liste Tupel sind, oder? Habs grade mit Liste aus Listen versucht und das ging nicht.

[BlackJack]

@hulkhomer: Welche Einträge in welcher Liste? In `hot_m_sort` und `hot_k_sort` müssen Einzelwerte stehen. `zip()` erzeugt dann Tupel aus den jeweils ”parallelen” Einträgen, und der Generatorausdruck multipliziert die beiden Elemente jedes Tupels, und `sum()` summiert das dann auf.

Edit (ungetestet):

Code: Alles auswählen

results = []
for _ in range(int(input())):
    input()  # Skip number of values.
    results.append(
        sum(
            str(m * f)
            for m, f in zip(
                sorted(map(int, input().split())),
                sorted(map(int, input().split()))
            )
        )
    )
print('\n'.join(results))

[hulkhomer]

Habs verstanden, vielen Dank! Es geht auch mit Listen in Listen. Nur die Anzahl der Einträge muss natürlich passen Wenn man mal die Fehlermeldung aufmerksam lesen würde...

Code: Alles auswählen

>>> a = [[1,2], [3,4]]
>>> b = [m*f for m,f in a]
>>> b
[2, 12]
>>> b = [x*y*z for x,y,z in a]
Traceback (most recent call last):
  File "<pyshell#104>", line 1, in <module>
    b = [x*y*z for x,y,z in a]
  File "<pyshell#104>", line 1, in <listcomp>
    b = [x*y*z for x,y,z in a]
ValueError: need more than 2 values to unpack
>>> 

Langsam wirds schon was mit mir und Python