PHP：更好的算法来严格类型识别数组中的重复项

Question

在寻找识别数组中重复项的解决方案时，我偶然发现了多种依赖 array_count_values 或 array_unique 的解决方案。但是所有这些解决方案都不关心数组中的对象。

array_count_values 为每个不是 string 或 integer.

的值抛出 E_WARNING 如果设置了选项 SORT_REGULAR，

array_unique 会处理各种类型的元素。但是看看用例如下。

class Foo
{
    private $value;

    public function __construct( $value )
    {
        $this->value = $value;
    }
}

$f1 = new Foo( 42 );
$f2 = $f1;
$f3 = new Foo( 42 );
$f4 = new Foo( '42' );
$f5 = new Foo( 'Bar' );
$a  = [ $f1, $f2, $f3, $f4, $f5 ];

与 array_unqiue 统一后，我希望得到一个包含 4 个元素的数组 [ $f1, $f3, $f4, $f5 ]。但它指出，array_unqiue 正在松散工作，我得到了 [ $f1, $f5 ] 这不是我需要的结果。

在我的例子中，我写了一个像集合一样工作的集合。我可以传递一些初始元素。应对这些要素进行验证。如果一个元素是重复的，则必须抛出异常。为了松散类型 array_unqiue 我想出了这个解决方案（可以很容易地调整以统一数组）。

$boundN = count( $elements );
$boundM = $boundN - 1;
for ( $m = 0; $m < $boundM; $m++ )
{
    for ( $n = $m + 1; $n < $boundN; $n++ )
    {
        if ( $elements[ $m ] === $elements[ $n ] )
        {
            throw new DuplicateElementException( 'The initial values contain duplicates.' );
        }
    }
}

至少我减少了内循环中的迭代次数。可以假设，外循环中所有传递的元素都经过验证，无需再次验证。

我的问题是：是否有更短的算法等于 Quick Search 之类的算法？

Answer 1

在您的示例中，每个对象的特定实例都是唯一的。 spl_object_id 方法可以获得每个对象的唯一标识符，您可以将它们用作关联数组中的键以折叠重复项。有几种 shorthand 的写法，但一个独立的例子可能是：

<?php
class Foo {
    private $data;

    public function __construct($data) {
        $this -> data = $data;
    }
}

$f1 = new Foo( 42 );
$f2 = $f1;
$f3 = new Foo( 42 );
$f4 = new Foo( '42' );
$f5 = new Foo( 'Bar' );
$a  = [ $f1, $f2, $f3, $f4, $f5 ];
$b = obj_unique($a);

print_r($b);

function obj_unique(array $not_unique) {
    $tmp = [];
    foreach($not_unique as $value) {
      $tmp[spl_object_id($value)] = $value;
    }
    return array_values($tmp);
}

这将创建以下输出，其中缺少重复值。

Array
(
    [0] => Foo Object
        (
            [data:Foo:private] => 42
        )

    [1] => Foo Object
        (
            [data:Foo:private] => 42
        )

    [2] => Foo Object
        (
            [data:Foo:private] => 42
        )

    [3] => Foo Object
        (
            [data:Foo:private] => Bar
        )

)

这个想法可以简单地修改为在数组已经包含键的情况下抛出异常。

if(contains_duplicates($a)) {
    throw new Exception("Duplicates are bad etc etc ...");
}

function contains_duplicates(array $test) {
    $tmp = [];
    foreach($test as $value) {
      $key = spl_object_id($value);
      if(array_key_exists($key, $tmp)) {
          // duplicates
          return true;
      }
      $tmp[$key] = $value;
    }
    // no duplicates
    return false;
}

Object has the same behaviour 上的 === 运算符。这是一个实例方面的比较，而不是对象内容的比较，这是你应该知道的。

Answer 2

这看起来像 XY 问题。

由于您的代码正在查找重复实例 (===) 而不仅仅是包含相同数据的对象，因此必须在运行时实例化这些对象。由于您使用的是数字索引数组，这表明您不关心在数组索引中保留信息。因此，最合适的解决方案是应用一种数组索引方法，以确保在向数组添加条目时的唯一性：

 $f1 = new Foo( 42 );
 $f2 = $f1;
 $f3 = new Foo( 42 );
 $f4 = new Foo( '42' );
 $f5 = new Foo( 'Bar' );
 $a  = [ 
   spl_object_hash($f1)=>$f1, 
   spl_object_hash($f2)=>$f2, 
   spl_object_hash($f3)=>$f3, 
   spl_object_hash($f4)=>$f4, 
   spl_object_hash($f5)=>$f5 
   ];

PHP：更好的算法来严格类型识别数组中的重复项

PHP: Better algorithm to strict typed identify duplicates in an array

php

arrays

strong-typing

unify