Conclusion d'abord

• Les dictionnaires sont rapides mais utilisent plus de mémoire que vous ne le pensez
• La méthode de détection de circulation Floyd est $ O (N) $, mais c'est un multiple constant (par rapport aux deux autres) plus lourd. Cependant, l'utilisation de la mémoire est O (1)

Matière

--Donné une liste composée d'entiers $ N $ et $ N + 1 $ éléments -L'élément $ a $ contient au moins un entier de 1 à n. (Autrement dit, un seul nombre en contient deux) --Etat en double (deux entiers inclus)

Exemple concret

Exemple: vous pouvez entrer quelque chose comme $ [3,1,3,4,2] $. Dans ce cas, répondez 3 $ $. Exemple: vous pouvez entrer quelque chose comme $ [1,3,2,1] $. Dans ce cas, répondez à 1 $. Exemple: vous pouvez entrer quelque chose comme $ [1,1] $. Dans ce cas, répondez à 1 $.

Approche 1: Tri et exploration linéaire

La première approche prise par le héros

• (a) Trier par ordre croissant, (b) Opérer linéairement depuis le début pour regarder les éléments deux par deux et trouver les doublons

Le montant du calcul spatial est de $ N $, mais le montant du calcul du temps coûte $ N log N $ pour traiter a et $ N $ en b, et par conséquent, le montant du calcul est 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

Approche 2: HashMap-Euh!

Enfin, le protagoniste utilise HashMap-Euh! (C'est-à-dire un dictionnaire), qui nécessite un pouvoir indépendant de sa volonté.

• (a) Initialisez d'abord le dictionnaire, (b) Regardez les nombres dans l'ordre, et s'ils existent déjà dans le dictionnaire, le nombre de doublons
• (c) Enregistrer la valeur comme existante si le nombre ne se chevauche pas En conséquence, MLE (erreur d'utilisation de la mémoire) se produit.

Je trouve que c'est stupide, mais c'est vrai que les dictionnaires utilisent plus de mémoire que d'éléments. Jetons un coup d'œil au code ci-dessous.

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]))

Quand tu fais ça,

Memory: 156 (Byte)
1
Memory: 184 (Byte)
3
Memory: 55100346 (Environ 55 Mo d'octets)
1000000

Par conséquent, une grande mémoire est utilisée pour le nombre d'éléments. Puisque la mémoire est de 55 M $ pour l'entrée de $ N = 10 ^ {6} $, si la mémoire est de 64 M $ avec $ N = 2 \ cdot 10 ^ {6} $, la quantité de données seules sera de $ MLE $. Cela finira.

[Original] Approach 2 Kai: Historique d'utilisation par liste du dictionnaire

Il s'avère que le dictionnaire utilise plus d'espace mémoire que prévu. Une autre approche consiste à créer un tableau de $ 1-N $ à l'avance et à comparer s'il apparaît dans $ False / True $. Cette approche sera utilisée pour l'évaluation dans des expériences ultérieures. La mise en œuvre est la suivante.

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

Approche 3: Méthode de détection de circulation Floyd

C'est là que Senpai entre en jeu. Sempai propose froidement l'algorithme de recherche de cycle de Floyd.

Dans un souci d'explication, cette phrase de question doit être lue comme suit. (Cela aura exactement les mêmes entrées et sorties que le problème d'origine)

――Il y a n villes dans ce monde, chacune avec un téléporteur. -Donné un tableau $ a $ composé de $ n + 1 $ entiers Ce tableau contient au moins un entier de 1 à n. (Autrement dit, un seul nombre en contient deux)

• Vous êtes maintenant dans la ville 0. --Lorsque vous êtes dans la ville de i ($ 0 \ leq i \ leq n $), téléportez-vous ensuite vers la ville de $ a_ {i} $
• Si vous visitez la même ville deux fois, arrêtez de vous téléporter dans cette ville. Où est cette ville?

À titre d'exemple, disons que vous recevez $ n = 4, a = {3,1,3,4,2} $. À ce moment, il se déplace comme "Ville 0-> Ville 3-> Ville 4-> Ville 2-> Ville 3" et s'arrête ici (car il s'est arrêté deux fois dans la ville 3). Il peut être exprimé comme suit dans la figure. Notez la figure ci-dessous. Il est divisé en une partie de boucle de $ 3-> 4-> 2-> .. $ et une "queue" de $ 0 $ jusqu'à l'entrée dans cette boucle. Maintenant, appelons le nœud de la queue à la boucle (3 sur la figure) «entrée de la boucle». Compte tenu de ce problème de téléportation, l'entrée de la boucle est l'endroit où elle entre par la queue et revient de la fin de la boucle (c'est-à-dire que c'est un nœud que vous visitez deux fois), donc c'est exactement le nœud que vous recherchez.

Vous devez maintenant trouver froidement l'entrée de la boucle. Considérez la méthode de détection de circulation floyd proposée par Sempai. Je laisserai l'explication à d'autres articles, mais en utilisant la méthode de détection circulaire de Floyd, il est possible de connaître la longueur de la $ loop \ mu $ et du nœud \ lambda $ à l'entrée de la $ loop, et ce montant de calcul spatial est incroyable. Puisqu'il est $ O (1) $ et que le montant du calcul du temps est $ O (\ lambda + \ mu) $, le pire est d'environ $ O (N) $.

Pour la méthode de détection de circulation Floyd, Visualisez la méthode de détection de circulation Floyd avec R est facile à comprendre.

Le code qui implémente ceci est le suivant.

from typing import List
def findDuplicate(nums: List[int]):
    hare = tortoise = 0
    #Tortue vitesse 1,Lapin court à la vitesse 2
    while True: #Boucle jusqu'à ce qu'il frappe
        tortoise = nums[tortoise]
        hare = nums[hare]
        hare = nums[hare]
        if tortoise == hare:
            break
    m = tortoise
    #Remettez le lapin dans sa position initiale
    hare = 0
    while tortoise != hare: #Boucle jusqu'à ce qu'il frappe
        tortoise = nums[tortoise]
        hare = nums[hare] #Lapin vitesse aussi 1
    l = hare
    u = 0
    #Déplacez uniquement le lapin de la position de chevauchement dans la boucle
    while True: #Boucle jusqu'à ce qu'il frappe
        u += 1
        hare = nums[hare]
        hare = nums[hare]
        if tortoise == hare:
            break
    # m:Nombre d'étages avant une collision
    # l:、u:Longueur de boucle
    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]))
#Approprié"30"Créer une liste de commandes aléatoires avec des doublons
import random
l = list(range(1,100)) + [30]
random.shuffle(l)
print(findDuplicate(l))

Résultat de l'exécution:

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

Regarder en arrière et expérimenter

Maintenant, revenons sur la quantité de calcul de temps et la quantité de calcul d'espace.

Dans le code donné en annexe, $ N = 10 ^ {7} $ et les doublons exécutaient chaque algorithme sur des données sélectionnées aléatoirement pour mesurer le temps et la mémoire.

Ceci a été testé comme suit.

• (Utilisez gen.py) Ajoutez $ 1-10 ^ 7 $ et un seul nombre aléatoire, mélangez et écrivez dans le fichier -Chaque algorithme lit le fichier et effectue le traitement (on parle de traitement 1,2,2 modification, 3) -Effectuer un traitement qui ne lit que (c'est ce qu'on appelle le traitement 0) -Soustraire le temps d'exécution et la mémoire du processus 0 du temps d'exécution et de la mémoire de chaque algorithme. En conséquence, le temps et la mémoire nécessaires au traitement sont calculés.

Voici l'utilisation de la mémoire / le temps d'exécution des processus 1, 2 et 3 moins l'utilisation de la mémoire du processus 0.

Voici quelques éléments à comprendre.

• Le processus 1 (tri / recherche linéaire) prend globalement beaucoup de temps. On estime que le tri prend (probablement 5 ou 6 secondes). L'utilisation de la mémoire concerne les données d'origine (devrait avoir généré un tableau de la même longueur pour le tri)
• Le processus 2 (dictionnaire) est rapide, mais utilise beaucoup de mémoire pour le dictionnaire --Le processus 2 break (liste) est encore plus rapide et la mémoire est stable à deux fois celle du processus 1.
• Le processus 3 est une vitesse intermédiaire, mais ce processus n'utilise presque pas de mémoire

De plus, des choses intéressantes ont été observées dans le Processus 2.

--Il n'y a qu'un modèle d'utilisation de la mémoire de «30 Mo», «245 Mo» ou «491 Mo» Cela semble être dû à l'implémentation du dictionnaire. .. Comme le dictionnaire ne sait pas combien de mémoire réserver lors de sa création ou de son ajout, réservez une petite quantité de mémoire et augmentez la quantité de réserve à mesure que le nombre d'éléments de gestion augmente. Ce qui précède n'est pas une expérience suffisante, mais peut-être que lorsque la quantité de gestion dépasse un certain niveau, cela va doubler ou doubler la mémoire.

Comparaison par langage C

J'ai implémenté et testé un algorithme similaire en C (pas C ++). --Le processus 1 trie par qsort dans stdlib

• Le processus 2 n'est pas exécuté. C'est parce qu'il n'y a pas d'équivalent de hashmap dans C.
• Les pauses du processus 2 gèrent l'utilisation avec une liste d'entiers --Processing 2 En tant que bit modifié, utilisez des bits longs et longs au lieu de char pour gérer l'utilisation.
• Le processus 3 continuera à être exécuté.

Le code est dans la référence 4.

Il n'y a pas de processus 2 dans le tableau ci-dessus, mais le processus 2 bits est inclus. Soyez prudent lorsque vous comparez. </ font>

//Code pour trouver XOR de 1 à N
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);

■ Traitement 3:Méthode de détection de circulation Floyd
$ ~/time-1.9/time -f "%M KB,%E sec" ./a.out 3 < in7
39704 KB,0:02.07 sec
■ Traitement de 2 bits de rupture:Traiter l'entrée telle quelle sans la mettre dans un tableau
$ ~/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;
}