Fazit zuerst

• Wörterbücher sind schnell, verbrauchen aber mehr Speicher als Sie denken
• Die Floyd-Zirkulationserkennungsmethode ist $ O (N) $, aber ein konstantes Vielfaches (im Vergleich zu den beiden anderen) schwerer. Die Speichernutzung beträgt jedoch O (1)

Gegenstand

--Geben Sie eine Liste mit Ganzzahlen $ N $ und $ N + 1 $ Elementen -Das $ a $ -Element enthält mindestens eine Ganzzahl von 1 bis n. (Das heißt, nur eine Zahl enthält zwei) --State doppelte (zwei eingeschlossene) Ganzzahlen

Konkretes Beispiel

Beispiel: Sie können so etwas wie $ [3,1,3,4,2] $ eingeben. In diesem Fall antworten Sie mit $ 3 $. Beispiel: Sie können so etwas wie $ [1,3,2,1] $ eingeben. In diesem Fall antworten Sie mit $ 1 $. Beispiel: Sie können so etwas wie $ [1,1] $ eingeben. In diesem Fall antworten Sie mit $ 1 $.

Ansatz 1: Sortieren und lineare Erkundung

Der erste Ansatz des Helden

• (a) In aufsteigender Reihenfolge sortieren, (b) Von Anfang an linear arbeiten, um die Elemente zwei mal zwei zu betrachten und Duplikate zu finden

Der räumliche Berechnungsbetrag beträgt $ N $, aber der Zeitberechnungsbetrag kostet $ N log N $, um a und $ N $ zu b zu verarbeiten, und als Ergebnis ist der Berechnungsbetrag TLE.

from typing import List
def findDuplicate(nums: List[int]):
    nums.sort()
    for i in range(len(nums) -1):
        if nums[i] == nums[i+1]:
            return nums[i]
print(findDuplicate([1,1])) # -> 1
print(findDuplicate([3,1,3,4,2])) # -> 3

Ansatz 2: HashMap-Uh!

Schließlich verwendet die Hauptfigur HashMap-Uh! (Das heißt ein Wörterbuch), das Macht erfordert, die von ihm selbst nicht kontrolliert werden kann.

• (a) Initialisieren Sie zuerst das Wörterbuch. (b) Sehen Sie sich die Zahlen der Reihe nach an und, falls sie bereits im Wörterbuch vorhanden sind, die Anzahl der Duplikate
• (c) Notieren Sie den Wert als vorhanden, wenn sich die Zahl nicht überschneidet Infolgedessen tritt MLE (Memory Usage Error) auf.

Ich finde es dumm, aber es stimmt, dass Wörterbücher mehr Speicher als Elemente verwenden. Werfen wir einen Blick auf den folgenden Code.

from typing import List
from sys import getsizeof
def findDuplicate(nums: List[int]):
    used = dict()
    for x in nums:
        if x in used:
            size = getsizeof(used) + sum(map(getsizeof, used.values())) + sum(map(getsizeof, used.keys()))
            print("Memory:", size)
            return x
        used[x] = True
print(findDuplicate([1,1])) # -> 1
print(findDuplicate([3,1,3,4,2])) # -> 3
print(findDuplicate(list(range(1,1000000+1)) + [1000000]))

Wenn Sie dies tun,

Memory: 156 (Byte)
1
Memory: 184 (Byte)
3
Memory: 55100346 (Ungefähr 55 MByte)
1000000

Daher wird ein großer Speicher für die Anzahl der Elemente verwendet. Da der Speicher für die Eingabe von $ N = 10 ^ {6} $ $ 55M $ beträgt, beträgt die Datenmenge allein $ MLE $, wenn der Speicher $ 64M $ mit $ N = 2 \ cdot 10 ^ {6} $ ist. Es wird enden.

[Original] Ansatz 2 Kai: Nutzungsverlauf nach Liste aus dem Wörterbuch

Es stellt sich heraus, dass das Wörterbuch mehr Speicherplatz benötigt als ich erwartet hatte. Ein anderer Ansatz besteht darin, im Voraus ein Array von $ 1-N $ zu erstellen und zu vergleichen, ob es in $ False / True $ erscheint. Dieser Ansatz wird in späteren Experimenten zur Bewertung verwendet. Die Implementierung ist wie folgt.

def findDuplicate22(nums: List[int]):
    used = [False] * len(nums)
    for x in nums:
        if used[x]:
            return x
        used[x] = True

Ansatz 3: Floyd-Zirkulationserkennungsmethode

Hier kommt Senpai ins Spiel. Sempai schlägt kühl Floyds Algorithmus zur Zyklusfindung vor.

Zur Erklärung sollte dieser Fragensatz wie folgt gelesen werden. (Dies hat genau die gleichen Ein- und Ausgänge wie das ursprüngliche Problem)

――Es gibt n Städte auf dieser Welt, jede mit einem Teleporter.

• Geben Sie ein Array $ a $, das aus $ n + 1 $ Ganzzahlen besteht. Dieses Array enthält mindestens eine Ganzzahl von 1 bis n. (Das heißt, nur eine Zahl enthält zwei)
• Jetzt bist du in Stadt 0.
• Wenn Sie sich in der Stadt i befinden ($ 0 \ leq i \ leq n $), teleportieren Sie sich als nächstes in die Stadt $ a_ {i} $
• Wenn Sie dieselbe Stadt zweimal besuchen, hören Sie auf, sich in dieser Stadt zu teleportieren. Wo ist diese Stadt?

Angenommen, Sie erhalten $ n = 4, a = {3,1,3,4,2} $. Zu diesem Zeitpunkt bewegt es sich als "Stadt 0-> Stadt 3-> Stadt 4-> Stadt 2-> Stadt 3" und stoppt hier (weil es zweimal in Stadt 3 gestoppt hat). Es kann wie folgt in der Figur ausgedrückt werden. Beachten Sie die Abbildung unten. Es ist in einen Schleifenteil von $ 3-> 4-> 2-> .. $ und einen "Schwanz" von $ 0 $ unterteilt, bis diese Schleife betreten wird. Nennen wir nun den Knoten vom Schwanz zur Schleife (3 in der Abbildung) den "Schleifeneingang". Angesichts dieses Teleport-Problems befindet sich der Eingang zur Schleife dort, wo er vom Heck aus eintritt und vom Ende der Schleife zurückkehrt (dh es ist ein Knoten, den Sie zweimal besuchen). Es ist also genau der Knoten, den Sie suchen.

Jetzt müssen Sie den Eingang zur Schleife kühl finden. Betrachten Sie die von Sempai vorgeschlagene Methode zur Erkennung der Floyd-Zirkulation. Ich werde die Erklärung anderen Artikeln überlassen, aber mit Floyds kreisförmiger Erkennungsmethode ist es möglich, die Länge der $ loop \ mu $ und des Knotens \ lambda $ am Eingang der $ loop zu kennen, und dieser räumliche Berechnungsbetrag ist erstaunlich. Da es $ O (1) $ ist und der Zeitberechnungsbetrag $ O (\ lambda + \ mu) $ ist, ist das Schlimmste ungefähr $ O (N) $.

Für die Floyd-Zirkulationserkennungsmethode ist Visualisieren Sie die Floyd-Zirkulationserkennungsmethode mit R leicht zu verstehen.

Der Code, der dies implementiert, lautet wie folgt.

from typing import List
def findDuplicate(nums: List[int]):
    hare = tortoise = 0
    #Schildkrötengeschwindigkeit 1,Kaninchen läuft mit Geschwindigkeit 2
    while True: #Schleife bis es trifft
        tortoise = nums[tortoise]
        hare = nums[hare]
        hare = nums[hare]
        if tortoise == hare:
            break
    m = tortoise
    #Bringen Sie das Kaninchen wieder in seine Ausgangsposition
    hare = 0
    while tortoise != hare: #Schleife bis es trifft
        tortoise = nums[tortoise]
        hare = nums[hare] #Kaninchen auch Geschwindigkeit 1
    l = hare
    u = 0
    #Bewegen Sie nur das Kaninchen aus der überlappenden Position in der Schleife
    while True: #Schleife bis es trifft
        u += 1
        hare = nums[hare]
        hare = nums[hare]
        if tortoise == hare:
            break
    # m:Anzahl der Stockwerke vor einer Kollision
    # l:、u:Schleifenlänge
    print("debug: m=",m, "l=",l, "u=",u)
    return l

print(findDuplicate([1,3,2,4,1,5]))
print(findDuplicate([3,3,4,2,5,1]))
print(findDuplicate([2,2,3,4,5,1]))
print(findDuplicate([4,3,4,2,1]))
#Angemessen"30"Erstellen Sie eine Liste zufälliger Bestellungen mit Duplikaten
import random
l = list(range(1,100)) + [30]
random.shuffle(l)
print(findDuplicate(l))

Ausführungsergebnis:

debug: m= 4 l= 1 u= 3
1
debug: m= 1 l= 3 u= 5
3
debug: m= 1 l= 2 u= 5
2
debug: m= 2 l= 4 u= 2
4
debug: m= 40 l= 30 u= 17
30

Rückblick und Experimentieren

Lassen Sie uns nun auf die Zeitberechnung und die Raumberechnung zurückblicken.

In dem im Anhang angegebenen Code haben $ N = 10 ^ {7} $ und Duplikate jeden Algorithmus mit zufällig ausgewählten Daten ausgeführt, um Zeit und Speicher zu messen.

Dies wurde wie folgt experimentiert.

• (Verwenden Sie gen.py) Fügen Sie $ 1-10 ^ 7 $ und nur eine Zufallszahl hinzu, mischen Sie und schreiben Sie in die Datei -Jeder Algorithmus liest die Datei und führt die Verarbeitung durch (diese werden als Verarbeitung 1, 2, 2 Modifikation, 3 bezeichnet).
• Führen Sie eine Verarbeitung durch, die nur liest (dies wird als Verarbeitung 0 bezeichnet).
• Subtrahieren Sie die Ausführungszeit und den Speicher von Prozess 0 von der Ausführungszeit und dem Speicher jedes Algorithmus. Infolgedessen werden die für die Verarbeitung erforderliche Zeit und der für die Verarbeitung erforderliche Speicher berechnet.

Das Folgende ist die Speichernutzung / Ausführungszeit der Prozesse 1, 2 und 3 abzüglich der Speichernutzung von Prozess 0.

Hier sind einige Dinge zu verstehen.

--Prozess 1 (Sortieren / Lineare Suche) dauert insgesamt lange. Es wird geschätzt, dass das Sortieren dauert (wahrscheinlich 5 oder 6 Sekunden). Bei der Speichernutzung handelt es sich um die Originaldaten (sollte zum Sortieren ein Array gleicher Länge generiert haben). --Prozess 2 (Wörterbuch) ist schnell, benötigt jedoch viel Speicher für das Wörterbuch --Prozess 2 Pause (Liste) ist noch schneller und der Speicher ist doppelt so stabil wie Prozess 1.

• Prozess 3 ist eine mittlere Geschwindigkeit, aber dieser Prozess verwendet fast keinen Speicher

Darüber hinaus wurden in Prozess 2 interessante Dinge beobachtet.

• Nur Muster mit einer Speichernutzung von "30 MB", "245 MB" oder "491 MB" Dies scheint auf die Implementierung des Wörterbuchs zurückzuführen zu sein. .. Da das Wörterbuch nicht weiß, wie viel Speicher beim Erstellen oder Hinzufügen reserviert werden muss, reservieren Sie eine kleine Speichermenge und erhöhen Sie die Reservemenge, wenn die Anzahl der Verwaltungselemente zunimmt. Das Obige ist kein ausreichendes Experiment, aber wenn der Verwaltungsaufwand ein bestimmtes Niveau überschreitet, wird der Speicher möglicherweise verdoppelt oder verdoppelt.

Vergleich nach C-Sprache

Ich habe einen ähnlichen Algorithmus in C implementiert und getestet (nicht in C ++). --Prozess 1 sortiert nach qsort in stdlib

• Prozess 2 wird nicht ausgeführt. Dies liegt daran, dass es in nicht markiertem C kein Hashmap-Äquivalent gibt. --Prozess 2-Pausen verwalten die Nutzung mit einer Liste von Ints --Processing 2 Als modifiziertes Bit wird die Verwendung durch ein langes langes Bit anstelle von char verwaltet.
• Prozess 3 wird weiterhin ausgeführt.

Der Code befindet sich in Referenz 4.

In der obigen Tabelle ist kein Prozess 2 enthalten, aber Prozess 2-Bits sind enthalten. Bitte seien Sie beim Vergleich vorsichtig. </ font>

//Code, um XOR von 1 bis N zu finden
if( ((N+1) / 2) % 2 == 1 ) { a = 1; } else { a = 0;}
for(int i = 0 ; i < 31 ; i++)
    if( ((N / (1<<i) ) % 2 == 1) && ((N % (1<<i) ) % 2 == 0)) a += (1 << i);

■ Verarbeitung 3:Floyd Zirkulationserkennungsmethode
$ ~/time-1.9/time -f "%M KB,%E sec" ./a.out 3 < in7
39704 KB,0:02.07 sec
■ Verarbeitung von 2 Unterbrechungsbits:Verarbeiten Sie die Eingabe unverändert, ohne sie in ein Array einzufügen
$ ~/time-1.9/time -f "%M KB,%E sec" ./a.out< in7
1844 KB,0:01.06 sec
■xor
$ ~/time-1.9/time -f "%M KB,%E sec" ./dup4< in7
624 KB,0:00.91 sec

#include <stdio.h>
int main(int argc, char **argv){
    unsigned int N, a, x, i;
    scanf("%d",&N);
    N -= 1;
    if( ((N+1) / 2) % 2 == 1 ) { a = 1; } else { a = 0;}
    for(i = 0 ; i < 31 ; i++)
        if( ((N / (1u << i) ) % 2 == 1) &&
            ((N % ((1u << i) ) % 2 == 0)) ) a += (1 << i);
    for(i = 0 ; i < N+1 ; i++){
        scanf("%d",&x);
        a ^= x;
    }
    printf("%d\n", a);
    return 0;
}

import random
import sys
n=int(sys.argv[1])
x = random.randrange(n)+1
l = list(range(1,n+1)) + [x]
random.shuffle(l)
print(n+1)
for i in range(n+1):
    print(l[i])

import sys
fd = open(sys.argv[1], "r")
q = int(fd.readline())
dat = [0] * q
for i in range(q):
    dat[i] = int(fd.readline())
findDuplicate(dat)

rm out*
for i in {0..9}; do
python3 gen.py 1000000 > in6
echo $i
~/time-1.9/time -f "%M,%E" python3 1.py in6 2>>out6.1.csv
~/time-1.9/time -f "%M,%E" python3 2.py in6 2>>out6.2.csv
~/time-1.9/time -f "%M,%E" python3 3.py in6 2>>out6.3.csv
~/time-1.9/time -f "%M,%E" python3 0.py in6 2>>out6.0.csv
done

for i in {0..9}; do
python3 gen.py 10000000 > in7
echo $i
~/time-1.9/time -f "%M,%E" python3 1.py in7 2>>out7.1.csv
~/time-1.9/time -f "%M,%E" python3 2.py in7 2>>out7.2.csv
~/time-1.9/time -f "%M,%E" python3 3.py in7 2>>out7.3.csv
~/time-1.9/time -f "%M,%E" python3 0.py in7 2>>out7.0.csv
done


for fn in `ls out*csv*`; do
 sed -i -e 's/,.:\([0-9][0-9]\)\.\([0-9][0-9]\)/,\1.\2/' $fn
done

#include <stdio.h>
#include <stdlib.h>

int fcmp(const void * n1, const void * n2)
{
    if (*(int *)n1 > *(int *)n2)
    {
        return 1;
    }
    else if (*(int *)n1 < *(int *)n2)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

int solve1(int N, int* a){
    qsort(a, N + 1, sizeof(int), fcmp);
    for(int i = 0; i < N; i++){
        if(a[i] == a[i+1]) return a[i];
    }
    return -1;
}

int solve2(int N, int* a){
    int *dict = (int *)calloc(sizeof(int), N + 1);
    for(int i = 0; i < N+1; i++){
        if (dict[a[i]] == 1){
            free(dict);
            return a[i];
        }
        dict[a[i]] = 1;
    }
    free(dict);
    return -1;
}

int solve22(int N, int* a){
    int cnt = ((N+1) / 64) + 2;
    unsigned long* dict = (unsigned long*)calloc(sizeof(unsigned long ), cnt);
    for(int i = 0; i < N+1; i++){
        if ( ( (dict[a[i]/64] >> (int)(a[i] % 64) ) & (unsigned long)1 )  == 1){
            free(dict);
            return a[i];
        }
        dict[a[i]/64] |= ((unsigned long)1 << (int)(a[i] % 64));
    }
    free(dict);
    return -1;
}


int solve3(int N, int* a){
    int tortoise;
    int hare;
    tortoise = a[0];
    hare = a[a[0]];
    while (tortoise != hare)
    {
        tortoise = a[tortoise];
        hare = a[a[hare]];
    }
    hare = 0;
    while (tortoise != hare)
    {
        tortoise = a[tortoise];
        hare = a[hare];
    }
    return hare;
}


int main(int argc, char **argv){
    int type=1;
    if (argc > 1){
        type = atoi(argv[1]);
    }

    int N;
    scanf("%d",&N);

    int *a;
    a = malloc(sizeof(int) * N +1);

    for(int i = 0 ; i < N+1 ; i++){
        scanf("%d",&a[i]);
    }
    switch (type) {
        case 1:
            printf("algo1\n");
            printf("%d\n", solve1(N, a));
            break;
        case 2:
            printf("algo2\n");
            printf("%d\n", solve2(N, a));
            break;
        case 22:
            printf("algo22\n");
            printf("%d\n", solve22(N, a));
            break;
        case 3:
            printf("algo3\n");
            printf("%d\n", solve3(N, a));
            break;
        case 0:
            break;

        default:
            break;
    }
    return 0;
}