Ru-MaNGOS

Вернуться   Ru-MaNGOS > Документация > Языки программирования

Важная информация

Языки программирования Изучаем С++, Sql, php, Lua, Python

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
Старый 14.04.2012, 19:37   #1
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию [Язык С] списки(мапы) с быстрым поиском и удалением

С си особо незнаком...нужна реализация очень быстрого контейнера для рандомного поиска и удаления элемента. Вставка не особо важна.
Размеры до ~5 млн записей ( запись 5 интов + хеш, если нужен).
Важен именно поиск и удаление.
Evgeniy вне форума   Ответить с цитированием
Старый 14.04.2012, 21:09   #2
Sid
Ученый
 
Аватар для Sid
 
Регистрация: 02.04.2010
Сообщений: 237
Сказал(а) спасибо: 41
Поблагодарили 99 раз(а) в 44 сообщениях
Sid Скоро придёт к известностиSid Скоро придёт к известности
По умолчанию

В C нет контейнеров. Они есть в C++ как STL.
Вектор это массив - можно обратиться по номеру элемента
Лист это лист - тупо список
Мап это мап - ключ и значение

Что тебе надо объясни.

Это я не понял что ты имел ввиду.
Цитата:
запись 5 интов + хеш
__________________
SpellWork Qt4
Sid вне форума   Ответить с цитированием
Старый 14.04.2012, 22:43   #3
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию

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

Нужен контейнер для быстрого рандомного поиска и удаления элемента по индексу, хешу; суть не важна - важна скорость рандомного поиска и удаления.
5 интов + хеш = 6*32 = 24 байта - размер объекта для хранения, поиска.
  1. Надо записать в контейнер много объектов - скорость не особо важна
  2. рандомно выдергивать по индексу - скорость важна
  3. доставать все по очереди - итерация ( порядок не важен ) - скорость важна
  4. удалять - скорость важна
Код 100% однопоточный.
Evgeniy вне форума   Ответить с цитированием
Старый 14.04.2012, 23:18   #4
rsa
Почетный флудер
Старожил
 
Аватар для rsa
 
Регистрация: 08.03.2010
Адрес: Мурманск, Россия
Сообщений: 788
Сказал(а) спасибо: 55
Поблагодарили 333 раз(а) в 151 сообщениях
Записей в дневнике: 1
rsa Как самоцвет среди гранитаrsa Как самоцвет среди гранитаrsa Как самоцвет среди гранитаrsa Как самоцвет среди гранита
По умолчанию

тогда std::unordered_map. правда его пока формально еще нет, но пользоваться уже можно.
rsa вне форума   Ответить с цитированием
Пользователь сказал cпасибо:
Evgeniy (16.04.2012)
Старый 16.04.2012, 18:10   #5
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию

Цитата:
Сообщение от rsa Посмотреть сообщение
тогда std::unordered_map. правда его пока формально еще нет, но пользоваться уже можно.
спасибо, наверное то что нужно...
нашел бенч - с сравнением stl_unordered_map, glib_hash_table, google_dense_hash_map, boost_unordered_map и тп. google_dense_hash_map таки выигрывает в скорости, хотя проигрывает в потреблении памяти (мне как раз и не критично). Буду пробовать, спасибо.
Evgeniy вне форума   Ответить с цитированием
Старый 19.04.2012, 11:37   #6
rsa
Почетный флудер
Старожил
 
Аватар для rsa
 
Регистрация: 08.03.2010
Адрес: Мурманск, Россия
Сообщений: 788
Сказал(а) спасибо: 55
Поблагодарили 333 раз(а) в 151 сообщениях
Записей в дневнике: 1
rsa Как самоцвет среди гранитаrsa Как самоцвет среди гранитаrsa Как самоцвет среди гранитаrsa Как самоцвет среди гранита
По умолчанию

я бы не стал полагаться на такие результаты тестов совсем. потому что результат _очень_ сильно зависит от компилятора, его билда/релиза, мемманагера, ключей компиляции, а в случае продукции M$ - еще и от погоды на Марсе и обострения геморроя у дядюшки Ляо. надо пробовать все варианты на своей конкретной задаче и своими конкретными руками.
rsa вне форума   Ответить с цитированием
Старый 19.04.2012, 20:14   #7
Йоха
Умный
 
Регистрация: 02.07.2010
Сообщений: 434
Сказал(а) спасибо: 27
Поблагодарили 73 раз(а) в 45 сообщениях
Йоха Скоро придёт к известности
По умолчанию

Цитата:
Сообщение от rsa Посмотреть сообщение
а в случае продукции M$ - еще и от погоды на Марсе и обострения геморроя у дядюшки Ляо.
это чушь, а остальное верно
Йоха вне форума   Ответить с цитированием
Старый 20.04.2012, 20:07   #8
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию

собиралось gcc version 4.6.2, OpenSuse 32 bit с ключем -o2 и -o3
результаты:
charts-o3.html.zip
charts-o2.html.zip
до "своей задаче попробовать" еще не дошло, с++ планирую использовать лишь в качестве подключаемой библиотеки...по тестам выгоднее минимум в 2 раза получается.
Не все так просто как хотелось бы...так как с языком не владею
Evgeniy вне форума   Ответить с цитированием
Старый 19.06.2012, 08:24   #9
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию

расстроился....
выкинул все мапы и т.п. использовал массив.
  • рандомный поиск - работает...только иногда натыкается на уже удаленных...берем следующего неудаленного.
  • Итерация есть
  • Удаления - нет, но после раунда, либо накопления большого % удаленных юнитов (для уменьшения кол-ва промахов по живым юнитам) - перестраиваю массив.
скорость выросла на хрензнает сколько порядков при работе с большим кол-вом юнитов.
зы вывод один - там где можно использовать массивы - нужно использовать.
Evgeniy вне форума   Ответить с цитированием
Пользователь сказал cпасибо:
KiriX (19.06.2012)
Старый 19.06.2012, 08:52   #10
KiriX
Умный
Старожил
 
Аватар для KiriX
 
Регистрация: 06.03.2010
Сообщений: 886
Сказал(а) спасибо: 698
Поблагодарили 433 раз(а) в 181 сообщениях
Записей в дневнике: 4
KiriX Реально хороший человекKiriX Реально хороший человекKiriX Реально хороший человекKiriX Реально хороший человекKiriX Реально хороший человек
По умолчанию

Цитата:
Сообщение от Evgeniy Посмотреть сообщение
  • рандомный поиск - работает...только иногда натыкается на уже удаленных...берем следующего неудаленного.
  • Итерация есть
  • Удаления - нет, но после раунда, либо накопления большого % удаленных юнитов (для уменьшения кол-ва промахов по живым юнитам) - перестраиваю массив.
зы вывод один - там где можно использовать массивы - нужно использовать.
1) Ну так это не проблема Обойти же легко можно
2) Ну так кто бы сомневался про итерацию в массиве
3) Тоже, в общем-то, не проблема...
Возможно, я сейчас сморожу чушь, т.к. от программирования довольно далёк
НО! разве это не априори, что если есть возможность использовать более простой элемент, который вполне справляется с поставленной задачей, то нужно именно его и использовать, а не более сложные структуры?
P.S: Как раз именно эта тема и затрагивалась когда я последний раз читал самоучитель для чайников (правда по С++). Резюме всей главы таким и было, как я описал. Ибо дело именно в скорости работы... В вашем конкретном случае, как мне сразу и показалось, именно массива как раз и достаточно.
KiriX вне форума   Ответить с цитированием
Старый 19.06.2012, 09:20   #11
Evgeniy
Пользователь
 
Регистрация: 06.01.2012
Сообщений: 98
Сказал(а) спасибо: 12
Поблагодарили 33 раз(а) в 21 сообщениях
Evgeniy На верном пути
По умолчанию

по "правильному" его не достаточно...искривляется рандомный поиск...
Нажмите на изображение для увеличения
Название: Untitled-1.png
Просмотров: 424
Размер:	2.5 Кб
ID:	1155
нормальные - зеленые
удаленные - серые
красный - нормальный, но с увеличенной вероятностью выбора

Как оказалось - вполне допустимая погрешность, хотя логически неправильно( что и помешало изначально использовать )

нет рандомного поиска по значению...так что приходится сохранять и пересохранять необходимые индексы для некоторых объектов...код получается запутанным.
Evgeniy вне форума   Ответить с цитированием
Ответ

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
русский язык в Mangos One Mediv MaNGOS 0.12 (2.4.3) 32 27.02.2011 20:39
Некорректо отоброжает русский язык Bupyc Корзина 10 02.12.2010 07:42


Текущее время: 16:13. Часовой пояс GMT +3.


ru-mangos.ru - Русское сообщество MaNGOS
Главная цель проекта MaNGOS - обучающая, поэтому разрешается использовать исходный код и собранную программу только для образовательных целей.
Вы не можете использовать MaNGOS в коммерческих целях, а также не разрешается устанавливать публичные серверы на базе MaNGOS.
Любое копирование материалов, информации в любом виде без указания источника - форума Ru-MaNGOS будет считаться нарушением авторских прав и нарушением Уголовного Кодекса РФ, ст. 146 ст. 147.
Перевод vBulletin: zCarot