Erreur d'exécution en C++ lors de l'analyse du temps

Question

J'essaie de vérifier le temps qui passe avec 3 solutions pour un problème, mais parfois je reçois une erreur d'exécution et je ne vois pas le temps passé pour la 3ème solution, mais parfois travaux. Je pense que le fichier solutions.h est correct mais je l'ai mis ici de toute façon.

#include <iostream> 
#include <cstdlib> 
#include <ctime> 
#include "solutions.h" 
using namespace std; 

    int main() 
{ 
cout << "Hello world!" << endl; 
int* input1 = new int[10000]; 
int* input2 = new int[20000]; 
int* input3 = new int[40000]; 
int* input4 = new int[80000]; 
int* input5 = new int[100000]; 

for(int i = 0; i<100000; i++) 
{ 
    input1[i]= rand(); 
    input2[i]= rand(); 
    input3[i]= rand(); 
    input4[i]= rand(); 
    input5[i]= rand(); 
} 
int* output1= new int[1000]; 

double duration; 


clock_t startTime1 = clock(); 
solution1(input1,10000,1000,output1); 
duration = 1000 * double(clock() - startTime1)/CLOCKS_PER_SEC; 
cout << "Solution 1 with 10000 inputs took " << duration << " milliseconds." << endl; 

startTime1 = clock(); 
solution2(input1,10000,1000,output1); 
duration = 1000 * double(clock() - startTime1)/CLOCKS_PER_SEC; 
cout << "Solution 2 with 10000 inputs took " << duration<< " milliseconds." << endl; 

startTime1 = clock(); 
solution3(input1,10000,1000,output1); 
duration = 1000 * double(clock() - startTime1)/CLOCKS_PER_SEC; 
cout << "Solution 3 with 10000 inputs took " << duration << " milliseconds." << endl<<endl<<endl; 



return 0; 
} 

Et le solutions.h est

#ifndef SOLUTIONS_H_INCLUDED 
#define SOLUTIONS_H_INCLUDED 
#include <cmath> 

void solution1(int input[], const int n, const int k, int output[]); 
void solution2(int input[], const int n, const int k, int output[]); 
void solution3(int input[], const int n, const int k, int output[]); 

void swap(int &n1, int &n2) { 

int temp = n1; 
n1 = n2; 
n2 = temp; 
} 

void solution1(int input[], const int n, const int k, int output[]) { 

int maxIndex, maxValue; 
for(int i = 0; i < k; i++) { 
    maxIndex = i; 
    maxValue = input[i]; 
    for(int j = i+1; j < n; j++) { 
     if(input[j] >= maxValue) { 
      maxIndex = j; 
      maxValue = input[ j ]; 
     } 
    } 
    swap(input[i], input[maxIndex]); 
    output[i] = input[i]; 
} 
} 

int partition(int input[], int p, int r) { 

int x = input[ r ], i = p - 1; 
for(int j = p; j < r; j++) { 
    if(input[ j ] >= x) { 
     i = i + 1; 
     swap(input[i], input[j]); 
    } 
} 
swap(input[i+1], input[r]); 
return i + 1; 
} 

void quickSort(int input[], int p, int r) { 

int q; 
if(p < r) { 
    q = partition(input, p, r); 
    quickSort(input, p, q - 1); 
    quickSort(input, q + 1, r); 
} 
} 

void solution2(int input[], const int n, const int k, int output[]) { 

quickSort(input, 0, n - 1); 
for(int i = 0; i < k; i++) { 
    output[i] = input[i]; 
} 
} 

int partition2(int input[], int a, int p, int r) { 

int x = a, i = p - 1; 
for(int j = p; j < r; j++) { 
    if(input[ j ] == x) { 
     swap(input[ j ], input[ r ]); 
    } 
    if(input[ j ] >= x) { 
     i = i + 1; 
     swap(input[i], input[j]); 
    } 
} 
swap(input[ i + 1 ], input[ r ]); 
return i + 1; 
} 

void quickSort2(int input[], int p, int r) { 

int q; 
if(p < r) { 
    q = partition2(input, input[ r ], p, r); 
    quickSort2(input, p, q - 1); 
    quickSort2(input, q + 1, r); 
} 
} 

int findMin(int n1, int n2) { 

if(n1 <= n2) 
    return n1; 
else 
    return n2; 
} 

int select(int input[], int n, int k, int start, int end, int flag) { 

if(n <= 5) { 
    quickSort2(input, start, end); 
    return input[ start + k - 1 ]; 
} 
int i = start, numGroups = (int) ceil((double) n/5), numElements, j =  0; 
int *medians = new int[numGroups]; 
while(i <= end) { 
    numElements = findMin(5, end - i + 1); 
    medians[(i - start)/5] = select(input, numElements, (int) ceil(( double) numElements/2), i, i + numElements - 1, 1); 
    i = i + 5; 
} 
int M = select(medians, numGroups, (int) ceil((double) numGroups/2), 0, numGroups - 1, 1); 
delete[] medians; 
if(flag == 1) 
    return M; 
int q = partition2(input, M, start, end); 
int m = q - start + 1; 
if(k == m) 
    return M; 
else if(k < m) 
    return select(input, m - 1, k, start, q - 1, 0); 
else 
    return select(input, end - q, k - m, q + 1, end, 0); 
} 

void solution3(int input[], const int n, const int k, int output[]) { 

select(input, n, k, 0, n - 1, 0); 
for(int i = 0; i < k; i++) 
    output[i] = input[i]; 
} 



#endif // SOLUTIONS_H_INCLUDED 

Answer 1

Construire votre programme avec adresse désinfectant pour les mains (clang ++ clock.cxx std = C++ 11 -O1 -g -fsanitize = adresse -fno-Omettre -frame-pointeur) révèle le problème:

$ ./a.out 
Hello world! 
================================================================= 
==8175==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x62e00000a040 at pc 0x000104dbd912 bp 0x7fff5ae43970 sp 0x7fff5ae43968 
WRITE of size 4 at 0x62e00000a040 thread T0 
    #0 0x104dbd911 in main clock.cxx:18 
    #1 0x7fff88cd85fc in start (libdyld.dylib+0x35fc) 
    #2 0x0 (<unknown module>) 

0x62e00000a040 is located 0 bytes to the right of 40000-byte region [0x62e000000400,0x62e00000a040) 

Et il y a votre code:

int* input1 = new int[10000]; 
    int* input2 = new int[20000]; 
    int* input3 = new int[40000]; 
    int* input4 = new int[80000]; 
    int* input5 = new int[100000]; 

    for(int i = 0; i<100000; i++) 
    { 
     input1[i]= rand(); 
     input2[i]= rand(); 
     input3[i]= rand(); 
     input4[i]= rand(); 
     input5[i]= rand(); 
    } 

Comme vous pouvez le voir, la taille de input1, input2, ..., input4 est de 10K, 20K, 40K, 80K éléments, mais dans la boucle nous accédons aux éléments hors de ce tableau .

processus retourne -1073741819 (0xC0000005)

Cela signifie "violation d'accès à la mémoire" ou SEGFAULT.

Espérons que cela aidera.