Существует ли более быстрая реализация TList?
Мое приложение делает интенсивное использование TList, таким образом, я задавался вопросом, существуют ли какие-либо альтернативные внедрения, которые быстрее или оптимизированы для конкретного варианта использования.
Я знаю о RtlVCLOptimize.pas 2.77, который оптимизировал реализации нескольких методов TList.
Но я хотел бы знать, существует ли что-либо еще там. Я также не требую, чтобы это было потомком TList, мне просто нужна функциональность TList независимо от того, как это реализовано.
Это совершенно возможно, учитывая довольно основную функциональность, которую TList обеспечивает, что нет большого простора для совершенствования, но все еще хотел бы проверить что, следовательно этот вопрос.
править: В моем конкретном варианте использования не отсортированы никакие списки. Существует много списков с различным числом элементов в. Я действительно заменял TList своим собственным классом для входа, количество Добавляют/Удаляют вызовы и количество элементов. Это сообщает (toatal для всех списков):
ListAdd = 15766012; ListRemove = 10630000; ListCount = 5136012
Я мог также узнать, каково самое большое количество элементов в единственном списке.
У меня нет конкретного вопроса, я просто задаюсь вопросом, существует ли способ сделать его быстрее всеми вокруг как с этими числами, даже маленькое улучшение сложило бы.
4 ответа
Одно из самых больших узких мест, которые я знаю о TList, - это удаление / извлечение в большом списке. Удаление элемента [0] происходит намного медленнее, чем удаление элемента [Count-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. Из-за процедуры Notify TList.Clear (который вызывается при уничтожении) является операцией O (n). Метод TList.Clear вызывает SetCount, который, в свою очередь, вызывает Delete для всех элементов, которые он содержит, поэтому процедура Notify будет вызываться для каждого удаленного элемента. Если вам не нужно переопределять метод Notify, вы можете настроить процедуру SetCount так, чтобы она не вызывала Delete. Это может сэкономить вам время 15.766.012 - 10.630.000 = 5.136.012 Удалить вызовы.
NB: прирост производительности, который вы получите, никогда не будет таким большим, как прирост производительности, который вы получите от сортировки списка и оптимизации процедуры удаления, как это было предложено Мэйсоном Уилером. Если список, который у вас есть, не содержит очень небольшого количества элементов, а функция сравнения занимает много времени.
Самая быстрая структура данных обычно не является структурой данных, а представляет собой имитацию, которая извлекает данные только по мере необходимости, как это делает Virtual Treeview . Возможно, вы можете написать своего рода TVirtualList, который вызывает соответствующие функции для сбора необходимых данных при запросе элементов.
Похоже, вы делаете много добавлений. Я не знаю, сколько списков распределено, но если ваши отдельные списки становятся очень большими, вы можете реализовать список, который растет быстрее.
Взгляните на TList.Grow , который вызывается, когда вы пытаетесь добавить элемент в список, в котором используются все его элементы массива, и вы увидите, что он увеличивается на 25%. . Это сделано для того, чтобы использовать память на разумном уровне. Но если вам нужны действительно большие списки, создайте свой собственный класс-потомок и переопределите Grow, чтобы во второй строке вместо Delta: = FCapacity div 4 было написано Delta: = FCapacity .Это увеличивает ваш список каждый раз в два раза, что означает меньше повторных блоков и меньше копий.
Но то, что, вероятно, убивает вас, - это все эти вызовы Remove. Remove должен найти элемент, прежде чем он сможет его удалить, что включает в себя вызов IndexOf, который представляет собой линейное сканирование всего массива. Если у вас большой список и вы делаете много удалений, это убьет вашу производительность.
Для чего вы используете эти списки, особенно большие? В зависимости от того, что вы с ними делаете, могут быть более подходящие структуры данных для работы.