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



  • 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.
    🙂



  • ;fricky schrieb:

    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.
    🙂

    Wobei BigInteger eine Krücke ist und keinesfalls mit anderen Mathematik-Bibliotheken mithalten kann.

    MfG SideWinder



  • SideWinder schrieb:

    Wobei BigInteger eine Krücke ist und keinesfalls mit anderen Mathematik-Bibliotheken mithalten kann.

    das ist klar, geschwindigkeitsmässig kann's mit reinen C-implementationen wie GMP und 'bignum' leider nicht mithalten. primzahlenforscher werden mit 'BigInteger' wohl nicht glücklich werden.
    🙂



  • ;fricky schrieb:

    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.
    🙂

    Ok, also müßte ich auf 63 Bit runter, um bei sowas Java zuzulassen.



  • volkard schrieb:

    Ok, also müßte ich auf 63 Bit runter, um bei sowas Java zuzulassen.

    und leute mit alten 32-bit CPUs haben auch pech - *fg*
    🙂



  • 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.

    Wie kommst du darauf? Wie hast du die Performance gemessen. Welche Hardware ist hinter der Seite ... Naja, EMC soll etwa genauso gut wie das Quadratische Sieb sein.

    Beispiel msieve:

    Mon Nov  9 13:31:01 2009  Msieve v. 1.43
    Mon Nov  9 13:31:01 2009  random seeds: 324bc4df a040795f
    Mon Nov  9 13:31:01 2009  factoring 1427247692705959881058285969449495136382746619 (46 digits)
    Mon Nov  9 13:31:01 2009  prp46 factor: 1427247692705959881058285969449495136382746619
    Mon Nov  9 13:31:01 2009  elapsed time 00:00:00
    

    Also bei 0sec kann man noch nicht wirklich vergleichen.

    Haskell eigetlich mit 64-Bit-Zahlen natürlich umgehen?

    Fuer grosse Zahlen nutzt GHC die gmp-Library.


Anmelden zum Antworten