Есть ли более быстрая реализация TList?
Мое приложение интенсивно использует TList, поэтому мне было интересно, есть ли альтернативные реализации, которые бывают быстрее или оптимизированы для конкретного случая использования.
Я знаю о RtlVCLOptimize.pas 2.77, которая оптимизировала реализации нескольких методов TList.
Но я хотел бы знать, есть ли что-нибудь еще там. Я также не требую, чтобы он был потомком TList, мне просто нужна функциональность TList независимо от того, как он реализован.
Вполне возможно, учитывая довольно базовую функциональность, которую обеспечивает TList, что не так много возможностей для улучшения, но все же хотелось бы проверить это, отсюда и этот вопрос.
редактировать: в моем конкретном случае использования списки не сортируются. Есть много списков с различным количеством элементов. Я заменил TList своим собственным классом, чтобы регистрировать количество вызовов Add/Remove и количество элементов. Это сообщает (итоги для всех списков):
ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012
Я также мог бы узнать, какое наибольшее количество элементов в одном списке.
У меня нет особой проблемы, я просто задаюсь вопросом, есть ли способ сделать это быстрее со всех сторон, так как с этими цифрами может быть даже небольшое улучшение.
4 ответа
Одним из самых больших узких мест, которые я знаю о TList, является удаление / извлечение большого списка. Удаление элемента [0] происходит намного медленнее, чем удаление элемента [Счетчик-1] из-за перемещения памяти, которое следует за ним.
Например, в списке, содержащем 65536 элементов:
while list.Count > 0 do List.Delete(0) //Takes 2 mins to complete
for I := List.Count-1 downto 0 do List.Delete(I) //Takes less than 1 sec
Поэтому, если у вас есть TList с миллионами элементов, удаление элемента с низким индексом может быть дорогостоящим с точки зрения производительности. Также учтите, что наличие списка, который не отсортирован, очень медленно находит элемент в нем. IndexOf очень медленный в большом списке. Возможно, вы захотите сохранить список отсортированным.
Кроме того, учитывая, что количество элементов может быть довольно большим, вы можете рассмотреть возможность использования Списка TList для хранения ваших элементов, что поможет уменьшить накладные расходы на удаление / извлечение, о которых я уже упоминал.
Похоже, вы делаете много дополнений. Я не знаю, сколько списков распределено, но если ваши отдельные списки становятся очень большими, вы можете захотеть реализовать список, который растет быстрее.
Взгляни на TList.Grow, который вызывается, когда вы пытаетесь добавить элемент в список, где используются все его элементы массива, и вы увидите, что он увеличивается на 25%. Это должно снизить использование памяти до разумного уровня. Но если вам нужны действительно большие списки, создайте свой собственный класс-потомок и переопределите Grow, чтобы во второй строке вместо Delta := FCapacity div 4 это говорит Delta := FCapacity, Это увеличивает ваш список в два раза каждый раз, что означает меньше перераспределений и меньше копий.
Но то, что, вероятно, убивает вас, это все эти звонки Удалить. Удалить должен найти элемент, прежде чем он сможет удалить его, что включает в себя вызов IndexOf, который представляет собой линейное сканирование всего массива. Если у вас большой список, и вы делаете много удалений, это убьет вашу производительность.
Для чего вы используете эти списки, особенно большие? В зависимости от того, что вы делаете с ними, могут быть лучшие структуры данных для работы.
Используете ли вы процедуру уведомления? Если нет, создайте свою собственную реализацию TList. Из-за процедуры уведомления, TList.Clear (который вызывается при уничтожении) является операцией O(n). Метод TList.Clear вызывает SetCount, который, в свою очередь, вызывает Delete для всех элементов, которые он содержит, поэтому процедура Notify будет вызываться для каждого удаленного элемента. Если вам не нужно переопределять метод Notify, вы можете настроить процедуру SetCount так, чтобы она не вызывала Delete. Это может сэкономить вам время 15.766.012 - 10.630.000 = 5.136.012 Удалить вызовы.
Примечание: выигрыш в производительности никогда не будет таким большим, как выигрыш в производительности, сортируя список и оптимизируя процедуру удаления, как это предложил Мейсон Уилер. Если в списке нет очень небольшого количества элементов, а функция сравнения занимает много времени.
Самая быстрая структура данных - это вообще не структура данных, а имитация, которая извлекает данные только по мере необходимости, так же, как это делает Virtual Treeview. Возможно, вы можете написать своего рода TVirtualList, который вызывает соответствующие функции для сбора необходимых данных при запросе элементов.