Hàng đợi <T> vs Danh sách <T>

Question

Tôi hiện đang sử dụng List<T> làm hàng đợi (sử dụng lst[0] rồi lst.removeAt(0)) để giữ đối tượng. Có khoảng 20 mục tối đa tại một thời điểm nhất định. Tôi nhận ra có một lớp thực tế Queue<T>. Tôi tự hỏi nếu có bất kỳ lợi ích (hiệu suất, bộ nhớ, vv) để sử dụng một Queue<T> trên một List<T> hoạt động như một hàng đợi?

Answer 1

Hiệu suất có thể được lược tả. Mặc dù trong trường hợp này của rất ít mục, bạn có thể cần phải chạy mã hàng triệu lần để thực sự có được sự khác biệt đáng giá.

Tôi sẽ nói điều này: Queue<T> sẽ phơi bày ý định một cách rõ ràng hơn, mọi người biết cách làm việc một hàng đợi của bạn.

Danh sách đang được sử dụng như hàng đợi không rõ ràng, đặc biệt nếu bạn có nhiều chỉ mục không cần thiết và mã RemoveAt(magicNumber). Dequeue có thể tiêu hao nhiều hơn từ quan điểm bảo trì mã.

Nếu điều này sau đó cung cấp cho bạn các vấn đề hiệu suất có thể đo lường, bạn có thể giải quyết vấn đề. Không giải quyết trước tiềm năng vấn đề hiệu suất trả trước.

Answer 2

Bên cạnh thực tế là lớp Queue<T> triển khai hàng đợi và lớp List<T> triển khai danh sách có sự khác biệt về hiệu suất.

Mỗi lần bạn xóa phần tử đầu tiên khỏi List<T> tất cả các phần tử trong hàng đợi sẽ được sao chép. Chỉ với 20 phần tử trong hàng đợi, nó có thể không đáng chú ý. Tuy nhiên, khi bạn dequeue các yếu tố tiếp theo từ Queue<T> không sao chép như vậy đang xảy ra và sẽ luôn luôn được nhanh hơn. Nếu hàng đợi dài thì sự khác biệt có thể là đáng kể.

Answer 3

Tôi muốn nhấn mạnh những gì HugoRune đã chỉ ra. Hàng đợi nhanh hơn đáng kể so với Danh sách, trong đó truy cập bộ nhớ là 1 so với n cho Danh sách trong trường hợp sử dụng này. Tôi có một trường hợp sử dụng tương tự nhưng tôi có hàng trăm giá trị và tôi sẽ sử dụng Hàng đợi vì nó là một thứ tự cường độ nhanh hơn.

Lưu ý về Hàng đợi đang được triển khai ở đầu Danh sách: khóa được "triển khai". Nó không sao chép mọi giá trị vào một vị trí bộ nhớ mới khi khử khí, thay vì sử dụng bộ đệm tròn. Điều này có thể được thực hiện trên "đầu Danh sách" mà không có hình phạt của các bản sao sử dụng trực tiếp Danh sách ngụ ý.

Answer 4

Câu trả lời ngắn:
Queue<T> nhanh hơn List<T> khi nó được sử dụng như một hàng đợi. List<T> nhanh hơn Queue<T> khi được sử dụng như danh sách.

Long trả lời:
Một Queue<T> là nhanh hơn cho dequeuing hoạt động, mà là một O (1) hoạt động. Toàn bộ khối các mục tiếp theo của mảng không được di chuyển lên. Điều này là có thể bởi vì Queue<T> không cần phải tạo điều kiện thuận lợi cho việc xóa khỏi các vị trí ngẫu nhiên, nhưng chỉ từ trên cùng. Vì vậy, nó duy trì một cái đầu (từ đó mục được kéo lên Dequeue) và vị trí đuôi (mà mục được thêm vào theo số Enqueue). Mặt khác, loại bỏ từ phía trên cùng của một List<T> đòi hỏi phải tự thay đổi vị trí của mỗi mục tiếp theo. Đây là O (n) - trường hợp xấu nhất nếu bạn đang loại bỏ từ đầu, đó là những gì một hoạt động dequeue. Ưu điểm tốc độ có thể được chú ý nếu bạn đang dequeuing trong một vòng lặp.

A List<T> có hiệu suất cao hơn nếu bạn cần truy cập được chỉ mục, truy xuất ngẫu nhiên, v.v. Queue<T> sẽ phải liệt kê đầy đủ để tìm vị trí chỉ mục phù hợp (không lộ IList<T>).

Điều đó nói rằng, Stack<T> và List<T> gần hơn, không có sự khác biệt về hiệu suất trong hoạt động đẩy và popping. Cả hai đều đẩy để kết thúc và loại bỏ từ kết thúc của các cấu trúc mảng (cả hai đều là O (1)).

---

Tất nhiên bạn nên sử dụng đúng cấu trúc cho biết mục đích. Trong hầu hết các trường hợp, chúng sẽ hoạt động tốt hơn vì chúng được thiết kế riêng cho mục đích. Tôi tin rằng không có sự khác biệt về hiệu suất nào cả, Microsoft sẽ không bao gồm Queue<T> và Stack<T> trong khuôn khổ chỉ cho các ngữ nghĩa khác nhau. Nó sẽ đơn giản dễ dàng mở rộng nếu đúng như vậy. Hãy suy nghĩ về SortedDictionary<K, V> và SortedList<K, V>, cả hai đều thực hiện giống hệt nhau nhưng được phân biệt bởi đặc tính hiệu suất duy nhất; họ tìm thấy một nơi trong BCL.