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

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;
}
...

}

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

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

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

Или сделайте только одну копию:

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

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

ОБНОВИТЬ

Я проверил код 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