Список и его индексация.

[moka]

Вот такая задачка появилась, хотя решил её другим методом, но хочеться найти более "деликатный" подход.
Есть у нас массив (контейнер). Я использую в данном случае простой List<>.
Содержит он объект.
У объекта есть различный набор полей, но также и ID (идентификационный номер).
Номер не меняется во время работы приложения, и грузится из бд.
Далее у контейнера имею функцию FindByID. В теле функции делаю простой цикл по всему контейнеру, и выдаю объект который имеет запрашиваемый ID.
Идентификационный номер не чередуется.
В общем, хочеться найти метод без перебора, но как-то не знаю за что уцепиться.
Есть ли идеи по реализации подобной задачи? А то контейнеров много, и порой выборок по ID тоже куча, при этом размеры контейнеров порой под 100 доходят.. Естественно постоянно перебирать, это как-то жестковато, хоть это и не сильно кусается, т.к. нету упора на скорость работы, но для себя хочеться найти оптимальный метод.

ЗЫ, по работе на C# сейчас, так что могу помочь по вопросам если что. Работаю с Windows Forms и DirectShow.

[HolyDel]

индекс целочисленный? тогда нужен аналог std::map из плюсов. он может называться "словарь".
в плюсах было бы как то так:

std::map<int, MyObject> map;
map[ID] = SomeMyObject(ID);

искать:

objById = map[ID];

думаю на шарпе будет не слишком сильно отличаться.

зы... на 100 элементах может быть эффективнее простой массив и линейный перебор по нему.

для серьезности стоит посмотреть сначала суда http://en.wikipedia.org/wiki/Binary_search_tree
на деле проще всего создать пару <id, object>, составить массив из нее и отсортировать его по возрастанию id, далее делать бинарный поиск по id (не забываем о O(logn), для чего собственно всё это) и получать сразу object, единственное что такую структуру нужно будет изменять при изменении списка

а на самом-то деле c# же написан чтобы не задумываться о такой фигне (кого-собственно должно волновать как массив структур расположен в памяти и что думает об этом кеш процессора), идем в msdn и читаем "Represents a strongly typed list of objects that can be accessed by index. Provides methods to search, sort, and manipulate lists.", находим метод Find, пишем предикат и всё. Зачем думать о скорости вне real-time программ ?

ps. Серьезно MoKa, почитай вот это http://www.amazon.com/Algorithms-Str.../dp/0130224189 и не задавай ... гхм ... таких вопросов, это основы нормального программирования (не блиц-стайл), это настолько основы что дальше еще бескрайнее море
ps2. плюс еще рекомендую книгу ответов на все вопросы жизни http://www.amazon.com/Algorithm-Desi.../dp/0387948600

[pax]

Бинарный поиск по сортированному массиву рулит. Использую его для поиска значения на сплайне.

Я бы предложил вариант не париться и использовать Hashtable.

[moka]

Дима, мне как раз и не хватает базовых знаний - школы то нету, где это на первых курсах учат. А в блице как самоучка тебе база и не нужна. Вот и получается, вроде уже "там", а ещё даже и не "тут".
Но насчёт обработки. Дело в том, что у меня обновления постоянные идут. Пользователь может "триггерить" каждые 200мс перезагрузку таблицы. При этом её размер может быть огромным (самая большая 2к записей, без фильтров, обычно на деле около 2 сотен с одним фильтром, и менее 100 с более сложными фильтрами).
При этом отказаться от этого не могу, т.к. это админское приложение, и перезагрузка таблиц нужна достаточно часто.

Олег, спасибо за альтернативу гляну.
Pax, спасибо!

[pax]

Сообщение от MoKa

Олег, спасибо за альтернативу гляну.

Эта альтернатива Dictionary<TKey,TValue>
Кстати тоже неплохой словарь по производительности как и хэш-таблица.

[HolyDel]

немного не понимаю, зачем хэш-таблицы, когда у него ключ итак int?

и не задавай ... гхм ... таких вопросов

прально.. лучше спросить про ночлег в Москве. ну или на крайняк кто какой фильм посмотрел.

[pax]

Если почитать про Dictionary<TKey,TValue>, то там написано, что он тоже реализован как хэш-таблица. А нужно использовать хэш-таблицу, потому что там реализован поиск по хэш-коду, чтобы не заморачиваться над алгоритмами поиска. Отличие Dictionary<TKey,TValue> от Hashtable в том, что первый универсальный тип, т.е. имеет возможность указать типы ключа и значения при создании экземпляра, что уменьшит количество приведений типов, чем при работе с хэш-таблицей у которой ключ и значение типа object.

UPD: Hashtable в некоторых случаях лучше, потому что предоставляет дополнительное управление сравнения элементов словаря.

[moka]

Сегодня на работе провёл тесты:
Класс FieldTestA, имеет int _id и string _name.
И класс FieldTestB, имеет string _name.
Параметры для доступа к ним, и конструкторы.

Создание в List<FieldTest> и Dictionary<int,FieldTestB>, одинакого, немного шустрее естественно в Dictionary.
Но при поиске разница огромная конечно. Чуть ли не в 10 раз. При этом в первом варианте ещё зависит от разницы максимального и минимального ID.
Во втором варианте сразу же профит: если нету такого Key, это можно получить спец функцией самого Dictionary, что избавляет от каких либо поисков.
И получение объекта сразу по ID, очень шустрое.
Только вот обратный вариант - получение ID по одному из параметров у объекта, всё равно нужно листать. Но всё-же, это в разы шустрее

[.Squid]

[кэп]Иногда надо таки документацию почитывать, в которой нюансы использования каждого контейнера расписаны.[/кэп]

[FDsagizi]

Сообщение от .Squid

[кэп]Иногда надо таки документацию почитывать, в которой нюансы использования каждого контейнера расписаны.[/кэп]

И базовую книжечку по яп.

[pax]

Сообщение от FDsagizi

И базовую книжечку по яп.

[кэп]Все что нужно, есть в документации. По Net Framework одна из лучших документаций и на разных языках. В том числе и на русском. И для разных ЯП. В том числе C#, VB.NET и т.д.[/кэп]