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

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

Сейчас эта задача решается в лоб, т.е.
foreach(array as key1 => value1) {
   //что-то делается

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


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

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

----
Я хотел бы уточнить, что элементы сложные, т.е. они не сравнимы в большую и меньшую сторону.
Например это тоже массивы или объекты и о них можно сказать только равны они или нет по каким-то условиям (данным из их структуры).
  • Вопрос задан
  • 4651 просмотр
Решения вопроса 2
EvgenijDv
@EvgenijDv
C/C++ programmer
А нельзя их отсортировать( O(logN) ) по данному признаку, чтобы одинаковые элементы оказались рядом, а потом в один проход( O(N) ) пометить все повторяющиеся?
Ответ написан
seyfer
@seyfer Автор вопроса
php
Решение:

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

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


В оригинале код конечно же разбит на ф-ии и методы, тут упрощено все для примера.
У меня получается за один проход выходит рез-т, только памяти больше занимается. :)
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
@dmtrrr
Backend developer
map reduce ?
Ответ написан
Комментировать
bavaria
@bavaria
Студент, Python, Ruby
Запись в систему непересекающихся множеств может поможет отобрать?
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы