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

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

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

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

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

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

Источник

5 ответов

Решение

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

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

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

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

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

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

Источник

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

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

Источник

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

Вы также можете хранить блоки. Наихудший случай такой же в пространстве 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<= возможные числа с размером слова нашего числа. type (т.е. 2^32 для C# int) - это проблематично в течение длительного времени, если последовательность действительно бесконечна / редко повторяется.

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

Источник

Возврат ИСТИНА

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

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

Источник
Другие вопросы по тегам