[C#] 대량의 목록에서 다수의 삭제가 필요한 경우 최적화

다음의 코드로 예시를 들어보겠습니다.

수십만 건의 목록에서 다수의 항목이 삭제가 될 때 생각보다 성능이 좋지 않습니다. List<T>의 구현이 항목 조회 및 추가에 최적화 되어 있기 때문입니다.

using System.Diagnostics;

var list = Enumerable.Range(1, 200000).ToList();

Console.WriteLine(list.Count);


var sw = Stopwatch.StartNew();

var index = 0;
foreach (var item in list.ToArray())
{
    if (item % 3 is 0)
    {
        list.RemoveAt(index);
        index--;
    }

    index++;
}

Console.WriteLine($"{sw.ElapsedMilliseconds} ms");

Console.WriteLine(list.Count);

| 출력

200000
5692 ms
133334

단지 20만 건 임에도 불구하고 제 컴퓨터에서 5초가 넘게 소요되었습니다.

List<T>의 내부 구현은 배열로 되어 있는데 항목 삭제 시 올바른 배열 인덱싱을 위해 배열 복사를 하기 때문입니다.

다음의 코드를 통해 처리 시간을 크게 개선할 수 있습니다.
(다만 항목의 순서가 바뀝니다. 항목의 순서가 중요하지 않을 경우 사용할 수 있습니다)

using System.Diagnostics;

var list = Enumerable.Range(1, 200000).ToList();

Console.WriteLine(list.Count);


var sw = Stopwatch.StartNew();

var index = 0;
foreach (var item in list.ToArray())
{
    if (item % 3 is 0)
    {
        list.RemoveUnorderedAt(index);
        index--;
    }
    index++;
}

Console.WriteLine($"{sw.ElapsedMilliseconds} ms");

Console.WriteLine(list.Count);


public static class ListExtensions
{
    public static void RemoveUnorderedAt<T>(this List<T> list, int index)
    {
        list[index] = list[^1];
        list.RemoveAt(list.Count - 1);
    }
}

| 출력

200000
1 ms
133334

이렇게 빨라진 이유는 마지막 항목을 삭제 항목 위치로 옮기고 마지막 항목을 삭제하므로 List<T>의 구현 상 배열 복사가 필요 없어지기 때문입니다.

16개의 좋아요

좋은 정보 감사드립니다!

5개의 좋아요

순서를 유지하면서 성능을 개선하는 방법이 없을까 싶어서 Span도 만들어 보고 여러 가지를 다 해봤는데도 List 클래스의 RemoveAt이나 RemoveAll 보다 잘 나오진 않네욥 ㅎㅎ

8개의 좋아요

C#의 List는 C++의 vector와 비슷하군요
이런 경우라면 LinkedList가 적합하지 않나 싶습니다.

6개의 좋아요

맞습니다 ㅎㅎ

혹은 하나의 항목씩 삭제하지 않고 동일한 Predicate로 한 번에 삭제하는 상황이라면 List의 RemoveAll 메서드를 사용하는 방법도 있지요

5개의 좋아요

이 짧은 소스코드가 이해가 안되네요ㅠㅠ

    public static void RemoveUnorderedAt<T>(this List<T> list, int index)
    {
        list[index] = list[^1];
        list.RemoveAt(list.Count - 1);
    }

여기서 값 복사가 되든 주소 복사가 되든, 어찌되었든 Copy의 개념이 되는거 아닌가요?
그래서 마지막 항목은 지워야될 항목으로 대체되면서 지워지지 않아야 할 마지막 항목이 지워지는건 아닐런지…
= 연산자가 복사가 아닌 이동의 개념으로 봐야되나요? 어찌해서 이런것인지…

5개의 좋아요

아… 이제 이해했습니다…
지워야 될 항목A 에다가 맨 마지막 항목 B를 복사하게 되면,
A항목은 B로 대체되고, 같은 값을 갖는 맨 마지막 인덱스는 그냥 지워버리는거군요…
이제 머리가 좀 안 돌아가는듯… :sob:

6개의 좋아요

저도 그부분 뭐지 하고 있었는데, 덕분에 바로 이해했습니다 감사합니다. :grinning:

5개의 좋아요

오! 1년만에 올라온 댓글 ㅋㅅㅋ

근데 저 10개 item 으로 다시 돌려봤는데…


결과가 이게 맞나욤?ㅅ?
(3,6,9 를 제거했는데 결과 list 에는 3만 빠지고 나머지는 남네요)

뭔가 이상한데… 뭘 잘못한 걸까요??
원래 list.RemoveAt(index); 를 가지고 다시 돌려보면


요렇게 나오네요?
저는 원래 의도한 동작이 list.RemoveAt(index); 요거인거 같은데…
의도한 게 RemoveUnorderedAt<T>() 방식인 건지 잘 모르겠네욤…;;;

4개의 좋아요

첫번째 결과에서 호출하신 인덱스가 궁금합니다.
올려주신 결과에서 보이는 순서로 파악하면, 3, 5, 7을 삭제하려고 하신게 아닌가 싶은데…
근데 remove 로그와 매칭이 안되는 느낌…

4개의 좋아요

foreach를 list의 복사본인 배열에서 수행하니 list[index]arr[index](item)간의 값이 불일치하게 되어 그런 것 같네요.

for (int index = 0; index < list.Count; index++)
{
    if (list[index] % 3 == 0)
    {
        list.RemoveUnorderedAt(index);
        index--;
    }
}

이렇게 list에 대해 for 문으로 순회하면 정상적으로 3, 6, 9가 삭제됩니다.

5개의 좋아요

암것두 안 건드리고 var list = Enumerable.Range(1, 10).ToList(); 요거 수행하면
위와 같이 나와욤.
원인은 @루나시아 님이 설명해주신대로 임다. ㅇㅅㅇ/

6개의 좋아요

이건 어떤가요?

		List<int> list = Enumerable.Range(1, 200000).ToList();

		Console.WriteLine(list.Count);

		var sw = Stopwatch.StartNew();
		list.RemoveAll(x => x % 3 == 0);
		sw.Stop();

		Console.WriteLine($"{sw.ElapsedMilliseconds} ms");
		Console.WriteLine(list.Count);

image

4개의 좋아요

신박한 접근이네요 :smiling_face_with_three_hearts:

4개의 좋아요

@dimohy 님의 블로그를 보다가 동일한 내용이 있어서 여기에 댓글을 달았는데,
거의 1년을 잠들어있던 이슈를 부활시켰네요…ㅋㅋ
덕분에 좋은 내용 많이 알아갑니당.
감사합니다 교수님!! (교수님이라고 불리시는거 불편하시면 담부터 안 그럴게요… 너무 해박하셔서 그래요…)

4개의 좋아요

흐 교수님 불편합니다. 그냥 디모이라고 해주세요. 나이는 많지만 정신은 청소년입니다 ㅎㅎ

4개의 좋아요

ㅋㅋㅋ 알겠습니다

4개의 좋아요

소스코드 그대로 들고가서 복붙해서 테스트 했었는데,
카운트만 보고 아 되는구나 생각했었네요…

리스트 item을 열거해보니 진짜 그렇게 나오는군요…

3개의 좋아요

이것이 스레드의 힘… 모두 대단하십니다

1개의 좋아요