Идея создания такой библиотеки появилась в процессе портирования кода с С++, который изобилует использованием 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"
MODULE ContainersTest; (** AUTHOR ""; PURPOSE ""; *)
IMPORT
Commands, Containers, Random, PreciseTimer;
PROCEDURE HashTest*(context: Commands.Context);
CONST
SETS = 100000;
TRIES = 20;
VAR
r: Random.Generator;
set: Containers.LongintSet;
setset1, setset2: Containers.LongintSetSet;
i, j, n, iTry: LONGINT;
t: HUGEINT;
BEGIN
context.out.Ln;
NEW(r);
t := PreciseTimer.GetTicks();
FOR iTry := 0 TO TRIES - 1 DO
NEW(set);
FOR i := 0 TO SETS - 1 DO
n := r.Dice(MAX(LONGINT));
IF ~set.Contains(n) THEN
set.Add(n)
END
END
END;
t := PreciseTimer.GetTicks() - t;
context.out.String("Count: ");
context.out.Int(set.GetCount(), 0);
context.out.Ln;
context.out.String("Collisions: ");
context.out.Int(set.dictionary.nCollisions, 0);
context.out.Ln;
context.out.String("Time: ");
context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
context.out.Ln;
context.out.Update;
NEW(setset1);
FOR i := 0 TO SETS - 1 DO
NEW(set);
FOR j := 0 TO 20 DO
n := r.Dice(MAX(LONGINT));
IF ~set.Contains(n) THEN
set.Add(n)
END
END;
IF ~setset1.Contains(set) THEN
setset1.Add(set)
END
END;
context.out.String("Sets generated");
context.out.Ln;
context.out.Update;
t := PreciseTimer.GetTicks();
FOR iTry := 0 TO TRIES - 1 DO
NEW(setset2);
setset1.Reset;
WHILE setset1.HasNext() DO
set := setset1.GetNext();
IF ~setset2.Contains(set) THEN
setset2.Add(set)
END
END
END;
t := PreciseTimer.GetTicks() - t;
context.out.String("Count: ");
context.out.Int(setset2.GetCount(), 0);
context.out.Ln;
context.out.String("Collisions: ");
context.out.Int(setset2.dictionary.nCollisions, 0);
context.out.Ln;
context.out.String("Time: ");
context.out.Float(PreciseTimer.GetTime(t) / TRIES, 15);
context.out.Ln;
END HashTest;
BEGIN
END ContainersTest.
ContainersTest.Test ~
ContainersTest.HashTest ~
SystemTools.Free ContainersTest Containers ~
Count: 99997
Collisions: 232111
Time: 7.291155E-002
Sets generated
Count: 100000
Collisions: 255930
Time: 9.049281E-001
Вход
Регистрация
FAQ
Поиск
