Is a Queue faster than a List if the List is used in FIFO format?

Or the difference is only in the lines of code ...

PS Code example:

Case A:

var list = new List<int>() {1,2,3,4,5,6,7,8,9}; for (int i = 0; i < list.Count; i++) { // работа с list[i] if (BOOL) //BOOL в 90% случаев = true { list.RemoveAt(i--); } }

Case B:

 var queue = new Queue<int>(); queue.Enqueue(1); queue.Enqueue(2); queue.Enqueue(3); queue.Enqueue(4); queue.Enqueue(5); queue.Enqueue(6); queue.Enqueue(7); queue.Enqueue(8); queue.Enqueue(9); for (int i = 0; i < queue.Count; i++) { var integer = queue.Dequeue(); // работа с integer if (!BOOL) //BOOL в 90% случаев = true (Инвертировано) { queue.Enqueue(integer); } }

Case C:

 var list = new List<int>() {1,2,3,4,5,6,7,8,9}; for (int i = 0; i < list.Count; i++) { // работа с list[i] if (BOOL) //BOOL в 90% случаев = true { //Обработать как то иначе текущий list[i]... } }

PPS The case of "Process as otherwise" and the Queue did not describe

  • I don’t know about C #, but it usually means that a Queue has a certain size, so access to any O (1) element, as opposed to a list with O (n). - 0andriy
  • 3
    And how are you going to organize the work of List<T> on the principle of FIFO? "Out of the box" he does not have such functionality. With a great desire, this can be emulated, but the meaning of such witches is not very clear - DreamChild
  • The point is that the list is forwarded with a for, the element is deleted under certain conditions. In fact, at this stage, it performs the function of FIFO. Will there be a speed gain if you put this on a Queue? - Opossum
  • PS The number of elements is not known in advance. - Opossum
  • Foggy Finder, Alexander Petrov, thanks for the comments. Apparently it is not entirely clear what I meant. Described the example in question. - Opossum

3 answers 3

The short answer is that in your task Queue will work faster.

A little information

With Queue, with List, these are collections that are built on an array. The difference in the implementation - Queue contains two pointers to the head and tail, which are updated during Enqueue / Dequeue. So the compiler optimizations as well as the benefits of the processor cache will be identical.

If I understand your task correctly, then there is a frequent call to RemoveAt \ Dequeue. And here the differences are huge, because each time calling List.RemoveAt you copy all the elements to the right of the deleted to a new position. Calling Dequeue does not make expensive copying, it only reduces the pointer to the head of the queue.

  • As I understand it, A and C are the same in time - Opossum
  • Oh, pardonte, B (The one with the queue) and C (the one with the additional processing) - Opossum
  • Provided that the processing code and the code "// work with .." will be the same - Opossum
  • Yes, almost the same. If to replace Dequeue + Enqueue with Peek, it is generally the same. - panchenko.dm

Yes, the queue will be faster, because there is no need to move the tail.

And the code from the question is not at all like FIFO, besides it works differently (in the second bug).
It would be correct to simply create another list.

  • In fact, I now have implemented Case C - Opossum
  • Is the bug here? for (int i = 0; i <queue.Count; i ++) ... queue.Enqueue (integer); ? - Opossum
  • So two bugs ... Or zero ... Probably. - Qwertiy ♦
  • Um ... confused. - Opossum

If the question concerns the allocation of memory and it should be considered as an operation that has been running the longest and that is what we want to optimize, then listen to the answer @ panchenko.dm.

But usually the problem is in other places for example:

  1. file access
  2. network resources
  3. non-optimal database queries
  4. large object heap
  5. non-optimal algorithms for solving the problem

Be sure to check your solutions using load testing, benchmarks, for example benchmarkdotnet , or in the simplest case, using the stopwatch class.

Personally, I would pay more attention to the code and its design:

 foreach (var item in list) { // ваша преобработка } foreach (var item in list.Where(x => ShoudBeProceed(x))) // метод определяющий необходимость пост обработки { // ваша постобработка }

Agree that this code looks more succinctly and is easier to maintain because its cyclomatic complexity is lower.