Быстрый доступ к (отсортированному) TList - PullRequest
Новая
       32

Быстрый доступ к (отсортированному) TList

2 голосов
/ 23 сентября 2011

Мой проект (запущенный на Delphi 6!) Требует список распределений памяти (TMemoryAllocation), который я храню в объекте, который также содержит информацию о размере выделения (FSize) и о том, используется ли выделение или свободно(плавленый).Я использую это в основном как GarbageCollector и как способ постоянно использовать свое приложение для выделения / освобождения памяти (и для этого требуется много выделений / освобождений).

Всякий раз, когда моему проекту требуется выделение, он просматривает списокнайти бесплатное распределение, которое соответствует требуемому размеру.Чтобы добиться этого, я использую простой цикл for: 

for I := 0 to FAllocationList.Count - 1 do
begin
  if MemoryAllocation.FUsed and (MemoryAllocation.FSize = Size) then
...

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

Я пытаюсь найти способ ускорить это решение.Я думал о сортировке TList по размеру выделения.Если я сделаю это, я должен использовать какой-то разумный способ доступа к списку для нужного размера при каждом вызове. Есть ли какой-нибудь простой способ сделать это?

Другой способ, о котором я думал, - это иметь два TList.Один для Неиспользованного и один из Используемых распределений.Это означало бы, что мне придется извлекать TList.Items из одного списка и постоянно добавлять в другой.И я все еще должен был бы использовать цикл for, чтобы пройти (теперь) меньший список. Это был бы правильный путь?

Другие предложения ОЧЕНЬ также приветствуются!

1 Ответ

5 голосов
/ 23 сентября 2011

У вас есть несколько возможностей:

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

Если ваше приложение очень чувствительно к распределению памяти, возможно, есть некоторые отзывы об изобретении колеса:

  • Используйте размер ваших блоков, например на 16 байтов, затем сохраните один список на размер блока, чтобы вы могли быстро найти «семейство» хороших блоков, и вам не нужно будет хранить каждый отдельный размер блока в памяти (если он есть в списке из 32 байтов, это блоки 32 байта);
  • Если вам нужно перераспределить, попытайтесь угадать лучший увеличивающийся коэффициент, чтобы уменьшить объем памяти, копируемый;
  • Сортируйте ваши блоки по размеру, затем используйте бинарный поиск , который будет намного быстрее, чем обычный цикл i: = 0 to Count-1;
  • Сохранение блока удаленных элементов в списке, в котором можно искать, когда вам нужен новый элемент (чтобы вам не пришлось удалять элемент, просто пометьте его как свободный - это значительно ускорит, если список огромен);
  • Вместо использования списка (который будет иметь некоторые проблемы со скоростью при удалении или вставке отсортированных элементов с огромным количеством элементов) используйте связанный список как для элементов, так и для освобожденных элементов.

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

...