PIR in python? java works fine

reox 2009-10-20 20:25:40 UTC #1

I programmed a solution for PIR in java and it worked very well. So i tried it in python and im getting a WA! So look at my testcases, everthing working fine:

2
1 1 1 1 1 1
1000 1000 1000 3 4 5
0.1179
1999.9937

i get the same from my java code... so whats wrong? i really got no idea... are they limitations for python with this problem?

numerix 2009-10-20 21:11:53 UTC #2

No, there is nothing special about it.

I'll explain in German (too tired to do in English ...):

Wenn man sich die Laufzeit deiner Java-Lösung ansieht, kann man sehen, dass es deutlich schnellere Lösungen in Java gibt.
Das könnte - muss natürlich nicht - damit zusammenhängen, dass deine Berechnung der Lösung auf zu vielen Berechnungen beruht, die sich reduzieren ließen. Falls dem so ist, könnte das wiederum ein Grund dafür sein, dass deine Python-Lösung nicht für alle Eingabewerte das richtige Ergebnis liefert, bedingt durch die vielen Berechnungen in der Fließkommaarithmetik.

reox 2009-10-20 21:57:05 UTC #3

mhh should i write now german?
also ich hab schon gesehen das die Java sachen die ich geschrieben habe alle sehr lahm sind... keines ist schneller als 0.25se wobei ich glaube das es auch daran liegt das die VM gestartet werden muss? wenn ich das programm an meinem laptop starte (klar ist kein vergleich) rennt es in 0.02sec durch...
Schau dir die submission von TEST an... ich hab sogar die variante aus dem forum hier genommen (also viel anders kann mans net machen, wobei ich equals verwende) aber selbst das braucht 0.25sec!
bei PIR ist das afaik die einzige möglichkeit. Ich verwende die cayey menger determinante zum ausrechnen, sonst könnt man das noch mit Vektoren machen aber ich glaube da rechne ich mehr als die determinate zu berechnen....
Die Ergebnisse die ich bei den testcases reinschmeise, auch irgend was anderes, sind bei java und python immer die gleichen, bis auf sehr kleine und große zahlen wo die potenz bei java nur mit E und bei python mit +E angezeigt wird...

ich werd das ganze mal noch irgendwie anders testen, mal wieder meine C kenntnisse auskramen, wenns da auch nicht geht kA

numerix 2009-10-21 06:04:05 UTC #4

Sicher, die VM braucht ihre Zeit zum Anlaufen, das ist keine Frage. Aber dennoch bleibt ja eine Differenz von 0.07 s zwischen deiner Java-Lösung und den schnellsten AC Java Lösungen. Das kann am Algorithmus liegen, muss aber nicht. Auffällig ist auch, dass deine Lösung weniger Speicher benötigt - das dürfte darauf hindeuten, dass die meisten anderen noch irgendwelche Pakete mit einbinden; ob die dann für die bessere Laufzeit sorgen - keine Ahnung.

Meine (Python-)Lösung ist vektorbasiert und ganz geradlinig.