c# List와 LinkedList 이터래이트 성능 비교

Bya programming trader

모든 프로그래밍 언어들에서 List는 메모리의 연속된 공간을 차지하고 LinkedList는 그렇지 않다. 메모리의 연속된 공간을 차지한다는 건 그 크기가 늘어날 때 통째로 복사를 할 새로운 공간이 있어야 하고 그 자리에 내용 전체를 복사한다는 의미로 대충 생각해 봐도 부담스러운 작업이다. 그러나 이런 구조에서는 이터래이트와 랜덤 액세스가 무척 빠르다. 반대로 연속된 공간을 차지하지 않는 경우에는 각 아이템이 그 앞뒤 아이템의 메모리 주소를 저장하고 있어야 한다. 이러면 각 아이템이 산지사방에 흩어져 있어서 이터래이트가 당연히 느려지고 특정 인덱스로 찾아 들어가려면 처음부터 훑고 지나가야 한다. 대신 아이템을 끼우고 더하고 지우고 하는 작업은 List에 비해 자유자재다. 따라서 이들 가운데 어떤 걸 써야 하느냐 하는 문제는 일련의 대이터를 주로 어떤 방법으로 다룰 것이냐 하는 관점에서 비교적 쉽게 판단할 수 있다.

List와 LinkedList의 장점 모두가 필요한 애매한 작업을 해야 한다면 이들 사이의 성능 차이가 구체적으로 어느 정도인지 파악을 하고 감수할 부분은 받아들여야 한다. 아래는 이터래이트를 할 때 성능의 차이를 확인하는 예제다. List와 LinkedList 모두에 백만 개의 아이템들을 만들고 List는 for로 LinkedList는 foreach와 for로 돌려 보니 차이가 크게 났다. 릴리스 빌드하여 워밍 업 결과를 빼고 안정된 다섯 번의 평균이 List는 4,909이고 LinkedList는 foreach의 경우 35,614였다. for를 이용한 경우에는 거의 멈추다시피 해서 결과에 의미가 없었다.

List<int> IntList = new();
LinkedList<int> IntLinkedList = new();

private void Form1_Load(object sender, EventArgs e)
{
    for (int i = 0; i < 1000000; i++)
    {
        IntList.Add(i);
        IntLinkedList.AddLast(i);
    }
}

private void button1_Click(object sender, EventArgs e)
{
    Stopwatch stopwatch = new();

    stopwatch.Start();

    for (int i = 0; i < IntList.Count; i++)
    {
        if (IntList[i] == 0)
        {

        }
    }

    textBox1.AppendText(stopwatch.ElapsedTicks.ToString("#,###") + "\r\n");
}

private void button2_Click(object sender, EventArgs e)
{
    Stopwatch stopwatch = new();

    stopwatch.Start();

    foreach (var item in IntLinkedList)
    {
        if (item == 0)
        {

        }
    }

    textBox2.AppendText(stopwatch.ElapsedTicks.ToString("#,###") + "\r\n");
}

private void button3_Click(object sender, EventArgs e)
{
    Stopwatch stopwatch = new();

    stopwatch.Start();

    for (int i = 0; i < IntLinkedList.Count; i++)
    {
        if (IntLinkedList.ElementAt(i) == 0)
        {

        }
    }

    textBox3.AppendText(stopwatch.ElapsedTicks.ToString("#,###") + "\r\n");
}

foreach 자체가 for보다 느린데 그 대상 자체도 이미 구조적으로 LinkedList가 이터래이트를 하기에는 느리게 설계되어 있으므로 저런 차이가 난다. foreach는 주로 Dictionary나 LinkedList처럼 메모리의 연속되지 않은 공간에 자리한 객체를 대상으로 쓴다. 물론 이들 객체에 for와 인덱스를 이용해 어거지로 이터래이트를 할 수도 있지만 이러면 위와 같은 참사가 벌어진다.

Post Views: 57
Post Tags: