OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 19 Октябрь, 2019 08:39

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Стратегия роста списка
СообщениеДобавлено: Воскресенье, 10 Февраль, 2013 23:24 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 1215
Откуда: Украина, Киев
Списки на базе массивов традиционно при нехватке места в массиве для очередного добавляемого элемента увеличиваются созданием нового массива удвоенного размера и копированием содержимого старого массива в новый.
Т.е. нет разницы 1048577 элементов добавлено или 2097152, массив будет размером 2097152 элементов.
Оказывается в Qt используется стратегия позволяющая более экономно расходовать память.
Цитата:
We build the string out dynamically by appending one character to it at a time. Let's assume that we append 15000 characters to the QString string. Then the following 18 reallocations (out of a possible 15000) occur when QString runs out of space: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. At the end, the QString has 16372 Unicode characters allocated, 15000 of which are occupied.
The values above may seem a bit strange, but here are the guiding principles:
[*]QString allocates 4 characters at a time until it reaches size 20.
[*]From 20 to 4084, it advances by doubling the size each time. More precisely, it advances to the next power of two, minus 12. (Some memory allocators perform worst when requested exact powers of two, because they use a few bytes per block for book-keeping.)
[*]From 4084 on, it advances by blocks of 2048 characters (4096 bytes). This makes sense because modern operating systems don't copy the entire data when reallocating a buffer; the physical memory pages are simply reordered, and only the data on the first and last pages actually needs to be copied.
http://doc.qt.digia.com/4.7-snapshot/co ... strategies
С использованием этой стратегии размер массива при 1048577 добавленных элементах будет равен 1050612 элементам.
Проверил эту стратегию в А2, и оказалось, что экономия памяти даже не сказалась на производительности.
Следующий код с использованием что одной что другой стратегии выполнялся примерно 170 секунд в обоих случаях:
Код:
MODULE ListTest; (** AUTHOR ""; PURPOSE ""; *)

IMPORT
   Commands, Lists, Random, PreciseTimer;

PROCEDURE Test*(context: Commands.Context);
VAR
   r: Random.Generator;
   l: Lists.LongintList;
   i, n: LONGINT;
   t: HUGEINT;
BEGIN
   context.out.Ln;
   t := PreciseTimer.GetTicks();
   NEW(r);
   NEW(l, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});
   FOR i := 0 TO 525000 DO
      n := r.Dice(500000);
      IF l.IndexOf(n) = -1 THEN
         l.Add(n)
      END
   END;
   t := PreciseTimer.GetTicks() - t;
   context.out.Ln;   
   context.out.String("Count: ");
   context.out.Int(l.GetCount(), 0);
   context.out.Ln;
   context.out.String("Time: ");
   context.out.Float(PreciseTimer.GetTime(t), 15);
   context.out.Ln;
END Test;

END ListTest.

ListTest.Test ~
SystemTools.Free ListTest Lists ~

Код библиотеки http://subversion.assembla.com/svn/ober ... /Lists.Mod


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Среда, 13 Февраль, 2013 06:51 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 1215
Откуда: Украина, Киев
Для несортированного списка ситуация другая, новая стратегия роста значительно портит картину.
5.279027E+000 и 2.681366E-001 секунд для новой и традиционной стратегии соответственно.
Код:
   NEW(l, {(*Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES*)});
   FOR i := 0 TO 525000 DO
      n := r.Dice(500000);
      (*IF l.IndexOf(n) = -1 THEN*)
         l.Add(n)
      (*END*)
   END;


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Среда, 13 Февраль, 2013 06:56 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3096
Откуда: Астрахань
Не понял. А в первом сообщении список сортированный?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Среда, 13 Февраль, 2013 11:20 
Аватара пользователя

Зарегистрирован: Суббота, 12 Июль, 2008 22:49
Сообщения: 573
Откуда: Россия, Санкт-Петербург
Судя по коду:
Ярослав Романченко писал(а):
Код:
NEW(l, {Lists.LIST_SORTED, Lists.LIST_NO_DUPLICATES});


Очевидно да. Плюс не поддерживаются дубли.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Пятница, 15 Февраль, 2013 06:34 
Аватара пользователя

Зарегистрирован: Пятница, 11 Май, 2007 21:57
Сообщения: 1215
Откуда: Украина, Киев
Хороший ответ на эту тему на stackoverflow http://stackoverflow.com/questions/1424 ... 65#1426065
Т.е. что-бы не терять эффективности можно оставить фактор роста 2, а если жалко простаивающей памяти можно не очень часто вызывать процедурку по сжатию массива до размера реально добавленных элементов или с небольшим запасом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Пятница, 15 Февраль, 2013 13:43 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9147
Откуда: Россия, Орёл
Я обычно не удваиваю размер, а увеличиваю на 50%.

Не сопоставлял, но интуитивно кажется более рациональным.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Стратегия роста списка
СообщениеДобавлено: Суббота, 09 Март, 2013 14:53 

Зарегистрирован: Вторник, 22 Май, 2007 15:38
Сообщения: 154
Откуда: Питер
В одной моей программе есть постоянно и часто увеличивающийся список записей. Список организован как массив указателей, сам массив, естественно, тоже располагается в куче. Я попробовал увеличивать размер массива на постоянную величину, как в третьем пункте описанного алгоритма. Это приводило к быстрой фрагментации памяти. Правда, прирост бвл маленьким - всего 32 элемента. Увеличение в 2 раза проблемм не вызывало.


Последний раз редактировалось Евгений Темиргалеев Понедельник, 11 Март, 2013 12:12, всего редактировалось 1 раз.
испр. (п. 3.2)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB