Подтвердить что ты не робот

Итерация словаря в С#

var dict = new Dictionary<int, string>();
for (int i = 0; i < 200000; i++)
    dict[i] = "test " + i;

Я повторил этот словарь, используя следующий код:

foreach (var pair in dict)
    Console.WriteLine(pair.Value);

Затем я повторил его, используя следующее:

foreach (var key in dict.Keys)
    Console.WriteLine(dict[key]);

И вторая итерация заняла ~ 3 секунды. Я могу получить оба ключа и значения с помощью обоих методов. Интересно, имеет ли второй подход недостаток. Поскольку Самый рейтинговый вопрос, который я могу найти об этом, не включает этот способ итерации словаря, Я хотел знать, почему никто не использует его и как он работает быстрее.

4b9b3361

ОТВЕТЫ

Ответ 1

В ваших тестах времени есть некоторые фундаментальные недостатки:

  • Console.Writeline - это операция ввода-вывода, которая занимает на порядок больше времени, чем доступ к памяти и вычисления ЦП. Любая разница во времени итерации, вероятно, затмевается стоимостью этой операции. Это как измерение веса гроша в чугунной печи.
  • Вы не указываете, как долго длилась общая операция, поэтому заявив, что на 3 секунды меньше, чем другой, бессмысленно. Если потребовалось 300 секунд для запуска первого и 303 секунды для запуска второго, тогда вы будете оптимизированы.
  • Вы не упоминаете, как вы измеряли время работы. Было ли время выполнения включать сборку и загрузку программы?
  • Вы не упоминаете повторяемость: несколько раз вы выполняли эти операции? Несколько сотен раз? В разных порядках?

Вот мои тесты. Обратите внимание, как я стараюсь, чтобы метод итерации был единственным, что менялось, и я включаю элемент управления, чтобы увидеть, сколько времени занимает только из-за цикла и назначения for:

void Main()
{
    // Insert code here to set up your test: anything that you don't want to include as
    // part of the timed tests.
    var dict = new Dictionary<int, string>();
    for (int i = 0; i < 2000; i++)
        dict[i] = "test " + i;
    string s = null;
    var actions = new[]
    {
        new TimedAction("control", () => 
        {
    for (int i = 0; i < 2000; i++)
            s = "hi";
        }),
        new TimedAction("first", () => 
        {
            foreach (var pair in dict)
            s = pair.Value;
        }),
        new TimedAction("second", () => 
        {
            foreach (var key in dict.Keys)
            s = dict[key];
        })
    };
    TimeActions(100, // change this number as desired.
        actions);
}


#region timer helper methods
// Define other methods and classes here
public void TimeActions(int iterations, params TimedAction[] actions)
{
    Stopwatch s = new Stopwatch();
    foreach(var action in actions)
    {
        var milliseconds = s.Time(action.Action, iterations);
        Console.WriteLine("{0}: {1}ms ", action.Message, milliseconds);
    }

}

public class TimedAction
{
    public TimedAction(string message, Action action)
    {
        Message = message;
        Action = action;
    }
    public string Message {get;private set;}
    public Action Action {get;private set;}
}

public static class StopwatchExtensions
{
    public static double Time(this Stopwatch sw, Action action, int iterations)
    {
        sw.Restart(); 
        for (int i = 0; i < iterations; i++)
        {
            action();
        }
        sw.Stop();

        return sw.Elapsed.TotalMilliseconds;
    }
}
#endregion

Результат

: 1.2173ms
первая: 9.0233ms
секунда: 18,1301мс

Таким образом, в этих тестах использование индексатора занимает примерно в два раза больше, чем итерация пар ключ-значение, что и я ожидаю *. Это примерно пропорционально, если я увеличиваю количество записей и количество повторений на порядок, и получаю те же результаты, если я запускаю два теста в обратном порядке.

* Почему я должен ожидать этого результата? Класс Dictionary, вероятно, представляет свои записи как KeyValuePairs внутренне, поэтому все, что ему действительно нужно делать, когда вы итерации его напрямую, проходит через свою структуру данных один раз, передавая вызывающей стороне каждую запись по мере ее появления. Если вы повторяете только Ключи, все равно нужно найти каждый KeyValuePair и дать вам значение свойства Key, так что только один шаг будет стоить примерно такой же суммы, как и итерация по нему в первую очередь. Затем вам нужно вызвать индексатор, который должен вычислить хэш для предоставленного ключа, перейти к правильному ведро хэш-таблицы и выполнить проверку равенства на ключах любого KeyValuePairs, который он находит там. Эти операции не очень дороги, но как только вы делаете их в N раз, это примерно так же дорого, как если бы вы снова повторяли внутреннюю структуру хэш-таблицы.