hash_map, хэш-функция карты для составного ключа - PullRequest
Новая
       37

hash_map, хэш-функция карты для составного ключа

0 голосов
/ 17 июня 2011

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

Мой ключ представляет собой составной тип данных, такой как 

typedef struct {
  char * name;
  int offset;
}position;

И дляstd :: map Я использую следующую функцию частичного упорядочения 

struct cmp_position {
  bool operator()(const position& first,const  position& second) {
    int tmp = std::strcmp(first.name, second.name);
    if(tmp!=0)
      return tmp<0;
    else
      return first.offset<second.offset;
  }
};

И определение моей карты 

typedef std::map<position,int,cmp_position> myMap;

Я смотрю на __gcc_ext :: hash_map, для этого требуетсяФункция равенства, которая может быть просто 

struct positionEq
{
  bool operator()(const position& s1, const position & s2) const
  {
    return strcmp(s1.name, s2.name) == 0 && (s1.offset==s2.offset) ;
  }
};

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

position s;
char buf[100];
snprintf(buf,100,"%s:%d\n",s.name,s.offset);

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

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

Я не намерен использовать std :: strings.

Спасибо

Редактировать:

В приведенном выше примере я попытался использовать std :: set вместо std :: map, а std :: set постоянно медленнее заполняет и ищет записи.Он использует намного меньше памяти, хотя общее сравнение приведено в таблице ниже.Я пытался запускаться каждые 10 раз 

         Set        map
 size   1.8gig     3.1gig
 pop    <15sec     <14sec
 find   <12sec     <9sec

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

1 Ответ

0 голосов
/ 18 июня 2011

Вы пробовали это с ключевой структурой, хранящей хэшированное значение name (используя, например, boost::hash_value), чтобы сравнение ключевых объектов было бы просто двумя сравнениями чисел, что должно быть довольно быстрым.

Попробуйте протестировать его с unordered_set.boost::multi_index_container заявляет, что превосходит std::set, и в некоторых случаях вы могли видеть, немного ли это ускоряет ход событий (см. Мой ответ здесь для примера его использования).

...