Я использую C++, скажу, что хочу сохранить 40 имен пользователей, я просто использую массив. Однако, если я хочу сохранить 40000 имен пользователей, это хорошая идея с точки зрения скорости поиска? Какую структуру данных следует использовать для улучшения этой скорости?выбор структуры данных
Необходимо указать, какие требования к вставке и удалению. Нужно ли удалять вещи и вставлять их в случайные точки в последовательности?
Кроме того, почему требование поиска последовательно? Выполняете ли вы поиск, не подходящий для поиска хеш-таблицы?
На данный момент я предлагаю deque или list. Часто лучше выбрать контейнер с интерфейсом, который упрощает реализацию вашего алгоритма, а затем только изменить выбор, если производительность неадекватна, а альтернатива обеспечивает необходимое ускорение.
A vector имеет два принципиальных преимущества: нет накладных расходов на предмет объекта, хотя векторы будут чрезмерно распределены, чтобы предотвратить частое копирование, и объекты хранятся смежно, поэтому последовательный доступ имеет тенденцию быть быстрым. Это также его недостатки. Растущие векторы требуют перераспределения и копирования, а вставка и удаление из любого другого места, кроме конца вектора, также требуют копирования. Непрерывное хранилище может создавать проблемы для векторов с большим количеством объектов или больших объектов, так как непрерывные требования к хранилищу могут быть трудными для удовлетворения даже при частичной фрагментации памяти.
A list не требует постоянного хранения, но узлы списка обычно имеют служебные расходы на один объект из двух указателей (в большинстве случаев реализации). Это может быть значительным в списке очень маленьких объектов (например, в списке указателей, каждый узел имеет размер в 3 раза от элемента данных). Вставка и удаление из середины списка очень дешевы, а список узлов мне никогда не нужно переводить в память после создания.
A deque использует хранилище с памятью, поэтому он имеет низкую служебную информацию на объект, подобную вектору, но не требует непрерывного хранения по всему контейнеру, поэтому не имеет такой же проблемы с фрагментированными пространствами памяти. Это часто очень хороший выбор для коллекций и часто упускается из виду.
std :: vector и std :: list выглядят хорошо для этой задачи. Вы можете использовать массив, если знаете максимальное количество записей перед удалением.
Если вам нужен только последовательный поиск и хранение, то list является надлежащим контейнером.
Также vector не будет плохим выбором.
std :: list - плохой выбор, если требуется только последовательный доступ, поскольку он имеет большие накладные расходы, чем вектор или deque. список - это только хороший выбор, если требуется вставка/удаление в середине. –
Я проверил список на ручном устройстве. Список содержит 70 000 строк. Мне пришлось «собирать» и постепенно искать данные. Поиск был очень быстрым. Я также тестировал вектор и карту. Ну, список выиграл в моем случае. Это действительно проблема * решение *. –
Я имел в виду память наверху. Конечно, если дополнительное распределение по каждому предмету доступно, тогда это не проблема, поэтому, возможно, «плохой выбор» слишком завышен. Но я не думаю, что это правильно назвать «надлежащим контейнером», поскольку вы платите за то, что вы не используете. –
Как правило, предпочитайте vector по номеру list или, исключая запрет, массив C-стиля.
После того, как вектор заполнен, убедитесь, что он правильно упорядочен, используя алгоритм sort. Затем вы можете найти конкретную запись, используя либо find, binary_search, либо lower_bound. (Вам не нужно сортировать, чтобы использовать find.)
Серьезно, если вы не находитесь в среде с ограниченными ресурсами (встроенная платформа, телефон или другой). Используйте std::map, сохраните усилия по сортировке или поиску, и пусть контейнер позаботится обо всем. Это, возможно, будет сортированная древовидная структура, вероятно, баланс (например, Red-Black), что означает, что вы получите хорошую производительность поиска. Если размер ваших данных близок к размеру одного или двух указателей, издержки на память любой структуры данных, которые вы выбираете, являются небрежными.У вас, возможно, есть больше памяти, которую вы собираетесь использовать для данных, о которых вы думаете.
Как другие сказали, что очень мало хорошая причина, чтобы использовать массив ванили, если вы не хотите использовать map использовать std::vector или std::list в зависимости от того, требуется ли вставлять/удалять данные (=> список) или нет (= > vector)
Также рассмотрите, действительно ли вам нужны все эти данные в памяти, как разместить его на диске через sqlite. Или даже используйте sqlite для доступа к памяти. Все зависит от того, что вам нужно делать с вашими данными.
Я не понимаю, почему вы когда-либо использовали массив - размер не является проблемой. – 2009-07-05 11:11:38