Erfassen Wiederholung mit unendlichem Eingang

Question

Was ist der optimale Weg, Wiederholung in einer unendlichen Folge von ganzen Zahlen zu finden?

d. wenn in der unendlichen Folge die Zahl ‚5‘ zweimal erscheint dann werden wir zurückkehren ‚false‘ das erste Mal und ‚true‘ zum zweiten Mal.

Am Ende, was wir brauchen, ist eine Funktion, die gibt ‚true‘, wenn die ganze Zahl erschien vor und ‚falsch‘, wenn die Funktion des ganzzahlige erstes Mal empfangen werden.

Wenn es zwei Lösungen, eine platz weise und die zweite ist zeitweise, dann beide erwähnen. Ich werde meine Lösung in den Antworten schreiben, aber ich glaube nicht, dass die optimale ist.

edit: Gehen Sie nicht davon die trivialen Fälle (das heißt keine Wiederholungen, eine stetig steigende Sequenz). Was mich interessiert, ist, wie die Speicherkomplexität der nicht-trivialen Fall (Zufallszahlen mit Wiederholungen) zu reduzieren.

Answer 1

würde ich den folgenden Ansatz verwenden:

Verwenden Sie eine Hash-Tabelle als Datenstruktur. Für jede Zahl lesen, speichern Sie es in Ihrer Datenstruktur. Wenn es bereits gespeichert, bevor Sie eine Wiederholung gefunden.

Wenn n die Anzahl der Elemente in der Reihenfolge vom Anfang der Wiederholung ist, dann erfordert dies nur O (n) Zeit und Raum. Zeitkomplexität ist optimal, da Sie benötigen mindestens lesen die Elemente der Eingangssequenz der Wiederholung Punkt.

Wie lange eine Folge sprechen wir (vor der Wiederholung auftritt)? Ist eine Wiederholung überhaupt gewährleistet? Bei extremen Fällen kann die Speicherkomplexität problematisch werden. Aber um es zu verbessern Sie wahrscheinlich brauchen mehr strukturelle Informationen über die Sequenz kennen.

Update: Wenn die Sequenz ist, wie Sie sehr lange sagen, mit selten Wiederholungen und Sie haben auf den Platzbedarf zu reduzieren, dann könnten Sie (ausreichende strukturelle Informationen zu der angegebenen Reihenfolge) in der Lage sein, die Raumkosten zu senken.

Als Beispiel: Angenommen, Sie wissen, dass Ihre unendliche Folge eine allgemeine Tendenz hat Zahlen zurückzugeben, die von Zeugen min-max innerhalb des aktuellen Sortiment passen. Dann werden Sie schließlich ganze Intervalle haben, die bereits in der Sequenz enthalten sind. In diesem Fall können Sie Speicherplatz durch das Speichern solcher Intervalle anstatt alle darin enthaltenen Elemente speichern.

Answer 2

Ein BitSet für int-Werte (2 ^ 32 Zahlen) würde 512Mb verbrauchen. Diese Ordnung sein kann, wenn die BitSets zugeordnet sind nicht zu oft, schnell genug und die mem verfügbar ist.

Eine Alternative sind komprimierte BitSets , dass die Arbeit am besten für spärliche BitSets.

Answer 3

Eigentlich, wenn die maximale Anzahl der Werte unendlich ist, können Sie einen beliebigen lossless Komprimierungsalgorithmus für eine monochrome Bitmap verwenden. so viele Pixel wie die Anzahl der möglichen Werte, wenn Sie ein Quadrat mit zumindest vorstellen, Sie jeden Wert auf ein Pixel abbilden kann (mit wenigen bis Ersatz). Dann kann Sie wissen, wie die Pixel darstellen, die erschienen und schwarz für die andere und die Verwendung jeden Kompressionsalgorithmus, wenn Raum an einer Prämie ist (das ist sicherlich ein Problem, das untersucht wurde)

Sie können auch Blöcke speichern. Der schlimmste Fall ist das gleiche im Raum O (n), aber für den schlimmsten Fall müssen Sie, dass die Zahl erschien genau 1 zwischen ihnen. Einmal mehr Zahlen erscheinen, dann verringert sich die Lagerung: Ich werde Pseudo-Code schreiben und ich werde eine Liste verwenden, aber man kann immer eine andere Struktur verwenden

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
}

Was dieser Code ist die folgende: Es speichert eine Liste von Blöcken. Für jede Zahl, die Sie hinzufügen, iteriert er die Liste zu speichern Blöcke von Zahlen über die erschienen und Zahlen, die dies nicht taten. Lassen Sie mich mit einem Beispiel veranschaulichen; Ich will hinzufügen [), auf die Zahlen im Block veranschaulichen, die erste Zahl enthalten ist, die letzte not.In der Pseudo-Code ist es durch die boolean appeared ersetzt wird. Zum Beispiel, wenn Sie erhalten die 5, 9, 6, 8, 7 (in dieser Reihenfolge) die folgenden Sequenzen nach jeder Funktion haben:

[5,6)

[5,6), [9,10)

[5,7), [9,10)

[5,7), [8,10)

[5,10)

In dem letzten Wert halten Sie einen Block von 5 Zahlen mit nur 2.

Answer 4

Zurück TRUE

Wenn die Folge unendlich ist, dann wird es Wiederholung jeder denkbaren Muster sein.

Wenn das, was Sie wissen wollen, ist der erste Ort in der Folge, wenn eine wiederholte Ziffer ist, die eine andere Sache ist, aber es gibt einige Unterschiede zwischen Ihrer Frage und Ihrem Beispiel.

Answer 5

Nun, scheint es offensichtlich, dass in jeder Lösung werden wir die Zahlen speichern müssen, die bereits erschienen, so Raum weise werden wir immer hat eine Worst-Case von O (N), wobei N < = mögliche Zahlen mit dem Wort Größe unseres Nummerntypen (dh 2 ^ 32 für C # int) - dies ist problematisch über eine lange Zeit, wenn die Sequenz wirklich unendlich / selten wiederholt mich

.

Für die Zahlen speichern, die bereits erschienen ich eine Hash-Tabelle verwenden würde und es dann überprüfen Sie jedes Mal, wenn ich eine neue Nummer erhalten.