Phát hiện phần tư

Question

Tôi đã viết một chương trình mà người dùng có thể nhập bất kỳ số lượng các giá trị vào một vector và nó là nghĩa vụ phải trả lại tứ phân vị, nhưng tôi cứ bị một "subscript vector ra khỏi phạm vi" lỗi:

#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

Thay vì làm std::sort(quantile.begin(), quantile.end()) một cách hơi rẻ hơn sẽ là

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

này sẽ không sắp xếp các mảng hoàn chỉnh, nhưng chỉ làm một "giữa các nhóm" loại 4 phần tư. Điều này tiết kiệm trên "sắp xếp trong nhóm" sắp xếp mà một đầy đủ std::sort sẽ làm.

Nếu mảng quantile của bạn không lớn, đó là một tối ưu hóa nhỏ. Tuy nhiên, hành vi thu nhỏ của std::nth_element là O(N) tuy nhiên, thay vì O(N log N) của số std::sort.

Answer 2

Nếu chỉ có một phần tử trong vector, hướng dẫn này là ra khỏi phạm vi:

quantile[mid-1] 

"i" bắt đầu từ giữa quá ba [0] là ra khỏi phạm vi

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

Answer 3

Dưới đây là một lỗi:

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

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

Các vector first không có bất kỳ nội dung, nhưng bạn cố gắng truy cập vào các nội dung. Cùng một vấn đề với third và vòng lặp của nó. Bạn có ý định sử dụng số push_back thay thế không?

Answer 4

Bạn cần preallocate first và third vectơ trước khi bạn đặt nội dung.

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

hoặc sử dụng push_back thay vì tập để first[i] và third[i]

Answer 5

Đây là chức năng quantile tương đương với MATLAB với suy tuyến tính:

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

Tìm tứ phân vị:

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++ template Chức năng này tính toán tứ phân vị dành cho bạn:

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

Để sử dụng nó:

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;