Frage Längste Teilsequenz mit gleichem Abstand


Ich habe eine Million Integer in sortierter Reihenfolge und ich möchte die längste Subsequenz finden, wo die Differenz zwischen aufeinanderfolgenden Paaren gleich ist. Beispielsweise

1, 4, 5, 7, 8, 12

hat eine Teilfolge

   4,       8, 12

Meine naive Methode ist gierig und prüft nur, wie weit Sie von jedem Punkt aus eine Teilsequenz verlängern können. Das dauert O(n²) Zeit pro Punkt scheint es.

Gibt es einen schnelleren Weg, um dieses Problem zu lösen?

Aktualisieren. Ich werde den in den Antworten angegebenen Code so schnell wie möglich testen (danke). Es ist jedoch bereits klar, dass die Verwendung von n ^ 2 Speicher nicht funktioniert. Bisher gibt es keinen Code, der mit der Eingabe als beendet wird [random.randint(0,100000) for r in xrange(200000)] .

Zeiten.  Ich habe mit folgenden Eingabedaten an meinem 32 Bit System getestet.

a= [random.randint(0,10000) for r in xrange(20000)] 
a.sort()
  • Die dynamische Programmiermethode von ZelluX benötigt 1.6G RAM und dauert 2 Minuten und 14 Sekunden. Mit Pypy dauert es nur 9 Sekunden! Bei großen Eingaben stürzt es jedoch mit einem Speicherfehler ab.
  • Die O (nd) time Methode von Armin benötigte 9 Sekunden mit Pypy aber nur 20MB RAM. Natürlich wäre dies viel schlimmer, wenn die Reichweite viel größer wäre. Die geringe Speichernutzung bedeutete, dass ich es auch mit a = [random.randint (0,100000) für r in xrange (200000)] testen konnte, aber es endete nicht in den wenigen Minuten, die ich es mit Pypy gab.

Um die Methode von Kluev testen zu können, ran ich mit

a= [random.randint(0,40000) for r in xrange(28000)] 
a = list(set(a))
a.sort()

um eine Längenliste grob zu machen 20000. Alle Zeiten mit Pypy

  • ZelluX, 9 Sekunden
  • Klüv, 20 Sekunden
  • Armin, 52 Sekunden

Es scheint, dass, wenn die ZelluX-Methode linearer Raum gemacht werden könnte, sie der klare Gewinner wäre.


76
2017-08-10 07:59


Ursprung


Antworten:


Aktualisieren: Der erste Algorithmus, der hier beschrieben wird, wird durch veraltet Armin Rigo's zweite Antwort, das ist viel einfacher und effizienter. Beide Methoden haben jedoch einen Nachteil. Sie benötigen viele Stunden, um das Ergebnis für eine Million Ganzzahlen zu finden. Also habe ich zwei weitere Varianten ausprobiert (siehe zweite Hälfte dieser Antwort), bei denen angenommen wird, dass der Bereich der Eingabe-Ganzzahlen begrenzt ist. Eine solche Beschränkung ermöglicht viel schnellere Algorithmen. Ich habe auch versucht, den Code von Armin Rigo zu optimieren. Sehen Sie meine Benchmarking-Ergebnisse am Ende.


Hier ist eine Idee des Algorithmus mit O (N) Speicher. Die Zeitkomplexität ist O (N2 log N), kann aber auf O (N2).

Algorithmus verwendet die folgenden Datenstrukturen:

  1. prev: Array von Indizes, die auf das vorherige Element der (möglicherweise unvollständigen) Subsequenz zeigen.
  2. hash: hashmap with key = Unterschied zwischen aufeinanderfolgenden Paaren in Teilfolge und Wert = zwei andere hashmaps. Für diese anderen Hashmaps: Schlüssel = Anfangs- / Endindex der Untersequenz, Wert = Paar von (Untersequenzlänge, Ende / Anfangsindex der Untersequenz).
  3. pq: Prioritätswarteschlange für alle möglichen "Differenz" -Werte für Untersequenzen, die in gespeichert sind prev und hash.

Algorithmus:

  1. Initialisieren prev mit Indizes i-1. Aktualisieren hash und pq um alle (unvollständigen) Teilsequenzen, die in diesem Schritt gefunden wurden, und ihre "Unterschiede" zu registrieren.
  2. Erhalte (und entferne) die kleinste "Differenz" von pq. Erhalte den entsprechenden Datensatz von hash und scannen Sie eine der Hash-Karten der zweiten Ebene. Zu diesem Zeitpunkt sind alle Teilfolgen mit gegebener "Differenz" abgeschlossen. Wenn die Hash-Map der zweiten Ebene die Länge der Subsequenz besser als die bisher gefundene enthält, aktualisieren Sie das beste Ergebnis.
  3. Im Array prev: Dekrementiere Index und Aktualisierung für jedes Element einer beliebigen Sequenz, die in Schritt 2 gefunden wurde hash und möglicherweise pq. Während der Aktualisierung hash, könnten wir eine der folgenden Operationen ausführen: Fügen Sie eine neue Subsequenz der Länge 1 hinzu oder erweitern Sie eine vorhandene Subsequenz um 1 oder fügen Sie zwei vorhandene Subsequenzen zusammen.
  4. Entfernen Sie den Hash-Karten-Datensatz, der in Schritt 2 gefunden wurde.
  5. Fahren Sie mit Schritt # 2 fort pq ist nicht leer.

Dieser Algorithmus aktualisiert O (N) Elemente von prev O (N) mal jeder. Und für jedes dieser Updates muss möglicherweise eine neue "Differenz" hinzugefügt werden pq. All dies bedeutet Zeitkomplexität von O (N2 log N) wenn wir eine einfache Heap-Implementierung für verwenden pq. Um es auf O (N2) können wir erweiterte Warteschlangenimplementierungen verwenden. Einige der Möglichkeiten sind auf dieser Seite aufgelistet: Prioritätswarteschlangen.

Siehe entsprechenden Python-Code auf Ideone. Dieser Code lässt keine doppelten Elemente in der Liste zu. Es ist möglich, dies zu beheben, aber es wäre sowieso eine gute Optimierung, Duplikate zu entfernen (und die längste Teilsequenz getrennt von Duplikaten zu finden).

Und der gleiche Code nach ein wenig Optimierung. Hier wird die Suche beendet, sobald die Untersequenzlänge multipliziert mit der möglichen Untersequenz "Differenz" den Quelllistenbereich überschreitet.


Armin Rigos Code ist einfach und ziemlich effizient. In einigen Fällen werden jedoch zusätzliche Berechnungen ausgeführt, die möglicherweise vermieden werden. Die Suche kann beendet werden, sobald die Untersequenzlänge multipliziert mit der möglichen Untersequenz "Differenz" den Quelllistenbereich überschreitet:

def findLESS(A):
  Aset = set(A)
  lmax = 2
  d = 1
  minStep = 0

  while (lmax - 1) * minStep <= A[-1] - A[0]:
    minStep = A[-1] - A[0] + 1
    for j, b in enumerate(A):
      if j+d < len(A):
        a = A[j+d]
        step = a - b
        minStep = min(minStep, step)
        if a + step in Aset and b - step not in Aset:
          c = a + step
          count = 3
          while c + step in Aset:
            c += step
            count += 1
          if count > lmax:
            lmax = count
    d += 1

  return lmax

print(findLESS([1, 4, 5, 7, 8, 12]))

Wenn der Bereich der ganzen Zahlen in den Quelldaten (M) klein ist, ist ein einfacher Algorithmus mit O (M2) Zeit und O (M) Raum:

def findLESS(src):
  r = [False for i in range(src[-1]+1)]
  for x in src:
    r[x] = True

  d = 1
  best = 1

  while best * d < len(r):
    for s in range(d):
      l = 0

      for i in range(s, len(r), d):
        if r[i]:
          l += 1
          best = max(best, l)
        else:
          l = 0

    d += 1

  return best


print(findLESS([1, 4, 5, 7, 8, 12]))

Es ähnelt der ersten Methode von Armin Rigo, verwendet jedoch keine dynamischen Datenstrukturen. Ich nehme an, Quelldaten haben keine Duplikate. Und (um den Code einfach zu halten) nehme ich auch an, dass der minimale Eingabewert nicht negativ ist und nahe bei Null liegt.


Der vorherige Algorithmus kann verbessert werden, wenn statt des Booleschen Arrays eine Bitset-Datenstruktur und bitweise Operationen verwendet werden, um Daten parallel zu verarbeiten. Der unten gezeigte Code implementiert Bitset als eine integrierte Python-Ganzzahl. Es hat die gleichen Annahmen: keine Duplikate, der minimale Eingabewert ist nicht negativ und nahe bei Null. Die Zeitkomplexität ist O (M2 * log L) wobei L die Länge der optimalen Teilfolge ist, ist die Raumkomplexität O (M):

def findLESS(src):
  r = 0
  for x in src:
    r |= 1 << x

  d = 1
  best = 1

  while best * d < src[-1] + 1:
    c = best
    rr = r

    while c & (c-1):
      cc = c & -c
      rr &= rr >> (cc * d)
      c &= c-1

    while c != 1:
      c = c >> 1
      rr &= rr >> (c * d)

    rr &= rr >> d

    while rr:
      rr &= rr >> d
      best += 1

    d += 1

  return best

Benchmarks:

Eingabedaten (ungefähr 100000 Ganzzahlen) werden auf diese Weise generiert:

random.seed(42)
s = sorted(list(set([random.randint(0,200000) for r in xrange(140000)])))

Und für schnellste Algorithmen habe ich auch folgende Daten verwendet (ca. 1000000 Integer):

s = sorted(list(set([random.randint(0,2000000) for r in xrange(1400000)])))

Alle Ergebnisse zeigen die Zeit in Sekunden an:

Size:                         100000   1000000
Second answer by Armin Rigo:     634         ?
By Armin Rigo, optimized:         64     >5000
O(M^2) algorithm:                 53      2940
O(M^2*L) algorithm:                7       711

11
2017-08-11 10:08



Wir können eine Lösung haben O(n*m) in der Zeit mit sehr wenig Speicherbedarf, indem Sie Ihre anpassen. Hier nist die Anzahl der Elemente in der angegebenen Eingabefolge von Zahlen und m ist der Bereich, d.h. die höchste Anzahl minus die niedrigste.

Rufen Sie A die Reihenfolge aller eingegebenen Zahlen auf (und verwenden Sie ein vorberechnetes set() die Frage "Ist diese Zahl in A?" in konstanter Zeit zu beantworten. Ruf d an Schritt der Untersequenz, nach der wir suchen (der Unterschied zwischen zwei Zahlen dieser Untersequenz). Führen Sie für jeden möglichen Wert von d den folgenden linearen Scan über alle Eingangsnummern durch: Für jede Zahl n von A in aufsteigender Reihenfolge, wenn die Nummer noch nicht gesehen wurde, schauen Sie in A nach der Länge der Sequenz, beginnend bei n mit a Schritt d. Markieren Sie dann alle Elemente in dieser Reihenfolge, wie bereits gesehen, so dass wir vermeiden, erneut nach ihnen zu suchen, für das gleiche d. Aus diesem Grund ist die Komplexität einfach O(n) für jeden Wert von d.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

for d in range(1, 12):
    already_seen = set()
    for a in A:
        if a not in already_seen:
            b = a
            count = 1
            while b + d in Aset:
                b += d
                count += 1
                already_seen.add(b)
            print "found %d items in %d .. %d" % (count, a, b)
            # collect here the largest 'count'

Aktualisierung:

  • Diese Lösung ist möglicherweise gut genug, wenn Sie nur an Werten von d interessiert sind, die relativ klein sind. zum Beispiel, wenn Sie das beste Ergebnis erhalten d <= 1000 wäre gut genug. Dann geht die Komplexität auf O(n*1000). Dies macht den Algorithmus approximativ, aber tatsächlich lauffähig n=1000000. (Gemessen bei 400-500 Sekunden mit CPython, 80-90 Sekunden mit PyPy, mit einer zufälligen Teilmenge von Zahlen zwischen 0 und 10'000'000.)

  • Wenn Sie immer noch nach dem gesamten Bereich suchen möchten, und wenn der häufigste Fall darin besteht, dass lange Sequenzen existieren, ist eine bemerkenswerte Verbesserung zu stoppen, sobald d zu groß ist, um eine noch längere Sequenz zu finden.


19
2017-08-10 10:40



UPDATE: Ich habe ein Papier zu diesem Problem gefunden, das Sie herunterladen können Hier.

Hier ist eine Lösung basierend auf dynamischer Programmierung. Es erfordert eine O (n ^ 2) -Zeitkomplexität und eine O (n ^ 2) -Komplexität und verwendet kein Hashing.

Wir nehmen an, dass alle Zahlen in einem Array gespeichert sind a in aufsteigender Reihenfolge und n spart seine Länge. 2D-Array l[i][j] Definiert die Länge der längsten gleich beabstandeten Subsequenz, die mit endet a[i] und a[j], und l[j][k] = l[i][j] + 1 wenn a[j] - a[i] = a[k] - a[j] (i <j <k).

lmax = 2
l = [[2 for i in xrange(n)] for j in xrange(n)]
for mid in xrange(n - 1):
    prev = mid - 1
    succ = mid + 1
    while (prev >= 0 and succ < n):
        if a[prev] + a[succ] < a[mid] * 2:
            succ += 1
        elif a[prev] + a[succ] > a[mid] * 2:
            prev -= 1
        else:
            l[mid][succ] = l[prev][mid] + 1
            lmax = max(lmax, l[mid][succ])
            prev -= 1
            succ += 1

print lmax

12
2017-08-11 16:34



Algorithmus

  • Hauptschleife durchquert die Liste
  • Wenn die Nummer in der Vorberechnungsliste gefunden wird und dann zu allen Sequenzen gehört, die sich in dieser Liste befinden, berechnen Sie alle Sequenzen mit der Anzahl + 1 neu
  • Entfernen Sie alle für das aktuelle Element vorausberechneten Elemente
  • Berechnen Sie neue Sequenzen neu, wobei das erste Element im Bereich von 0 bis aktuell liegt und das zweite Element das aktuelle Element der Traversierung ist (eigentlich nicht von 0 bis aktuell), können wir das neue Element nicht mehr als max (a) und neu verwenden Liste sollte Möglichkeit haben, länger zu werden, die bereits einen gefunden hat)

Also für die Liste [1, 2, 4, 5, 7] Ausgabe wäre (es ist ein wenig chaotisch, versuchen Sie es selbst und sehen)

  • Index 0, Element 1:
    • ob 1 in vorcalc? Nein - nichts tun
    • Nichts tun
  • Index 1, Element 2:
    • ob 2 in vorcalc? Nein - nichts tun
    • Überprüfen Sie, ob 3 = 1 + (2 - 1) * 2 in unserem Set? Nein - nichts tun
  • Index 2, Element 4:
    • ob 4 in vorcalc? Nein - nichts tun
      • überprüfe ob 6 = 2 + (4 - 2) * 2 in unserem Set? Nein
      • überprüfe ob 7 = 1 + (4 - 1) * 2 in unserem Set? Ja - neues Element hinzufügen {7: {3: {'count': 2, 'start': 1}}}  7 - Element der Liste, 3 ist Schritt.
  • Index 3, Element 5:
    • ob 5 in vorcalc? Nein - nichts tun
      • nicht prüfen 4 weil 6 = 4 + (5 - 4) * 2 ist weniger als das berechnete Element 7
      • überprüfe ob 8 = 2 + (5 - 2) * 2 in unserem Set? Nein
      • prüfen 10 = 2 + (5 - 1) * 2 - mehr als max (a) == 7
  • Index 4, Element 7:
    • ob 7 in vorcalc? Ja - setze es in das Ergebnis
      • nicht prüfen 5 weil 9 = 5 + (7 - 5) * 2 ist mehr als max (a) == 7

result = (3, {'count': 3, 'start': 1}) # Schritt 3, Zähle 3, starte 1, verwandle es in Sequenz

Komplexität

Es sollte nicht mehr als O (N ^ 2) sein, und ich denke, es ist weniger wegen der früheren Beendigung der Suche nach neuen Sequenzen, ich werde versuchen, später eine detaillierte Analyse zu liefern

Code

def add_precalc(precalc, start, step, count, res, N):
    if step == 0: return True
    if start + step * res[1]["count"] > N: return False

    x = start + step * count
    if x > N or x < 0: return False

    if precalc[x] is None: return True

    if step not in precalc[x]:
        precalc[x][step] = {"start":start, "count":count}

    return True

def work(a):
    precalc = [None] * (max(a) + 1)
    for x in a: precalc[x] = {}
    N, m = max(a), 0
    ind = {x:i for i, x in enumerate(a)}

    res = (0, {"start":0, "count":0})
    for i, x in enumerate(a):
        for el in precalc[x].iteritems():
            el[1]["count"] += 1
            if el[1]["count"] > res[1]["count"]: res = el
            add_precalc(precalc, el[1]["start"], el[0], el[1]["count"], res, N)
            t = el[1]["start"] + el[0] * el[1]["count"]
            if t in ind and ind[t] > m:
                m = ind[t]
        precalc[x] = None

        for y in a[i - m - 1::-1]:
            if not add_precalc(precalc, y, x - y, 2, res, N): break

    return [x * res[0] + res[1]["start"] for x in range(res[1]["count"])]

3
2017-08-10 09:28



Hier ist eine andere Antwort, arbeiten in der Zeit O(n^2) und ohne nennenswerte Speicheranforderungen jenseits der Umwandlung der Liste in eine Menge.

Die Idee ist ziemlich naiv: Wie das Original - Poster ist es gierig und prüft nur, wie weit man von jedem Punktepaar eine Teilfolge verlängern kann - allerdings zuerst, ob wir auf der Anfang einer Teilfolge. Mit anderen Worten, von Punkten a und b Sie prüfen, wie weit Sie verlängern können b + (b-a), b + 2*(b-a), ... aber nur wenn a - (b-a) ist nicht schon in der Menge aller Punkte. Wenn dies der Fall ist, haben Sie bereits die gleiche Subsequenz gesehen.

Der Trick ist, uns davon zu überzeugen, dass diese einfache Optimierung ausreicht, um die Komplexität zu reduzieren O(n^2) vom Original O(n^3). Das ist eine Übung für den Leser :-) Die Zeit ist wettbewerbsfähig mit anderen O(n^2) Lösungen hier.

A = [1, 4, 5, 7, 8, 12]    # in sorted order
Aset = set(A)

lmax = 2
for j, b in enumerate(A):
    for i in range(j):
        a = A[i]
        step = b - a
        if b + step in Aset and a - step not in Aset:
            c = b + step
            count = 3
            while c + step in Aset:
                c += step
                count += 1
            #print "found %d items in %d .. %d" % (count, a, c)
            if count > lmax:
                lmax = count

print lmax

3
2017-08-15 06:25



Ihre Lösung ist O(N^3) jetzt (du sagtest O(N^2) per index). Hier ist es O(N^2) der Zeit und O(N^2) der Speicherlösung.

Idee

Wenn wir Subsequenz kennen, die durch Indizes geht i[0],i[1],i[2],i[3] Wir sollten keine Teilsequenz versuchen, die mit beginnt i[1] und i[2] oder i[2] und i[3]

Hinweis: Ich habe diesen Code bearbeitet, um die Verwendung dieses Codes zu vereinfachen a sortiert, aber es funktioniert nicht für gleiche Elemente. Sie können die Anzahl der maximalen Anzahl der gleichen Elemente in überprüfen O(N) leicht

Pseudocode

Ich suche nur nach maximaler Länge, aber das ändert nichts

whereInA = {}
for i in range(n):
   whereInA[a[i]] = i; // It doesn't matter which of same elements it points to

boolean usedPairs[n][n];

for i in range(n):
    for j in range(i + 1, n):
       if usedPair[i][j]:
          continue; // do not do anything. It was in one of prev sequences.

    usedPair[i][j] = true;

    //here quite stupid solution:
    diff = a[j] - a[i];
    if diff == 0:
       continue; // we can't work with that
    lastIndex = j
    currentLen = 2
    while whereInA contains index a[lastIndex] + diff :
        nextIndex = whereInA[a[lastIndex] + diff]
        usedPair[lastIndex][nextIndex] = true
        ++currentLen
        lastIndex = nextIndex

    // you may store all indicies here
    maxLen = max(maxLen, currentLen)

Gedanken zur Speichernutzung

O(n^2) Zeit ist sehr langsam für 1000000 Elemente. Aber wenn Sie diesen Code für eine solche Anzahl von Elementen ausführen, ist das größte Problem die Speichernutzung.
Was kann getan werden, um es zu reduzieren?

  • Ändern Sie boolesche Arrays in Bitfelder, um mehr boolesche Werte pro Bit zu speichern.
  • Machen Sie jedes nächste boolesche Array kürzer, weil wir es nur verwenden usedPairs[i][j] ob i < j

Wenige Heuristiken:

  • Speichere nur paarweise verwendete Indices. (Konflikte mit der ersten Idee)
  • Entfernen Sie usedPairs, die nie mehr verwendet werden (das sind für solche i,j das war schon in der Schleife gewählt)

2
2017-08-10 09:20



Das sind meine 2 Cent.

Wenn Sie eine Liste namens input haben:

input = [1, 4, 5, 7, 8, 12]

Sie können eine Datenstruktur erstellen, die für jeden dieser Punkte (mit Ausnahme des ersten) angibt, wie weit dieser Punkt von einem seiner Vorgänger entfernt ist:

[1, 4, 5, 7, 8, 12]
 x  3  4  6  7  11   # distance from point i to point 0
 x  x  1  3  4   8   # distance from point i to point 1
 x  x  x  2  3   7   # distance from point i to point 2
 x  x  x  x  1   5   # distance from point i to point 3
 x  x  x  x  x   4   # distance from point i to point 4

Jetzt, wo Sie die Spalten haben, können Sie die i-th Eingabeelement (das ist input[i]) und jede Zahl n in seiner Spalte.

Die Zahlen, die zu einer Reihe von äquidistanten Zahlen gehören, einschließlich input[i], sind diejenigen, die haben n * j in dem i-th Position ihrer Spalte, wo j ist die Anzahl der Übereinstimmungen, die bereits beim Verschieben von Spalten von links nach rechts gefunden wurden k-th Vorgänger von input[i], woher k ist der Index von n in der Spalte von input[i].

Beispiel: wenn wir darüber nachdenken i = 1, input[i] = 4, n = 3dann können wir ein Sequenzverständnis identifizieren 4 (input[i]), 7 (weil es eine hat 3 in Position 1 seiner Spalte) und 1, weil k ist 0, also nehmen wir den ersten Vorgänger von i.

Mögliche Implementierung (tut mir leid, wenn der Code nicht die gleiche Notation wie die Erklärung verwendet):

def build_columns(l):
    columns = {}
    for x in l[1:]:
        col = []
        for y in l[:l.index(x)]:
            col.append(x - y)
        columns[x] = col
    return columns

def algo(input, columns):
    seqs = []
    for index1, number in enumerate(input[1:]):
        index1 += 1 #first item was sliced
        for index2, distance in enumerate(columns[number]):
            seq = []
            seq.append(input[index2]) # k-th pred
            seq.append(number)
            matches = 1
            for successor in input[index1 + 1 :]:
                column = columns[successor]
                if column[index1] == distance * matches:
                    matches += 1
                    seq.append(successor)
            if (len(seq) > 2):
                seqs.append(seq)
    return seqs

Der längste:

print max(sequences, key=len)

1
2017-08-10 21:46



Durchstreichen Sie das Array und halten Sie eine Aufzeichnung des optimalen Ergebnisses und einer Tabelle mit

(1) Index - der Elementunterschied in der Reihenfolge,
(2) count - Anzahl der Elemente in der bisherigen Sequenz und
(3) das zuletzt aufgezeichnete Element

Untersuchen Sie für jedes Array-Element die Differenz von jedem vorherigen Array-Element. Wenn dieses Element das letzte in einer Sequenz ist, die in der Tabelle indiziert ist, passe diese Sequenz in der Tabelle an und aktualisiere die beste Sequenz, falls anwendbar, andernfalls starte eine neue Sequenz, außer das aktuelle Maximum ist größer als die Länge der möglichen Sequenz.

Wenn wir rückwärts scannen, können wir den Scan stoppen, wenn d größer als die Mitte des Array-Bereichs ist. oder wenn das aktuelle Maximum größer als die Länge der möglichen Sequenz ist, für d größer als die größte indizierte Differenz. Sequenzen wo s[j] größer als das letzte Element in der Sequenz ist gelöscht.

Ich habe meinen Code von JavaScript in Python konvertiert (mein erster Python-Code):

import random
import timeit
import sys

#s = [1,4,5,7,8,12]
#s = [2, 6, 7, 10, 13, 14, 17, 18, 21, 22, 23, 25, 28, 32, 39, 40, 41, 44, 45, 46, 49, 50, 51, 52, 53, 63, 66, 67, 68, 69, 71, 72, 74, 75, 76, 79, 80, 82, 86, 95, 97, 101, 110, 111, 112, 114, 115, 120, 124, 125, 129, 131, 132, 136, 137, 138, 139, 140, 144, 145, 147, 151, 153, 157, 159, 161, 163, 165, 169, 172, 173, 175, 178, 179, 182, 185, 186, 188, 195]
#s = [0, 6, 7, 10, 11, 12, 16, 18, 19]

m = [random.randint(1,40000) for r in xrange(20000)]
s = list(set(m))
s.sort()

lenS = len(s)
halfRange = (s[lenS-1] - s[0]) // 2

while s[lenS-1] - s[lenS-2] > halfRange:
    s.pop()
    lenS -= 1
    halfRange = (s[lenS-1] - s[0]) // 2

while s[1] - s[0] > halfRange:
    s.pop(0)
    lenS -=1
    halfRange = (s[lenS-1] - s[0]) // 2

n = lenS

largest = (s[n-1] - s[0]) // 2
#largest = 1000 #set the maximum size of d searched

maxS = s[n-1]
maxD = 0
maxSeq = 0
hCount = [None]*(largest + 1)
hLast = [None]*(largest + 1)
best = {}

start = timeit.default_timer()

for i in range(1,n):

    sys.stdout.write(repr(i)+"\r")

    for j in range(i-1,-1,-1):
        d = s[i] - s[j]
        numLeft = n - i
        if d != 0:
            maxPossible = (maxS - s[i]) // d + 2
        else:
            maxPossible = numLeft + 2
        ok = numLeft + 2 > maxSeq and maxPossible > maxSeq

        if d > largest or (d > maxD and not ok):
            break

        if hLast[d] != None:
            found = False
            for k in range (len(hLast[d])-1,-1,-1):
                tmpLast = hLast[d][k]
                if tmpLast == j:
                    found = True
                    hLast[d][k] = i
                    hCount[d][k] += 1
                    tmpCount = hCount[d][k]
                    if tmpCount > maxSeq:
                        maxSeq = tmpCount
                        best = {'len': tmpCount, 'd': d, 'last': i}
                elif s[tmpLast] < s[j]:
                    del hLast[d][k]
                    del hCount[d][k]
            if not found and ok:
                hLast[d].append(i)
                hCount[d].append(2)
        elif ok:
            if d > maxD: 
                maxD = d
            hLast[d] = [i]
            hCount[d] = [2]


end = timeit.default_timer()
seconds = (end - start)

#print (hCount)
#print (hLast)
print(best)
print(seconds)

0
2017-08-20 15:27



Dies ist ein besonderer Fall für das allgemeinere Problem, das hier beschrieben wird: Entdecke lange Muster wo K = 1 und fest ist. Es wird dort gezeigt, dass es in O (N ^ 2) gelöst werden kann. Runnig meine Implementierung des C-Algorithmus vorgeschlagen dort dauert es 3 Sekunden, um die Lösung für N = 20000 und M = 28000 in meiner 32-Bit-Maschine zu finden.


0
2018-02-25 04:12