Оберон-клуб «ВЄДАsoft»

Твердыня модульных языков
Текущее время: 26 сен 2017, 13:00

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




Начать новую тему Ответить на тему  [ Сообщений: 2 ] 
Автор Сообщение
СообщениеДобавлено: 28 фев 2013, 14:22 
Не в сети

Сообщения: 58
Идея создания такой библиотеки появилась в процессе портирования кода с С++, который изобилует использованием STL шаблонов. Библиотека в какой-то мере имитирует шаблоны С++, во всяком случае, способ работы с контейнерами, а декларация контейнеров не намного сложнее чем в С++. Моя статья: http://sage.com.ua/ru.shtml?e1l5
Потом я внёс некоторые новшества и улучшения в свою библиотеку контейнеров.
List переименовал в Vector, поскольку, если рассуждать логически, это именно вектор на базе динамического массива. Настоящий List ещё необходимо будет реализовать на базе двухсвязного списка.
Реализовал Dictionary на базе хеш-таблицы. Хеш-таблица простейшая на базе динамического массива с простым механизмом разрешения коллизий и возможностью роста. Все возможные размеры таблицы заранее заданы табличкой простых чисел. При росте хеш-таблицы, позиции элементов пересчитываются с новым модулем, при этом хеш-коды элементов берутся из кэша, так-как операция взятия хеш-кода может быть достаточно медленной.
На базе Dictionary можно строить контейнеры типа Set и типа Map. В контейнере Set как-правило хранятся только ключи, и они-же являются и данными. В контейнере Map хранятся пары ключ:значение.
Реализовал двоичную кучу BinaryHeap.
Конейнер под любой тип данных описывается очень быстро, в библиотеке в качестве примера реализованы: вектор целых (LongintVector), вектор векторов целых (LongintVectorVector), вектор строк (StringVector), множество целых (LongintSet), множество множеств целых (LongintSetSet), куча целых (LongintHeap).
Dictionary получился достаточно быстрым. Добавление в LongintSetSet 100000 множеств LongintSet, содержащих в свою очередь до 21 случайного целого, с предварительной проверкой на вхождение в множество выполняется чуть менее чем за секунду. Для сравнения, заполнение LongintSet 100000 случайных целых с предварительной проверкой занимает порядка 70 мс. Без предварительной проверки будет просто останов по ASSERTу, поскольку Dictionary предполагает хранение лишь уникальных ключей.
http://svn.assembla.com/svn/oberonru/tr ... ainers.Mod

Код: "OBERON"
  1. MODULE ContainersTest; (** AUTHOR ""; PURPOSE ""; *)
  2.  
  3. IMPORT
  4. Commands, Containers, Random, PreciseTimer;
  5.  
  6. PROCEDURE HashTest*(context: Commands.Context);
  7. CONST
  8. SETS = 100000;
  9. TRIES = 20;
  10. VAR
  11. r: Random.Generator;
  12. set: Containers.LongintSet;
  13. setset1, setset2: Containers.LongintSetSet;
  14. i, j, n, iTry: LONGINT;
  15. t: HUGEINT;
  16. BEGIN
  17. context.out.Ln;
  18.  
  19. NEW(r);
  20.  
  21. t := PreciseTimer.GetTicks();
  22.  
  23. FOR iTry := 0 TO TRIES - 1 DO
  24. NEW(set);
  25. FOR i := 0 TO SETS - 1 DO
  26. n := r.Dice(MAX(LONGINT));
  27. IF ~set.Contains(n) THEN
  28. set.Add(n)
  29. END
  30. END
  31. END;
  32.  
  33. t := PreciseTimer.GetTicks() - t;
  34.  
  35. context.out.String("Count: ");
  36. context.out.Int(set.GetCount(), 0);
  37. context.out.Ln;
  38. context.out.String("Collisions: ");
  39. context.out.Int(set.dictionary.nCollisions, 0);
  40. context.out.Ln;
  41. context.out.String("Time: ");
  42. context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
  43. context.out.Ln;
  44. context.out.Update;
  45.  
  46. NEW(setset1);
  47. FOR i := 0 TO SETS - 1 DO
  48. NEW(set);
  49. FOR j := 0 TO 20 DO
  50. n := r.Dice(MAX(LONGINT));
  51. IF ~set.Contains(n) THEN
  52. set.Add(n)
  53. END
  54. END;
  55. IF ~setset1.Contains(set) THEN
  56. setset1.Add(set)
  57. END
  58. END;
  59.  
  60. context.out.String("Sets generated");
  61. context.out.Ln;
  62. context.out.Update;
  63.  
  64. t := PreciseTimer.GetTicks();
  65.  
  66. FOR iTry := 0 TO TRIES - 1 DO
  67. NEW(setset2);
  68. setset1.Reset;
  69. WHILE setset1.HasNext() DO
  70. set := setset1.GetNext();
  71. IF ~setset2.Contains(set) THEN
  72. setset2.Add(set)
  73. END
  74. END
  75. END;
  76.  
  77. t := PreciseTimer.GetTicks() - t;
  78.  
  79. context.out.String("Count: ");
  80. context.out.Int(setset2.GetCount(), 0);
  81. context.out.Ln;
  82. context.out.String("Collisions: ");
  83. context.out.Int(setset2.dictionary.nCollisions, 0);
  84. context.out.Ln;
  85. context.out.String("Time: ");
  86. context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
  87. context.out.Ln;
  88.  
  89. END HashTest;
  90.  
  91. BEGIN
  92. END ContainersTest.
  93.  
  94. ContainersTest.Test ~
  95. ContainersTest.HashTest ~
  96. SystemTools.Free ContainersTest Containers ~
  97.  
  98. Count: 99997
  99. Collisions: 232111
  100. Time: 7.291155E-002
  101. Sets generated
  102. Count: 100000
  103. Collisions: 255930
  104. Time: 9.049281E-001


Вернуться к началу
 Профиль  
Ответить с цитатой  
СообщениеДобавлено: 30 май 2016, 21:08 
Не в сети

Сообщения: 58
Тем временем, удалось таки для AO написать полностью всеядный базовый объект Vector для реализации на базе него всевозможных контейнеров. Причём, любые данные достаточно обернуть в статическую запись. Т.е. не требуется никаких дополнительных указателей. Единственный указатель во всём контейнере - динамический массив.
Удалось это не без помощи импорта модуля SYSTEM. Но для базового объекта это, пожалуй, простительно.
Бенчмарк RegExp показал, что с новыми контейнерами он работает почти в 2 раза быстрее чем с использованием старого Containers.Mod


Вложения:
Vector.zip [3.77 КБ]
Скачиваний: 236
Вернуться к началу
 Профиль  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

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


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Тех.поддержка phpBB