发现四分位数

Question

我写了一个程序，用户可以输入任何数值到载体和它应该返回四分位数，但我不断收到一个“向量下标超出范围”错误：

#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <algorithm> 
#include <iomanip> 
#include <ios> 
#include <vector> 

int main() { 
    using namespace std; 

    cout << "Enter a list of numbers: "; 

    vector<double> quantile; 
    double x; 
    //invariant: homework contains all the homework grades so far 
    while (cin >> x) 
     quantile.push_back(x); 

    //check that the student entered some homework grades 
    //typedef vector<double>::size_type vec_sz; 
    int size = quantile.size(); 

    if (size == 0) { 
     cout << endl << "You must enter your numbers . " 
         "Please try again." << endl; 
     return 1; 
    } 

    sort(quantile.begin(), quantile.end()); 

    int mid = size/2; 
    double median; 
    median = size % 2 == 0 ? (quantile[mid] + quantile[mid-1])/2 : quantile[mid]; 

    vector<double> first; 
    vector<double> third; 

    for (int i = 0; i!=mid; ++i) 
    { 
     first[i] = quantile[i]; 

    } 

     for (int i = mid; i!= size; ++i) 
    { 
     third[i] = quantile[i]; 
    } 
     double fst; 
     double trd; 

     int side_length = 0; 

     if (size % 2 == 0) 
     { 
      side_length = size/2; 
     } 
     else { 
      side_length = (size-1)/2; 
     } 

     fst = (size/2) % 2 == 0 ? (first[side_length/2]/2 + first[(side_length-1)/2])/2 : first[side_length/2]; 
     trd = (size/2) % 2 == 0 ? (third[side_length/2]/2 + third[(side_length-1)/2])/2 : third[side_length/2]; 

    streamsize prec = cout.precision(); 
    cout << "The quartiles are" << setprecision(3) << "1st" 
     << fst << "2nd" << median << "3rd" << trd << setprecision(prec) << endl; 

    return 0; 

} 

Answer 1

而不是做std::sort(quantile.begin(), quantile.end())的便宜一点的办法是

auto const Q1 = quantile.size()/4; 
auto const Q2 = quantile.size()/2; 
auto const Q3 = Q1 + Q2; 

std::nth_element(quantile.begin(),   quantile.begin() + Q1, quantile.end()); 
std::nth_element(quantile.begin() + Q1 + 1, quantile.begin() + Q2, quantile.end()); 
std::nth_element(quantile.begin() + Q2 + 1, quantile.begin() + Q3, quantile.end()); 

这不是完整的数组进行排序，但只能做“群体之间”排在第四位。这节省了“组内”排序，完整的std::sort会做。

如果您的quantile数组不大，那么这是一个小优化。但是std::nth_element的缩放行为是O(N)，但是std::sort的O(N log N)。

Answer 2

如果只有一个在矢量元素，则该指令超出范围：

quantile[mid-1] 

“i”的中旬开始所以第三个[0]超出范围

for (int i = mid; i!= size; ++i) 
{ 
    third[i] = quantile[i]; 
} 

Answer 3

这是一个错误：

vector<double> first; 
vector<double> third; 

for (int i = 0; i!=mid; ++i) 
{ 
    first[i] = quantile[i]; 
} 

矢量first没有任何内容，但您尝试访问的内容。与third及其循环相同的问题。你的意思是用push_back代替吗？

Answer 4

在设置内容之前，您需要预先分配first和third矢量。

vector<double> first(mid); 
vector<double> third(size-mid); 

或使用push_back，而不是分配给first[i]和third[i]

Answer 5

这里是位数功能，该功能的MATLAB的等效采用线性插值：

template<typename T> 
static inline double Lerp(T v0, T v1, T t) 
{ 
    return (1 - t)*v0 + t*v1; 
} 

template<typename T> 
static inline std::vector<T> Quantile(const std::vector<T>& inData, const std::vector<T>& probs) 
{ 
    if (inData.empty()) 
    { 
     return std::vector<T>(); 
    } 

    if (1 == inData.size()) 
    { 
     return std::vector<T>(1, inData[0]); 
    } 

    std::vector<T> data = inData; 
    std::sort(data.begin(), data.end()); 
    std::vector<T> quantiles; 

    for (size_t i = 0; i < probs.size(); ++i) 
    { 
     T poi = Lerp<T>(-0.5, data.size() - 0.5, probs[i]); 

     size_t left = std::max(int64_t(std::floor(poi)), int64_t(0)); 
     size_t right = std::min(int64_t(std::ceil(poi)), int64_t(data.size() - 1)); 

     T datLeft = data.at(left); 
     T datRight = data.at(right); 

     T quantile = Lerp<T>(datLeft, datRight, poi - left); 

     quantiles.push_back(quantile); 
    } 

    return quantiles; 
} 

查找四分位数：

std::vector<double> in = { 1,2,3,4,5,6,7,8,9,10,11 }; 
auto quartiles = Quantile<double>(in, { 0.25, 0.5, 0.75 }); 

Answer 6

这个C++模板函数计算四分位数为您提供：

#include <assert.h> 

template <typename T1, typename T2> typename T1::value_type quant(const T1 &x, T2 q) 
{ 
    assert(q >= 0.0 && q <= 1.0); 

    const auto n = x.size(); 
    const auto id = (n - 1) * q; 
    const auto lo = floor(id); 
    const auto hi = ceil(id); 
    const auto qs = x[lo]; 
    const auto h = (id - lo); 

    return (1.0 - h) * qs + h * x[hi]; 
} 

要用它做：

std::vector<float> x{1,1,2,2,3,4,5,6}; 
std::cout << quant(x, 0.25) << std::endl; 
std::cout << quant(x, 0.50) << std::endl; 
std::cout << quant(x, 0.75) << std::endl;