|
С# Средство разработки на платформе .Net |
17.01.2011, 03:51
|
#1
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Список и его индексация.
Вот такая задачка появилась, хотя решил её другим методом, но хочеться найти более "деликатный" подход.
Есть у нас массив (контейнер). Я использую в данном случае простой List<>.
Содержит он объект.
У объекта есть различный набор полей, но также и ID (идентификационный номер).
Номер не меняется во время работы приложения, и грузится из бд.
Далее у контейнера имею функцию FindByID. В теле функции делаю простой цикл по всему контейнеру, и выдаю объект который имеет запрашиваемый ID.
Идентификационный номер не чередуется.
В общем, хочеться найти метод без перебора, но как-то не знаю за что уцепиться.
Есть ли идеи по реализации подобной задачи? А то контейнеров много, и порой выборок по ID тоже куча, при этом размеры контейнеров порой под 100 доходят.. Естественно постоянно перебирать, это как-то жестковато, хоть это и не сильно кусается, т.к. нету упора на скорость работы, но для себя хочеться найти оптимальный метод.
ЗЫ, по работе на C# сейчас, так что могу помочь по вопросам если что. Работаю с Windows Forms и DirectShow.
|
(Offline)
|
|
17.01.2011, 06:11
|
#2
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Список и его индексация.
индекс целочисленный? тогда нужен аналог std::map из плюсов. он может называться "словарь".
в плюсах было бы как то так:
std::map<int, MyObject> map;
map[ID] = SomeMyObject(ID);
искать:
думаю на шарпе будет не слишком сильно отличаться.
зы... на 100 элементах может быть эффективнее простой массив и линейный перебор по нему.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
17.01.2011, 10:38
|
#3
|
|
Ответ: Список и его индексация.
для серьезности стоит посмотреть сначала суда 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
|
|
|
Эти 4 пользователя(ей) сказали Спасибо за это полезное сообщение:
|
|
17.01.2011, 15:52
|
#4
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Список и его индексация.
Бинарный поиск по сортированному массиву рулит. Использую его для поиска значения на сплайне.
Я бы предложил вариант не париться и использовать Hashtable.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
18.01.2011, 01:16
|
#5
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: Список и его индексация.
Дима, мне как раз и не хватает базовых знаний - школы то нету, где это на первых курсах учат. А в блице как самоучка тебе база и не нужна. Вот и получается, вроде уже "там", а ещё даже и не "тут".
Но насчёт обработки. Дело в том, что у меня обновления постоянные идут. Пользователь может "триггерить" каждые 200мс перезагрузку таблицы. При этом её размер может быть огромным (самая большая 2к записей, без фильтров, обычно на деле около 2 сотен с одним фильтром, и менее 100 с более сложными фильтрами).
При этом отказаться от этого не могу, т.к. это админское приложение, и перезагрузка таблиц нужна достаточно часто.
Олег, спасибо за альтернативу гляну.
Pax, спасибо!
|
(Offline)
|
|
18.01.2011, 01:55
|
#6
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Список и его индексация.
Сообщение от MoKa
Олег, спасибо за альтернативу гляну.
|
Эта альтернатива Dictionary<TKey,TValue>
Кстати тоже неплохой словарь по производительности как и хэш-таблица.
Последний раз редактировалось moka, 18.01.2011 в 03:54.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
18.01.2011, 06:21
|
#7
|
☭
Регистрация: 26.09.2006
Сообщений: 6,035
Написано 1,474 полезных сообщений (для 2,707 пользователей)
|
Ответ: Список и его индексация.
немного не понимаю, зачем хэш-таблицы, когда у него ключ итак int?
и не задавай ... гхм ... таких вопросов
|
прально.. лучше спросить про ночлег в Москве. ну или на крайняк кто какой фильм посмотрел.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
18.01.2011, 11:49
|
#8
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Список и его индексация.
Если почитать про Dictionary<TKey,TValue>, то там написано, что он тоже реализован как хэш-таблица. А нужно использовать хэш-таблицу, потому что там реализован поиск по хэш-коду, чтобы не заморачиваться над алгоритмами поиска. Отличие Dictionary<TKey,TValue> от Hashtable в том, что первый универсальный тип, т.е. имеет возможность указать типы ключа и значения при создании экземпляра, что уменьшит количество приведений типов, чем при работе с хэш-таблицей у которой ключ и значение типа object.
UPD: Hashtable в некоторых случаях лучше, потому что предоставляет дополнительное управление сравнения элементов словаря.
Последний раз редактировалось pax, 18.01.2011 в 13:10.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
18.01.2011, 23:53
|
#9
|
.
Регистрация: 05.08.2006
Сообщений: 10,429
Написано 3,454 полезных сообщений (для 6,863 пользователей)
|
Ответ: Список и его индексация.
Сегодня на работе провёл тесты:
Класс FieldTestA, имеет int _id и string _name.
И класс FieldTestB, имеет string _name.
Параметры для доступа к ним, и конструкторы.
Создание в List<FieldTest> и Dictionary<int,FieldTestB>, одинакого, немного шустрее естественно в Dictionary.
Но при поиске разница огромная конечно. Чуть ли не в 10 раз. При этом в первом варианте ещё зависит от разницы максимального и минимального ID.
Во втором варианте сразу же профит: если нету такого Key, это можно получить спец функцией самого Dictionary, что избавляет от каких либо поисков.
И получение объекта сразу по ID, очень шустрое.
Только вот обратный вариант - получение ID по одному из параметров у объекта, всё равно нужно листать. Но всё-же, это в разы шустрее
|
(Offline)
|
|
19.01.2011, 00:52
|
#10
|
Дэвелопер
Регистрация: 06.04.2009
Адрес: Запорожье
Сообщений: 1,500
Написано 1,011 полезных сообщений (для 4,642 пользователей)
|
Ответ: Список и его индексация.
[кэп]Иногда надо таки документацию почитывать, в которой нюансы использования каждого контейнера расписаны.[/кэп]
__________________
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо .Squid за это полезное сообщение:
|
moka (19.01.2011), pax (19.01.2011)
|
19.01.2011, 17:15
|
#11
|
Бывалый
Регистрация: 04.01.2008
Адрес: Казахстан \ Талдыкорган
Сообщений: 659
Написано 170 полезных сообщений (для 509 пользователей)
|
Ответ: Список и его индексация.
Сообщение от .Squid
[кэп]Иногда надо таки документацию почитывать, в которой нюансы использования каждого контейнера расписаны.[/кэп]
|
И базовую книжечку по яп.
__________________
Жизнь как говориться игра- делать игры моя профессия(с)
Программирование, это религия! Её нужно исповедовать.
|
(Offline)
|
|
19.01.2011, 18:09
|
#12
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Список и его индексация.
Сообщение от FDsagizi
И базовую книжечку по яп.
|
[кэп]Все что нужно, есть в документации. По Net Framework одна из лучших документаций и на разных языках. В том числе и на русском. И для разных ЯП. В том числе C#, VB.NET и т.д.[/кэп]
|
(Offline)
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 13:00.
|