1

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

array_count_valuesE_WARNING为每个不是 astring或 an 的值抛出一个integer。

array_unique如果设置了该选项，则确实会关注具有各种类型的元素SORT_REGULAR。但是看看下面的用例。

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？

4

2 回答 2

2

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

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

对象上的===运算符具有与此相同的行为。这是一个实例比较，而不是对象内容的比较，这是您应该注意的。

于 2018-05-30T10:03:03.907 回答
0

这看起来像 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 
   ];
于 2018-05-30T11:24:57.767 回答