Вычислить режим (самый частый элемент) набора в линейное время? - PullRequest
Новая
       5

Вычислить режим (самый частый элемент) набора в линейное время?

6 голосов
/ 12 ноября 2010

В книге Скиены "Руководство по разработке алгоритмов" вычисление режима (наиболее частый элемент) набора, как говорят, имеет Ω ( n log * 1005). * n ) нижняя граница (это озадачивает меня), но также (правильно я предполагаю), что для вычисления режима не существует более быстрого алгоритма наихудшего случая. Меня озадачивает только нижняя граница Ω ( n log n ).

См. Страницу книги в Google Книгах

Но, безусловно, в некоторых случаях это можно рассчитать за линейное время (наилучший случай), например, с помощью кода Java, как показано ниже (находит наиболее часто встречающийся символ в строке), «хитрость» заключается в подсчете вхождений с использованием хеш-таблицы. Это кажется очевидным.

Итак, что мне не хватает в моем понимании проблемы?

РЕДАКТИРОВАТЬ: (загадка разгадана). Как указывает StriplingWarrior, нижняя граница сохраняется, если используются только сравнения, т.е. нет индексации памяти, см. Также: http://en.wikipedia.org/wiki/Element_distinctness_problem

// Linear time
char computeMode(String input) {
  // initialize currentMode to first char
  char[] chars = input.toCharArray();
  char currentMode = chars[0];
  int currentModeCount = 0;
  HashMap<Character, Integer> counts = new HashMap<Character, Integer>();
  for(char character : chars) {
    int count = putget(counts, character); // occurences so far
    // test whether character should be the new currentMode
    if(count > currentModeCount) {
      currentMode = character;
      currentModeCount = count; // also save the count
    }
  }
  return currentMode;
}

// Constant time
int putget(HashMap<Character, Integer> map, char character) {
  if(!map.containsKey(character)) {
    // if character not seen before, initialize to zero
    map.put(character, 0);
  }
 // increment
  int newValue = map.get(character) + 1;
  map.put(character, newValue);
  return newValue;
}

Ответы [ 3 ]

10 голосов
/ 12 ноября 2010

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

Однако, если бы числа выбирались вручную, чтобы всегда вызывать коллизии хешей, вы в конечном итоге фактически превратили бы свой хеш-набор в список, что превратило бы ваш алгоритм в O (n²). Как указывает автор, простая сортировка значений в списке вначале обеспечивает лучший гарантированный алгоритм, хотя в большинстве случаев предпочтителен хэш-набор.

2 голосов
/ 13 ноября 2010

Поиск в хэш-таблице представляет собой амортизированное постоянное время, т. Е. В целом общая стоимость поиска n случайных ключей составляет O (n).В худшем случае они могут быть линейными.Следовательно, хотя в целом они могли бы уменьшить порядок расчета режима до O (n), в худшем случае он увеличит порядок расчета режима до O (n ^ 2).

2 голосов
/ 12 ноября 2010

Итак, что мне не хватает в моем понимании проблемы?

Во многих частных случаях достаточно массива или хеш-таблицы. В «общем случае» это не так, потому что доступ к хеш-таблице не всегда постоянное время.

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

...