Продолжение вот этого

Автор: Sinix
Дата: 24.09.10

топика.

Дано:
Большой список, порядок важен, допускаются дубликаты, частые изменения.
Необходимо как можно быстрее получать все индексы по значению аля int[] IndexesOf(T value).

Есть два юз-кейза. В первом:
— много повторяющихся элементов
— новые значения добавляются в конец, удаляется все элементы начиная с i-го
— значения в списке достаточно часто заменяются новыми.
Производительность удаления неважна, вставки — важна. Текущая реализация здесь устраивает.

Во втором — коллекция используется абсолютно аналогично обычному списку, внешний код работает с IList<T>, внутри используется в первую очередь метод IndexesOf(). Этот вариант в текущей реализации малокритичен, но если бы его удалось ускорить, появилась бы возможность делать интересные плюшки.

Текущая релизация IndexedList<T> — код, тесты, измерение производительности (в коллекции убраны проверки аргументов и оптимизации под первый юз-кейз).

	Результаты
	SimpleIndexedList`1: tests passed! IndexedList`1: tests passed! StubIndexedList`1: Add: 5,0ms Remove: 0,0ms this[i]: 0,0ms Insert: 0,0ms RemoveAt: 0,0ms GetIndexes: 0,0ms SimpleIndexedList`1: Add: 16,0ms Remove: 1 052,0ms this[i]: 0,0ms Insert: 161,0ms RemoveAt: 395,0ms GetIndexes: 6 518,0ms IndexedList`1: Add: 974,0ms Remove: 3 503,0ms this[i]: 37,0ms Insert: 1 009,0ms RemoveAt: 2 476,0ms GetIndexes: 1,0ms Done. Press any key to exit.