Обнаружение повторения с бесконечным вводом

StackOverflow https://stackoverflow.com/questions/2279568

Вопрос

Какой наиболее оптимальный способ найти повторение в бесконечной последовательности целых чисел?

то естьесли в бесконечной последовательности число «5» появляется дважды, мы вернем «ложь» в первый раз и «истина» во второй раз.

В конце концов, нам нужна функция, которая возвращает «истину», если целое число появилось раньше, и «ложь», если функция получила целое число в первый раз.

Если есть два решения: одно пространственное, второе временное, укажите оба.Я напишу свое решение в ответах, но не думаю, что оно оптимальное.

редактировать:Пожалуйста, не принимайте во внимание тривиальные случаи (т.никаких повторений, постоянно возрастающая последовательность).Меня интересует, как уменьшить пространственную сложность нетривиального случая (случайные числа с повторениями).

Это было полезно?

Решение

Я бы использовал следующий подход:

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

Если n — количество элементов в последовательности от начала до повторения, то для этого требуется всего O(n) времени и пространства.Временная сложность оптимальна, так как вам нужно как минимум прочитать элементы входной последовательности до точки повторения.

О какой продолжительности последовательности мы говорим (до того, как произойдет повторение)?Гарантировано ли вообще повторение?В крайних случаях сложность пространства может стать проблематичной.Но чтобы улучшить его, вам, вероятно, понадобится больше структурной информации о вашей последовательности.

Обновлять:Если последовательность, как вы говорите, очень длинная с редкими повторениями, и вам нужно сократить занимаемое пространство, то вы могли бы (при наличии достаточной структурной информации о последовательности) сократить затраты на пространство.

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

Другие советы

BitSet для значений int (2^32 чисел) будет занимать 512 МБ.Это может быть нормально, если наборы битов выделяются не часто, достаточно быстро и память доступна.

Альтернативой являются сжатые наборы битов которые лучше всего работают для разреженных BitSets.

На самом деле, если максимальное количество значений бесконечно, вы можете использовать любой алгоритм сжатия без потерь для монохромного растрового изображения.ЕСЛИ вы представляете себе квадрат, в котором по крайней мере столько пикселей, сколько возможных значений, вы можете сопоставить каждое значение с пикселем (оставив несколько лишних).Затем вы можете представить белый цвет как появившиеся пиксели и черный цвет остальных и использовать любой алгоритм сжатия, если пространство ограничено (это, безусловно, проблема, которая изучалась).

Вы также можете хранить блоки.В худшем случае то же самое происходит в пространстве O(n), но для этого худшего случая вам нужно, чтобы между появившимися числами была ровно 1.Как только появятся новые цифры, объем памяти уменьшится:Я напишу псевдокод и буду использовать список, но вы всегда можете использовать другую структуру.

List changes // global

boolean addNumber(int number):
  boolean appeared = false
  it = changes.begin()
  while it.hasNext():
    if it.get() < number:
      appeared != appeared
      it = it.next()
    else if it.get() == number:
      if !appeared: return true
      if it.next().get() == number + 1
        it.next().remove() // Join 2 blocks 
      else 
        it.insertAfter(number + 1)  // Insert split and create 2 blocks
      it.remove()
        return false
    else: // it.get() > number
      if appeared: return true
      it.insertBefore(number)
      if it.get() == number + 1:
        it.remove() // Extend next block
      else:
        it.insertBefore(number + 1)  
  }
  return false
}

Что представляет собой этот код:он хранит список блоков.Для каждого добавляемого числа он перебирает список, сохраняя блоки появившихся и не появившихся чисел.Позвольте мне проиллюстрировать это примером;Добавлю [) для иллюстрации какие числа в блоке, первое число входит, последнее нет. В псевдокоде оно заменяется на логическое appeared.Например, если вы получите 5, 9, 6, 8, 7 (в этом порядке), после каждой функции у вас будут следующие последовательности:

[5,6)

[5,6),[9,10)

[5,7),[9,10)

[5,7),[8,10)

[5,10)

В последнем значении вы сохраняете блок из 5 чисел, в котором только 2.

Вернуть ИСТИНА

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

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

Что ж, кажется очевидным, что в любом решении нам нужно будет сохранять уже появившиеся числа, поэтому с точки зрения пространства мы будем всегда имеют наихудший случай O(N), где N<=возможных чисел с размером слова нашего числового типа (т.е.2^32 для C# int) — это проблематично в течение длительного времени, если последовательность действительно бесконечна/редко повторяется.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top