PHP: лучший алгоритм для строгой типизации идентификаторов в массиве

Question

В поисках решения для идентификации дубликатов в массиве я наткнулся на множество решений, рассчитывающих на array_count_values или же array_unique, Но все эти решения не заботятся об объектах в массиве.

array_count_values бросает E_WARNING для каждого значения, которое не является string или 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 или что-то?

Answer 1

В вашем примере это конкретный экземпляр каждого объекта, который является уникальным. Метод 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;
}

=== Оператор на объекте имеет такое же поведение, как это. Это примерное сравнение, а не сравнение содержимого объекта, о котором вам следует знать.

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 
   ];