当我的 vector/array 尺寸变得太大时 VS 抛出异常
VS throwing exception when my vector/array size becomes too large
我的问题是，当我的数组大小变得太大时，我抛出了一个异常：“抛出 away.exe 中 0x005B3BC7 处未处理的异常：0xC00000FD：堆栈溢出（参数：0x00000001、0x01002F68）”。我需要能够 运行 此代码 array/vector 大小 n = 100000，但截至目前它仅适用于 n = 1000。超过此阈值的任何内容都会导致 VS 抛出堆栈溢出异常。建议我使用向量而不是数组，但这并没有解决问题。我添加了一个中断并开始调试。这就是我注意到在输入 quickSort 函数时会发生这种情况的地方。我假设，array/vector 大小如此之大，堆栈在被分区并划分为子数组时会变满。推荐的修复方法是什么？
#include <iostream>
#include <chrono>
#include <cmath>
#include <math.h>
#include <random>
#include <vector>
using namespace std;
// Insertion Sort
void insertionSort(std::vector<int>& arr, int n) {
for (int i = 1; i < n; i++) {
int j, temp = arr[i]; // make a copy of a[i]
for (j = i - 1; j >= 0; j--) { // starting "moving left"
if (arr[j] > temp)
arr[j + 1] = arr[j]; // inversion detected, move a[j] to the right
else
break; // index j is one spot to the left of where temp belong
}
arr[j + 1] = temp;
}
}
// Partition
int partition(std::vector<int>& arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr[pivotIndex], arr[right]); // move pivotValue to end
// partition the array. upon finding an element smaller than pivot,
// swap it ot the next position in the "store"
int store = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivotValue) {
swap(arr[store], arr[i]);
store++;
}
}
swap(arr[right], arr[store]); // swap pivot to its final position
return store;
}
// Quick Sort
// std::vector<int> &data, int left, int right
void quickSort(std::vector<int> &arr, int left, int right) {
// Perform IS when sub array(s) are less than 10
if ((right - left) < 10) {
insertionSort(arr, right);
}
else {
int M = (right - left) / 2;
int j = partition(arr, left, right - 1, M);
quickSort(arr, left, j); // sort the left of M
quickSort(arr, j + 1, right); // sort the right of M
}
}
// Check if array has been ordered
bool isOrdered(std::vector<int>& arr, int n) {
// array with 1 or no elements will always be sorted
if (n <= 1)
return true;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}
int main() {
int input;
// Prompt user with catch if input not within bounds
do
{
cout << "----------------------------------------------------------------" << endl;
cout << " Press 1 to exit the program " << endl;
cout << " Press 2 to select the array that is sorted in increasing order " << endl;
cout << " Press 3 to select the array that is randomly sorted " << endl;
cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
cout << "----------------------------------------------------------------" << endl;
cin >> input;
} while (input != 1 && input != 2 && input != 3 && input != 4);
while (input != 1)
{
int n = 100000; // works with n = 1000
vector<int> a(n); // originally int* a = new int[n]
vector<int> b(n); // originally int* b = new int[n]
vector<int> c(n); // originally int* c = new int[n]
vector<int> a_c1(n);
vector<int> b_c1(n);
vector<int> c_c1(n);
vector<int> a_c2(n);
vector<int> b_c2(n);
vector<int> c_c2(n);
if (input == 2) {
// Fill array with numbers in ascending order
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
// create first duplicate array
for (int i = 0; i < n; i++) {
a_c1[i] = a[i];
}
// get start time for IS
auto start = std::chrono::steady_clock::now();
insertionSort(a_c1, n);
// get end time
auto end = std::chrono::steady_clock::now();
double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
// output time to screen
cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;
// create second duplicate array
for (int i = 0; i < n; i++) {
a_c2[i] = a[i];
}
// get start time for QS
auto start2 = std::chrono::steady_clock::now();
quickSort(a_c2, 0, n);
// get end time
auto end2 = std::chrono::steady_clock::now();
double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
// output time to screen
cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(a_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(a_c2, n) << endl;
}
else if (input == 3) {
// seed the PRNG (MT19937) using a variable value (in our case, rd)
std::random_device rd;
std::mt19937 generator(rd()); // seed by variable input
std::uniform_int_distribution<int> distribution(1, n); // random numbers need to be in range between 1, n
for (int i = 0; i < n; i++) {
b[i] = distribution(generator);
}
// create first duplicate array
for (int i = 0; i < n; i++) {
b_c1[i] = b[i];
}
insertionSort(b_c1, n);
// create second duplicate array
for (int i = 0; i < n; i++) {
b_c2[i] = b[i];
}
quickSort(b_c2, 0, n);
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(b_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(b_c2, n) << endl;
}
else {
int temp_1 = n;
for (int i = 0; i < n; i++) {
c[i] = temp_1;
temp_1--;
}
// create first duplicate array
for (int i = 0; i < n; i++) {
c_c1[i] = c[i];
}
insertionSort(c_c1, n);
// create second duplicate array
for (int i = 0; i < n; i++) {
c_c2[i] = c[i];
}
quickSort(c_c2, 0, n);
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(c_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(c_c2, n) << endl;
}
// Prompt user again with catch if input not within bounds
do
{
cout << "----------------------------------------------------------------" << endl;
cout << " Press 1 to exit the program " << endl;
cout << " Press 2 to select the array that is sorted in increasing order " << endl;
cout << " Press 3 to select the array that is randomly sorted " << endl;
cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
cout << "----------------------------------------------------------------" << endl;
cin >> input;
} while (input != 1 && input != 2 && input != 3 && input != 4);
}
exit(0);
}
您在 int M = (right - left) / 2; 中计算的中位数指数是错误的。
未优化的方程为
M = left + (right - left) / 2
相当于
2 * M = 2 * left + (right - left)
相当于
2 * M = left + right（假设 left + right 没有溢出）
相当于
M = (left + right) / 2
通过在较小的分区上递归，然后循环返回较大的分区，可以将堆栈开销减少到 O(log(n))。最坏情况下的时间复杂度仍然是 O(n^2).
void quickSort(std::vector<int> &arr, int left, int right) {
while(right - left > 10){
int M = left + ((right - left) / 2);
int j = partition(arr, left, right - 1, M);
if((j - left) < (right - j)){ // recurse on smaller, loop on larger
quickSort(arr, left, j);
left = j;}
} else {
quickSort(arr, j + 1, right);
right = j;
}
}
if(right - left > 0)
insertionSort(arr, left, right); // insertion sort needs a fix
}
我的问题是，当我的数组大小变得太大时，我抛出了一个异常：“抛出 away.exe 中 0x005B3BC7 处未处理的异常：0xC00000FD：堆栈溢出（参数：0x00000001、0x01002F68）”。我需要能够 运行 此代码 array/vector 大小 n = 100000，但截至目前它仅适用于 n = 1000。超过此阈值的任何内容都会导致 VS 抛出堆栈溢出异常。建议我使用向量而不是数组，但这并没有解决问题。我添加了一个中断并开始调试。这就是我注意到在输入 quickSort 函数时会发生这种情况的地方。我假设，array/vector 大小如此之大，堆栈在被分区并划分为子数组时会变满。推荐的修复方法是什么？
#include <iostream>
#include <chrono>
#include <cmath>
#include <math.h>
#include <random>
#include <vector>
using namespace std;
// Insertion Sort
void insertionSort(std::vector<int>& arr, int n) {
for (int i = 1; i < n; i++) {
int j, temp = arr[i]; // make a copy of a[i]
for (j = i - 1; j >= 0; j--) { // starting "moving left"
if (arr[j] > temp)
arr[j + 1] = arr[j]; // inversion detected, move a[j] to the right
else
break; // index j is one spot to the left of where temp belong
}
arr[j + 1] = temp;
}
}
// Partition
int partition(std::vector<int>& arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr[pivotIndex], arr[right]); // move pivotValue to end
// partition the array. upon finding an element smaller than pivot,
// swap it ot the next position in the "store"
int store = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivotValue) {
swap(arr[store], arr[i]);
store++;
}
}
swap(arr[right], arr[store]); // swap pivot to its final position
return store;
}
// Quick Sort
// std::vector<int> &data, int left, int right
void quickSort(std::vector<int> &arr, int left, int right) {
// Perform IS when sub array(s) are less than 10
if ((right - left) < 10) {
insertionSort(arr, right);
}
else {
int M = (right - left) / 2;
int j = partition(arr, left, right - 1, M);
quickSort(arr, left, j); // sort the left of M
quickSort(arr, j + 1, right); // sort the right of M
}
}
// Check if array has been ordered
bool isOrdered(std::vector<int>& arr, int n) {
// array with 1 or no elements will always be sorted
if (n <= 1)
return true;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
return false;
}
}
return true;
}
int main() {
int input;
// Prompt user with catch if input not within bounds
do
{
cout << "----------------------------------------------------------------" << endl;
cout << " Press 1 to exit the program " << endl;
cout << " Press 2 to select the array that is sorted in increasing order " << endl;
cout << " Press 3 to select the array that is randomly sorted " << endl;
cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
cout << "----------------------------------------------------------------" << endl;
cin >> input;
} while (input != 1 && input != 2 && input != 3 && input != 4);
while (input != 1)
{
int n = 100000; // works with n = 1000
vector<int> a(n); // originally int* a = new int[n]
vector<int> b(n); // originally int* b = new int[n]
vector<int> c(n); // originally int* c = new int[n]
vector<int> a_c1(n);
vector<int> b_c1(n);
vector<int> c_c1(n);
vector<int> a_c2(n);
vector<int> b_c2(n);
vector<int> c_c2(n);
if (input == 2) {
// Fill array with numbers in ascending order
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
// create first duplicate array
for (int i = 0; i < n; i++) {
a_c1[i] = a[i];
}
// get start time for IS
auto start = std::chrono::steady_clock::now();
insertionSort(a_c1, n);
// get end time
auto end = std::chrono::steady_clock::now();
double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
// output time to screen
cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;
// create second duplicate array
for (int i = 0; i < n; i++) {
a_c2[i] = a[i];
}
// get start time for QS
auto start2 = std::chrono::steady_clock::now();
quickSort(a_c2, 0, n);
// get end time
auto end2 = std::chrono::steady_clock::now();
double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
// output time to screen
cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(a_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(a_c2, n) << endl;
}
else if (input == 3) {
// seed the PRNG (MT19937) using a variable value (in our case, rd)
std::random_device rd;
std::mt19937 generator(rd()); // seed by variable input
std::uniform_int_distribution<int> distribution(1, n); // random numbers need to be in range between 1, n
for (int i = 0; i < n; i++) {
b[i] = distribution(generator);
}
// create first duplicate array
for (int i = 0; i < n; i++) {
b_c1[i] = b[i];
}
insertionSort(b_c1, n);
// create second duplicate array
for (int i = 0; i < n; i++) {
b_c2[i] = b[i];
}
quickSort(b_c2, 0, n);
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(b_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(b_c2, n) << endl;
}
else {
int temp_1 = n;
for (int i = 0; i < n; i++) {
c[i] = temp_1;
temp_1--;
}
// create first duplicate array
for (int i = 0; i < n; i++) {
c_c1[i] = c[i];
}
insertionSort(c_c1, n);
// create second duplicate array
for (int i = 0; i < n; i++) {
c_c2[i] = c[i];
}
quickSort(c_c2, 0, n);
cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(c_c1, n) << endl;
cout << "After passing array through Quick Sort funtion, is it sorted? " << isOrdered(c_c2, n) << endl;
}
// Prompt user again with catch if input not within bounds
do
{
cout << "----------------------------------------------------------------" << endl;
cout << " Press 1 to exit the program " << endl;
cout << " Press 2 to select the array that is sorted in increasing order " << endl;
cout << " Press 3 to select the array that is randomly sorted " << endl;
cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
cout << "----------------------------------------------------------------" << endl;
cin >> input;
} while (input != 1 && input != 2 && input != 3 && input != 4);
}
exit(0);
}
您在 int M = (right - left) / 2; 中计算的中位数指数是错误的。
未优化的方程为
M = left + (right - left) / 2
相当于
2 * M = 2 * left + (right - left)
相当于
2 * M = left + right（假设 left + right 没有溢出）
相当于
M = (left + right) / 2
通过在较小的分区上递归，然后循环返回较大的分区，可以将堆栈开销减少到 O(log(n))。最坏情况下的时间复杂度仍然是 O(n^2).
void quickSort(std::vector<int> &arr, int left, int right) {
while(right - left > 10){
int M = left + ((right - left) / 2);
int j = partition(arr, left, right - 1, M);
if((j - left) < (right - j)){ // recurse on smaller, loop on larger
quickSort(arr, left, j);
left = j;}
} else {
quickSort(arr, j + 1, right);
right = j;
}
}
if(right - left > 0)
insertionSort(arr, left, right); // insertion sort needs a fix
}