대기열 <T> 대리스트

Question

현재 대기열에 List<T> (lst[0] 다음 lst.removeAt(0))을 사용하고 있습니다. 주어진 시간에 최대 약 20 개의 항목이 있습니다. 실제 Queue<T> 클래스가 있다는 것을 깨달았습니다. 대기열처럼 작동하는 List<T>을 통해 Queue<T>을 사용하면 어떤 이점 (성능, 메모리 등)이 있는지 궁금합니다.

Answer 1

성능을 프로파일 링 할 수 있습니다. 이 경우 항목 수가 매우 적기 때문에 실제로 가치있는 차이를 얻으려면 수백만 번 코드를 실행해야 할 수 있습니다.

내가 이런 말을합니다 : Queue<T>가 노출됩니다 더 명시 적으로, 사람들이 큐가 작동하는 방법을 알고 의도.

대기열과 같이 사용되는 목록은 명확하지 않습니다. 특히 불필요한 색인 생성이 많고 RemoveAt(magicNumber) 코드 인 경우 특히 그렇습니다. Dequeue은 코드 관리 관점에서 훨씬 더 많은 비용을 소모합니다.

그러면 측정 가능한 성능 문제가 발생하면 해결할 수 있습니다. 번으로 성능 문제를 미리 해결하지 마십시오.

Answer 2

Queue<T> 클래스가 대기열을 구현하고 List<T> 클래스가 목록을 구현한다는 사실 외에도 성능 차이가 있습니다.

List<T>에서 첫 번째 요소를 제거 할 때마다 큐의 모든 요소가 복사됩니다. 대기열에 20 개의 요소 만 있으면 눈에 띄지 않을 수 있습니다. 그러나 Queue<T>에서 다음 요소를 dequeue하면 이러한 복사가 발생하지 않으며 항상 빠릅니다. 큐가 길면 차이가 클 수 있습니다.

Answer 3

나는 HugoRune이 이미 지적한 것을 강조하고 싶었습니다. 대기열은 List보다 훨씬 빠르며,이 경우에는 메모리 액세스가 List에 대해 1 대 n 인 경우입니다. 유사한 사용 사례가 있지만 값이 수백 가지이며 대기열은 크기가 더 빠르기 때문에 사용합니다.

대기열이 목록 상단에 구현되는 것에 대한 메모 : 키는 "구현 됨"입니다. 순환 버퍼를 사용하는 대신 큐를 제거 할 때 모든 값을 새 메모리 위치에 복사하지 않습니다. 이는 List의 사용법이 내포하는 사본을 처벌하지 않고 "List of Top"에서 수행 할 수 있습니다.

Answer 4

짧은 대답은 :이 큐처럼 사용되는 경우
Queue<T>List<T>보다 빠릅니다. List<T>은 목록처럼 사용할 경우 Queue<T>보다 빠릅니다.

긴 않음 :
Queue<T>가 빠르며 O (1) 연산 인 동작을위한 대기열에서 제외된다. 배열의 후속 항목 블록 전체가 위로 이동하지 않습니다. Queue<T>은 임의 위치에서 쉽게 제거 할 필요가 없기 때문에 가능합니다. 따라서 머리 부분 (항목은 Dequeue)과 꼬리 위치 (항목이 Enqueue에 추가됨)를 유지합니다. 반면에 List<T> 상단에서 제거하려면 모든 후속 항목의 위치를 ​​하나씩 위로 이동해야합니다. 이것은 O (n)입니다. 최하위 경우, 대기열에서 제외하는 것은 대기열에서 제거하는 경우입니다. 루프에서 대기열을 풀면 속도 이점이 눈에 띄게됩니다.

인덱싱 된 액세스, 임의 검색 등의 경우 List<T>이 더 적합합니다. Queue<T>은 적절한 인덱스 위치를 찾기 위해 완전히 열거해야합니다 (IList<T>을 노출하지 않음).

즉, Stack<T> 대 List<T>은 훨씬 가깝고 푸시 및 팝핑 작업에는 성능 차이가 없습니다. 그들은 모두 끝내고 배열 구조의 끝에서 제거합니다 (둘 다 O (1) 임).

---

물론 의도를 나타내는 올바른 구조를 사용해야합니다. 대부분의 경우 그들은 목적에 맞게 맞춤 제작 되었기 때문에 더 잘 수행됩니다. 나는 성능상의 차이가 전혀 없다고 생각한다. Microsoft는 Queue<T>과 Stack<T>을 단순히 다른 의미에 대한 프레임 워크에 포함시키지 않았을 것이다. 그럴 경우 쉽게 확장 할 수있었습니다. SortedDictionary<K, V> 및 SortedList<K, V>에 대해 생각해보십시오. 둘 다 정확히 동일하지만 성능 특성만으로 구별됩니다. 그들은 BCL에있는 장소를 찾습니다.