Süre analiz edilirken C++ 'da çalışma zamanı hatası

Question

Bir problem için her 3 çözümün ne kadar zaman geçtiğini kontrol etmeye çalışıyorum, ancak bazen bir çalışma zamanı hatası alıyorum ve 3. çözüm için geçen zamanı göremiyorum, ancak bazen Eserleri. Ben solutions.h dosya doğru olduğunu düşünüyorum ama yine de buraya koydu.

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

Ve solutions.h (clang ++ clock.cxx -std = C++ 11 -O1 -g -fsanitize = adres -fno-omit dezenfektanı adresi ile programınızı Bina

#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

olduğunu -Frame-işaretçi) sorunu ortaya çıkarır:

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

Ve kod vardır:

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

Gördüğünüz gibi, giriş1, giriş2, ..., giriş4'ün boyutu 10K, 20K, 40K, 80K öğeleridir, ancak döngüde, bu dizinin dışındaki öğelere erişiyoruz, böylece bu, yığın bozulmasına neden olabilir .

Süreci Bu "bellek erişimi ihlali" veya segfault anlamına gelir -1073741819 (0xC0000005)

döndü.

Bu yardımcı olacaktır umarım.