Какой использовать алгоритм обхода массива и сравнения каждого элемента с остальными в этом массиве?

Question

[Олег Абражаев]

В общем суть задачи в заголовке.
Дан некоторый массив размера N. Он заполнен полностью. В массиве есть элементы, которые по каким-то условиям считаются одинаковыми.
Надо обойти этот массив, по ходу сравнив каждый с каждым элементом и выявить (или удалить, или пометить) элементы, которые одинаковы.

Сейчас эта задача решается в лоб, т.е.

foreach(array as key1 => value1) {
   //что-то делается

   foreach (array as key2 => value2) {
     //cравнение value1 и value2
   }
}

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

Язык реализации не важен.

----
Я хотел бы уточнить, что элементы сложные, т.е. они не сравнимы в большую и меньшую сторону.
Например это тоже массивы или объекты и о них можно сказать только равны они или нет по каким-то условиям (данным из их структуры).

Comments

[Lynn «Кофеман»]

В общем случае ничего быстрее O^2 не получится.

Answer 1

[Евгений]

А нельзя их отсортировать( O(logN) ) по данному признаку, чтобы одинаковые элементы оказались рядом, а потом в один проход( O(N) ) пометить все повторяющиеся?

Comments

[Олег Абражаев]

Если построить хеш по элементам и использовать этот хеш для сравнений (см мое уточнение в вопросе), тогда может и получится.

[Mrrl]

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

[Олег Абражаев]

В припципе можно данные, по которым идет сравнение, преобразовать в хеш.

[Mrrl]

Если условие, по которому "равны два объекта" для какого-нибудь поля имеет вид, например, ((a.X<0 && b.X<0) || a.X==b.X) (т.е. если поля отрицательны, то они считаются равными независимо от их конкретных значений), то хеш придётся специально изобретать - просто так ввести в него поле X не получится. А если условие ещё сложнее, когда сравниваются комбинации полей, одни поля сравниваются при определённых условиях на другие поля, и т.п. - то в конечном итоге мы рискуем получить задачу поиска канонического представления объекта. И в общем виде она может оказаться неразрешимой :(
А если ситуация более простая - когда мы сравниваем только определённые поля объектов и структур, то функцию сравнения, скорее всего, можно "поднять" до функции порядка (например, лексикографически по результатам сравнения отдельных полей). И после этого сортировать массивы уже без всякого хеша.

Answer 2

[Олег Абражаев]

Решение:

Делаю обход массива, создаю хеш таблицу. По ходу обхода ищу в хеш таблице по хешу элемент, если не нашел то добавляю его как уникальный.
Если нашел, то сравниваю с найденным и по результату либо иду дальше, либо заменяю найденный на текущий.

profit

Для решения задачи после всех советов я пошел следующим путем.
Если принять H за таблицу хешей, а h() - ф-ю создающую хеш, то мой итоговой алгоритм выглядит так.

Замечу еще, что структура несколько сложнее, чем просто элементы в массиве.

someMethod(array) {

finalResult = [];
H = [];
//итерируюсь по элементам.
foreach (array as resultKey => resultElement) {
   resultArray = resultElement['result'];
   resultInfo = resultElement['request'];
   
   //тут проверки на корректность
   ...

   //далее итерируюсь по внутреннему массиву
   foreach(resultArray as currentElement) {
   
   currentHash = h(currentElement);

   if (!H[currentHash]) {
       //нету в таблице
       //добавляю в рез-т
       currentUniqueId = currentElement['unique'];
       finalResult[resultKey]['result'][currentUnique] = currentElement;
       
       //запоминаю, чтобы можно было удалить в будущем
       currentElement['resultKey'] = resultKey;
       //добавяю в хеш таблицу
       H[currentHash] = currentElement;
   } else {
       //уже есть в таблице
       hashedElement = H[currentHash];
       currentUniqueId = currentElement['unique'];
       hashedUniqueId = hashedElement['unique'];
 
      //не сравниваем сам с собой
      if (compareUnique(currentUniqueId, hashedUniqueId)) {
         continue;
       }

       //дальше сравнение
       if (compareBigger(currentElement, hashedElement)) {
            //текущий больше, ничего не делаем
       } else if (compareSmaller(currentElement, hashedElement)) {
           //не буду приводить код, просто действия
           /*
           1. Удалить текущий из рез-та fullResult
           2. Сохранить currentElement в fullResult
           3. Обновить H[currentHash] на текущий элемент

          */
       }       
   }
   }
}

return fullResult;
}

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

Answer 3

[Дмитрий]

map reduce ?

Answer 4

[Дима Петрук]

Запись в систему непересекающихся множеств может поможет отобрать?