Я не могу понять несоответствия между временем, которое требуется для метода Contains для поиска элемента в ArrayList, и временем, которое требуется для небольшой функции, которую я написал, чтобы выполнить то же самое. В документации говорится, что Contains выполняет линейный поиск, поэтому он должен быть в O(n), а не каким-либо другим более быстрым методом. Однако, хотя точные значения могут не иметь значения, метод Contains возвращает через 00:00:00.1087087 секунд, а моя функция занимает 00:00:00.1876165. Это может быть немного, но эта разница становится более очевидной при работе с массивами еще больших размеров. Чего мне не хватает и как мне написать свою функцию, чтобы соответствовать выступлениям Contains?
Я использую C # в .NET 3.5.
public partial class Window1 : Window
{
public bool DoesContain(ArrayList list, object element)
{
for (int i = 0; i < list.Count; i++)
if (list[i].Equals(element)) return true;
return false;
}
public Window1()
{
InitializeComponent();
ArrayList list = new ArrayList();
for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);
Stopwatch sw = new Stopwatch();
sw.Start();
//Console.Out.WriteLine(list.Contains("zzz 9000000") + " " + sw.Elapsed);
Console.Out.WriteLine(DoesContain(list, "zzz 9000000") + " " + sw.Elapsed);
}
}
EDIT:
Хорошо, ребята, посмотрите:
public partial class Window1 : Window
{
public bool DoesContain(ArrayList list, object element)
{
int count = list.Count;
for (int i = count - 1; i >= 0; i--)
if (element.Equals(list[i])) return true;
return false;
}
public bool DoesContain1(ArrayList list, object element)
{
int count = list.Count;
for (int i = 0; i < count; i++)
if (element.Equals(list[i])) return true;
return false;
}
public Window1()
{
InitializeComponent();
ArrayList list = new ArrayList();
for (int i = 0; i < 10000000; i++) list.Add("zzz " + i);
Stopwatch sw = new Stopwatch();
long total = 0;
int nr = 100;
for (int i = 0; i < nr; i++)
{
sw.Reset();
sw.Start();
DoesContain(list,"zzz");
total += sw.ElapsedMilliseconds;
}
Console.Out.WriteLine(total / nr);
total = 0;
for (int i = 0; i < nr; i++)
{
sw.Reset();
sw.Start();
DoesContain1(list, "zzz");
total += sw.ElapsedMilliseconds;
}
Console.Out.WriteLine(total / nr);
total = 0;
for (int i = 0; i < nr; i++)
{
sw.Reset();
sw.Start();
list.Contains("zzz");
total += sw.ElapsedMilliseconds;
}
Console.Out.WriteLine(total / nr);
}
}
Я сделал в среднем 100 рабочих времен для двух версий моей функции (прямая и обратная петля) и для функции Contains по умолчанию. Время у меня 136 и
133 миллисекунд для моих функций и отдаленный победитель 87 для Contains версии. Что ж, если раньше вы могли утверждать, что данных было мало, и я основал свои выводы на первом, изолированном прогоне, что вы скажете об этом тесте? Не только в среднем Contains работает лучше, но он достигает неизменно лучших результатов в каждом запуске. Итак, есть ли здесь какой-то недостаток для сторонних функций или что?