cantorsche paarungsfunktion

[feuervogel]

hallihallo!

wer nicht weiß, was die überschrift bedeutet, lese hier:

http://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion

oder meine erklärung: es geht darum einem paar von zahlen eine zahl zuzuordnen. der trick dabei ist, dass diese zahl eindeutig ist, also kein unterschiedliches zahlenpaar hat genau die gleiche zugeordnete zahl. (0,1) und (1,0) sind z.b. unterschiedlich, weil die reihenfolge auch eine rolle spielt.

man kann zudem auch von dieser zahl auf das paar zurückschließen.

dadurch kann man in einer matrix die werte nicht mehr mit $m[ $zeile ][ $spalte] oder so speichern, sondern eleganter, in dem man nur noch ein eindimensionales array hat.

dazu habe ich folgende klasse geschrieben und denke, sie wird einigen menschen nützlich sein (achtung, ist PHP5):


class Cantor {

public function compute( $x , $y ) {

return 0.5 * ($x + $y) * ($x + $y + 1) + $y;

}

public function computeX( $z ) {

$j = floor( -0.5 + sqrt( 0.25 + 2 * $z ) );

return $j - $this->computeY( $z );

}

public function computeY( $z ) {

$j = floor( -0.5 + sqrt( 0.25 + 2 * $z ) );

return $z - $this->f( $j );

}

private function f( $w ) {

return 0.5 * $w * ($w + 1);

}

}


so. weil ich für so nen schnickschnack nicht rechenzeit verschwenden will, sollte das schnell gehen. ich habe die in meinen augen schnellste version geschrieben, die möglich ist...oder? findet jemand eine schnellere? die genauen regeln zur berechnung finden sich im wikipedia-artikel (s.o.)

zum testen:

$c = new Cantor();

for( $i = 0; $i < 1000; $i++ ) {

for( $j = 0; $j < 1000; $j ++ ) {

$e = $c->compute( $i , $j );
$x = $c->computeX( $e );
$y = $c->computeY( $e );

}

}

braucht auf meinem system unter 17 sekunden. amd 2400+ mit 512 mb ram, also nichts berauschendes. würde mich freuen, wenn jemand eine bessere lösung findet.

ansonsten: macht damit, was ihr wollt, ich werds morgen dokumentieren, bin jetzt zu müde...

[Opendix]

hmm... das ganze hört sich noch ziemlich interssant an :)


nun, ich habe nur eine frage: warum machst du eine privat function f?





wäre es nicht sinvoller (ob es schneller ist weis ich nicht) einfach statt:





return $z - $this->f($j);





einfach gleich so:





return $z - 0.5 * $j * ($j+1);





zu machen da du diese funktion ja doch nur aus einem teil der klasse aufrufst und
von aussen eh nicht darauf zugegriffen werden kann?


werde das dann heute abend mal noch testen :)

[feuervogel]

hm, also einerseits hatte ich versucht, die rückrechnung 1:1 aus der wikipedia abzubilden, denn dort werden zwei hilfsfunktionen benutzt, darunter auch f, siehe hier:

http://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion#Formale_Definition

f(w). dort wird gesagt, man sollte das größte $j finden, für das gilt: f($j) <= $z.

das hatte ich zuerst mit einer while-schleife gelöst, die das j so lange hochzählt, bis f( $j ) > $z ist und dann $j-1 nimmt, da dann f( $j-1 ) <= $z ist. dadurch kam die funktion f an mehr als einer stelle vor (genauer gesagt an dreien) und es wäre sinnlos gewesen, den code direkt hinzuschreiben. funktionen dienen ja eben dazu, um code, den man öfters braucht, zusammenzufassen.

andererseits wird der compiler oder sonst eine zwischenstufe vor dem ausführen vom script sicher genau das machen (wenn er klug ist), und wenn ich das script ein mal aufrufe und 1.000.000 mal ausführe, würde ich ihm jetzt eine klitzekleine arbeit abnehmen, die zwar nicht wirklich ins gewicht fallen würde, aber hier natürlich eleganter wäre, da ich ja nun den code aus f($z) nur noch ein mal aufrufe.

achja, mit der while-schleife hat das berechnen von 10.000 paaren mit rückrechnen etwa 30 sekunden gedauert - ohne, bei 250.000 paaren noch unter 5 sekunden. da sieht man mal, was schleifen ausmachen...

vielen dank für den tipp, die klasse sieht nun so aus:


class Cantor {

public function compute( $x , $y ) {

return 0.5 * ($x + $y) * ($x + $y + 1) + $y;

}

public function computeX( $z ) {

$j = floor( -0.5 + sqrt( 0.25 + 2 * $z ) );

return $j - $this->computeY( $z );

}

public function computeY( $z ) {

$j = floor( -0.5 + sqrt( 0.25 + 2 * $z ) );

return $z - 0.5 * $j * ($j + 1);

}

}

[feuervogel]

nachtrag: der gleiche algorithmus in java braucht für 100.000.000 berechnungen gut 45 sekunden auf meinem rechner.