Как я могу сделать так, чтобы моя функция работала так же быстро, как «Содержит» в ArrayList? - PullRequest
Новая
       29

Как я могу сделать так, чтобы моя функция работала так же быстро, как «Содержит» в ArrayList?

6 голосов
/ 25 февраля 2010

Я не могу понять несоответствия между временем, которое требуется для метода 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 работает лучше, но он достигает неизменно лучших результатов в каждом запуске. Итак, есть ли здесь какой-то недостаток для сторонних функций или что?

Ответы [ 11 ]

0 голосов
/ 25 февраля 2010

Пересмотрено после прочтения комментариев:

Он не использует некоторый хеш-алгоритм для быстрого поиска.

Страница:
...