Пользователь
88,6
рейтинг
31 января 2013 в 14:24

Разработка → Поиск часто встречающихся элементов в массиве

Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

Есть один нюанс: для словаря нам потребуется O(N) дополнительной памяти — в несколько раз больше размера исходного массива, и это при реализации словаря хоть хэш-таблицей, хоть деревом. Что будем делать, если наша цель — обработка сигнала неким устройством с маленькой памятью? Массив — замеры уровня сигнала, из которых один — «настоящий» передаваемый уровень, а остальные — шум и помехи. Неужели придётся для определения «настоящего» уровня возиться с хэш-таблицами и деревьями?

К счастью, нет: достаточно O(1) дополнительной памяти, и по-прежнему одного прохода по массиву. Алгоритм Бойера-Мура — тех самых Бойера и Мура, что придумали намного более известный алгоритм поиска подстроки — проще всего представить следующим образом: на вечеринке собрались N людей, и на каждом по одному элементу из массива. Когда встречаются двое, у которых элементы разные, они присаживаются это обсудить. В конце концов останутся стоять только люди с одинаковыми элементами; очевидно, это тот самый элемент, который встречался больше N/2 раз.

Реализация алгоритма Бойера-Мура занимает всего несколько строк:
int* majority(int[] array, int N) {
  int confidence = 0; // количество людей, не нашедших пары и оставшихся стоять
  int* candidate = NULL; // последний человек, не нашедший пару -- 
                         // возможно, его элемент встречается чаще всего

  // проходим по массиву и усаживаем пары с разными элементами
  for (int i = 0; i<N; i++) {

    // если до сих пор все сидят, то следующему пока придётся постоять
    if (confidence == 0) {
      candidate = array+i;
      confidence++;
    }

    // иначе следующий либо садится с одним из стоящих,
    // либо будет стоять вместе с ними, если у него такой же элемент
    else if (*candidate == array[i])) 
      confidence++;
    else 
      confidence--;
  }

  return confidence > 0 ? candidate : NULL;
}

В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.


Усложним задачу. Теперь в массиве длиной N надо найти элементы, которые повторяются больше N/3 раз — если есть два, то оба, если есть один, то один.

Например, нашему устройству с маленькой памятью нужно принять двоичный сигнал с неизвестными уровнями нуля и единицы, но известно, что примерно половину времени передаётся ноль, примерно половину времени — единица, а любые отличные от них уровни сигнала — это помехи и дребезг от переключения.

Идею прошлого алгоритма несложно обобщить и для троек: пусть люди с разными элементами рассаживаются по трое. Значит, в конце вечеринки останутся стоять люди максимум с двумя разными элементами. Если какой-то элемент встречался больше N/3 раз, значит человек с ним гарантированно останется стоять, ведь сидящих троек получится не больше N/3. Как и в прошлом случае, если искомые элементы существуют — то они будут найдены, но если их нет — то найтись может кто попало.

Код мало отличается от предыдущего: по-прежнему один проход по массиву и O(1) дополнительной памяти.
void majority(int[] array, int N, int** cand1, int** cand2) {
  int conf1 = 0, conf2 = 0; // количество стоящих людей с двумя элементами
  *cand1 = NULL; *cand2 = NULL; // два стоящих человека с разными элементами

  // проходим по массиву и усаживаем тройки с разными элементами
  for (int i = 0; i<N; i++) {

    // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними
    if (conf1 > 0 && **cand1 == array[i])
      conf1++;
    else if (conf2 > 0 && **cand2 == array[i])
      conf2++;
    else // может, стоят только с одним элементом, или вообще стоящих нет?
      if (conf1 == 0) {
        *cand1 = array+i;
        conf1++;
      } else if (conf2 == 0) {
        *cand2 = array+i;
        conf2++;
      }
    else { // стоят с двумя другими элементами, так что усаживаем всю тройку
      conf1--;
      conf2--;
    }
  }

  if(conf1 == 0) *cand1 = NULL;
  if(conf2 == 0) *cand2 = NULL;
}

Этот алгоритм опубликован в 1982 американскими учёными Джаядевом Мисрой и Дэвидом Грисом (Jayadev Misra & David Gries), и в их работе используется более скучная метафора — мешок с N числами, из которого они извлекают по 3 разных числа за каждую операцию. Кроме того, их псевдокод не похож ни на один понятный современному программисту язык. Мне больше понравилось объяснение их алгоритма в позапрошлогоднем конспекте лекций американского профессора Амита Чакрабарти.



В наиболее общей форме, когда в массиве длиной N надо найти элементы, которые повторяются больше N/k раз — придётся-таки воспользоваться словарём. Хранить в словаре мы будем только те элементы, с которыми люди стоят — т.е. не больше k-1 записей.

int[] majority(int[] array, int N, int k) {
  // словарь стоящих людей изначально пуст
  Dictionary<int,uint> candidates = new Dictionary<int,uint>{};

  // проходим по массиву и усаживаем группы по k
  for (int i = 0; i<N; i++) {

    // у следующего такой же элемент, как у стоящих? тогда встанет вместе с ними
    if (candidates.ContainsKey(array[i]))
      candidates[array[i]]++;
    else // может, стоят менее чем с k-1 элементами?
      if (candidates.Count < k - 1)
        candidates[array[i]] = 1;
    else // стоят с k-1 другими элементами, так что усаживаем всю группу
      foreach(int l in candidates.Keys)
        if (candidates[l]-- == 0)              // (**)
          candidates.Remove(l);                // (*)
  }

  return candidates.Keys.ToArray();
}

В этой наиболее общей форме алгоритма — по-прежнему один проход по массиву и O(k) дополнительной памяти. Если мы пользуемся для реализации словаря хэш-таблицей, а все записи в словаре свяжем в список — тогда общая сложность алгоритма останется линейной: строчка (*) с удалением записи из словаря выполняется самое большее N раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

Таким образом наше устройство с маленькой памятью смогло бы общаться с одним пушистым зверьком, недавно препарированным хабраумельцами. Сигналы этого зверька имеют пять логических уровней: полагаем k=6, и получаем все пять уровней прямо на ходу, даже без сохранения сигнала в память. Нужно только обеспечить протоколом, чтобы все пять уровней встречались в сигнале одинаково часто.

Для алгоритма Мисры-Гриса упоминаются и другие применения. Например, можно следить в реальном времени за трафиком в сети, и если некий один хост потребляет непропорционально большую часть трафика — начинать расследование. Так же можно следить за кликами по баннерам, за финансовыми транзакциями, за потоком инструкций в моделируемом процессоре… В общем, всюду, где большое число повторений — подозрительная аномалия.

За оживление текста иллюстрациями надо благодарить Nitatunarabe
@tyomitch
карма
327,7
рейтинг 88,6
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (38)

  • +2
    «В конце мы получаем «наиболее вероятного кандидата» на присутствие в N/2 экземплярах: если такой элемент в массиве действительно существует, то он будет найден; если же такого элемента нет, то возможно, стоять останется просто какой-то бедолага, которому не хватило пары. Для более строгой реализации majority требуется пройти по массиву второй раз и проверить, действительно ли найденный элемент встречается требуемое количество раз.»

    Правильно ли я понимаю, что второй проход по массиву нужен только если N — нечетное? А если N — четное, то тогда либо «никого не останется», либо «останутся как минимум 2 представителя большинства».
    • +2
      Второй проход требуется, чтобы в ситуации, когда такого элемента в принципе нет (условие задачи «некий элемент встречается как минимум N/2 раз» не выполняется) — понять это, а не выдать неверный ответ
    • +2
      Сказал, не подумав.
      Здесь важно, что элемент встречается строго больше, чем N/2 раз
      иначе все действительно ломается при нечетном N:
      N=5
      12134
      результат — 4
      • +1
        Да, думаю, я понял, спасибо, отличный пример. Но у вас N = 5 — нечетное. Я как раз говорил что в этом случае может быть нужна проверка.

        Однако, с вашей подачи я придумал другой пример, который опровергает то, что я написал ваше.
        Если взять N = 6 и массив [112345] и удалить пары 23 и 45, то остануться элементы 11, которые не являются удовлетворяющими условиям поиска.
        • +1
          Нет, я все правильно написал=)
          Как раз про Ваш пример.

          Еще раз. Для нечетного числа проверка нужна, если в условии будет нестрогое неравенство:
          «некий элемент встречается как минимум N/2 раз»

          Тогда, действительно, написанное Вами верно, и я лишь привел пример для N=5

          Но на самом деле в условии строгое неравенство:
          «Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.»

          И тут уже при выполнении условия выполнение второго прохода не требуется ни для каких N.

          кстати, в вашем примере
          112345
          алгоритм выдаст 5 (опять же, условие задачи не выполнено)
    • 0
      А какая разница сколько проходов? Алгоритмически сложность все равно o(N), а операций даже при одном проходе может быть 10*N, второй проход добавит лишь N.
      Кстати во втором случае сложность как я понимаю o(k*N), если k сравнимо c N.
      • 0
        Второй проход может оказаться физически невозможным. Например, в ситуации, когда данные поступают в реальном времени, а памяти для их сохранения нет. Но тогда нам должны гарантировать, что есть подходящий элемент.
      • 0
        Во втором случае всё равно O(N) — ниже winger уже пояснил, почему.
  • –18
    1. А тесты будут ??
    2.Не лучше бы использовать Buckets тогда вообще не придется использовать поиск ???
    Buckets это хеш таблицы без колизий!!!
  • 0
    Казалось бы, чего тут думать? Возьмём Dictionary<значение элемента, число появлений>, за один проход по массиву сосчитаем появления каждого элемента, потом выберем из словаря искомый элемент. Решение за O(N), куда может быть ещё быстрее?

    Покажите мне, что ли, такую реализацию Dictionary, которая за O(1) будет позволять достучаться до произвольного элемента.
    • +1
      Любая хэш-таблица даёт в среднем O(1)
      • 0
        Тогда следовало заметить, что и предложенный алгоритм с хэш-таблицами в среднем даёт O(N).
        • +1
          А никто с этим не спорит и в статье это указано. Но решение со словарем требует дополнительной памяти O(N), а этот алгоритм нет.
        • 0
          Он не «предложенный» — как раз взамен ему предлагается более эффективный.
          • –3
            «Предложенный», «упомянутый», «описанный» — один хер, асимптотика всё равно неверная.
  • –2
    Может кто знает, можно ли как-нибудь подсчитать кол-во повторений (частоту слов) через regexp?
  • 0
    Асимптотика второго алгоритма будет O(N*k) из-за foreach(int l in candidates.Keys).
    • 0
      Исходя из смысла задачи, k существенно меньше N, поэтому можно ее считать константой и пренебречь.
    • 0
      Вы имеете ввиду проверку candidates.ContainsKey(array[i])?
      Но ведь если словарь реализован как самобалансирующееся дерево, то в нем поиск осуществляется за log(n). Т.е. сложность второго алгоритма будет O(N*log(k)). Я думаю, что при относительно малых k, величиной log(k) можно пренебречь.
      • +3
        Я имел ввиду
        foreach(int l in candidates.Keys) if (candidates[l]-- == 0) candidates.Remove(l);
        Правда я только что осознал что амортизированно там будет O(1) декрементов :)
    • –1
      Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

      Это был намеренный «подвох» :)
  • +1
    Возможно, это многим покажется очевидно, но всё же замечу: первый алгоритм обнаруживает числа, которых строго больше половины в исходной последовательности. Для ситуации, когда их может быть ровно половина, такой алгоритм даст сбой на последовательностях вида ACBС, где A, B и C — разные числа (при необходимости повторённых любое количество раз).
    • 0
      Собственно, первая строчка статьи это и говорит: "Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз."
  • +2
    Задача: в массиве длиной N найти элемент, который повторяется больше N/2 раз.

    Заметим, что если отсортировать массив, то искомое число будет находиться на непрерывном отрезке индексов, который будет длинее N/2. Это значит, что какое бы ни было это число — оно обязательно покроет ячейку массива с номером N/2.

    Другими словами, надо найти число, которое после сортировки встанет на позицию N/2, а это можно найти вызовом одной функции nth_element в С++.
    • +1
      Да, но сортировка — это O(n*log(n)), а тут O(n).
      К тому же, не всегда возможна сортировка in-place, а иначе надо дополнительно O(n) памяти.
      Т.е. этот алгоритм необходим, когда существуют серьезные ограничения по использованию других, более очевидных, но и несколько более дорогостоящих алгоритмов.
      • +1
        Никакой сортировки в решении нет, она есть только в объяснении алгоритма.

        int find(vector<int> a) {
        	nth_element(a.begin(), a.begin() + (a.size() / 2), a.end());
        	return a[a.size() / 2];
        }            
        
        • +1
          Есть частичная сортировка.
        • 0
          Да, согласен. Почему-то на nth_element в первом сообщении вообще внимания не обратил.
    • 0
      Да, это верно для элемента, повторяющегося больше N/2 раз, но этот подход невозможно обобщить для N/3 и N/k.
      Кроме того, алгоритм nth_element и сложнее в реализации, чем предложенный, и сложнее него вычислительно (рекурсия требует O(log N) дополнительной памяти).
      • 0
        А нужна ли в nth_element рекурсия? Если он реализован «за O(N) в среднем», используя идеи быстрой сортировки, то это просто цикл. В честной реализации за гарантированные O(N) без рекурсии обойтись сложно, но писал ли её кто-нибудь когда-нибудь вообще?
      • +1
        И, кстати, почему невозможно обобщить? Чтобы вывести правильные элементы в точки N/k, (2*N)/k, ..., (k-1)*N/k, потребуется O(N*log(k)) операций, столько же, сколько для реализации словаря с помощью дерева. Словарь в виде хеш-таблицы, конечно, не догнать.
    • 0
      A nth_element есть ничто иное как Selection Algorithm или K-тая порядковая статистика.
      • –2
        вообще-то я прекрасно знаю, что она делает, я ж сказал
        надо найти число, которое после сортировки встанет на позицию N/2
        . в следующий раз читайте внимательнее
        • 0
          Я это не для вас оставлял а для людей которые на C++ не программируют и с nth_element дело не имеют. Им будет полезна ссылка к теории, чтобы иметь представление о чем идет речь.
  • +1
    А ведь ту же идею можно использовать для поиска точки сгущения в облаке. Если нам надо найти шар радиуса R, содержащий больше, чем 1/k точек, то поступаем точно так же, но вместо проверки равенства точек проверяем, что расстояние между ними меньше 2*R (придётся немного повозиться при создании «группы стоящих» — если двое стояли рядом, надо запомнить их обоих, а когда рядом с ними найдётся третий, взять в качестве центра того из двух, кто ближе к третьему. Или середину самой короткой стороны треугольника).
    Выглядит гораздо проще других алгоритмов. И за один проход :)
  • +1
    В сборнике задач K&R помимо этой была ещё такая задача (к сожалению не могу нагуглить):
    На космическом корабле вышли из строя некоторые из N процессоров, при этим исправных осталось больше половины. Процессор можно спросить, исправен ли какой-то другой. Исправный процесс выдаст правильный ответ, неисправный ответит ложью. Как за N/2+1 (или N/2?) таких запросов найти исправный процессор.
  • 0
    Слишком поздно, похоже мозги совсем не соображают.
    Как быть в случае если первая пара «села», т.к. элементы не совпадают, села также и следующая,
    но скажем во второй паре один элемент совпал с одним из первой пары?
    • 0
      Это не важно. Главное, что в оставшемся массиве одинаковых элементов всё равно больше половины: в самом худшем случае, когда одинаковые элементы и 1 и 2 пары это и есть искомый элемент, получается, что одинаковых мы вычеркнули столько же, сколько неодинаковых — а значит, условие сохранилось.

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