PHP: лучший алгоритм для строгой типизации идентификаторов в массиве
В поисках решения для идентификации дубликатов в массиве я наткнулся на множество решений, рассчитывающих на 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 или что-то?
Решение
В вашем примере это конкретный экземпляр каждого объекта, который является уникальным. 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;
}
=== оператор на объекте имеет такое же поведение как это. Это примерное сравнение, а не сравнение содержимого объекта, о котором вы должны знать.
Другие решения
Это похоже на проблему 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
];