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

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

0 голосов
/ 30 мая 2018

При поиске решения для идентификации дубликатов в массиве я наткнулся на многие виды решений в расчете на 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 или что-то еще?

Ответы [ 2 ]

0 голосов
/ 30 мая 2018

Это похоже на проблему 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 
   ];
0 голосов
/ 30 мая 2018

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

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

...