Поиск элемента. Какие есть способы?

Ну, типа, линейно еще можно.

Или же на них всё вообще и строится?

this; по крайней мере я не видел принципиально других путей.

автор наверняка имел в виду структуры данных, предназначенные для поиска, а не линейный поиск по какой-то левой структуре

[zanuda] хз. В тегах стоят контейнеры. Строка «Hello world!», тоже контейнер, например. [/zanuda]

По неупорядоченому множеству - перебор и метод Монте-Карло, остальные алгоритмы оперируют над упорядоченными множествами: хэш-таблица, дерево - это способы упорядочить; можно без них: сортировка элементов, хранение элементов в т.н. куче (heap, это не про динамическую память).

хеш-таблица не обязана упорядочивать элементы. Только дифференцировать. А дерево да, упорядочивает.

А вот про монте-карло не думал, но да, забавный вариант.

Куча концепций, начиная от высоких математический материй до практических реализаций, которые не дотягивают до заявленных теорией высот, зато хорошо делают свою работу. Но тебе же шашечки...

Представь, что есть N элементов из множества 0 ... U. Тогда основное правило в том, что при N, сопоставимом с U, используется массив или хеш-функция; если N значительно меньше U — бинарный поиск. Дело в том, что массив и хеш-функции слишком охотны до памяти, зато дают поиск за O(1); а дерево хорошо экономит память, зато дает O(log N) по времени.

Более возвышенно: нужно отталкиваться от необходимых запросов. Кардинально различаются случаи, когда просто нужно узнать, что элемент находится среди N элементов, или найти конкретный элемент. Вторая задача требует больше ресурсов. Первая задача решается за время O(1) при памяти O(N). Вторая задача при памяти O(N) в общем случае не решается поиском за константное время. Здесь сосредоточена масса работ, которые обозначены как проблема fully indexable dictionary. На сегодня, основной упор делается на хранение больших объемов текста в сжатом виде, при этом сохраняя возможность поиска по нему. Это обширная тематика, кури про Succinct Data Structures.

Здесь сосредоточена масса работ, которые обозначены как проблема fully indexable dictionary. На сегодня, основной упор делается на хранение больших объемов текста в сжатом виде, при этом сохраняя возможность поиска по нему. Это обширная тематика, кури про Succinct Data Structures.

Ты key words скажи более конкретные. А то так можно до смерти курить, но выхлопа будет не сильно много.

бинарный поиск

Оно же работает только на упорядоченном множестве, не?

Ты не обозначил, зачем тебе это всё. Ты собираешься обрабатывать гигабайты текста или второго абзаца достаточно? Отдельно упомяну проблему быстрого поиска при памяти O(N): в теории получены красивые асимптотики, зато на практике всё не так однозначно. Отдельная проблема, что многие берут за основу модель RAM, хотя на самом деле в компе I/O модель. Тут, насколько я могу судить, теория fully indexable dictionary отстает, но там понятно — основной упор на сжатие данных. Есть реализации поиска в дереве в модели I/O, здесь асимптотики такие же, что и у деревьев, но поиск происходит реально быстро.

Оно же работает только на упорядоченном множестве, не?

Если не упорядочено, то перебором ищется. В подавляющем количестве задач поиск нужен регулярно, а сами элементы обновляются редко. Лучше один раз отсортировать элементы за O(N log N), например. Зато потом получить быстрый поиск за O(log N) и удаление/добавление элемента за те же O(log N).

Ты не обозначил, зачем тебе это всё.

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

Интересно, можно ли свести задачу (в самом общем смысле) к чему-то кроме поиска эффективной хеш-функции или очередной модификации дерева поиска (коих тонны).

Вон выше высказали идею, что можно монте-карло заюзать. Метод выглядит странно, но в некоторых задачах может быть вполне приемлем. Вот такие идеи мне и интересны.

Из странного наверняка есть какие-нибудь квантовые алгоритмы: https://www.google.de/search?q=quantum algorithms search&oq=quantum algor...

Интересно, можно ли свести задачу (в самом общем смысле) к чему-то кроме поиска эффективной хеш-функции или очередной модификации дерева поиска (коих тонны).

Если иметь в виду абстрактную структуру «дерево» или «хеш-функцию», то рассуждать в их терминах никто не запрещает. Везде можно их увидеть, есть смотреть под нужным углом. Разве что квантовые алгоритмы, но пока что это чистая теория. Но когда речь идет о сверхбыстрых и компактных структурах, основной акцент — это кодировка, т.е., задача в том, чтобы данные закодировать таким образом, чтобы выполнять операции (часто это rank и select) и экономить память.

концепции поиска элемента в контейнере кроме деревьев поиска и хеш-функций

1. Прямое индексирование: контейнер является массивом, а ключ является непосредственным индексом в этом массиве.

2. map-reduce (удивительно, что никто до сих пор его не помянул)

концепции поиска

Есть ещё занятные вероятностные структуры данных, которые язык не поворачивается назвать разновидностью дерева/хештаблицы. Например, bloom filter.

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

Прошу прощения за вопрос в стиле анонiмуса. Придумана ли конструкция, такая, чтобы деревья и хеш-таблицы были двумя её частными случаями (то есть естественным получались бы из неё подстановкой определенных параметров)? Я имею ввиду не банальное хранение букетов в деревьях, а иллюстрацию общей природы таблиц и деревьев (если таковая имеется). Разглядеть в концепции дерева — хэш, а в концепции хэша — дерево, и параметризовать эту связь.

Фильтр Блума не дает поиска элемента. Он только утверждает, что элемент присутствует в массиве с некоторой вероятностью.

Фильтр Блума не дает поиска элемента.

Если только в качестве элемента не выступает сам факт наличия ключа.

Придумана ли конструкция, такая, чтобы деревья и хеш-таблицы были двумя её частными случаями (то есть естественным получались бы из неё подстановкой определенных параметров)?

Думаю, нет. Хеш-таблица отвечает на membership запрос, не отвечая на predecesor. В то время как для дерева реализация первого запроса влечет реализацию второго. Другими словами, хеш-таблица дает indexed dictionary, а дерево — fully indexed dictionary. Еще тут true_admin подметил, что поиск по дереву требует сортировки массива, а хеш-таблица — нет.

Рискуя сказать чушь.. Я воспринимаю деревья и хэш-таблицы примерно одинаково. Оба варианта основываются на том что мы данные кладём более-менее детерменистично чтобы сократить пространство поиска. У дерева на каждом уровне мы всё точнее и точнее узнаём положение элемента. А у хэш-таблицы... мы сильно ограничиваем пространство поиска раскладывая данные по «корзинам», они тоже бывают многоуровневые (гибрид деревьев и хэш-таблиц?)

Ты напираешь на отличия этих структур. Едва ли это тот угол зрения, который позволил бы в каждой из них разглядеть другую :)

поиск по дереву требует сортировки массива, а хеш-таблица — нет

Хэш-таблица в некотором роде упорядочена, в той проекции, которую даёт хеш-функция. Деревья упорядочены в той проекции, которую даёт оператор сравнения. Так ли принципиальна эта разница?

Деревья подразумевают иерархичность, в то время как аналогичный аспект хеш-таблиц — коллизии — является предметом творчества и эвристик разной степени упоротости. Не ясно только, куда тут приткнуть вопросы балансировки.

Впрочем, это всё никчемные философствования...

Думаю, нет.

Ок, значит никто из нас такой конструкции не знает. Спасибо за ответ.

квантовый тарантас и метод (поли?)Шора для sqrt(n) поиска на неупородоченном входе.

http://www.stepanovpapers.com/#SIMD_Decoding_TR :)

В большей степени, нежели уменьшение пространства, важно наличие отношений между элементами дерева. Например, есть такое дерево как Binary Indexed Tree, которое бинарным поиском находит сумму элементов, предшествующих данному. Еще можно вспомнить проблему RMQ (Range Minimum Query - минимум на отрезке), когда заданы границы для индексов, в пределах которых находится минимальный элемент. С хеш-таблицами такое быстро не провернуть, а для дерева понадобится O(log n) операций. И все потому, что дерево отсортировано.

Большущее спасибо! Не видел этой работы, хотя для дерева есть похожее --> http://openproceedings.org/EDBT/2014/paper_107.pdf