[Язык С] списки(мапы) с быстрым поиском и удалением
С си особо незнаком...нужна реализация очень быстрого контейнера для рандомного поиска и удаления элемента. Вставка не особо важна.
Размеры до ~5 млн записей ( запись 5 интов + хеш, если нужен). Важен именно поиск и удаление. |
В C нет контейнеров. Они есть в C++ как STL.
Вектор это массив - можно обратиться по номеру элемента Лист это лист - тупо список Мап это мап - ключ и значение Что тебе надо объясни. Это я не понял что ты имел ввиду. Цитата:
|
массив - тоже контейнер.
Лист - это лист....только с учетом того - упорядоченный, отсортированый, динамичческий...не тупо список. мап - хешмап, сетмап ...с сохранением упорядоченности и без. Нужен контейнер для быстрого рандомного поиска и удаления элемента по индексу, хешу; суть не важна - важна скорость рандомного поиска и удаления. 5 интов + хеш = 6*32 = 24 байта - размер объекта для хранения, поиска.
|
тогда std::unordered_map. правда его пока формально еще нет, но пользоваться уже можно.
|
Цитата:
нашел бенч - с сравнением stl_unordered_map, glib_hash_table, google_dense_hash_map, boost_unordered_map и тп. google_dense_hash_map таки выигрывает в скорости, хотя проигрывает в потреблении памяти (мне как раз и не критично). Буду пробовать, спасибо. |
я бы не стал полагаться на такие результаты тестов совсем. потому что результат _очень_ сильно зависит от компилятора, его билда/релиза, мемманагера, ключей компиляции, а в случае продукции M$ - еще и от погоды на Марсе и обострения геморроя у дядюшки Ляо. надо пробовать все варианты на своей конкретной задаче и своими конкретными руками.
|
Цитата:
|
Вложений: 2
собиралось gcc version 4.6.2, OpenSuse 32 bit с ключем -o2 и -o3
результаты: Вложение 1133 Вложение 1134 до "своей задаче попробовать" еще не дошло, с++ планирую использовать лишь в качестве подключаемой библиотеки...по тестам выгоднее минимум в 2 раза получается. Не все так просто как хотелось бы...так как с языком не владею :sorry: |
расстроился....
выкинул все мапы и т.п. использовал массив.
зы вывод один - там где можно использовать массивы - нужно использовать. |
Цитата:
2) Ну так кто бы сомневался про итерацию в массиве =))) 3) Тоже, в общем-то, не проблема... Возможно, я сейчас сморожу чушь, т.к. от программирования довольно далёк =) НО! разве это не априори, что если есть возможность использовать более простой элемент, который вполне справляется с поставленной задачей, то нужно именно его и использовать, а не более сложные структуры? =) P.S: Как раз именно эта тема и затрагивалась когда я последний раз читал самоучитель для чайников (правда по С++). Резюме всей главы таким и было, как я описал. Ибо дело именно в скорости работы... В вашем конкретном случае, как мне сразу и показалось, именно массива как раз и достаточно. |
Вложений: 1
по "правильному" его не достаточно...искривляется рандомный поиск...
Вложение 1155 нормальные - зеленые удаленные - серые красный - нормальный, но с увеличенной вероятностью выбора Как оказалось - вполне допустимая погрешность, хотя логически неправильно( что и помешало изначально использовать =))) ) нет рандомного поиска по значению...так что приходится сохранять и пересохранять необходимые индексы для некоторых объектов...код получается запутанным. |
Текущее время: 00:14. Часовой пояс GMT +3. |
ru-mangos.ru - Русское сообщество MaNGOS