Étant donné une liste d'identifiants triés selon certaines conditions, il était nécessaire de faire correspondre d'une manière ou d'une autre dans une plage étroite. Extraire un élément du tableau est O (n), mais s'il est limité aux éléments de la plage fixe à partir de la fin ou de la fin, c'est O (1), donc si vous extrayez les éléments en faisant correspondre à partir de l'arrière, O ( Vous devriez pouvoir faire correspondre avec n).
Ce n'est pas du tout difficile, et si vous l'écrivez en Python, ce sera comme ça. C'est bien de permettre à `` list.pop () '' d'indexer à partir de la fin (-1 pour le dernier élément).
matching.py
# coding: utf-8
def match(seq, r=100):
from random import randint
#Si vous ne voulez pas que les éléments du début se transforment en pétanque quand il y a un nombre impair, le dos
#Retirez l'élément et gardez-le au même niveau.
while len(seq) >= 2:
#Si l'argument est omis, le dernier élément est extrait..
a = seq.pop()
#Sélectionnez et extrayez au hasard à la fin du tableau dans la plage de 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)
Quand j'ai entendu les exigences, j'ai immédiatement proposé cet algorithme et j'ai promis que c'était "facile et facile", mais ce n'était pas du tout facile en termes de php. Je peux supprimer l'élément de la clé spécifiée du tableau associatif, mais je ne le trouve pas, peu importe combien je recherche une fonction qui récupère l'élément au milieu (remplit la fin) du tableau.
Après avoir lu le chapitre sur les tableaux de la référence php pendant des dizaines de minutes, il n'y avait pas d'équivalent à `` list.pop () ''. Si vous coupez le tableau une fois et le concaténez, vous pouvez faire quelque chose de similaire, mais comme le coût de concaténation du tableau est O (n), l'algorithme de correspondance devient O (n ^ 2). Au final, j'ai dû écrire une boucle qui déplace les éléments derrière les éléments que j'ai retirés un à un.
En php, les tableaux et les tableaux associatifs sont confus, de sorte que les fonctions de type tableau sont difficiles à comprendre comment gérer les clés. Vous ne savez peut-être pas que les développeurs php ne fournissent pas un processus aussi basique car c'est trop déroutant.
Comme vous l'avez souligné dans les commentaires, nous avons pu obtenir le comportement attendu avec ʻarray_splice (). Il prend également en charge les index de la fin avec des nombres négatifs. La réécriture du code ci-dessus en php ressemble à ceci:
Cependant, il semble que le temps d'exécution ne soit pas O (n) après tout orz En tant que bord de l'algorithme, je revendique le droit de ne pas utiliser php comme un droit humain fondamental.
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);
#Résultat d'exécution
$ 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
Je pensais pouvoir le mettre en œuvre moi-même, mais c'était aussi difficile. J'ai peur, mais je sens que le CoW s'est produit lorsque j'ai compté la référence, donc je pense que c'est la raison.
Vous ne pouvez même pas gérer le tableau vous-même en php pour éviter les fonctions intégrées de merde, donc si vous voulez manipuler un tableau, créez une extension php et écrivez-la en C. php est un langage modèle, et il est sûr d'écrire des programmes en langage C.
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);
#Résultat d'exécution
$ 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
Lorsque j'ai écrit le processus défini sur `` list_pop () '' dans l'Addendum 2, la performance est finalement sortie comme prévu. Ne manipulez pas les références de tableau en php. Autrement dit, l'algorithme qui manipule le tableau ne doit pas être une fonction.
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");
}
}
}
#Résultat d'exécution
$ 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