TStringList, динамический массив или связанный список в Delphi?

Question

У меня есть выбор.

У меня есть несколько уже заказанных строк, которые мне нужно сохранить и получить к ним доступ. Похоже, я могу выбирать между использованием:

1. A TStringList
2. Динамический массив строк и

3. Связанный список строк (односвязный)

   и Алан в своем комментарии предложил также добавить к выбору:

4. TList<string>

При каких обстоятельствах каждый из них лучше других?

Что лучше всего подходит для небольших списков (до 10 наименований)?

Что лучше всего подходит для больших списков (более 1000 наименований)?

Что лучше всего подходит для огромных списков (более 1 000 000 наименований)?

Что лучше всего минимизировать использование памяти?

Что лучше всего минимизировать время загрузки, чтобы добавить дополнительные элементы в конце?

Что лучше всего минимизировать время доступа для доступа ко всему списку от первого до последнего?

На этой основе (или любой другой), какая структура данных будет предпочтительнее?

Для справки я использую Delphi 2009.

---

Дмитрий в комментарии сказал:

Опишите вашу задачу и схему доступа к данным, тогда можно будет дать вам точный ответ

Хорошо. У меня есть программа генеалогии с большим количеством данных.

Для каждого человека у меня есть ряд событий и атрибутов. Я храню их в виде коротких текстовых строк, но их много для каждого человека, от 0 до нескольких сотен. И у меня есть тысячи людей. Мне не нужен произвольный доступ к ним. Мне нужно, чтобы они ассоциировались как ряд строк в известном порядке, прикрепленных к каждому человеку. Это мой случай с тысячами «маленьких списков». Они требуют времени для загрузки и использования памяти, а также для доступа к ним, если они мне нужны (например, для экспорта всего сгенерированного отчета).

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

Надеюсь, это даст вам представление о том, чего я пытаюсь достичь.

p.s. Я написал много вопросов об оптимизации Delphi здесь, в StackOverflow. Моя программа читает 25 МБ файлов с 100 000 человек и создает структуры данных, а также отчет и древовидную структуру для них за 8 секунд, но использует для этого 175 МБ ОЗУ. Я работаю над уменьшением этого, потому что я стремлюсь загружать файлы с несколькими миллионами людей в 32-битной Windows.

---

Я только что нашел несколько превосходных предложений по оптимизации TList в этом вопросе StackOverflow: Есть ли более быстрая реализация TList?

Answer 1

Если у вас нет особых потребностей, TStringList трудно победить, поскольку он обеспечивает интерфейс TStrings, который многие компоненты могут использовать напрямую. При TStringList.Sorted := True будет использоваться бинарный поиск, что означает, что поиск будет очень быстрым. Вы также получаете сопоставление объектов бесплатно, каждый элемент также может быть связан с указателем, и вы получаете все существующие методы для маршалинга, потоковых интерфейсов, текста с запятой, текста с разделителями и т. Д.

С другой стороны, для особых нужд, если вам нужно сделать много вставок и удалений, то лучше будет использовать что-то более подходящее для связанного списка. Но тогда поиск становится медленнее, и это действительно редкий набор строк, который никогда не нуждается в поиске. В таких ситуациях часто используется некоторый тип хеша, когда хеш создается, скажем, из первых 2 байтов строки (предварительно выделите массив длиной 65536, и первые 2 байта строки преобразуются непосредственно в хеш индекс в этом диапазоне), а затем в этом месте хеш-памяти сохраняется связанный список с каждым ключом элемента, состоящим из оставшихся байтов в строках (для экономии места - хеш-индекс уже содержит первые два байта). Тогда начальный поиск по хешу - O (1), а последующие вставки и удаления - быстрый-связанный-список. Это компромисс, которым можно манипулировать, и рычаги должны быть ясны.

Answer 2

1. TStringList. Плюсы: расширенная функциональность, позволяющая динамически увеличивать, сортировать, сохранять, загружать, искать и т. Д. Минусы: при большом объеме доступа к элементам по индексу Strings [Index] вносит ощутимую потерю производительности (несколько процентов), сравнивая для доступа к массиву, накладные расходы памяти для каждой ячейки элемента.

2. Динамический массив строк. Плюсы: сочетает в себе способность динамически расти, как TStrings, с самым быстрым доступом по индексу, минимальным использованием памяти другими. Минусы: ограниченная стандартная функциональность "списка строк".

3. Связанный список строк (односвязный). Плюсы: линейная скорость добавления элемента в конец списка. Минусы: самый медленный доступ по индексу и поиску, ограниченная стандартная функциональность «списка строк», накладные расходы памяти для указателя «следующий элемент», накладные расходы на выделение памяти для каждого элемента.

4. TList <строка>. Как указано выше.

5. TStringBuilder. У меня нет хорошей идеи, как использовать TStringBuilder в качестве хранилища для нескольких строк.

На самом деле подходов гораздо больше:

• связанный список динамических массивов
• хеш-таблицы
• базы данных
• бинарные деревья
• и т.д.

Лучший подход будет зависеть от задачи .

Что лучше всего подходит для небольших списков (под 10 штук)?

Любой, может быть даже статический массив с переменной общего количества элементов.

Что лучше всего подходит для больших списков (более 1000 наименований)? Что лучше всего подходит для огромных списков (более 1 000 000 наименований)?

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

Что лучше всего минимизировать использование памяти?

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

Что лучше всего минимизировать время загрузки, чтобы добавить дополнительные элементы в конце?

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

Что лучше всего минимизировать время доступа для доступа ко всему списку от первого до последнего?

динамический массив.

На этой основе (или любой другой), какая структура данных будет предпочтительнее?

Для какой задачи?

Answer 3

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

Посчитайте - вы загружаете файл размером 25 МБ, содержащий около 100 000 человек, что приводит к тому, что ваше приложение использует 175 МБ памяти. Если вы хотите загружать файлы с несколькими миллионами человек, вы можете оценить, что без кардинальных изменений в вашей программе вам также потребуется умножить свои потребности в памяти на n * 10. Невозможно сделать это в 32-битном процессе, сохраняя все в памяти так, как вы это делаете в настоящее время.

У вас есть два варианта:

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

2. Храните все в памяти, но максимально экономно. Пока нет 64-битной Delphi, это должно учитывать несколько миллионов человек, в зависимости от того, сколько данных будет для каждого человека. Повторная компиляция для 64-битной системы также устранит этот предел.

Если вы выберете второй вариант, вам нужно будет гораздо агрессивнее минимизировать потребление памяти:

• Использовать интернирование строк . Каждый загруженный элемент данных в вашей программе, который содержит одни и те же данные, но содержится в разных строках, в основном тратит впустую память. Я понимаю, что ваша программа - это программа просмотра, а не редактор, так что вы, вероятно, можете обойтись только добавлением строк в пул интернированных строк. Выполнение интернирования строк с миллионами строк по-прежнему затруднено, сообщения в блоге «Оптимизация потребления памяти с помощью пулов строк» ​​ в блоге SmartInspect могут дать вам хорошие идеи. Эти ребята регулярно работают с огромными файлами данных и должны были заставить их работать с теми же ограничениями, с которыми вы сталкиваетесь.
  Это также должно связать этот ответ с вашим вопросом - если вы используете интернирование строк, вам не нужно будет хранить списки строк в ваших структурах данных, но списки индексов пула строк.
  Также может быть полезно использовать несколько пулов строк, например, один для имен, но другой - для таких мест, как города или страны. Это должно ускорить вставку в пулы.

• Используйте строковое кодирование, которое дает наименьшее представление в памяти. Хранение всего как собственной строки Unicode в Windows, вероятно, будет занимать гораздо больше места, чем хранение строк в UTF-8, если только вы регулярно не работаете со строками, которые содержат в основном символы, которым требуется три или более байтов в кодировке UTF-8.
  Из-за необходимого преобразования набора символов вашей программе потребуется больше циклов ЦП для отображения строк, но с таким количеством данных это достойный компромисс, поскольку доступ к памяти будет узким местом, а меньший размер данных помогает уменьшить нагрузку на доступ к памяти.

Answer 4

Возможная альтернатива:

Недавно я обнаружил SynBigTable (http://blog.synopse.info/post/2010/03/16/Synopse-Big-Table), который имеет класс TSynBigTableString для хранения больших объемов данных с использованием строкового индекса.

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

Так же просто, как:

aId: = UTF8String (Формат ('% s.% S', [имя, фамилия]));

bigtable.Add (data, aId)

и

bigtable.Get (aId, data)

Один улов, индексы должны быть уникальными, а стоимость обновления немного высока (сначала удалите, затем вставьте заново)

Answer 5

Из вашего описания я не совсем уверен, может ли он соответствовать вашему дизайну, но один из способов улучшить использование памяти без огромных потерь производительности - использовать trie .

Преимущества относительно дерева двоичного поиска

Ниже приведены основные преимущества попыток над бинарными деревьями поиска (BSTs):

• Поиск клавиш быстрее. Поиск ключа длины m принимает наихудший случай O (м) время. BST выполняет O (log (n)) сравнения ключей, где n - это количество элементов в дереве, потому что поиск зависит от глубины дерево, которое является логарифмическим в количество ключей, если дерево сбалансирован. Следовательно, в худшем случае BST занимает O (m log n) время. Более того, в худшем случае подойдет log (n) м. Кроме того, простые операции пытается использовать во время поиска, например, массив индексирование с использованием символа, быстро на реальных машинах.

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

• Попытки облегчают сопоставление длинных префиксов, помогая найти ключ разделяя максимально длинный префикс все персонажи уникальны.

Answer 6

Один вопрос: как вы выполняете запрос: сопоставляете ли вы строки или запросы по идентификатору или позиции в списке?

Подходит для небольших # строк:

Все, что делает вашу программу легкой для понимания. Читаемость программы очень важна, и вы должны жертвовать ею только в реальных горячих точках в вашем приложении для скорости.

Лучше всего для памяти (если это самое большое ограничение) и времени загрузки:

Храните все строки в одном буфере памяти (или в файле отображения памяти) и сохраняйте только указатели на строки (или смещения). Всякий раз, когда вам нужна строка, вы можете вырезать строку, используя два указателя, и вернуть ее как строку Delphi. Таким образом вы избежите накладных расходов на саму структуру строки (refcount, length int, code page int и структуры менеджера памяти для каждого выделения строки.

Это работает нормально, только если строки статичны и не меняются.

TList, TList <>, массив строк и вышеприведенное решение имеют «список» служебных данных по одному указателю на строку. Связанный список содержит не менее 2 указателей (один связанный список) или 3 указателей (двойной связанный список). Решение со связанным списком не имеет быстрого произвольного доступа, но позволяет изменять размеры O (1), если в других параметрах есть O (lgN) (с использованием коэффициента изменения размера) или O (N) с использованием фиксированного изменения размера.

Что бы я сделал:

Если <1000 элементов и производительность не очень важна: используйте TStringList или массив dyn, как вам удобнее. иначе, если статический: используйте трюк выше. Это даст вам время запроса O (lgN), наименее используемую память и очень быстрое время загрузки (просто наберите его или используйте отображенный в память файл) </p>

Все упомянутые структуры в вашем вопросе потерпят неудачу при использовании больших объемов данных 1M + строк, которые должны динамически изменяться в коде. В то время я использовал бинарное дерево весов или хеш-таблицу в зависимости от типа запросов, которые мне нужно создать.

Answer 7

TStringList хранит массив указателей на записи (string, TObject).

TList хранит массив указателей.

TStringBuilder не может хранить коллекцию строк. Он похож на .NET StringBuilder и должен использоваться только для объединения (многих) строк.

Изменение размера динамических массивов происходит медленно, поэтому даже не рассматривайте его как вариант.

Я бы использовал общий код Delphi TList<string> во всех ваших сценариях. Он хранит массив строк (не строковые указатели). Он должен иметь более быстрый доступ во всех случаях из-за отсутствия (не) бокса.

Возможно, вам удастся найти или реализовать немного лучшее решение со связанным списком, если вам нужен только последовательный доступ. См. Алгоритмы Delphi и структуры данных .

Delphi продвигает свои TList и TList<>. Реализация внутреннего массива высоко оптимизирована, и у меня никогда не возникало проблем с производительностью / памятью при его использовании. См. Эффективность TList и TStringList