2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Оптимальная структура данных для добавления и поиска
Сообщение30.11.2017, 21:03 
Аватара пользователя


26/05/12
1534
приходит весна?
Подскажите, пожалуйста, существует ли такая структура данных, которая обеспечивает логарифмическое время поиска, как, например, сортированный массив, и в то же время константное время добавления элемента, как, например, связанный список. Добавление элемента должно осуществляться с сохранением сортированного порядка, поэтому, наверное, время добавления будет тоже логарифмическим, как и поиск. Дело ещё осложняется тем, что ключ, по которому производится сортировка у различных элементов может быть одинаков, но все такие элементы всё равно необходимо хранить в этой структуре. Что может удовлетворить мои нужды? Заранее благодарен любой помощи.

 Профиль  
                  
 
 Re: Оптимальная структура данных для добавления и поиска
Сообщение30.11.2017, 21:21 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
B@R5uk в сообщении #1270507 писал(а):
и в то же время линейное время добавления элемента, как, например, связанный список
Здесь точно линейное, а не константное?

Вообще все основные операции за логарифм умеют делать самобалансирующиеся деревья поиска. Вы какие оценки всё-таки хотите? И в худшем или в среднем случае?

B@R5uk в сообщении #1270507 писал(а):
ключ, по которому производится сортировка у различных элементов может быть одинаков, но все такие элементы всё равно необходимо хранить в этой структуре
Это как раз не проблема, просто вместо значения храните контейнер значений.

 Профиль  
                  
 
 Re: Оптимальная структура данных для добавления и поиска
Сообщение30.11.2017, 21:53 
Аватара пользователя


26/05/12
1534
приходит весна?
Спасибо за быстрый ответ.
mihaild в сообщении #1270513 писал(а):
Здесь точно линейное, а не константное?
Разумеется константное! Опечатку исправил.

mihaild в сообщении #1270513 писал(а):
Вообще все основные операции за логарифм умеют делать самобалансирующиеся деревья поиска.
То есть, например, класс TreeSet из коллекций языка Java?

mihaild в сообщении #1270513 писал(а):
Вы какие оценки всё-таки хотите? И в худшем или в среднем случае?
Вот если честно, то даже не знаю. Текущая подзадача у меня такая: вести непрерывно пополняющийся список сложных объектов и постоянно проверять каждый новый объект, нет ли уже точно такого же в списке. На какую оценку мне в этом случае стоит ориентироваться?

mihaild в сообщении #1270513 писал(а):
просто вместо значения храните контейнер значений
То есть деревья ломаются, если есть одинаковые элементы?

 Профиль  
                  
 
 Re: Оптимальная структура данных для добавления и поиска
Сообщение30.11.2017, 22:13 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
B@R5uk в сообщении #1270519 писал(а):
То есть, например, класс TreeSet из коллекций языка Java?
Это надо смотреть, что у него внутри (скорее всего да, какое-нибудь классическое дерево).

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

B@R5uk в сообщении #1270519 писал(а):
То есть деревья ломаются, если есть одинаковые элементы?
В принципе ничто не мешает в дереве хранить и узлы с одинаковым ключом (требуем чтобы значения в правом поддереве были больше либо равны значению в узле, а не строго больше). Позволяет ли это делать конкретная реализация - зависит от реализации.

 Профиль  
                  
 
 Re: Оптимальная структура данных для добавления и поиска
Сообщение02.12.2017, 13:30 
Аватара пользователя


26/05/12
1534
приходит весна?
mihaild, спасибо за советы. TreeSet оказывается как и любое множество из пакета коллекций Java допускает только уникальные элементы. Проблему решил так: сначала сравниваю хэши объектов, затем, если они совпадают, сравниваю по очереди все ключевые поля данных. Так достигается баланс между соблюдением требований и быстродействием. В итоге, подзадача решена, и задача, где это всё используется тоже заработала. Ещё раз, большое СПАСИБО.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group