Как я могу заставить свою функцию работать так же быстро, как" содержит " в ArrayList?

Во-первых, вы не запускаете его много раз и не сравниваете средние значения.

Во-вторых, ваш метод не будет jitted, пока он фактически не запустится. Таким образом, время компиляции just in time добавляется во время его выполнения.

Истинный тест будет выполняться каждый несколько раз и усреднять результаты (любое количество вещей может привести к тому, что один или другой будет медленнее для запуска X из общего числа Y), и ваши сборки должны быть предварительно скомпонованы с использованием ngen.exe .

Поскольку вы используете .NET 3.5, почему вы используете ArrayList Для начала, а не List<string>?

Несколько вещей, чтобы попробовать:

• вы можете посмотреть, помогает ли использование foreach вместо цикла for

• Вы можете кэшировать количество:

  public bool DoesContain(ArrayList list, object element)
  {
      int count = list.Count;
      for (int i = 0; i < count; i++)
      {
          if (list[i].Equals(element))
          {
              return true;
          }
          return false;
      }
  }
  

• Вы можете изменить сравнение:

  if (element.Equals(list[i]))
  

Хотя я не ожидаю, что что-либо из этого будет иметь существенное (положительное) значение, это следующие вещи, которые я бы попробовал.

Вам нужно это сделать? проводите ли вы этот сдерживающий тест более одного раза? Если это так, вы можете построить HashSet<T> и использовать его повторно.

Я не уверен, что вам разрешено публиковать код Reflector, но если вы откроете метод с помощью Reflector, вы увидите, что это, по сути, то же самое (есть некоторые оптимизации для нулевых значений, но ваша тестовая проводка не содержит нулей).

Единственное различие, которое я вижу, заключается в том, что вызов list[i] делает проверку границ на i, тогда как метод Contains этого не делает.

С действительно хорошим оптимизатором вообще не должно быть разницы, потому что семантика кажется одинаковой. Однако существующий оптимизатор может оптимизировать вашу функцию не так хорошо, как оптимизирован жестко закодированныйContains. Некоторые пункты для оптимизации:

1. сравнение со свойством каждый раз может быть медленнее, чем обратный отсчет и сравнение с 0
2. сам вызов функции имеет свой штраф за производительность
3. использование итераторов вместо явное индексирование может быть быстрее (foreach цикл вместо простого for)

Во-первых, если вы используете типы, которые вы знаете заранее, я бы предложил использовать дженерики. Так что список вместо ArrayList. Под капотом-Аррайлист.Содержит на самом деле делает немного больше, чем то, что вы делаете. Следующее от рефлектора:

public virtual bool Contains(object item)
{
    if (item == null)
    {
        for (int j = 0; j < this._size; j++)
        {
            if (this._items[j] == null)
            {
                return true;
            }
        }
        return false;
    }
    for (int i = 0; i < this._size; i++)
    {
        if ((this._items[i] != null) && this._items[i].Equals(item))
        {
            return true;
        }
    }
    return false;
}

Обратите внимание, что он разветвляется при передаче нулевого значения для элемента. Однако, поскольку все значения в вашем примере не являются null, дополнительная проверка на null в начале и во втором цикле должна теоретически занять длиннее.

Вы уверены, что имеете дело с полностью скомпилированным кодом? То есть, когда ваш код запускается в первый раз, он получает JIT-компиляцию, где, как очевидно, уже скомпилирован фреймворк.

После вашей правки я скопировал код и внес в него несколько улучшений.
Разница не была воспроизводимой, она оказалась проблемой измерения/округления.

Чтобы увидеть это, измените свои пробеги на следующую форму:

    sw.Reset();
    sw.Start();
    for (int i = 0; i < nr; i++)
    {          
        DoesContain(list,"zzz");            
    }
    total += sw.ElapsedMilliseconds;
    Console.WriteLine(total / nr);

Я только что передвинул несколько строк. Проблема JIT была незначительной при таком количестве повторений.

Я предполагаю, что ArrayList написан на C++ и может использовать преимущества некоторых микрооптимизаций (Примечание: это предположение).

Например, в C++ можно использовать арифметику указателей (в частности, увеличение указателя для итерации массива), чтобы быть быстрее, чем использование индекса.

Используя структуру массива, вы не можете искать быстрее, чем O (n) без какой-либо дополнительной информации. если вы знаете, что массив отсортирован, то можете воспользоваться алгоритмом бинарного поиска и потратить только o (log(n)) в противном случае вы должны использовать набор.

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

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

Использование SortedList<TKey,TValue>, Dictionary<TKey, TValue> или System.Collections.ObjectModel.KeyedCollection<TKey, TValue> для быстрого доступа на основе ключа.

var list = new List<myObject>(); // Search is sequential
var dictionary = new Dictionary<myObject, myObject>(); // key based lookup, but no sequential lookup, Contains fast
var sortedList = new SortedList<myObject, myObject>(); // key based and sequential lookup, Contains fast

KeyedCollection<TKey, TValue> он также быстр и позволяет индексировать поиск, однако он должен быть унаследован, поскольку он абстрактен. Поэтому вам нужна конкретная коллекция. Однако с помощью следующего вы можете создать универсальный KeyedCollection.

public class GenericKeyedCollection<TKey, TValue> : KeyedCollection<TKey, TValue> {
   public GenericKeyedCollection(Func<TValue, TKey> keyExtractor) {
      this.keyExtractor = keyExtractor;
   }

   private Func<TValue, TKey> keyExtractor;

   protected override TKey GetKeyForItem(TValue value) {
      return this.keyExtractor(value);
   }
}

Преимущество использования KeyedCollection заключается в том, что метод Add не требует указания ключа.