Cách (gần) tốt nhất để quản lý danh sách với các mục dịch chuyển

Question

Đây là tình huống:
Tôi có danh sách các chuỗi cửa hàng thực sự là số và có thể trở nên khá lớn (hàng trăm triệu mặt hàng).
Tôi lưu trữ các số dưới dạng chuỗi vì có tùy chọn hiển thị một số thông tin bổ sung là văn bản.

Vì điều này cần nhiều bộ nhớ để lưu trữ, tôi quyết định rằng tôi sẽ chỉ lưu trữ tối đa 5 triệu mục. (điều này sẽ chỉ mất khoảng 250-300mb).

Danh sách được lấp đầy bởi đầu ra của phép tính. Nếu một số được tìm thấy nó sẽ được thêm vào danh sách, con số này luôn luôn lớn hơn các mục hiện có.

Khi danh sách đạt đến 5 triệu, tôi muốn xóa mục đầu tiên và thêm mục mới vào danh sách.

thích:

// Why is this so freaking slow??? 
    if (_result.Count == 5000000) 
     _result.RemoveAt(0); 
    _result.Add(result); 

Như bạn có thể đọc trong các bình luận, điều này rất, rất, rất chậm. Nó chỉ cắt giảm hiệu suất của tôi xuống 15 lần. Trường hợp mất khoảng 2 phút, nó mất khoảng 30.

Tôi đã thử một vài điều với LINQ như .Skip(1).ToList nhưng điều đó sẽ tạo lại danh sách và do đó thậm chí còn chậm hơn.

Danh sách phải theo thứ tự đúng, do đó ghi đè theo chỉ mục không phải là một tùy chọn (trừ khi bạn có thể giải thích một công việc tốt đẹp xung quanh).

Câu hỏi của tôi:
Có cách nào tốt để làm điều này không?

Tôi thực sự cần hiệu suất ở đây vì có thể cần kiểm tra khoảng 10000000000 số. Điều này có thể mất một ngày là dĩ nhiên, nhưng một tháng là một chút quá nhiều :(

Cần biết thêm chi tiết, cảm thấy tự do để hỏi, tôi sẽ rất vui để cung cấp

Giải pháp:..
này thực hiện O (1)

// Set the _result 
    Queue<object> _result = new Queue<object>(5000000); 

    /// Inside the method 
    // If the count has reach it's max, dequeue the first item 
    if (_result.Count == 5000000) 
     _result.Dequeue(); 
    _result.Enqueue(result); 

Answer 1

Bạn có bao giờ sắp xếp lại các mục? Nếu không, hàng đợi hình tròn sẽ hoạt động khá tốt.

System.Collections.Generic.Queue là một, tôi chỉ cần kiểm tra kỹ.

Để mở rộng những lợi ích của một Queue, đây là việc thực hiện RemoveAt (xấp xỉ):

for (int i = 1; i < count; i++) 
    items[i-1] = items[i]; 
count--; 

Vì list[0] luôn là mục đầu tiên, bạn phải di chuyển tất cả mọi thứ để loại bỏ các mục đầu tiên.

Ngược lại, hàng đợi theo dõi riêng mục đầu tiên. Điều này thay đổi mã trên cho điều này:

head++ 

Answer 2

Tôi sẽ đề nghị bạn thực hiện tốt hơn hàng đợi tròn. Sau đó, bạn đẩy mọi thứ vào cuối hàng đợi và khi bạn hết dung lượng (được xác định bằng kích thước cố định) thì mỗi hoạt động sẽ yêu cầu bật đầu tiên và đẩy xuống phía dưới. O(1).

Lợi thế so với mảng là bạn sẽ không preallocate không gian cho đến khi cần thiết. Nhưng, cuối cùng, hãy xem xét thực sự để lưu trữ ints như, tốt, ints. Không có vấn đề gì hoạt động bạn sẽ thực hiện, bạn nên luôn luôn lưu trữ số như số.

Answer 3

Tại sao bạn không preallocate mảng, và có hai số nguyên, cho biết bắt đầu và kết thúc của mảng. Rõ ràng, cả hai sẽ bắt đầu bằng 0. Khi bạn chạy ra khỏi phòng, bạn chỉ cần bắt đầu quấn quanh.

Một ví dụ psuedo helper class:

class CircularArray 
{ 
    const int maxSize = 5000000; 
    private int[] arr = new int[maxSize]; 
    private int start = 0; 
    private int end = 0; 

    public void Add(int value) 
    { 
    int newEnd = (end + 1) % maxSize; 
    if (newEnd == start) 
     start = (start + 1) % maxSize; 
    end = newEnd; 
    arr[end] = value; 
    } 

    public int Get(int index) 
    { 
    int newIndex = (start + index) % maxSize; 
    return arr[newIndex]; 
    } 
} 

Answer 4

Khi bạn loại bỏ mục đầu tiên trong ArrayList, tất cả các mục khác sẽ được chuyển xuống. Một hàng đợi hình tròn sẽ cho phép bạn giữ nguyên thứ tự ban đầu và loại bỏ các thay đổi tiêu tốn thời gian xảy ra khi bạn loại bỏ phần đầu của danh sách.

Answer 5

Có thể là LinkedList<T> Class có thể giúp bạn? Việc loại bỏ và thêm vào cả hai đầu là hoạt động O (1), nhưng phép lặp lại sẽ là O (n), hoặc nếu bạn cần O (1) khi truy cập, bạn có thể sử dụng Dictionary hoặc SortedDictionary Thực hiện tùy chỉnh khác là QueueDictionary, tôi đã sử dụng nó khi tôi cần O (1) hoạt động trên cả hai thêm và loại bỏ ở cuối hoặc bắt đầu (Queue/Dequeue) và truy cập vào một giá trị. QueueDictionary tại đây: How would I implement a QueueDictionary, a combination of Queue and Dictionary in C#?