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

 В общем суть задачи в заголовке.  

Дан некоторый массив размера N. Он заполнен полностью. В массиве есть элементы, которые по каким-то условиям считаются одинаковыми.  

Надо обойти этот массив, по ходу сравнив каждый с каждым элементом и выявить (или удалить, или пометить) элементы, которые одинаковы.  
  

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

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

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

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

Так же не тривиальна структура самих элементов и условий сравнения.  
  

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

----  

Я хотел бы уточнить, что элементы сложные, т.е. они не сравнимы в большую и меньшую сторону.  

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

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

 Решение:  
  

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

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

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;
}
```
  
  

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

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

 map reduce ? 

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