[Язык С] списки(мапы) с быстрым поиском и удалением

[Evgeniy]

С си особо незнаком...нужна реализация очень быстрого контейнера для рандомного поиска и удаления элемента. Вставка не особо важна.
Размеры до ~5 млн записей ( запись 5 интов + хеш, если нужен).
Важен именно поиск и удаление.

[Sid]

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

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

Это я не понял что ты имел ввиду.

запись 5 интов + хеш

[Evgeniy]

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

Нужен контейнер для быстрого рандомного поиска и удаления элемента по индексу, хешу; суть не важна - важна скорость рандомного поиска и удаления.
5 интов + хеш = 6*32 = 24 байта - размер объекта для хранения, поиска.

1. Надо записать в контейнер много объектов - скорость не особо важна
2. рандомно выдергивать по индексу - скорость важна
3. доставать все по очереди - итерация ( порядок не важен ) - скорость важна
4. удалять - скорость важна

Код 100% однопоточный.

[rsa]

тогда std::unordered_map. правда его пока формально еще нет, но пользоваться уже можно.

[Evgeniy]

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

тогда std::unordered_map. правда его пока формально еще нет, но пользоваться уже можно.

спасибо, наверное то что нужно...
нашел бенч - с сравнением stl_unordered_map, glib_hash_table, google_dense_hash_map, boost_unordered_map и тп. google_dense_hash_map таки выигрывает в скорости, хотя проигрывает в потреблении памяти (мне как раз и не критично). Буду пробовать, спасибо.

[rsa]

я бы не стал полагаться на такие результаты тестов совсем. потому что результат _очень_ сильно зависит от компилятора, его билда/релиза, мемманагера, ключей компиляции, а в случае продукции M$ - еще и от погоды на Марсе и обострения геморроя у дядюшки Ляо. надо пробовать все варианты на своей конкретной задаче и своими конкретными руками.

[Йоха]

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

а в случае продукции M$ - еще и от погоды на Марсе и обострения геморроя у дядюшки Ляо.

это чушь, а остальное верно

[Evgeniy]

собиралось gcc version 4.6.2, OpenSuse 32 bit с ключем -o2 и -o3
результаты:
charts-o3.html.zip
charts-o2.html.zip
до "своей задаче попробовать" еще не дошло, с++ планирую использовать лишь в качестве подключаемой библиотеки...по тестам выгоднее минимум в 2 раза получается.
Не все так просто как хотелось бы...так как с языком не владею

[Evgeniy]

расстроился....
выкинул все мапы и т.п. использовал массив.

• рандомный поиск - работает...только иногда натыкается на уже удаленных...берем следующего неудаленного.
• Итерация есть
• Удаления - нет, но после раунда, либо накопления большого % удаленных юнитов (для уменьшения кол-ва промахов по живым юнитам) - перестраиваю массив.

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

[KiriX]

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

• рандомный поиск - работает...только иногда натыкается на уже удаленных...берем следующего неудаленного.
• Итерация есть
• Удаления - нет, но после раунда, либо накопления большого % удаленных юнитов (для уменьшения кол-ва промахов по живым юнитам) - перестраиваю массив.

зы вывод один - там где можно использовать массивы - нужно использовать.

1) Ну так это не проблема Обойти же легко можно
2) Ну так кто бы сомневался про итерацию в массиве
3) Тоже, в общем-то, не проблема...
Возможно, я сейчас сморожу чушь, т.к. от программирования довольно далёк
НО! разве это не априори, что если есть возможность использовать более простой элемент, который вполне справляется с поставленной задачей, то нужно именно его и использовать, а не более сложные структуры?
P.S: Как раз именно эта тема и затрагивалась когда я последний раз читал самоучитель для чайников (правда по С++). Резюме всей главы таким и было, как я описал. Ибо дело именно в скорости работы... В вашем конкретном случае, как мне сразу и показалось, именно массива как раз и достаточно.

[Evgeniy]

по "правильному" его не достаточно...искривляется рандомный поиск...

нормальные - зеленые
удаленные - серые
красный - нормальный, но с увеличенной вероятностью выбора

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

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