Vorschläge für "normale" Zahlenverteilungen für Programmierwettbewerbe



  • Wenn ich im Rahmen eines Programmierwettbewerbs programmierte Funktionen hinsichtlich ihres Laufzeitverhaltens vergleichen will, werfe ich zum Beispiel 10000 Eingabezahlen in die zu messende Funktion und prüfe die 10000 Ergebnisse und messe die verbrauchte Zeit.

    Sagen wir mal, die Aufgabe wäre

    Aufgabe schrieb:

    Bauen Sie eine Funktion

    bool istPrimzahl(UInt32 n);
    

    Wenn jetzt jemand eine Funktion baut, die bei Eingaben n<1000 total Gas gibt, aber dann bei größeren Zahlen total abschneckt, ist das natürlich nicht so klasse.
    Aber wenn jemand eine Funktion baut, die auf allen möglichen 4.3 Millarden möglichen Eingaben gleich schnell ist aber bei kleinen keinen Speedbooster hat, ist das auch nicht so klasse.

    Bei sowas würde ich ungern einfach nur urand32() werfen, sondern eine Verteilung, wo die kleinen Zahlen schon häufiger vorkommen. Sozusagen, wie im richtigen Programmiererleben. Viele Funktionen werden für kleine Werte einfach öfter aufgerufen als für große. Aber große kommen auch manchmal vor.

    Um zu den Primzahlen zurückzukommen, wenn jemand einen schuckeligen SPRP-Test baut, ist der praktisch für alle Eingaben gut. Macht er ein leckeres

    if(n<magicnumber)
       return istPrimzahlFuerKleineZahlen(n);
    else
       return schnuckeligerSPRPTest(n);
    

    gewinnt er natürlich. Aber auf die Idee kommen alle, die den schnuckeligen SPRP-Test ergooglen können.
    Ob nun magicnumer=1000 oder magicnumber=2000 macht keinen meßbaren Unterschied mehr wenn ich über alle möglichen Eingaben mittle. Wenn ich nur über [1;5000] mittle aber sehr wohl. Würde ich eine Verteilung wählen, die kleine Zahlen bevorzugt, wäre es vielleicht möglich, ohne genaues vorheriges Wissen der Problemstellung dafür sorgen zuz können, daß Leute, die die magicnumbers nicht nur raten, sondern ausmessen, auch messbar gewinnen.

    Was könnten denn sinnvolle Verteilungen für sowas sein und warum?



  • Die sinnvollste Verteilung ist IMO die, die am ehesten dem realen Einsatz entspricht. Und der ist je nach Aufgabe der Funktion anders, je nach Programm in dem die Funktion dann wirklich verwendet etc.

    Kurz: das kann man so pauschal nicht sagen 🙂



  • hustbaer schrieb:

    Kurz: das kann man so pauschal nicht sagen 🙂

    Ja.
    Deswegen mag ich Vorschläge sammeln und je nach Aufgabe die irgendwie passendste Verteilung wählen. Ich hoffe, daß aus diesem Sammelthread dann so 5 oder 6 "gelegentlich sinnvolle" Verteilungen rauskommen. Bei einer Aufgabenstellung würde ich als Teil der Aufgabe auch die Verteilung nennen und damit im Gegensatz zu anderen Wettbewerben erst möglich machen, daß man daheim schon messen kann. Das hat mich an Wettbewerben, an denen ich teilnahm immer sehr gestört, daß ich raten mußte, über welche Eingabebereiche und Verteilungen gemessen wurde, die niemals vorher gesagt wurden. Da war dann die halbe Note das Raten und ein weiteres Viertel, bisher keinen schlechten Eindruck gemacht zu haben.



  • Dem "kleine zahlen vor" halte ich entgegen, dass es oft so ist, wie eben dein beispiel zeigt, das kleine zahlen keine herausforderung sind. Ein contest sollte doch problemstellungen aufwerfen die zum nachdenken sind und nicht einfach nur 08/15 code monkey arbeit erfordern nach 5min googlen.

    Ich wuerde an deiner stelle also einfach komplett ausschliessen, dass zahlen in einem bereich getestet werden der niemanden interesiert weil es eben eh jeder fast gleich implementiert.

    Natuerlich kann es mal nen fall geben bei dem man unglaublich schnell immer wieder 8zahlen sortiert, oder primes bis 16bit testet, dann sollte man das beim kontest auch explizit als ziel setzen.
    Ansonsten werden wohl die meisten programmierer eher auf die O(..)-performance schauen und da ignoriert man die fixkosten bei kleinstzahlen.



  • volkard schrieb:

    Bei einer Aufgabenstellung würde ich als Teil der Aufgabe auch die Verteilung nennen und damit im Gegensatz zu anderen Wettbewerben erst möglich machen, daß man daheim schon messen kann.

    Oder einen Algorithmus zur Erzeugung der Eingabezahlen vorgeben. Dann muß daheim gemessen werden. 🙂



  • Kleine Zahlen oefter als grosse? Nimm doch einfach eine Exponentialverteilung 😕


  • Mod

    Wobei kleine Zahlen höchst unpassend für das gegebene Beispiel 'Primzahltest' sind, schließlich liegt der normale Anwendungsfall dort bei riesigen Zahlen.



  • mach doch jeweils einen Test für kleine und große zahlen und gewichte die dann entsprechend.



  • Also ich könnte mir vorstellen dass durchaus ein paar der einfachsten Verteilungen oft Sinn machen.

    * gleichverteilt
    * normalverteilt
    * 1/n
    * 1/n², 1/n³, ...
    * 1/k^n



  • Wie wäre es, mit einer Reyleigh-Verteilung?

    http://en.wikipedia.org/wiki/Rayleigh_distribution

    Besonders der abschnitt 'Generating Rayleigh-distributed random variates'.



  • volkard schrieb:

    Ob nun magicnumer=1000 oder magicnumber=2000 macht keinen meßbaren Unterschied mehr wenn ich über alle möglichen Eingaben mittle. Wenn ich nur über [1;5000] mittle aber sehr wohl. Würde ich eine Verteilung wählen, die kleine Zahlen bevorzugt, wäre es vielleicht möglich, ohne genaues vorheriges Wissen der Problemstellung dafür sorgen zuz können, daß Leute, die die magicnumbers nicht nur raten, sondern ausmessen, auch messbar gewinnen.

    Was könnten denn sinnvolle Verteilungen für sowas sein und warum?

    Wenn du die Verteilung nicht in der Aufgabe bekannt gibst, dann kann man die magicnumber nur raten. Wenn du sie angibst, ist die genaue Verteilung egal. Sag halt einfach z.b. 100 x ( 0 - 1000 ); 100 x ( 1000 - 1000000 ); 100 x ( 1000000 - 1000000000 ) oder gib eine Liste mit n Zahlen vor. Wenn fuer alle gleiche Bedingungen herrschen gibt es keine Anspruch an die Guete der Verteilung ausser die von dir definierten. f'`8k

    Gruß, TGGC (Was Gamestar sagt...)



  • bool istPrimzahl(UInt32 n);
    

    Du wirfst also 10.000 Zufallszahlen in einem bestimmten Intervall auf diese Funktion. Nun nutze ich in meiner Funktion eine Variante des Siebes von Eratosthenes. Ein Test von n=12345 kann alle weiteren Funktionsaufrufe mit kleineren n beschleunigen, in dem ich mir einfach Zwischenergebnisse merke.

    Was ich damit sagen will: 10.000 mal die Funktion mit Zufallszahlen aufzurufen und die Zeit messen, ist nicht wirklich ein geeignetes Kriterium. Natuerlich kann man durch Regeln beim Wettbewerb ausschliessen, doch die sind manchmal recht einschraenkend und sollten gut ueberlegt sein. Beispiel: Zu starke Restriktionen haben eine gutes Programm fuer die Loesung des Problems der (begrenzeten) exakten Summe verhindert.



  • TGGC schrieb:

    Wenn du die Verteilung nicht in der Aufgabe bekannt gibst, dann kann man die magicnumber nur raten.

    Ich will die Verteilung angeben.

    TGGC schrieb:

    Wenn du sie angibst, ist die genaue Verteilung egal. Sag halt einfach z.b. 100 x ( 0 - 1000 ); 100 x ( 1000 - 1000000 ); 100 x ( 1000000 - 1000000000 )

    Ja, die ist nett. Die kann man auch nach Blue-Tiger stetig machen. x=untergrenze*pow(basis,zufall) oder sowas.

    TGGC schrieb:

    oder gib eine Liste mit n Zahlen vor.

    Dann kriege ich nur vorausberechnete Tabellen, fürchte ich.
    Stattdessen mag ich die erzeugende Funktion angeben und nur den ramdom-seed beim Messen austauschen.



  • Mehrere Bereiche machen und die dann zu einem vermischen, damit es keine Reihenfolge gibt.



  • knivil schrieb:

    bool istPrimzahl(UInt32 n);
    

    Du wirfst also 10.000 Zufallszahlen in einem bestimmten Intervall auf diese Funktion. Nun nutze ich in meiner Funktion eine Variante des Siebes von Eratosthenes. Ein Test von n=12345 kann alle weiteren Funktionsaufrufe mit kleineren n beschleunigen, in dem ich mir einfach Zwischenergebnisse merke.

    Ja, aber das sind ja eh nur Tricks bei kleinen Zahlen. Die Plätze 10 bis 15 mögen sich um sowas streiten. Die vorderen Plätze entscheiden sich im Bereich 2^63 bis 2^64, wo die kleinen schon lange raus sind. Das stelle ich mir so vor, daß ich unter Beibehaltung zum Beispiel der Exponentialverteilung zuerst nur 100-1000 werfe, dann 100-10000, dann 100-100000 und so fort und sukzessive die rauswerfe, die länger als 10 Minuten brauchen bis ich dann zu den elend schnellen komme, die bei 100-2^64 noch unter 10 min brauchen und die sollten normalerweise auch deutliche Unterschiede zeigen. Und in den Bereichen hilft kein caching. Irgendwelche Beschränkungen an den Speicher werde ich auch machen, zum Beispiel max 1G Plattenplatz nach und max 10min für "make learn", max 10M nach und mach 10min für "make build".

    knivil schrieb:

    Was ich damit sagen will: 10.000 mal die Funktion mit Zufallszahlen aufzurufen und die Zeit messen, ist nicht wirklich ein geeignetes Kriterium. Natuerlich kann man durch Regeln beim Wettbewerb ausschliessen, doch die sind manchmal recht einschraenkend und sollten gut ueberlegt sein. Beispiel: Zu starke Restriktionen haben eine gutes Programm fuer die Loesung des Problems der (begrenzeten) exakten Summe verhindert.

    Ja, ich habe mal bei einem Wettbewerb mitgemacht, der alle vorausberechneten Tabellen verboten hatte. Aber hey, die Primzahlen bis 30 für einen Vortest als Tabelle abzulegen ist eine *sehr* gute Idee für alle Größenordnungen. Sowas will ich gar nicht einschränken. Wenn nur die besten Tabellen gewinnen, war die Aufgabenstellung schlecht.

    Gegen caching während des Programmlaufs und Vorausberechnung kleiner Eingabewerte kann ich mich bei 10000 Eingabezahlen nicht generell schützen. Die Aufgabenstellungen müssen halt so sein, daß das nicht enorm viel bringt. Ein kleines "if(n<1000) return precomputed[n];" wird sich wohl stets einschleichen, aber egal, das macht jeder und dann isses wieder fair. Besonder coole Programmierer werden auf diese Kinderkacke normalerweise verzichten, außer natürlich, sie rechnen damit, daß der zweitplazierte für 2^63 bis 2^64 auf den Takt genau gleichschnell ist.

    Ok, ich könnte, wenn ich nur Funktionsaufrufe messen würde und den Code sichten würde, aber das will ich nicht. Ich will, daß alle Sprachen mitspielen können. Und ich will nicht sichten und bewerten müssen, ob was regelgerecht ist. Deswegen auch die Möglichkeit, ein makefile oder -script abzugeben, daß mit "make learn" erstmal checkt, wieviele Kerne da sind und ob DIV 20-mal so langsam wie MUL ist oder nur 10-mal.



  • a) Wo kann ich mich beim Wettbewerb anmelden? 🙂
    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.



  • knivil schrieb:

    z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    das hier ist schneller: http://www.alpertron.com.ar/ECM.HTM
    gib z.b. mal 35742549198872617291353508656626642567 ein.
    ^^38 stellen, mehr als 2^64, unter einer sekunde.
    🙂



  • knivil schrieb:

    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    Pro Zahl, oder? f'`8k

    Autocogito

    Gruß, TGGC (Was Gamestar sagt...)



  • knivil schrieb:

    a) Wo kann ich mich beim Wettbewerb anmelden? 🙂

    Hier. Siehe sig, wenns soweit ist, falls es überhaupt soweit kommt. Aber ich muß mir noch viele Gedanken machen und ich fange auch erst an, wenn ich genug gute Aufgaben habe. So ein Puffer von zwei Jahren schwebt mir vor.

    knivil schrieb:

    b) Du solltest einige gaengige Implementationen vorher mal besichtigen, z.B. msieve. Fuer Zahlen im Bereich von 2^64 braucht es nur wenige Sekunden.

    Lachhaft. 🙂 Wenn die Obergrenze 2^64 ist, gehts Faktorisieren (was deutlich teurer ist als nur Primalität festzustellen) gerne in 1ms. Aber Primzahlen sind ja nur ein Beispiel.

    Ich denke, ich werde auch von Ein- und Ausgabeperformance absehen können, wenn ich den Problemgenerator vorgebe und zum Beispiel als Anfrage nur sende "seed maxwert anzahl" und nur einen Hashwert (normalerweise Summe) der Ausgaben frage. Das Summieren ist aber nur ein Zugeständnis daran, daß manche völlig interesasante Themen recht schnell berechenbar sind und das Programmstarten viel länger dauert als eine einzelne Problemlösung. Bei Sachen wie 9-Live Dreiecke-Rätsel geht die Rechenzeit auch so dermaßen hoch, daß eine Aufgabe pro Programmstart reicht. Vermutlich. Wenn doch mehr als einer eine Lösung in log(n) findet und die Programmstartzeit die Lösezeit überwiegt, müßte ich dann dummerweise diese Aufgabe nochmal starten.

    Ich rechne aber damit, daß viele interessante Probleme so sind, daß sie ruck zuck in wenigen Millisekunden gelöst sind, weshalb ich an die Zeitsumme von 10000 Problemen denke.

    Können Java und Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?



  • volkard schrieb:

    Können Java und Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?

    Java's longs sind 64 bit signed. ausserdem hat Java noch 'ne 'BigInteger' klasse mit dabei.
    🙂


Log in to reply