Cách ngắn nhất để có được danh sách con của danh sách giá trị được sắp xếp nằm trong khoảng thời gian nhất định

Question

Hôm nay tôi đã tự hỏi mình có thể là mã ngắn nhất có thể để có được tất cả giá trị trong một vector được sắp xếp std::vector<double>, lớn hơn hoặc bằng a và nhỏ hơn hoặc bằng b.

tiếp cận đầu tiên của tôi là một cái gì đó như sau:

#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 

// Returns all values in sortedValues being greater equal start and smaller equal end; 
std::vector<double> cutValues(const std::vector<double>& sortedValues, double start, double end) { 
    std::vector<double> ret; 

    auto startIter=std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
    auto stopIter = std::upper_bound(sortedValues.begin(), sortedValues.end(), end); 
    std::copy(startIter, stopIter, std::back_inserter(ret)); 
    return ret; 
} 

int main(int argc, char **args) { 
    { 
     auto ret = cutValues({ 0.1,0.2,0.3 }, 0.1, 0.3); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
    { 
     auto ret = cutValues({ 0.12,0.2,0.31 }, 0.1, 0.3); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
    { 
     auto ret = cutValues({ 0.1,0.2,0.3 }, 0.2, 0.2); 
     std::copy(ret.begin(), ret.end(), std::ostream_iterator<double>(std::cout, ",")); 
     std::cout << std::endl; 
    } 
} 

nghĩ thứ hai của tôi là một cái gì đó rất đơn giản như sau:

std::vector<double> cutValues2(const std::vector<double>& sortedValues, double start, double end) { 
    std::vector<double> ret; 
    std::copy_if(sortedValues.begin(), sortedValues.end(), std::back_inserter(ret), [&start, &end](auto v) { return v >= start && v <= end; }); 
    return ret; 
} 

Nhưng xem xét trường hợp của chỉ loại bỏ các phần nhỏ từ một rất vector lớn nó có thể có một số vấn đề hiệu quả.

Bây giờ tôi tự hỏi bản thân mình, liệu có cách nào tốt hơn để làm điều đó không?

Answer 1

Một chút thay đổi phiên bản đầu tiên:

std::vector<double> cutValues(const std::vector<double>& sortedValues, double start, double end) { 
    auto startIter = std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
    auto stopIter = std::upper_bound(startIter, sortedValues.end(), end); 
    return std::vector<double>(startIter, stopIter); 
} 

Answer 2

Khi bạn biết bắt đầu khoảng thời gian của mình, không cần phải xem lại vectơ lỗ một lần nữa để tìm trình kết thúc. Bắt đầu tìm kiếm sau start_iterator thay vì

auto startIter = std::lower_bound(sortedValues.begin(), sortedValues.end(), start); 
if (startIter == sortedValues.end()) { 
    // either the last element was inside the interval (return it) or not (return empty vector) 
    return *(--startIter) == start ? {start} : {}; 
} 
auto stopIter = std::upper_bound(++startIter, sortedValues.end(), end); 
           // start from here 
std::copy(--startIter, stopIter, std::back_inserter(ret));  

Tối ưu hóa khác sẽ phụ thuộc vào nội dung. Ví dụ. Nếu bạn biết rằng phần tử cuối cùng bên trong khoảng thời gian của bạn sẽ là ở phần cuối của vectơ, nó sẽ có ý nghĩa hơn để lặp lại nó.

Bạn cũng có thể cân nhắc kiểm tra khoảng thời gian trước để ngăn chặn việc thực thi không cần thiết nếu giá trị lớn hơn hoặc bằng b.

Answer 3

Không ngắn hơn, nhưng nhìn chung hiệu quả hơn: sử dụng std::lower_bound để tìm sự bắt đầu của khoảng thời gian "thú vị", và tiếp tục sao chép miễn là các yếu tố nhỏ hơn giá trị tối đa của bạn; theo cách đó bạn đang định vị nhanh chóng (O (log N)) bắt đầu ngay cả đối với các vectơ lớn và bạn không lãng phí thời gian thực hiện tìm kiếm nhị phân lần nữa tìm kiếm kết thúc của khoảng thời gian - bạn sẽ tìm thấy nó trong suốt sao chép vòng lặp.

Có thể việc so sánh có thể là miễn phí, bởi vì double so sánh chúng cực kỳ rẻ, nhánh được dự đoán tốt (nó luôn giống nhau cho đến cuối bản sao) và phụ thuộc vào dữ liệu đã có trong bộ đệm; so sánh với một tìm kiếm nhị phân bổ sung, mà "nhảy xung quanh" trong bộ nhớ (địa phương bộ nhớ cache tồi tệ hơn) và có chi nhánh ít dự đoán hơn.

std::vector<double> cutValues(const std::vector<double>& sortedValues, double minv, double maxv) { 
    std::vector<double> ret; 
    auto end = sortedValues.end(); 
    for(auto it = std::lower_bound(sortedValues.begin(), end, minv); 
     it != end && *it <= max; ++it) { 
     ret.push_back(*it); 
    } 
    return ret; 
} 

Điều này có thể được viết lại theo cách tương tự để cutValues2 sử dụng các thuật toán STL của bạn, nhưng tôi không chắc chắn đó là nhiều sự cải thiện.

std::vector<double> cutValues(const std::vector<double>& sortedValues, double minv, double maxv) { 
    std::vector<double> ret; 
    std::copy_if(
     std::lower_bound(sortedValues.begin(), sortedValues.end(), minv), 
     sortedValues.end(), 
     std::back_inserter(ret), 
     [=](double v) { return v <= maxv; }); 
    return ret; 
} 

Answer 4

Bạn có thể viết chức năng STL-style và làm việc với bất kỳ loại container nào (và nó sẽ thanh lịch hơn).

template <typename ForwardIt, typename T> 
auto bounded_range(ForwardIt first, ForwardIt last, T lb, T ub) { 
    return std::pair{std::lower_bound(first, last, lb), std::upper_bound(first, last, ub)}; 
} 

std::vector<double> v1{0.1, 0.1, 0.2, 0.3, 0.3, 0.5, 0.7, 0.9}; 

auto [beg, end] = bounded_range(std::begin(v), std::end(v), 0.3, 0.5); 
std::vector<double> v2{beg, end}; 

// Or using 'std::make_from_tuple'. 
auto v3 = std::make_from_tuple<std::vector<double>>(bounded_range(std::begin(v), std::end(v), 0.3, 0.5)); 

_{Lưu ý: ví dụ sử dụng 17 C++ template argument deduction for class templates, và structured bindings.}