Скорость вставки в LinkedList - PullRequest
Новая
       22

Скорость вставки в LinkedList

0 голосов
/ 24 октября 2011

Во время тестирования производительности я заметил кое-что интересное.

Я заметил, что самая первая вставка в LinkedList (C # Generics) происходит намного медленнее, чем любая другая вставка в начале списка.Я просто использовал шаблон Ced LinkedList и использовал AddFirst () для каждой вставки в LinkedList.Почему самая первая вставка самая медленная?

Первые пять результатов вставки:

Первая вставка в список: 0,0152 миллисекунды

Вторая вставка в список (в начале): 0,0006 миллисекунд

Третья вставка в список (в начале): 0,0003 миллисекунды

Четвертая вставка в список (в начале): 0,0006 миллисекунды

Пятая вставка в список(в начале): 0,0006 миллисекунд

Код тестирования производительности: 

        using (StreamReader readText = new StreamReader("MillionNumbers.txt"))
        {
            String line;
            Int32 counter = 0; 
            while ((line = readText.ReadLine()) != null)
            {

                watchTime.Start();
                theList.AddFirst(line);
                watchTime.Stop();
                Double time = watchTime.Elapsed.TotalMilliseconds;
                totalTime = totalTime + time; 
                Console.WriteLine(time);
                watchTime.Reset();
                ++counter; 
            }
            Console.WriteLine(totalTime);
            Console.WriteLine(counter);
            Console.WriteLine(totalTime / counter); 
        }

1 Ответ

3 голосов
/ 24 октября 2011

Сроки одной операции очень опасны - малейшее заикание может иметь огромное значение в результатах.Кроме того, не ясно, что вы сделали что-нибудь с LinkedList<T> перед этим кодом, что означает, что вы будете синхронизировать JITting AddFirst и, возможно, даже целые другие задействованные типы.

Сроки только первая вставка довольно сложна, так как, как только вы это сделали, вы не сможете легко повторить это.Тем не менее, вы можете время «вставить и удалить» несколько раз, как этот код: 

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    public static void Main(string[] args)
    {
        // Make sure we've JITted the LinkedList code
        new LinkedList<string>().AddFirst("ignored");

        LinkedList<string> list = new LinkedList<string>();        
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");        
    }

    const int Iterations = 100000000;

    static void TimeInsert(LinkedList<string> list)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            list.AddFirst("item");
            list.RemoveFirst();
        }
        sw.Stop();

        Console.WriteLine("Initial size: {0}; Ticks: {1}",
                           list.Count, sw.ElapsedTicks);
    }
}

Мои результаты: 

Initial size: 0; Ticks: 5589583
Initial size: 1; Ticks: 8137963
Initial size: 2; Ticks: 8399579

Это то, что я ожидал, в зависимости отво внутреннем представлении есть немного больше работы, связанной с подключением «предыдущей главы» при добавлении и удалении к уже заполненному списку.

Я предполагаю, что вы видите время JIT, но на самом деле ваш кодне совсем точное время, чтобы быть полезным, ИМО.

...