Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > составной ключ для map

Автор: afx33sd 20.8.2013, 11:28

Стоит задача быстрого нахождения элемента по ключу. Использую stl. Для реальной задачи он должен быть достаточно большой.

Код


struct {
   uint32_t ip1;
   uint32_t ip2;
   uint16_t port1;
   uint16_t port2;
   unsigned char id[16];
}

Стоит ли делать такой большой ключ или лучше сделать хэш-таблицу для этого случая, или map, где в качестве значения список c разными id. Тут надо сказать, что различных id планируется немного, а в большинстве случаев это будет массив нулей. Мне кажется, что в большом ключе страшного ничего нет, если значения в общей массе будут различаться в начале области памяти, a less делать каким-нибудь memcmp.

+ Еще такой вопрос: как сыграет на производительности, если сделать в качестве ключа структуру с двумя конструкторами - ну очень уж удобно. Я пока не понимаю как это все в памяти лежит, где указатели на методы и т.п. Читаю ABI, но пока понимая нет.

Код


struct key
{
 struct {
    uint32_t ip1;
    uint32_t ip2;
    uint16_t port1;
    uint16_t port2;
    unsigned char id[16];
 }
 bool dir;
 key(....) {}
 key(....) {}
 bool operator<(const key &other) const {...}
 bool operator==(const key &other) const {...}
}

Спасибо.

Автор: bsa 20.8.2013, 13:25

Цитата(afx33sd @ 20.8.2013, 12:28

)

Стоит ли делать такой большой ключ или лучше сделать хэш-таблицу для этого случая, или map, где в качестве значения список c разными id.

Хэш таблица нужна тогда, когда количество элементов в контейнере довольно большое. Если у тебя десяток элементов, то скорее всего, ты получишь замедление, по сравнению с обычным map.

Цитата(afx33sd @ 20.8.2013, 12:28

)

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

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

Автор: afx33sd 20.8.2013, 13:54

Количество элементов не больше 65535.

Цитата

Количество конструкторов и других методов не влияет на скорость

Это да. Если нет полиморфизма, то размер ключа будет размер величине данных, так?
Это я все думаю о размере и как он будет влиять на сложность поиска и вставки.

Думаю, что фактически размер ключа влияет только на скорость сравнения элементов. Следовательно, если я буду сравнивать до первого расхождения и данные ключа расположить по степени редкости этого расхождения, то вполне можно оставить map с таким ключом.

Автор: bsa 20.8.2013, 14:52

Цитата(afx33sd @ 20.8.2013, 14:54

)

Количество элементов не больше 65535.

Максимальное количество не сильно интересно. Скорей интересно среднее-взвешенное (с вероятностью 80% количество элементов будет от 10-20 или от 10000 до 20000).

Цитата(afx33sd @ 20.8.2013, 14:54

)

Если нет полиморфизма, то размер ключа будет размер величине данных, так?

не забывай о выравнивании. Но в целом да (только тут не полиморфизм, а всего-лишь наличие виртуальных функций).

Цитата(afx33sd @ 20.8.2013, 14:54

)

Это я все думаю о размере и как он будет влиять на сложность поиска и вставки.

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

Цитата(afx33sd @ 20.8.2013, 14:54

)

Следовательно, если я буду сравнивать до первого расхождения и данные ключа расположить по степени редкости этого расхождения, то вполне можно оставить map с таким ключом.

memcmp именно так и работает - до первого расхождения.

Автор: akizelokro 20.8.2013, 14:58

Цитата

Думаю, что фактически размер ключа влияет только на скорость сравнения элементов. Следовательно, если я буду сравнивать до первого расхождения и данные ключа расположить по степени редкости этого расхождения, то вполне можно оставить map с таким ключом.

А вот и не так.
Для составных ключей, если мне память не изменяет, есть не map, а multimap.
А иначе получится такая вещь. Для контейнеров существуют свои алгоритмы поиска и так далее по списку. В случае если вы закидываете в стандартный контейнер некую структуру с дополнительными условиями сортировки и поиска, для которого используете свой алгоритм (у которого есть примерный показатель затратности опреаций поиска и сортировки), это всё может наложиться на сопутствующие действия контейнера и привести к довольно неожиданным для разработчика результатам.

Автор: SenkraD 20.8.2013, 15:04

Цитата(akizelokro @ 20.8.2013, 14:58

)

Для составных ключей, если мне память не изменяет, есть не map, а multimap.

ну не совсем smile

. если std::map позволяет держать асоциацию один к одному, то std::multimap - один ко многим, один ключ - много значений.

скорость вставки и поиска в std::map зависит от алгоритма сравнение обьектов типа, который используется для ключа.

Автор: akizelokro 20.8.2013, 15:22

Цитата(SenkraD @ 20.8.2013, 15:04

)

ну не совсем smile. если std::map позволяет держать асоциацию один к одному, то std::multimap - один ко многим, один ключ - много значений.

Во-во, а то я уже обрадовался, что что-то знаю)