Список и его индексация.
Вот такая задачка появилась, хотя решил её другим методом, но хочеться найти более "деликатный" подход.
Есть у нас массив (контейнер). Я использую в данном случае простой List<>. Содержит он объект. У объекта есть различный набор полей, но также и ID (идентификационный номер). Номер не меняется во время работы приложения, и грузится из бд. Далее у контейнера имею функцию FindByID. В теле функции делаю простой цикл по всему контейнеру, и выдаю объект который имеет запрашиваемый ID. Идентификационный номер не чередуется. В общем, хочеться найти метод без перебора, но как-то не знаю за что уцепиться. Есть ли идеи по реализации подобной задачи? А то контейнеров много, и порой выборок по ID тоже куча, при этом размеры контейнеров порой под 100 доходят.. Естественно постоянно перебирать, это как-то жестковато, хоть это и не сильно кусается, т.к. нету упора на скорость работы, но для себя хочеться найти оптимальный метод. ЗЫ, по работе на C# сейчас, так что могу помочь по вопросам если что. Работаю с Windows Forms и DirectShow. |
Ответ: Список и его индексация.
индекс целочисленный? тогда нужен аналог std::map из плюсов. он может называться "словарь".
в плюсах было бы как то так: Код:
std::map<int, MyObject> map; Код:
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 |
Ответ: Список и его индексация.
Бинарный поиск по сортированному массиву рулит. Использую его для поиска значения на сплайне.
Я бы предложил вариант не париться и использовать Hashtable. |
Ответ: Список и его индексация.
Дима, мне как раз и не хватает базовых знаний - школы то нету, где это на первых курсах учат. А в блице как самоучка тебе база и не нужна. Вот и получается, вроде уже "там", а ещё даже и не "тут".
Но насчёт обработки. Дело в том, что у меня обновления постоянные идут. Пользователь может "триггерить" каждые 200мс перезагрузку таблицы. При этом её размер может быть огромным (самая большая 2к записей, без фильтров, обычно на деле около 2 сотен с одним фильтром, и менее 100 с более сложными фильтрами). При этом отказаться от этого не могу, т.к. это админское приложение, и перезагрузка таблиц нужна достаточно часто. Олег, спасибо за альтернативу гляну. Pax, спасибо! |
Ответ: Список и его индексация.
Цитата:
Кстати тоже неплохой словарь по производительности как и хэш-таблица. |
Ответ: Список и его индексация.
немного не понимаю, зачем хэш-таблицы, когда у него ключ итак int?
Цитата:
|
Ответ: Список и его индексация.
Если почитать про Dictionary<TKey,TValue>, то там написано, что он тоже реализован как хэш-таблица. А нужно использовать хэш-таблицу, потому что там реализован поиск по хэш-коду, чтобы не заморачиваться над алгоритмами поиска. Отличие Dictionary<TKey,TValue> от Hashtable в том, что первый универсальный тип, т.е. имеет возможность указать типы ключа и значения при создании экземпляра, что уменьшит количество приведений типов, чем при работе с хэш-таблицей у которой ключ и значение типа object.
UPD: Hashtable в некоторых случаях лучше, потому что предоставляет дополнительное управление сравнения элементов словаря. |
Ответ: Список и его индексация.
Сегодня на работе провёл тесты:
Класс FieldTestA, имеет int _id и string _name. И класс FieldTestB, имеет string _name. Параметры для доступа к ним, и конструкторы. Создание в List<FieldTest> и Dictionary<int,FieldTestB>, одинакого, немного шустрее естественно в Dictionary. Но при поиске разница огромная конечно. Чуть ли не в 10 раз. При этом в первом варианте ещё зависит от разницы максимального и минимального ID. Во втором варианте сразу же профит: если нету такого Key, это можно получить спец функцией самого Dictionary, что избавляет от каких либо поисков. И получение объекта сразу по ID, очень шустрое. Только вот обратный вариант - получение ID по одному из параметров у объекта, всё равно нужно листать. Но всё-же, это в разы шустрее :) |
Ответ: Список и его индексация.
[кэп]Иногда надо таки документацию почитывать, в которой нюансы использования каждого контейнера расписаны.[/кэп]
|
Ответ: Список и его индексация.
Цитата:
|
Ответ: Список и его индексация.
Цитата:
|
Часовой пояс GMT +4, время: 15:49. |
vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot