0

我对 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中只是一个简单的字符串数组。

使用上述方法处理由大约 40k 个对象组成usort()的数组需要大约 2 秒。TestTokenGroup

有没有加快速度的明智方法？这里的瓶颈在哪里？

编辑：添加了我最初忘记包含的 getTokens() 方法。

4

1 回答 1

1

你知道对象是“按引用传递”，而数组是“按值传递”吗？

如果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).

优化一：移除数组副本

替换->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
于 2015-11-02T19:17:12.660 回答