Оптимизация fO_o

[Wicked]

Оптимизация f

объясните, как так надо было написать array_unique(), что array_flip(array_flip()) работает в ~14 раз быстрее? Пусть с ограничениями (напр., сложные значения теряются, когда становятся ключами массива), но все же...

$a = array_merge(range(0, 10000), range(5000, 15000));

shuffle($a);
echo count($a), "\n";

for($i = 0; $i < 10; $i++) {
  $t=-microtime(true);
  $z = array_unique($a);
  echo "uniq: ", count($z), "\n";
  echo $t+microtime(true), "\n";

  $t=-microtime(true);
  $z = array_flip(array_flip($a));
  echo "flip: ", count($z), "\n";
  echo $t+microtime(true), "\n";
}

20002
uniq: 15001
0.30942606926
flip: 15001
0.022145986557
uniq: 15001
0.316202163696
flip: 15001
0.022628068924
...

C:\WWWROOT>c:\php\php -v
PHP 5.2.5 (cli) (built: Nov  8 2007 23:18:51)

 

[Фанат]

возможно, в этих ограничениях, и связанных с ними проверках все дело?

 

[Wicked]

в виду частоты использования array_unique() для массивов со сложными данными, я бы на месте разработчиков всегда заодно строил и хэш-таблицу: авось сложных структур не найдется, и можно будет сделать все быстро... или это только у меня такое имхо?

-~{}~ 16.04.08 21:04:

отношение ~1:14 сохраняется и при увеличении массивов в 10 раз, и при их уменьшении в 10 раз.

-~{}~ 16.04.08 21:07:

ну и ты не подумай, что я тут спички оптимизирую - строю кэш для морфологии, массивы по 170к слов...

 

[tony2001]

действительно, как можно написать функцию, которая делает что-то СОВЕРШЕННО ИНОЕ медленнее, чем другая функция?
ужас, ужас.

 

[Wicked]

tony2001
я ожидал такого ответа Прям уж СОВЕРШЕННО ИНОЕ?

array_unique() takes input array and returns a new array without duplicate values.

Note that keys are preserved. array_unique() sorts the values treated as string at first, then will keep the first key encountered for every value, and ignore all following keys. It does not mean that the key of the first related value from the unsorted array will be kept.

Вот из ее названия и описания (выделено жирным) вполне ожидать от нее поведения, как у двойного array_flip(), за исключением работы со сложными структурами.

Я так подозреваю, что тормоза из-за сортировки. Если не секрет, нафига она там? Типа так дубликаты выкидывать потом легче за один проход, сравнивая текущий элемент с предыдущим?

А еще array_unique() не знает, какой ключ для каждой группы она выберет... а array_flip знает.

 

[tony2001]

две совершенно разные функции делают совершенно разные вещи.
вместо гаданий давно пора открыть исходники и посмотреть самому.

-~{}~ 16.04.08 18:23:

сравни:
выполнить 10 000 хэш-лукапов по ключу и 10 000 раз пройтись по массиву в поисках такого же значения.
есть разница?

 

[Wicked]

две совершенно разные функции делают совершенно разные вещи.

"если что-то крякает как утка, ..." (с)

сорцы посмотрю обязательно, чуток попозже

 

[tony2001]

нет, не крякает как утка, в том-то и дело.

 

[Wicked]

выполнить 10 000 хэш-лукапов по ключу и 10 000 раз пройтись по массиву в поисках такого же значения.
есть разница?

это уже внутренние алгоритмы, которые к семантике не имеют никакого отношения, поэтому как оправдание не принимаются

Two elements are considered equal if and only if (string) $elem1 === (string) $elem2. In words: when the string representation is the same.

The first element will be used.

повторю (и перефразирую) свой вопрос: почему бы не составлять хэш-мап этих строк, чтобы не приходилось 10 000 проходиться по массиву?

 

[tony2001]

>это уже внутренние алгоритмы, которые к семантике не имеют никакого
>отношения, поэтому как оправдание не принимаются

они имеют самое непосредственное отношение к алгоритму работы.
это по сути разные вещи, поэтому довольно странно ожидать от них одинаковых результатов.

>почему бы не составлять хэш-мап этих строк, чтобы не приходилось 10 000 проходиться по массиву?

потому, что массив строк или массив интов - это всего лишь частный случай массива.
не все массивы состоят только из строк или интов.

 

[Wicked]

потому, что массив строк или массив интов - это всего лишь частный случай массива.
не все массивы состоят только из строк или интов.

погоди... я хотел сказать: если уж там все равно используется приведение к строкам, то нужно составлять хэшмап этих самых строк, чтобы не бегать по массиву. Хэш-мап использовать только для проверок, ессно.

Даже приведу код на пхп, который работает в 4..5 раз быстрее, чем array_unique(), и вроде даже аналогичен последнему, если не принимать во внимание (имхо ненужную в array_unique()) сортировку:

function array_unique2($a) {
  $return = array();
  $hash = array();
  foreach($a as $k => $v) {
    $hash_key = (string)$v;
    if (!isset($hash[$hash_key])) {
      $hash[$hash_key] = true;
      $return[$k] = $v;
    }
  }
  return $return;
}

 

[StUV]

работает в 4..5 раз быстрее

а если в конце добавить sort - какая разница в скорости ? =)

 

[tony2001]

>который работает в 4..5 раз быстрее, чем array_unique():

в конкретном частном случае - вполне возможно.

вот тебе другой частный случай:
сделай массив из 10000 строк по 1000 символов.
array_unique() делает все твои варианты.

 

[Wicked]

StUV

а если в конце добавить sort - какая разница в скорости ? =)

а можно вопрос: зачем добавлять sort в конце, если мне нужны уникальные значения, а не отсортированные?

tony2001

вот тебе другой частный случай:
сделай массив из 10000 строк по 1000 символов.
array_unique() делает все твои варианты.

Хорошо, я понял, что ситуация не однозначная, поумерю свою иронию. Перейдем к конструктиву.

Мои соображения:
1) Нужно стремиться использовать правильные алгоритмы с минимальной алгоритмической сложностью. Выборка уникальных значений может, и посему должна происходить за время O(n) (n - кол-во элементов).
2) Что мы сейчас видим в array_unique - это использование quicksort'а, который на самом деле не нужен в этой функции, но поднимает сложность до O(n*log(n)).
3) Поскольку можно привести примеры, когда array_unique в 10 раз быстрее (на очень длинных строках), и когда наоборот, двойной array_flip быстрее в 50 раз (много интов, из которых уникальных - 1%), то лично я прихожу к таким выводам: оба этих метода не идеальны, но позволяют увидеть компромиссный вариант (сишная функция, которая испльзует hashmap для оптимизации), который будет быстрее их обоих.

Посему вопрос к тебе: какие есть разумные преграды, мешающие существованию такой функции?

 

[crocodile2u]

Wicked
Я не залезал в исходники, не знаю Си и даже в алгоритмах разбираюсь на два с минусом. И все таки, по-моему, разумный вопрос: тебе часто встречались ситуации, где array_unique() был бы узким местом? И может быть, если это действительно узкое место - то можно обойти его другим путем? Ведь заметное время потратится только на довольно больших массивах, а зачем они тебе нужны такие большие - можно спросить?

 

[StUV]

Wicked

а можно вопрос

это было чистое любопытство - самому проверить времени нет... =)

 

[Wicked]

тебе часто встречались ситуации, где array_unique() был бы узким местом?

не часто, но если есть возможность не особо заморачиваясь ускорить базовые функции языка, то к чему ими пренебрегать?

а зачем они тебе нужны такие большие - можно спросить?

строю кэш для морфологии, массивы по 170к слов...

 

[rotoZOOM]

Выборка уникальных значений может, и посему должна происходить за время O(n) (n - кол-во элементов).

Опа ... я что-то пропустил. А расскажи мне такой алгоритм пожалуйста, не для частного случая, а для общего?

 

[Wicked]

rotoZOOM
вставка 1 элемента в хэш-таблицу - O(1).
проверка присутствия 1 элемента значения в хэш-таблице - О(1).
выполняя это в цикле для n элементов получаем суммарную сложность O(n).

 

[rotoZOOM]

Wicked вот именно там же где ты дал ссылку прочитай, что O(1) - это не всегда и в худшем случае - O(n), таким образом при плохой хэш-функции общая сложность в худшем случае O(n^2).
Если же использовать сбалансированные деревья (красно-черные например), то худшую сложность для вставки/поиска/удаления можно получить как O(log n). За сим для любых случаев входных данных в худшем случае можно получить только алгоритм O(n log n). Посмотри например std::map из STL.