分析时间时c ++中的运行时错误

Question

我正在尝试检查一个问题的每 3 个解决方案经过了多少时间，但有时我会遇到运行时错误并且看不到第 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

使用地址清理器构建程序 (clang++ clock.cxx -std=c++11 -O1 -g -fsanitize=address -fno-omit-frame-pointer) 揭示了问题：

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

如您所见，input1、input2、...、input4 的大小为 10K、20K、40K、80K 个元素，但在循环中我们正在访问此数组之外的元素，因此这可能导致堆损坏。

Process returned -1073741819 (0xC0000005)

这意味着 "memory access violation" 或 SEGFAULT。

希望这会有所帮助。

分析时间时c ++中的运行时错误

Runtime error in c++ when analysing time

c++

analysis

runtime

timing

ctime