|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
03.03.2009, 21:51 | #1 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 23
|
Реализация контейнера map.
Если кто не знает, то стандартный (для С++ ) 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 |
03.03.2009, 21:55 | #2 |
Пользователь
Регистрация: 27.07.2008
Сообщений: 30
|
молодец
|
03.03.2009, 22:01 | #3 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 23
|
при чем тут молодец?))
просто очевидно, что STL сыроватая (виндовую реализацию не считаю, потому как криворукие вообще писали походу)... это мое мнение... мож у кого то другое мнение.. было бы интерестно послушать |
03.03.2009, 22:19 | #4 |
Пользователь
Регистрация: 27.07.2008
Сообщений: 30
|
Просто разработчики больше времени уделяли эффективному распределению памяти и подобным проблемам, а быстродействие их походу не волновало .
|
03.03.2009, 22:22 | #5 |
Eclipse Foundation
Старожил
Регистрация: 19.09.2007
Сообщений: 2,604
|
А ваше деревцо с какими типами работает?
|
03.03.2009, 22:30 | #6 | |
Пользователь
Регистрация: 01.03.2009
Сообщений: 23
|
ну с какими укажете, с такими и будет работать))) говорю же, аналогичный контейнер...
Цитата:
и еще.. почему это их не волновало быстродействие?)) странная однако логика... Последний раз редактировалось MaTBeu; 03.03.2009 в 23:36. |
|
03.03.2009, 22:48 | #7 | |
Пользователь
Регистрация: 27.07.2008
Сообщений: 30
|
Цитата:
|
|
04.03.2009, 11:41 | #8 |
Пользователь
Регистрация: 01.03.2009
Сообщений: 23
|
|
25.08.2009, 07:43 | #9 |
Новичок
Джуниор
Регистрация: 24.08.2009
Сообщений: 1
|
Прогу мне на почту отправь плизз: dilshodbek87@gmail.com
|
27.12.2012, 19:01 | #10 |
Форумчанин
Регистрация: 05.04.2012
Сообщений: 134
|
fabregas, не надо делать такие скоропостижные выводы, АВЛ-дерево выигрывает перед красно-чёрным деревом только при чтение, а вот вставка и удаление проигрывает красно-чёрному дереву. АВЛ-дерево страдает расбалансировкой при удаление в итоге приходится заново балансировать.
Код:
Упс. на дату не посмотрел. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Есть проблема с версткой на div. Накладывается фон поверх соседнего контейнера. | Volfgang | HTML и CSS | 1 | 15.12.2008 09:43 |
File Map | MaTBeu | Win Api | 5 | 17.11.2008 15:38 |
Как программно удалить компонент от формы или другого компонента (контейнера)? | SkAndrew | Общие вопросы Delphi | 3 | 27.05.2008 15:20 |
Google Map API | qwestor | PHP | 3 | 22.01.2008 08:12 |