Datastructure для быстрого и эффективного поиска

Я должен хранить отсортированные данные в структуре данных. Структура данных, которую я хочу использовать, представляет собой кучи или двоичное дерево поиска. Но я смущен тем, что лучше выполнять требование, то есть быстрый и эффективный поиск.Datastructure для быстрого и эффективного поиска

---- ПОДРОБНЕЕ ---

Я разработка приложения, которые получают данные из источника (скажем, сетка данных), а затем сохранить его в структуру данных. Данные, поступающие от станции GRID данных, представлены в виде отсортированных цифр. Сортированные данные могут быть в порядке возрастания или убывания.

Теперь я должен искать данные. и процесс должен быть эффективным и быстрым.

источник

2014-02-11 user3297557

Может помочь: http://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree –

Я уже проверил, что это касается хранения данных в отсортированной форме. мое требование - эффективный поиск. что было бы лучше, когда дело доходило до поиска некоторых конкретных данных в структуре данных. – user3297557

оба являются хорошими вариантами, используйте то, что легко реализовать. если вы реализуете BST, тогда ищите дерево AVL (BST легко реализовать и использовать, чем куча в соответствии со мной). –

Куча позволит вам быстрее искать минимальный элемент (найти его в O (1) раз, удалить его в O (log n)). Если вы создадите его другим способом, это позволит вам найти максимум, но вы не получите оба. Чтобы быстро найти произвольные элементы (в O (log n)), вам понадобится двоичное дерево поиска.

источник

2014-02-11 14:22:11

данные anyways сортируются так, что он может проходить через список, то есть зависит от его реализации. –

Хороший ответ. Я бы дополнил его, сказав, что вы можете посмотреть на сбалансированное двоичное дерево, в зависимости от того, что вы знаете о данных. То есть, если ваши данные в порядке, перебалансировка будет поддерживать эффективность дерева. – wmorrison365

Для получения дополнительной информации см. Skienna на http://www.algorist.com/ или выполните поиск по «алгоритму проектирования алгоритмов лыжны pdf» для загружаемого первого издания. – wmorrison365

Позвольте мне составить список потенциальных структур данных, и мы будем подробно:

бинарное дерево поиска - он содержит отсортированные данные таким образом добавление новых элементов является дорогостоящим (O (журнал N), я думаю). При поиске через него вы можете использовать двоичный поиск, который является O (log n). ИТ-память эффективна и не нуждается в дополнительной памяти.
Хеш-таблица (http://en.wikipedia.org/wiki/Hash_table) - каждый элемент хранится с хешем. Вы можете получить элемент, предоставив хэш. Ваши элементы не должны сортироваться, они должны только предоставить метод хеширования. Доступ к элементам - O (1), который, я полагаю, довольно приличный :)

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

Проверить это также: Advantages of Binary Search Trees over Hash Tables

Поэтому, на мой взгляд, из кучи и двоичного списка поиска, используйте Hash таблицу.

источник

2014-02-11 14:28:10

BST требует O (n) памяти, так же как и большинство других структур, включая хеш-таблицу, поэтому я не уверен, что вы подразумеваете под «не нужна дополнительная память». Поиск в хэш-таблице принимает O (1) (не O (n)), но хеш-таблица не является сортированной структурой данных, поэтому, по-видимому, не соответствует требованиям OP. – Dukeling

@ Dukeling Вы правы, не знаете, как я писал это :) –

Для эффективного поиска определенно предпочтите двоичное дерево поиска.

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

Так что поиск в куче принимает O (n), где - как это берет O (log n) в двоичном дереве поиска (self-balancing).

Куча действительно предпочтительнее, если вы в первую очередь заинтересованы в поиске и/или удалении минимума/максимума вместе с вставками.

Любой может быть построен в O (n), если вы получили уже отсортированные данные.

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

Если вы собираетесь искать точные значения, вам не нужна сортированная структура данных и вместо этого можно использовать hash table, который поддерживает ожидаемые O (1) поисковые запросы.

источник

2014-02-11 14:29:16 Dukeling

Вы можете построить кучу из произвольных данных (не обязательно отсортированных) в O (n). –

@JimMischel True (и полезная нота), он просто казался ненужной деталью во время записи, так как входные данные уже отсортированы. – Dukeling

Я бы пошел с хеш-таблицей с отдельной цепью с помощью AVLTree (я предполагаю, что происходит столкновение). Он будет работать лучше, чем O (logn), где n - количество элементов. После получения индекса с хэш-функцией, m элементов будет в этом индексе, где m меньше или равно n. (Обычно он намного меньше, но не больше). O (1) для хэширования и O (logm) для поиска в AVLTree. Это быстрее, чем двоичный поиск отсортированных данных.

источник

2017-01-08 12:15:48

Datastructure для быстрого и эффективного поиска

ответ

Смежные вопросы