Ошибка выполнения в C++ при анализе времени

Question

Я пытаюсь проверить, сколько времени проходит с каждым 3-мя решениями проблемы, но иногда я получаю ошибку времени выполнения и не могу видеть прошедшее время для третьего решения, но иногда это работает. Я думаю, что файл solutions.h верен, но я все равно его разместил.

#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; 
} 

И solutions.h является

#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

Построение вашей программы с адресом дезинфицирующее (лязгом ++ clock.cxx -std = C++ 11 -O1 -g -fsanitize = адрес -fno-опускаем -реперов-указатель) раскрывает проблему:

$ ./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) 

И есть код:

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(); 
    } 

Как вы можете видеть, размер входных данных1, input2, ..., input4 составляет 10K, 20K, 40K, 80K элементов, но в цикле мы получаем доступ к элементам из этого массива, поэтому это может привести к повреждению кучи ,

Процесс возвращается -1073741819 (0xC0000005)

Это означает, что "нарушение доступа к памяти" или Segfault.

Надеюсь, это поможет.