Реализация контейнера map.

[fabregas]

Если кто не знает, то стандартный (для С++ ) std::map юзает красно-черные деревья. Для одного проэкта я решил реализовать свой аналогичный контейнер, только реализовал через АВЛ-дерево...

Когда начал тестировать, то просто обалдел... Тестировал и на винде и на линуксе... к сожаленью результов виндовых тестов нет, но там было на что посмотреть... Реализация стандартного кантейнера в Microsoft Visual Studio оказалась просто жуткой... все виды тестов мой контейнер выиграл в 5-8 раз!! Как по мне - это очень много...

На линуксе же результаты были не такими плачевными для STL, на все же, зацените:

========= My AVL tree =========
Insert of 10000 sorted elements - 0 ms.
Insert of 100000 sorted elements - 5 ms.
Insert of 1000000 sorted elements - 69 ms.

Insert of 10000 random elements - 1 ms.
Insert of 100000 random elements - 10 ms.
Insert of 1000000 random elements - 166 ms.

Remove 10000 sorted elements - 1 ms.
Remove 100000 sorted elements - 5 ms.
Remove 1000000 sorted elements - 71 ms.

Remove 10000 random elements - 1 ms.
Remove 100000 random elements - 13 ms.
Remove 1000000 random elements - 209 ms.

Get 10000 elements - 0 ms.
Get 100000 elements - 2 ms.
Get 1000000 elements - 34 ms.

Iterator
Iteration of 100000 elements - 1 ms.
Iteration of 1000000 elements - 8 ms.

========= std::map =========
Insert 10000 sorted elements - 1 ms.
Insert 100000 sorted elements - 14 ms.
Insert 1000000 sorted elements - 169 ms.

Insert 10000 random elements - 1 ms.
Insert 100000 random elements - 14 ms.
Insert 1000000 random elements - 211 ms.

Remove 10000 sorted elements - 1 ms.
Remove 100000 sorted elements - 14 ms.
Remove 1000000 sorted elements - 162 ms.

Remove 10000 random elements - 2 ms.
Remove 100000 random elements - 19 ms.
Remove 1000000 random elements - 274 ms.

Get 10000 elements - 1 ms.
Get 100000 elements - 8 ms.
Get 1000000 elements - 90 ms.

Iterator
Iteration 100000 elements - 1 ms.
Iteration 1000000 elements - 9 ms.
___________________________________ _____

ps. Хотя это не очень имеет значение, но все же:
# uname -a
Linux fabregas_host 2.6.25-gentoo-r7 #10 SMP Tue Jan 27 20:37:04 UTC 2009 x86_64 AMD Turion(tm) 64 X2 Mobile Technology TL-56 AuthenticAMD GNU/Linux

[KVF]

молодец

[fabregas]

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

[KVF]

Просто разработчики больше времени уделяли эффективному распределению памяти и подобным проблемам, а быстродействие их походу не волновало .

[MaTBeu]

А ваше деревцо с какими типами работает?

[fabregas]

ну с какими укажете, с такими и будет работать))) говорю же, аналогичный контейнер...

Сообщение от KVF

Просто разработчики больше времени уделяли эффективному распределению памяти и подобным проблемам, а быстродействие их походу не волновало .

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

и еще.. почему это их не волновало быстродействие?)) странная однако логика...

[KVF]

почему это их не волновало быстродействие?)) странная однако логика...

Я просто сделал такой вывод исходя из быстродействия всех STLевских контейнеров ))

[fabregas]

Сообщение от KVF

Я просто сделал такой вывод исходя из быстродействия всех STLевских контейнеров ))

А вы оптимист) Я обычно делаю в таком случае вывод, что библиотеку писали китайцы с американцами на пару)))

[apus_pro]

Прогу мне на почту отправь плизз: dilshodbek87@gmail.com

[Nuklon]

fabregas, не надо делать такие скоропостижные выводы, АВЛ-дерево выигрывает перед красно-чёрным деревом только при чтение, а вот вставка и удаление проигрывает красно-чёрному дереву. АВЛ-дерево страдает расбалансировкой при удаление в итоге приходится заново балансировать.

А вы оптимист) Я обычно делаю в таком случае вывод, что библиотеку писали китайцы с американцами на пару)))

Не очень умный ответ, ничего пыл утихнет со временем.

Упс. на дату не посмотрел.