Удивительные различия в производительности: List.Constains, SortedList.ContainsKey, DataRowCollection.Contains, DataTable.Select, DataTable.FindBy

Question

Изначально я хотел попросить самый быстрый способ запроса Datatable для специальной строки.

Я проверил 5 различных методов их работы с удивительным (для меня) результатом.

Справочная информация: Я создал представление в базе данных MS Sql-Server 2005. Это представление имеет общее количество строк 6318. Поскольку я должен очень часто проверять, существует ли данный идентификатор в этом представлении, я задавался вопросом, что является наиболее эффективным способом сделать. Я создал DataAdapter в строго типизированном наборе данных, который возвращает все строки и заполняет Datatable. Мой первый подход состоял в том, чтобы создать общий общий список (из Int32) и заполнить его идентификаторами из представления один раз при запуске приложения. Затем используйте List.Contains , чтобы проверить, есть ли текущий идентификатор в этом списке. Поскольку все строки различны, я подумал, не будет ли быстрее использовать SortedList и его ContainsKey -метод. Затем я проверил также производительность прямого доступа к Datable с помощью Select-Method , его автоматически сгенерированного (когда столбец определен как первичный ключ) FindBy-method и последний, но не минимум DatarowCollection.Contains -Метод. Так что у меня есть 5 методов, чтобы проверить, находится ли мой идентификатор в этом представлении (или отображается список / SortedList).

Я измерил их производительность с помощью System.Diagnostics.StopWatch и получил несколько интересных результатов. Я думал, что SortedList.ContainsKey должен быть быстрее, чем List.Contains, потому что они различны и отсортированы, но верно обратное. Но самым удивительным для меня было то, что DataRowCollection.Contains-Method (о котором я впервые забыл), безусловно, самый быстрый. Это даже в 50 раз быстрее, чем метод dataTable.FindBy.

1. Чем вызваны эти различия?
2. Я забыл лучший способ?
3. Является ли мой метод измерения правильным (я думаю, мне лучше зациклить их и принять эти значения)?
4. Являются ли значения переносимыми или зависят от размера таблицы данных / коллекции?
5. После моего обновления (1000000 итераций) ContainsKey - самый быстрый. Это потому, что я всегда проверяю один и тот же идентификатор или вообще? Есть ли какой-нибудь SortedList без издержек KeyValue-Pair словаря?

Результаты [для 1000000 итераций *]

• Интервал времени 1 = SortedList.ContainsKey = Ø 0,65634 [ 238.1095 ] мс
• Timespan 2 = Список. Содержит = Ø 0,06802 [ 57045.37955 ] мс
• Timespan 3 = DataTable.FindByIdData (автоматически сгенерированный метод) = Ø 0,31580 [ 1542.62345 ] мс
• Интервал времени 4 = Таблица данных. Выберите = Ø 0,27790 [ 26029.39635 ] мс

• Timespan 5 = DataRowCollection.Contains = Ø 0,00638 [ 1202.79735 ] мс

  1.)
  Timespan 1: 0,6913 ms
  Timespan 2: 0,1053 ms
  Timespan 3: 0,3279 ms
  Timespan 4: 0,1002 ms
  Timespan 5: 0,0056 ms
  
  2.)
  Timespan 1: 0,6405 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3112 ms
  Timespan 4: 0,3872 ms
  Timespan 5: 0,0067 ms
  
  3.)
  Timespan 1: 0,6502 ms
  Timespan 2: 0,0588 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,1268 ms
  Timespan 5: 0,007 ms
  
  4.)
  Timespan 1: 0,6504 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3092 ms
  Timespan 4: 0,3893 ms
  Timespan 5: 0,0063 ms
  
  5.)
  Timespan 1: 0,6493 ms
  Timespan 2: 0,0586 ms
  Timespan 3: 0,3215 ms
  Timespan 4: 0,386 ms
  Timespan 5: 0,0063 ms
  
  
  
  Timespan 1: 0,6913 0,6405 0,6502 0,6504 0,6493 = Ø 0,65634
  Timespan 2: 0,1053 0,0588 0,0588 0,0586 0,0586 = Ø 0,06802
  Timespan 3: 0,3279 0,3112 0,3092 0,3092 0,3215 = Ø 0,31580
  Timespan 4: 0,1002 0,3872 0,1268 0,3893 0,3860 = Ø 0,27790
  Timespan 5: 0,0056 0,0067 0,0070 0,0063 0,0063 = Ø 0,00638
  

И ради полноты часть источника VB.Net :

Dim applies As Boolean
Dim clock As New System.Diagnostics.Stopwatch

clock.Start()
For i As Int32 = 1 To 1000000
    applies = sortedListAC17NextClaims.ContainsKey(myClaim.idData)
Next
clock.Stop()
Dim timeSpan1 As String = "Timespan 1: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = listAC17NextClaims.Contains(myClaim.idData)
Next
clock.Stop()
Dim timeSpan2 As String = "Timespan 2: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = Not MyDS.AC17NextClaims.FindByIdData(myClaim.idData) Is Nothing
Next
clock.Stop()
Dim timeSpan3 As String = "Timespan 3: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = MyDS.AC17NextClaims.Select("idData=" & myClaim.idData).Length > 0
Next
clock.Stop()
Dim timeSpan4 As String = "Timespan 4: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

clock.Reset()
clock.Start()
For i As Int32 = 1 To 1000000
    applies = MyDS.AC17NextClaims.Rows.Contains(myClaim.idData)
Next
clock.Stop()
Dim timeSpan5 As String = "Timespan 5: " & clock.Elapsed.TotalMilliseconds.ToString & " ms"

• UPDATE: Я изменил свои результаты и источник выше. В квадратных скобках указаны значения для 1000000 итераций. Теперь результат совершенно другой. Самый быстрый метод сейчас определенно - это ContainsKey из SortedList.

• ОБНОВЛЕНИЕ 2: Я забыл альтернативу использовать List.BinarySearch . Это кажется самым быстрым для меня:

  clock.Start()
  For i As Int32 = 1 To 1000000
      applies = listAC17NextClaims.BinarySearch(myClaim.idData) > -1
  Next
  clock.Stop()
  

  требуется всего 219,1805 мсек для выполнения 1000000 итераций, и, следовательно, он является самым быстрым без издержек SortedList-KeyValue-Pair. Я могу использовать его без сортировки списка, потому что DataAdapter заполнил элемент данных предложением Order By.

Answer 1

Почему бы вам не использовать коллекцию, которая имеет HashTable в качестве базовой структуры данных (Dictionary<TKey, TValue> или HashSet<T>)?HashTables должен предоставить O(1) время поиска, если в ключах нет коллизий (как вы заявили), и вам не нужны служебные данные для "сортировки".

РЕДАКТИРОВАТЬ: Если вы только хотите сохранить ключи, вы должны использовать HashSet , который доступен в .NET 3.5 и выше.

Из MSDN в SortedList:

Операции над объектом SortedList, как правило, выполняются медленнее, чем операции над объектом Hashtable из-за сортировки.

Чтобы нацелиться на .NET 2.0, вы можете бросить свой собственный или использовать предварительно созданный, например, Коллекции энергии Wintellect (вы также можете просто использовать источник).

Answer 2

Мне не кажется, что вы предоставляете достаточно работы, чтобы получить полезные тайминги здесь. Все ваше время меньше миллисекунды и почти наверняка просто шум - кеширование, джитинг, упреждение и т. Д.

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

Answer 3

Как уже было отмечено, ваш код запускает действие только один раз.Обычная тактика - запускать код несколько раз (скажем, выполнить 3 поиска), чтобы получить большие числа (поэтому, если 3 поиска занимают 0,9 секунды, можно сказать, что поиск занимает 0,3).Затем зациклите это несколько раз, чтобы позволить вам рассчитать среднее значение (включая стандартное отклонение, если хотите, чтобы отфильтровать дикие результаты), и, кроме того, запустить один раз, не обращая внимания на время записи, чтобы любой JIT

Кроме того, запустите код в режиме выпуска без отладчика.