Binomialkoeffizent ("n über k") effizient berechnen

[DaftWullie]

Hallo,

ich lese nun schon seit einiger Zeit in diesem Forum mit. Und das mit großem Vergnügen.

Jetzt bin ich an einem Punkt, an dem ich das Gefühl habe, ohne Eure Unterstützung nicht weiterzukommen. Es geht um die Berechnung des Binomialkoeffizenten, die in einer SPOJ-Aufgabe erforderlich ist (Marbles).

Die Berechnung in Python ist nicht schwierig, und ich finde keine offensichtliche Ineffizienz in meinem Code. Bei SPOJ erhalte ich aber immer nur eine Laufzeitüberschreitung.

Wie kann ich den Code beschleunigen?

Code der Berechnungsfunktion, Python 2.5, nur Standardbibliothek

Code: Alles auswählen

def choose(n, k):
    if not 0 <= k <= n:
        return 0
    if k == 0 or k == n:
        return 1
    if 2 * k > n:
        k = n -k
    ntok = 1
    for t in xrange(min(k, n-k)):
        ntok = ntok * (n-t) /(t+1)
    return ntok

Gruß
Daft

[BlackJack]

@DaftWullie: Du könntest als erstes überflüssige Bedingungen rauswerfen. Das 1≤k≤n ist, wird in der Aufgabenstellung schon garantiert.

Als nächstes ist die Frage ob ``min(k, n - k)`` wirklich was bringt wenn Du vorher schon `k` entsprechend veränderst wenn 2k>n gilt.

Bei solchem Code sollte das `psyco`-Modul auch helfen. Das ist zwar nicht in der Standardbibliothek, aber bei SPOJ IIRC installiert.

[DaftWullie]

@BlackJack: Danke für die superschnelle Antwort!

Den Psyco-Kniff kannte ich schon, der hatte leider nicht genutzt - hätte ich natürlich erwähnen sollen.

Die Bedingungen sind in der Tat redundant. Allerdings wird ja gemäß Aufgabenstellung die Berechnung maximal 100mal aufgerufen, und die Bedingungen nur 1* je Funktionsaufruf ausgewertet - da sollte also nicht soo viel Zeit "draufgehen". Ich habe den Code angepasst, und leider immer noch "Time Limit Exceeded".

Code: Alles auswählen

def choose(n, k):
    if k == 0 or k == n:
        return 1
    if 2 * k > n:
        k = n -k
    ntok = 1
    for t in xrange(k):
        ntok = ntok * (n-t) /(t+1)
    return ntok

[BlackJack]

@DaftWullie: Hast Du das Ergebnis von n über k mal mit dem Beispiel Ein- und Ausgabewerten verglichen‽

[BlackJack]

@DaftWullie: Ich habe das mal gelöst und meine `choose()`-Funktion sieht Deiner sehr ähnlich. Das lief gleich beim ersten Anlauf in 0.04 Sekunden bei SPOJ mit dem korrekten Ergebnis. Also sehr deutlich unter der 1s Grenze der Aufgabe.

Was immer Dein Problem ist, muss also ausserhalb von `choose()` liegen. Entweder fütterst Du die Funktion mit falschen Werten, deren Berechnung zu lange dauert; oder Du berechnest ausserhalb der Funktion etwas was zu lange dauert; oder Du hast Dir irgendwie ausserhalb eine Endlosschleife gebastelt, oder etwas anderes was das Programm hängen bleiben lässt.

[DaftWullie]

@DaftWullie: Hast Du das Ergebnis von n über k mal mit dem Beispiel Ein- und Ausgabewerten verglichen‽

Ja hab ich . Ich habe ja auch nicht behauptet, dass n über k unmittelbar die Lösung zur SPOJ Aufgabe ist. Es wird halt benötigt.

Was immer Dein Problem ist, muss also ausserhalb von `choose()` liegen

In der Tat, das stimmt. Ich hab es irgendwie geschafft, den "Standard-Rahmen" den man für jede SPOJ Aufgabe braucht (Input lesen, Elemente verarbeiten, zusammensetzen und ausgeben) so falsch von einer anderen Aufgabe zu kopieren, dass er nicht mehr fertig wurde.

Inzwischen hat SPOJ meine Lösung akzeptiert (0,03 Sekunden), Problem ist gelöst. Danke für die Hilfe!

Daft

P.S.: "Marbles" ist imho kein besonders interessantes SPOJ Problem, jedenfalls nachdem man die Kombinatorik "fertig" hat.