Angesichts einer Liste von IDs, die nach bestimmten Bedingungen sortiert waren, war es erforderlich, in einem engen Bereich irgendwie übereinzustimmen. Das Extrahieren eines Elements aus dem Array ist O (n). Wenn es jedoch auf die Elemente im festen Bereich vom Ende oder vom Ende beschränkt ist, ist es O (1). Wenn Sie also die Elemente extrahieren, während Sie von hinten übereinstimmen, ist O (n) Sie sollten in der Lage sein, mit n) übereinzustimmen.
Es ist überhaupt nicht schwierig, und wenn Sie es in Python schreiben, wird es so sein. Es ist schön, list.pop () vom Ende indizieren zu lassen (-1 für das letzte Element).
matching.py
# coding: utf-8
def match(seq, r=100):
from random import randint
#Wenn Sie nicht möchten, dass die Elemente am Anfang Boccia werden, wenn es eine ungerade Zahl gibt, die dahinter liegenden
#Entfernen Sie das Element und halten Sie es gleichmäßig.
while len(seq) >= 2:
#Wenn das Argument weggelassen wird, wird das letzte Element extrahiert..
a = seq.pop()
#Wählen Sie das Ende des Arrays zufällig aus und extrahieren Sie es im Bereich von r.
b = seq.pop(-randint(1, min(r, len(seq))))
yield a, b
def test(n, r):
for a, b in match(range(n), r):
#print a, b
assert a - b < 20
import sys
test(int(sys.argv[1]), 10)
Sobald ich die Anforderungen hörte, kam ich auf diesen Algorithmus und versprach, dass er "einfach und leicht" sei, aber in Bezug auf PHP überhaupt nicht einfach. Ich kann das Element des angegebenen Schlüssels aus dem assoziativen Array entfernen, aber ich kann es nicht finden, egal wie oft ich nach einer Funktion suche, die das Element in der Mitte (füllt das Ende) aus dem Array abruft.
Nachdem ich das Array-Kapitel der PHP-Referenz einige zehn Minuten lang gelesen hatte, gab es kein Äquivalent zu list.pop (). Wenn Sie das Array einmal ausschneiden und verketten, können Sie etwas Ähnliches tun. Da die Verkettungskosten des Arrays jedoch O (n) betragen, wird der Übereinstimmungsalgorithmus zu O (n ^ 2). Am Ende musste ich eine Schleife schreiben, die die Elemente hinter den Elementen verschiebt, die ich nacheinander herausgenommen habe.
In PHP sind Arrays und assoziative Arrays verwirrt, so dass Funktionen vom Typ Array schwer zu verstehen sind, wie mit Schlüsseln umgegangen wird. Sie sind sich vielleicht nicht bewusst, dass die PHP-Entwickler keine so grundlegende Verarbeitung anbieten, weil sie zu verwirrend ist.
Wie im Kommentarbereich erwähnt, konnte ich mit array_splice () das erwartete Verhalten erreichen. Es werden auch Indizes vom Ende mit negativen Zahlen unterstützt. Das Umschreiben des obigen Codes in PHP sieht folgendermaßen aus:
Es scheint jedoch, dass die Ausführungszeit doch nicht O (n) ist Als Rand des Algorithmus beanspruche ich das Recht, PHP nicht als grundlegendes Menschenrecht zu verwenden.
matching.php
<?php
function match($seq, $r=100) {
$res = array();
while (count($seq) >= 2) {
$a = array_pop($seq);
$i = mt_rand(1, min($r, count($seq)));
$b = $seq[count($seq)-$i];
array_splice($seq, -$i, 1);
$res[$a] = $b;
}
return $res;
}
function test($n, $r) {
foreach (match(range(0, $n-1), $r) as $a => $b) {
//printf("%d %d\n", $a, $b);
if ($a - $b >= $r*2) {
error_log("XXX");
}
}
}
test($argv[1], 10);
#Ausführungsergebnis
$ time python matching.py 10000
real 0m0.038s
user 0m0.031s
sys 0m0.006s
$ time python matching.py 20000
real 0m0.043s
user 0m0.035s
sys 0m0.007s
$ time php matching.php 10000
real 0m1.821s
user 0m1.806s
sys 0m0.012s
$ time php matching.php 20000
real 0m11.842s
user 0m11.797s
sys 0m0.041s
Ich dachte, ich könnte es selbst implementieren, aber das war auch schwierig. Ich erinnere mich, aber ich habe das Gefühl, dass CoW aufgetreten ist, als ich die Referenz gezählt habe. Ich denke, das ist der Grund.
Sie können das Array nicht einmal selbst in PHP verarbeiten, um beschissene integrierte Funktionen zu vermeiden. Wenn Sie also ein Array bearbeiten möchten, erstellen Sie eine PHP-Erweiterung und schreiben Sie sie in C. PHP ist eine Vorlagensprache und es ist sicher, Programme in C-Sprache zu schreiben.
matching2.php
<?php
function list_pop(&$seq, $index) {
$n = count($seq);
if ($index < 0)
$index += $n;
$value = $seq[$index];
for ($i = $index; $i < $n-1; ++$i) {
$seq[$i] = $seq[$i+1];
}
array_pop($seq);
return $value;
}
function match($seq, $r=100) {
$res = array();
while (count($seq) >= 2) {
$a = array_pop($seq);
$i = mt_rand(1, min($r, count($seq)));
$b = list_pop($seq, -$i);
$res[$a] = $b;
}
return $res;
}
function test($n, $r) {
foreach (match(range(0, $n-1), $r) as $a => $b) {
printf("%d %d\n", $a, $b);
if ($a - $b >= $r*2) {
error_log("XXX");
}
}
}
test($argv[1], 10);
#Ausführungsergebnis
$ time php matching2.php 10000
real 0m1.631s
user 0m1.607s
sys 0m0.020s
$ time php matching2.php 20000
real 0m9.160s
user 0m9.105s
sys 0m0.052s
Nach dem Schreiben des Prozesses, der in Anhang 2 auf list_pop () gesetzt wurde, kam die Leistung schließlich wie erwartet heraus. Manipulieren Sie keine Array-Referenzen in PHP. Das heißt, der Algorithmus, der das Array manipuliert, sollte keine Funktion sein.
matching3.php
<?php
function match($seq, $r=100) {
$res = array();
while (count($seq) >= 2) {
$a = array_pop($seq);
$n = count($seq);
$i = $n - mt_rand(1, min($r, $n));
$b = $seq[$i];
for (; $i < $n-1; ++$i) {
$seq[$i] = $seq[$i+1];
}
array_pop($seq);
$res[$a] = $b;
}
return $res;
}
function test($n, $r) {
foreach (match(range(0, $n-1), $r) as $a => $b) {
//printf("%d %d\n", $a, $b);
if ($a - $b >= $r*2) {
error_log("XXX");
}
}
}
#Ausführungsergebnis
$ time php matching2.php 10000
real 0m0.064s
user 0m0.052s
sys 0m0.011s
$ time php matching2.php 20000
real 0m0.076s
user 0m0.064s
sys 0m0.011s
Recommended Posts