Вопрос по performance, linked-list, list, c# – ).

4

жный дубликат:
Когда я должен использовать список против LinkedList

Этот вопрос связан с моим предыдущим вопросом, который был объединен: связан сСписок против LinkedList

Если я ожидаю, что не буду использовать доступ по индексу для моей структуры данных, сколько я сэкономлю, используя LinkedList over List? Если я не уверен на 100%, что никогда не буду использовать доступ по индексу, я бы хотел узнать разницу.

Предположим, у меня есть N экземпляров. вставка и удаление в LinkedList будет только операцией o (1), где, как и в List, это может быть O (n), но, поскольку она оптимизирована, было бы неплохо узнать, в чем разница для некоторых значений n. скажем, N = 1 000 000 и N = 1 000 000 000

Просто напишите простое консольное приложение и используйтеStopWatch чтобы увидеть разницу. Поверьте мне, это занимает 5 минут. Aliostad
FYI,List<T> является частью .NET, а не частью "библиотеки C #" John Saunders
Хорошая идея Алиостад HCP

Ваш Ответ

1   ответ
6

Это прошедшие тики для списка и связанного списка с 1000 000 элементов:

LinkedList 500 insert/remove operations: 10171
List 500 insert/remove operations: 968465

Связанный списокВ 100 раз быстрее по сравнению с 1000 000 предметов.

Вот код:

    static void Main(string[] args)
    {

        const int N = 1000*1000;
        Random r = new Random();
        LinkedList<int> linkedList = new LinkedList<int>();
        List<int> list = new List<int>();
        List<LinkedListNode<int>> linkedListNodes = new List<LinkedListNode<int>>();

        for (int i = 0; i < N; i++)
        {
            list.Add(r.Next());
            LinkedListNode<int> linkedListNode = linkedList.AddFirst(r.Next());
            if(r.Next() % 997 == 0)
                linkedListNodes.Add(linkedListNode);
        }

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();
        for (int i = 0; i < 500; i++)
        {
            linkedList.AddBefore(linkedListNodes[i], r.Next());
            linkedList.Remove(linkedListNodes[i]);
        }
        stopwatch.Stop();
        Console.WriteLine("LinkedList 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
        stopwatch.Reset();

        stopwatch.Start();
        for (int i = 0; i < 500; i++)
        {
            list.Insert(r.Next(0,list.Count), r.Next());
            list.RemoveAt(r.Next(0, list.Count));
        }
        stopwatch.Stop();
        Console.WriteLine("List 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);


        Console.Read();
    }
}

Похожие вопросы