Có cấu trúc dữ liệu giống mảng nào có thể tăng kích thước ở cả hai bên không?

Question

Tôi là một sinh viên làm việc trên một dự án nhỏ cho một khóa học điện toán hiệu suất cao, do đó hiệu quả đó là một vấn đề quan trọng.

Giả sử tôi có vectơ N float và tôi muốn loại bỏ các phần tử n nhỏ nhất và các phần tử n lớn nhất. Có hai cách đơn giản để làm điều này:

Một

sort in ascending order // O(NlogN) 
remove the last n elements // O(1) 
invert elements order  // O(N) 
remove the last n elements // O(1) 

B

sort in ascending order  // O(NlogN) 
remove the last n elements // O(1) 
remove the first n elements // O(N) 

In A đảo ngược các yếu tố đơn hàng yêu cầu trao đổi tất cả các yếu tố, trong khi ở B tháo đầu tiên n yếu tố yêu cầu di chuyển tất cả những người khác để chiếm các vị trí còn trống. Sử dụng std :: remove sẽ đưa ra cùng một vấn đề.

Nếu tôi có thể loại bỏ các phần tử n đầu tiên miễn phí thì giải pháp B sẽ rẻ hơn. Điều đó phải dễ dàng đạt được, nếu thay vì có vectơ, tức là một mảng có một số khoảng trống sau vector::end(), tôi sẽ có một vùng chứa có một số khoảng trống miễn phí trước vector::begin(). Vì vậy, câu hỏi là: không tồn tại đã là giống như mảng (nghĩa là bộ nhớ liền kề, không có danh sách liên kết) trong một số thư viện (STL, Boost) cho phép O (1) chèn/xóa trên cả hai mặt của mảng?

Nếu không, bạn có nghĩ rằng có giải pháp tốt hơn là tạo cấu trúc dữ liệu như vậy không?

Answer 1

Bạn đã nghĩ đến việc sử dụng std::partition với một functor tùy chỉnh như ví dụ dưới đây:

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

template<typename T> 
class greaterLess { 
    T low; 
    T up; 
    public: 
    greaterLess(T const &l, T const &u) : low(l), up(u) {} 
    bool operator()(T const &e) { return !(e < low || e > up); } 
}; 

int main() 
{ 
    std::vector<double> v{2.0, 1.2, 3.2, 0.3, 5.9, 6.0, 4.3}; 
    auto it = std::partition(v.begin(), v.end(), greaterLess<double>(2.0, 5.0)); 
    v.erase(it, v.end()); 

    for(auto i : v) std::cout << i << " "; 
    std::cout << std::endl; 

    return 0; 
} 

Bằng cách này bạn sẽ xóa các yếu tố từ vector của bạn trong thời gian O(N).

Answer 2

Hãy thử boost::circular_buffer:

Nó hỗ trợ lặp truy cập ngẫu nhiên, chèn thời gian liên tục và xóa các hoạt động ở đầu hoặc cuối của bộ đệm và khả năng tương tác với các thuật toán std.

Đã xem source, có vẻ như (và chỉ hợp lý) dữ liệu được lưu giữ dưới dạng khối bộ nhớ liên tục.

Thông báo trước là bộ đệm có dung lượng cố định và sau khi cạn kiệt, các phần tử sẽ bị ghi đè. Bạn có thể tự phát hiện các trường hợp như vậy và thay đổi kích thước vùng đệm theo cách thủ công hoặc sử dụng boost::circular_buffer_space_optimized với khả năng được công bố rộng rãi vì nó sẽ không phân bổ bộ đệm nếu không cần thiết.

Answer 3

Để thu nhỏ & phát triển một vector ở cả hai đầu, bạn có thể sử dụng ý tưởng lát, đặt thêm bộ nhớ để mở rộng trước thời gian ở mặt trước và mặt sau, nếu cần tăng trưởng hiệu quả.

Đơn giản chỉ cần tạo một lớp không chỉ có chiều dài mà còn cho các thành phần cuối cùng và một vectơ có kích thước phù hợp để tạo một cửa sổ dữ liệu trên khối lưu trữ cơ bản.Một lớp C++ có thể cung cấp các hàm nội tuyến, cho những thứ như xóa các mục, địa chỉ vào mảng, tìm giá trị lớn nhất thứ n, chuyển giá trị lát xuống hoặc lên để chèn các phần tử mới duy trì thứ tự sắp xếp. Không nên có sẵn các phần tử dự phòng, sau đó phân bổ động của một cửa hàng nổi lớn hơn, cho phép tăng trưởng liên tục với chi phí của một bản sao mảng.

Một bộ đệm tròn được thiết kế như một FIFO, với các phần tử mới được thêm vào cuối, loại bỏ ở phía trước và không cho phép chèn ở giữa, một lớp tự định nghĩa cũng có thể (trivially) hỗ trợ giá trị chỉ số mảng khác 0. N-1

Do vị trí bộ nhớ, tránh sự gián đoạn quá mức do chuỗi con trỏ và đường ống tính toán chỉ số trên bộ xử lý hiện đại, giải pháp dựa trên mảng (hoặc vectơ), có khả năng hiệu quả nhất, mặc dù sao chép phần tử khi chèn. Deque sẽ phù hợp nhưng nó không đảm bảo lưu trữ tiếp giáp.

Thông tin bổ sung bổ sung. Nghiên cứu các lớp học cung cấp lát, thấy một số lựa chọn thay thế đáng tin cậy để đánh giá:

A) std::slice which uses slice_arrays B) Boost Class Range

Hope đây là loại thông tin cụ thể mà bạn đang mong đợi, nói chung một giải pháp rõ ràng đơn giản là dễ bảo trì hơn, hơn là một khó khăn . Tôi mong đợi các lát và phạm vi trên các tập dữ liệu được sắp xếp, là khá phổ biến, ví dụ như lọc dữ liệu thử nghiệm trong đó "các ngoại lệ" bị loại trừ là các chỉ số bị lỗi. Tôi nghĩ một giải pháp tốt, nên thực sự là - O (NlogN), 2xO (1), với bất kỳ tìm kiếm nhị phân O (logN +1) nào để lọc các giá trị ngoại lệ, thay cho việc xóa số lượng cố định nhỏ hoặc giá trị lớn; điều quan trọng là "O" tương đối nhanh, đôi khi một thuật toán O (1) có thể thực tế chậm hơn đối với các giá trị thực tế của N hơn một giá trị O (N).

Answer 4

làm bổ sung cho câu trả lời @ 40two, trước khi phân vùng mảng, bạn sẽ cần tìm trục phân vùng, bạn sẽ cần tìm số nhỏ nhất thứ n và số thứ n lớn nhất trong mảng chưa được phân loại. Có một cuộc thảo luận về điều đó trong SO: How to find the kth largest number in unsorted array

Có một số thuật toán để giải quyết vấn đề này. Một số là xác định O (N) - trong số chúng là một biến thể trong việc tìm kiếm trung bình (trung vị của trung vị). Có một số thuật toán không xác định với trường hợp trung bình O (N). Một cuốn sách nguồn tốt để tìm các thuật toán đó là Introduction to algorithms. Cũng trong cuốn sách như

Vì vậy, cuối cùng, mã của bạn sẽ chạy trong một O (N) thời gian