Сравнение объектов и сортировка массивов в PHP

Question

У меня проблема с сопоставлением объектов в PHP. То, что кажется простой код на самом деле работает способ слишком медленно на мой вкус, и как я не так продвинут в языке я хотел бы некоторые отзывы и предложения по поводу следующего кода:

class TestTokenGroup { 
    private $tokens; 
    ... 

    public static function create($tokens) { 
     $instance = new static(); 
     $instance->tokens = $tokens; 
     ... 
     return $instance; 
    } 

    public function getTokens() { 
     return $this->tokens; 
    } 

    public static function compare($tokenGroup1, $tokenGroup2) { 
     $i = 0; 
     $minLength = min(array(count($tokenGroup1->getTokens()), count($tokenGroup2->getTokens()))); 
     $equalLengths = (count($tokenGroup1->getTokens()) == count($tokenGroup2->getTokens())); 
     $comparison = strcmp($tokenGroup1->getTokens()[$i], $tokenGroup2->getTokens()[$i]); 
     while ($comparison == 0) { 
      $i++; 
      if (($i == $minLength) && ($equalLengths == true)) { 
       return 0; 
      } 
      $comparison = strcmp($tokenGroup1->getTokens()[$i], $tokenGroup2->getTokens()[$i]); 
     } 
     $result = $comparison; 
     if ($result < 0) 
      return -1; 
     elseif ($result > 0) 
      return 1; 
     else 
      return 0; 
    } 
    ... 

} 

В коде выше $tokens это просто массив строк.

Использование метода выше через usort() для массива TestTokenGroup, состоящего из около 40 тыс. Объектов, занимает ~ 2 сек.

Есть ли разумный способ ускорить это? Где узкое место здесь?

EDIT: Добавлен метод getTokens(), который я изначально забыл включить.

Answer 1

Вы знаете, что объекты «проходят по ссылке», а массивы «проходят по значению»?

Если getTokens() возвращает $this->tokens, массив копируется каждый раз, когда вы вызываете этот метод.

Попытайтесь получить доступ к $tokens непосредственно через $tokenGroup1->tokens. Вы также можете использовать ссылки (&), хотя возвращение ссылки не работает во всех версиях PHP.

С другой стороны, сделать одну копию только:

$tokens1 = $tokenGroup1->getTokens(); 
$tokens2 = $tokenGroup2->getTokens(); 

Даже если каждая лексема группа является относительно небольшим, он будет сохранять по крайней мере 40000 * (6 + $average_token_group_length * 2) копии массива.

UPDATE

Я протестированный код OP (в удалении ... линий) с помощью:

function gentokens() { 
     $ret = []; 
     for ($i=0; $i< 3; $i++) 
     { 
       $str = ""; 
       for ($x = rand(0,3); $x < 10; $x ++) 
         $str .= chr(rand(0,25) + ord('a')); 
       $ret[] = $str; 
     } 
     return $ret; 
} 


$start = microtime(true); 

$array = []; // this will hold the TestTokenGroup instances 
$dummy = ""; // this will hold the tokens, space-separated and newline-separated 
$dummy2= []; // this will hold the space-concatenated strings 

for ($i=0; $i < 40000; $i++) 
{ 
     $array[] = TestTokenGroup::create($t = gentokens()); 

     $dummy .= implode(' ', $t) . "\n"; 
     $dummy2[] = implode(' ', $t); 
} 

// write a test file to benchmark GNU sort: 
file_put_contents("sort-data.txt", $dummy); 

$inited = microtime(true); 
printf("init: %f s\n", ($inited-$start)); 

usort($array, [ 'TestTokenGroup', 'compare']); 

$sorted = microtime(true); 
printf("sort: %f s\n", ($sorted-$inited)); 

usort($dummy2, 'strcmp'); 

$sorted2 = microtime(true); 
printf("sort: %f s\n", ($sorted2-$sorted)); 

со следующими результатами:

init: 0.359329 s // for generating 40000 * 3 random strings and setup 
sort: 1.012096 s // for the TestTokenGroup::compare 
sort: 0.120583 s // for the 'strcmp' compare 

И, бег time sort sort-data.txt > /dev/null урожаев

.052 u (user-time, in seconds). 

оптимизации 1: удалить копии массива

замещающие ->getTokens() с ->tokens выходами (я только список TestTokenGroup::compare результатов):

sort: 0.832794 s 

Оптимизация 2: удаление избыточных array() в min

Изменение $minlength линия:

$minLength = min(count($tokenGroup1->tokens), count($tokenGroup2->tokens)); 

дает

sort: 0.779134 s 

Оптимизация 3: count вызова только один раз для каждого tokenGroup

$count1 = count($tokenGroup1->tokens); 
    $count2 = count($tokenGroup2->tokens); 
    $minLength = min($count1, $count2); 
    $equalLengths = ($count1 == $count2); 

дает

sort: 0.679649 s 

Альтернативный подход

Самый быстрый сорт до сих пор strcmp($stringarray, 'strcmp'): 0.12s - еще в два раза медленнее, как GNU рода, но последний делает только одну вещь, и делает это хорошо.

Итак, чтобы эффективно сортировать TokenGroups, нам нужно построить ключ сортировки, состоящий из простой строки. Мы можем использовать \0 в качестве разделителя для токенов, и нам не нужно беспокоиться о том, что они равны по длине, потому что, как только один символ отличается, сравнение прерывается.

Вот реализация:

$arr2 = []; 
foreach ($array as $o) 
    $arr2[ implode("\0", $o->getTokens()) ] = $o; 

$init2 = microtime(true); 
printf("init2: %f s\n", ($init2-$sorted2)); 

uksort($arr2, 'strcmp'); 

$sorted3 = microtime(true); 
printf("sort: %f s\n", ($sorted3-$init2)); 

и вот результаты:

init2: 0.125939 s 
sort: 0.104717 s