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

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

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

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

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

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

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

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

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

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

В основном у вас есть два варианта:

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

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

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

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

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

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

Преимущества по сравнению с двоичным деревом поиска

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лучше всего для небольших # строк:

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

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

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

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

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

Что бы я хотел do:

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

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

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

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

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

Все просто:

aId := UTF8String(Format('%s.%s', [имя, фамилия]));

bigtable.Add(data, aId)

и

bigtable.Get(aId, data)

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