(Это вопрос возникает из обсуждения, которое началось здесь)
Я сравнивал время поиска значения true
в List<bool>
с использованием List.Contains()
с таковым для скрученного вручную цикла.
Я вижу результаты, отличные от тех, о которых сообщают другие люди. Я пробовал это на нескольких системах, и цикл кажется быстрее в 2-3,5 раза на всех системах, на которых я пробовал. Эти системы варьируются от ноутбуков 5-летней давности под управлением XP с .Net 4 до последних ПК с Windows 8 и .Net 4.5.
Другие люди сообщают о других результатах, а именно о том, что List.Contains()
примерно такой же или немного быстрее, чем цикл.
Вот мой тестовый код.
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace ConsoleApplication1
{
internal class Program
{
private static void Main()
{
int size = 10000000;
int count = 10;
List<bool> data = new List<bool>(size);
for (int i = 0; i < size; ++i)
data.Add(false);
var sw = new Stopwatch();
for (int trial = 0; trial < 5; ++trial)
{
sw.Restart();
for (int i = 0; i < count; ++i)
TestViaLoop(data);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()");
sw.Restart();
for (int i = 0; i < count; ++i)
TestViaListContains(data);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()");
Console.WriteLine();
}
}
static bool TestViaLoop(List<bool> data)
{
for (int i = 0; i < data.Count; ++i)
if (data[i])
return true;
return false;
}
static bool TestViaListContains(List<bool> data)
{
return data.Contains(true);
}
}
}
Чтобы протестировать этот код, вы должны скомпилировать его как сборку x86 RELEASE и запустить вне отладчика.
Вот мои результаты на моем ПК с Windows 8 x64 с использованием платформы .Net 4.5 (хотя я получаю аналогичные результаты с .Net 4):
Times are in milliseconds
126 TestViaLoop()
441 TestViaListContains()
122 TestViaLoop()
428 TestViaListContains()
131 TestViaLoop()
431 TestViaListContains()
138 TestViaLoop()
426 TestViaListContains()
122 TestViaLoop()
439 TestViaListContains()
Как видите, в моей системе цикл занимает около 1/3 времени.
Теперь, если мы используем Resharper
, чтобы посмотреть на реализацию List.Contains()
, она будет выглядеть так:
bool Contains(T item)
{
if (item == null)
{
for (int j = 0x0; j < this._size; j++)
{
if (this._items[j] == null)
{
return true;
}
}
return false;
}
EqualityComparer<T> comparer = EqualityComparer<T>.Default;
for (int i = 0x0; i < this._size; i++)
{
if (comparer.Equals(this._items[i], item))
{
return true;
}
}
return false;
}
Хотя он использует Comparer.Equals()
(что должно сделать его медленнее, чем цикл), он также напрямую использует закрытый массив _items[]
, что позволяет избежать проверки диапазона индексов, которая будет использоваться для моей реализации цикла.
У меня три вопроса:
- Может ли кто-нибудь еще повторить результаты, которые я вижу? (Не забудьте запустить выпускную сборку вне отладчика.)
- Если да, может ли кто-нибудь объяснить, как мой цикл может быть намного быстрее, чем
List.Contains()
? - Если нет, может ли кто-нибудь объяснить, почему я вижу, что мой цикл работает быстрее?
Это представляет для меня не только академический интерес, так как я пишу код, который работает с большими объемами числовых данных и который должен быть максимально быстрым, а это то, о чем мне нужно знать. (Примечание: да, я профилирую вещи и пытаюсь оптимизировать только то, что нужно оптимизировать... Я знаю о проблемах преждевременной оптимизации.)
[РЕДАКТИРОВАТЬ]
Мне кажется, что это может быть связано с процессором. Все системы, на которых я пробовал, имеют процессоры Intel, хотя и очень разные модели, от четырехъядерных с тактовой частотой 3,8 ГГц до одноядерных Pentium M с тактовой частотой 1,6 ГГц...
Для тех из вас, кто видит, что цикл работает медленнее, вы используете процессоры Intel?
HashSet<T>
или похожий. - person Marc Gravell   schedule 17.04.2013comparer.Equals
). Двигаться дальше. - person spender   schedule 17.04.2013Contains
. Например, если я используюList.FindIndex(pred)
, чтобы найти индекс первого отрицательного элемента вList<int>
(это то, что нам нужно сделать в некоторых наших вычислениях), то цикл снова будет примерно в три раза быстрее... Я думаю, что хотя делает что-то совсем другое. - person Matthew Watson   schedule 17.04.2013Contains
был в два раза быстрее. - person Tim Schmelter   schedule 17.04.2013