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

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

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

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

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

Реализация ^[3] алгоритма Бойера-Мура занимает всего несколько строк:

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

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

В наиболее общей форме, когда в массиве длиной 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 раз, ведь на каждой итерации основного цикла в словарь добавляется не больше одной записи. Читателям в качестве упражнения предлагается понять, почему строчка (**) не нарушает линейности алгоритма.

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

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

За оживление текста иллюстрациями надо благодарить Nitatunarabe ^[7]

Автор: tyomitch

Источник ^[8]