TStringList, динамический массив или связанный список в Delphi?
У меня есть выбор.
У меня есть несколько уже заказанных строк, которые мне нужно хранить и получать к ним доступ. Похоже, я могу выбирать между использованием:
- TStringList
- Динамический массив строк, и
Связанный список строк (односвязный)
и Алан в своем комментарии предложил мне также добавить к выбору:
TList<string>
При каких обстоятельствах каждый из них лучше других?
Что лучше для небольших списков (до 10 наименований)?
Что лучше для больших списков (более 1000 наименований)?
Что лучше всего подходит для огромных списков (более 1 000 000 наименований)?
Что лучше всего минимизировать использование памяти?
Что лучше всего минимизировать время загрузки, чтобы добавить дополнительные элементы в конце?
Что лучше всего минимизировать время доступа для доступа ко всему списку от первого до последнего?
На этой основе (или любой другой), какая структура данных будет предпочтительнее?
Для справки я использую Delphi 2009.
Дмитрий в комментарии сказал:
Опишите вашу задачу и схему доступа к данным, тогда можно будет дать вам точный ответ
Хорошо. У меня есть программа генеалогии с большим количеством данных.
Для каждого человека у меня есть ряд событий и атрибутов. Я храню их в виде коротких текстовых строк, но их много для каждого человека, от 0 до нескольких сотен. И у меня есть тысячи людей. Мне не нужен произвольный доступ к ним. Мне нужно, чтобы они ассоциировались как ряд строк в известном порядке, прикрепленных к каждому человеку. Это мой случай с тысячами "маленьких списков". Они требуют времени для загрузки и использования памяти, а также для доступа к ним, если они мне понадобятся (например, для экспорта всего сгенерированного отчета).
Затем у меня есть несколько больших списков, например, все имена разделов моего "виртуального" дерева, которые могут иметь сотни тысяч имен. Опять же мне нужен только список, к которому я могу получить доступ по индексу. Они сохраняются отдельно от древовидного представления для эффективности, и древовидное представление извлекает их только по мере необходимости. Это занимает некоторое время для загрузки и очень дорого с точки зрения памяти для моей программы. Но мне не нужно беспокоиться о времени доступа, потому что только несколько обращаются одновременно.
Надеюсь, это даст вам представление о том, чего я пытаюсь достичь.
PS Я написал много вопросов по оптимизации Delphi здесь, в Stackru. Моя программа читает 25 МБ файлов с 100 000 человек и создает структуры данных, а также отчет и древовидную структуру для них за 8 секунд, но использует для этого 175 МБ ОЗУ. Я работаю над уменьшением этого, потому что я стремлюсь загружать файлы с несколькими миллионами людей в 32-битной Windows.
Я только что нашел несколько отличных предложений по оптимизации TList в этом вопросе Stackru: есть ли более быстрая реализация TList?
7 ответов
Если у вас нет особых потребностей, TStringList трудно победить, потому что это обеспечивает TStrings интерфейс, который многие компоненты могут использовать напрямую. С TStringList.Sorted := Trueбудет использоваться двоичный поиск, что означает, что поиск будет очень быстрым. Вы также получаете сопоставление объектов бесплатно, каждый элемент также может быть связан с указателем, и вы получаете все существующие методы для маршалинга, потоковых интерфейсов, запятого, текста с разделителями и так далее.
С другой стороны, для особых нужд, если вам нужно сделать много вставок и удалений, тогда лучше будет использовать что-то более подходящее для связанного списка. Но тогда поиск становится медленнее, и это действительно редкий набор строк, который никогда не нуждается в поиске. В таких ситуациях часто используется некоторый тип хэша, когда хеш создается, скажем, из первых 2 байтов строки (предварительно выделите массив длиной 65536, и первые 2 байта строки преобразуются непосредственно в хеш индекс в этом диапазоне), а затем в этом месте хеширования сохраняется связанный список с каждым ключом элемента, состоящим из оставшихся байтов в строках (для экономии места - индекс хеша уже содержит первые два байта). Тогда начальный поиск по хешу - O(1), а последующие вставки и удаления - быстрый-связанный-список. Это компромисс, которым можно манипулировать, и рычаги должны быть ясны.
TStringList. Плюсы: расширенная функциональность, позволяющая динамически увеличивать, сортировать, сохранять, загружать, искать и т. Д. Минусы: при большом объеме доступа к элементам по индексу Strings[Index] вносит ощутимую потерю производительности (несколько процентов), сравнивая чтобы получить доступ к массиву, накладные расходы памяти для каждой ячейки элемента.
Динамический массив строк. Плюсы: сочетает в себе способность динамически расти, как TStrings, с самым быстрым доступом по индексу, минимальным использованием памяти другими. Минусы: ограниченная стандартная функциональность "списка строк".
Связанный список строк (односвязный). Плюсы: линейная скорость добавления элемента в конец списка. Минусы: самый медленный доступ по индексу и поиску, ограниченная стандартная функциональность "списка строк", накладные расходы памяти для указателя "следующий элемент", накладные расходы на выделение памяти для каждого элемента.
TList
. Как указано выше. TStringBuilder. У меня нет хорошей идеи, как использовать TStringBuilder в качестве хранилища для нескольких строк.
На самом деле подходов гораздо больше:
- связанный список динамических массивов
- хеш-таблицы
- базы данных
- бинарные деревья
- так далее
Лучший подход будет зависеть от задачи.
Что лучше для небольших списков (до 10 наименований)?
Любой, может быть даже статический массив с переменной общего количества элементов.
Что лучше для больших списков (более 1000 наименований)? Что лучше всего подходит для огромных списков (более 1 000 000 наименований)?
Для больших списков я выберу: - динамический массив, если мне нужно много доступа по индексу или поиск определенного элемента - хеш-таблицу, если мне нужно искать по динамически связанному списку динамических массивов, если мне нужно много элементов добавляет и нет доступа по индексу
Что лучше всего минимизировать использование памяти?
динамический массив будет кушать меньше памяти. Но вопрос не в накладных расходах, а в том, по какому количеству пунктов эти накладные расходы становятся разумными. А потом как правильно обрабатывать это количество предметов.
Что лучше всего минимизировать время загрузки, чтобы добавить дополнительные элементы в конце?
динамический массив может динамически увеличиваться, но при очень большом количестве элементов диспетчер памяти может не найти непрерывную область памяти. При этом связанный список будет работать до тех пор, пока не будет памяти хотя бы для ячейки, но за счет стоимости выделения памяти для каждого элемента. Смешанный подход - связанный список динамических массивов должен работать.
Что лучше всего минимизировать время доступа для доступа ко всему списку от первого до последнего?
динамический массив.
На этой основе (или любой другой), какая структура данных будет предпочтительнее?
Для какой задачи?
Если ваша заявленная цель состоит в том, чтобы улучшить вашу программу до такой степени, что она может загружать файлы генеалогии с миллионами людей в ней, то выбор между четырьмя структурами данных в вашем вопросе на самом деле не приведет вас туда.
Посчитайте - вы загружаете файл размером 25 МБ, в котором содержится около 100000 человек, что приводит к тому, что ваше приложение потребляет 175 МБ памяти. Если вы хотите загружать файлы с несколькими миллионами человек, вы можете оценить, что без радикальных изменений в вашей программе вам нужно будет умножить свои потребности в памяти на n * 10 также. Невозможно сделать это в 32-битном процессе, сохраняя все в памяти так, как вы это делаете в настоящее время.
У вас есть два варианта:
Не хранить все в памяти сразу, вместо этого использовать базу данных или файловое решение, из которого вы загружаете данные, когда вам это нужно. Я помню, у вас уже были другие вопросы по этому поводу, и, вероятно, вы отказались от них, поэтому я оставлю это на этом.
Храните все в памяти, но максимально экономно. Пока нет 64-битной Delphi, это должно учитывать несколько миллионов человек, в зависимости от того, сколько данных будет для каждого человека. Перекомпиляция для 64-битной системы также устранит этот предел.
Если вы выберете второй вариант, вам нужно будет более агрессивно минимизировать потребление памяти:
Используйте интернирование строк. Каждый загруженный элемент данных в вашей программе, который содержит одни и те же данные, но содержится в разных строках, в основном тратит впустую память. Я понимаю, что ваша программа - это программа просмотра, а не редактор, так что вы, вероятно, можете обойтись только добавлением строк в пул интернированных строк. Выполнение интернирования строк с миллионами строк по-прежнему затруднено, и публикации в блоге "Оптимизация потребления памяти с помощью пулов строк" в блоге SmartInspect могут дать вам хорошие идеи. Эти ребята регулярно работают с огромными файлами данных и должны были заставить их работать с теми же ограничениями, с которыми вы сталкиваетесь.
Это также должно связать этот ответ с вашим вопросом - если вы используете интернирование строк, вам не нужно будет хранить списки строк в ваших структурах данных, но списки индексов пула строк.
Также может быть полезно использовать несколько пулов строк, например, один для имен, но другой - для таких мест, как города или страны. Это должно ускорить вставку в бассейны.Используйте строковое кодирование, которое дает наименьшее представление в памяти. Хранение всего как собственной строки Unicode в Windows, вероятно, будет занимать гораздо больше места, чем хранение строк в UTF-8, если только вы регулярно не работаете со строками, которые содержат в основном символы, которым требуется три или более байтов в кодировке UTF-8.
Из-за необходимого преобразования набора символов вашей программе потребуется больше циклов ЦП для отображения строк, но с таким количеством данных это достойный компромисс, поскольку доступ к памяти будет узким местом, а меньший размер данных помогает уменьшить нагрузку на доступ к памяти.
Возможная альтернатива:
Недавно я обнаружил SynBigTable ( http://blog.synopse.info/post/2010/03/16/Synopse-Big-Table), который имеет класс TSynBigTableString для хранения больших объемов данных с использованием строкового индекса.
Очень простая, однослойная реализация с возможностью создания больших таблиц, в которой в основном используется дисковое хранилище, что потребляет намного меньше памяти, чем ожидалось при хранении сотен тысяч записей
Так просто как:
aId: = UTF8String (Формат ('%s.%s', [имя, фамилия]));
bigtable.Add (data, aId)
а также
bigtable.Get(идентификатор, данные)
Один улов, индексы должны быть уникальными, а стоимость обновления немного высока (сначала удалите, а затем вставьте заново)
Один вопрос: как вы делаете запрос: сопоставляете ли вы строки или запросы по идентификатору или позиции в списке?
Подходит для небольших # строк:
Что бы ни делало вашу программу легкой для понимания. Читаемость программы очень важна, и вы должны жертвовать ею только в реальных горячих точках в вашем приложении для скорости.
Лучше всего для памяти (если это самое большое ограничение) и времени загрузки:
Храните все строки в одном буфере памяти (или в файле отображения памяти) и сохраняйте только указатели на строки (или смещения). Всякий раз, когда вам нужна строка, вы можете вырезать строку, используя два указателя, и вернуть ее как строку Delphi. Таким образом вы избегаете издержек самой строковой структуры (refcount, length int, code page int и структур менеджера памяти для каждого распределения строк.
Это работает нормально только если строки статичны и не меняются.
TList, TList<>, массив строк и вышеприведенное решение имеют "список" служебных данных по одному указателю на строку. Связанный список содержит не менее 2 указателей (один связанный список) или 3 указателей (двойной связанный список). Решение со связанным списком не имеет быстрого произвольного доступа, но позволяет изменять размеры O(1), если в других параметрах есть O(lgN) (с использованием коэффициента изменения размера) или O(N) с использованием фиксированного изменения размера.
Что бы я сделал:
Если< 1000 элементов и производительность не важна: используйте TStringList или массив dyn, как вам удобнее. иначе, если статический: используйте трюк выше. Это даст вам время запроса O (lgN), наименее используемую память и очень быстрое время загрузки (просто наберите его или используйте отображенный в память файл)
Все упомянутые структуры в вашем вопросе потерпят неудачу при использовании больших объемов данных 1M+ строк, которые должны динамически изменяться в коде. В то время я использовал бинарное дерево весов или хеш-таблицу в зависимости от типа запросов, которые мне нужно создать.
TStringList хранит массив указателей на (string, TObject) записи.
TList хранит массив указателей.
TStringBuilder не может хранить коллекцию строк. Он похож на.NET StringBuilder и должен использоваться только для объединения (многих) строк.
Изменение размера динамических массивов происходит медленно, поэтому даже не рассматривайте это как вариант.
Я бы использовал универсальный Delphi TList<string> во всех ваших сценариях. Он хранит массив строк (не строковые указатели). Это должно иметь более быстрый доступ во всех случаях из-за отсутствия (не) бокса.
Возможно, вам удастся найти или реализовать немного лучшее решение со связанными списками, если вам нужен только последовательный доступ. Смотрите Delphi Алгоритмы и структуры данных.
Delphi продвигает его TList а также TList<>, Реализация внутреннего массива высоко оптимизирована, и у меня никогда не возникало проблем с производительностью / памятью при его использовании. См. Эффективность TList и TStringList
Исходя из вашего описания, я не совсем уверен, может ли он вписаться в ваш дизайн, но одним из способов улучшить использование памяти, не понеся огромных потерь производительности, является использование trie.
Преимущества относительно бинарного дерева поиска
Ниже приведены основные преимущества попыток перед деревьями двоичного поиска (BST):
Поиск ключей быстрее. Поиск ключа длины m занимает наихудшее время O(m). BST выполняет O(log(n)) сравнений ключей, где n - количество элементов в дереве, потому что поиск зависит от глубины дерева, которая является логарифмической по количеству ключей, если дерево сбалансировано. Следовательно, в худшем случае BST занимает O(m log n) времени. Более того, в худшем случае log (n) подойдет к m. Кроме того, простые операции, которые пытаются использовать во время поиска, такие как индексация массива с использованием символа, бывают быстрыми на реальных машинах.
Для попыток может потребоваться меньше места, если они содержат большое количество коротких строк, поскольку ключи не хранятся в явном виде и узлы совместно используются ключами с общими начальными подпоследовательностями.
- Попытки облегчают сопоставление с самым длинным префиксом, помогая найти ключ, разделяющий самый длинный из возможных префиксов символов.