1
問題ごとに3つの解決策がどれくらい時間がかかるかを確認しようとしていますが、時にはランタイムエラーが発生し、働く私はsolutions.hファイルが正しいと思いますが、とにかくここに入れます。時間を分析するときにC++でランタイムエラーが発生する
#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が
-fno-オミット(打ち鳴らす++ clock.cxx -std = C++ 11 -O1 -g -fsanitize =アドレス消毒アドレスを使用してプログラムを構築#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
実行時エラーとは何ですか? – Dijkgraaf
プロセスが返されました-1073741819(0xC0000005) – codemonkey
おそらくオーバーフローです。 入力配列を初期化するときに少なくとも1つあります。 input1のサイズは10000で、100000個の要素を入力しようとしています。 コードがこの質問には大きすぎます。狭めてください。 –