Динамический хэш-> тег класса - PullRequest
Новая
       12

Динамический хэш-> тег класса

1 голос
/ 23 июля 2010

У меня есть: 

const unsigned int hash_1 = 0xaf019b0c;
const unsigned int hash_2 = 0xf864e55c;  
const unsigned int hash_3 = 0xfaea8ed5;

Хеши приходят из автоматически сгенерированного заголовка.Эти хэши косвенно связаны с тегами 1, 2, 3. Теги связаны с классами через простой идентификатор, сгенерированный во время компиляции.Таким образом, я могу GetTag<Class1>() и получить свой int-тег для Class1.

Моя цель - упростить ассоциацию hash-> tag.Предпочтительно это должно быть время генерации компиляции и время доступа O (1).Память в этом случае не проблема.Я не могу использовать стороннее программное обеспечение.

Я пробовал следующее: 

template<uint32 t>  size_t GetTagByHash() { return 0; }

с конкретными реализациями, такими как: 

template<> size_t GetTagByHash<hash_1>() { return GetTag<Class1>(); }

, но такой тип реализации сложно использовать, так как, если у меня есть локальныйпеременная uint32 my_hash;, которую компилятор не может определить, какое значение он имеет во время компиляции, тогда компилятор не может разрешить правильную реализацию GetTagByHash() для вызова.

1 Ответ

2 голосов
/ 23 июля 2010

Насколько я понимаю, ваша проблема в том, как выполнить этот поиск со значениями времени выполнения, а также значениями времени компиляции.

У тебя действительно есть два вопроса. Во-первых, какой алгоритм вы хотите использовать для поиска, а во-вторых, как вы скажете C ++ реализовать это?

Алгоритм, который нужно использовать, отчасти неочевиден; у вас есть список эффективно-случайных чисел, и вы хотите найти что-то в этом списке и вернуть связанный тег. Возможно, вам нужна какая-то хеш-таблица, но для начала я покажу несколько примеров с чем-то более простым - и, вероятно, лучше для небольшого числа хешей: простой O (N) поиск в псевдокоде: 

if i = N return tag_N
else if i = N-1 ...
...
else if i = 1 return tag_1
else return tag_0

Теперь, как вы скажете C ++ сделать это? Вы должны создать список всех ваших хеш-тегов и инструкции для этого. Вот простой способ: 

template<int i> struct lookup
{
  int result(int j) { return 0; }
};

const unsigned int hash_1 = 0xaf019b0c;
template<> struct lookup<1>
{
  int result(int j)
  {
    if (j == hash_1)
      return GetTag<Class1>();
    return lookup<0>::result(j);
  }
};

const unsigned int hash_2 = 0xf864e55c;
template<> struct lookup<2>
{
  int result(int j)
  {
    if (j == hash_2)
      return GetTag<Class2>();
    return lookup<1>::result(j);
  }
};

И так далее. Тогда в конце вы можете получить 

int hash_lookup(int j)
{
  return lookup<last_hash_number>::result(j);
}

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

template<int> struct hash_tag {
  static const int value = 0;
  typedef type void;
};

#define SET_HASH(I, VALUE, CLASS)   \
template<> struct hash_tag<(I)>     \
{                                   \
  static const int value = (VALUE); \
  typedef type (CLASS);             \
}

SET_HASH(1, 0xaf019b0c, Class1);
SET_HASH(2, 0xf864e55c, Class2);
SET_HASH(3, 0xfaea8ed5, Class3);

// Define a general recursive lookup struct.
template<int i> struct lookup
{
  int result(int j)
  {
    if (j == hash_tag<i>::value)
      return GetTag<hash_tag<i>::type>;
    return lookup<i-1>::result(j);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  int result(int) { return 0; }
};

Затем вы используете это, как и раньше.

Теперь давайте вернемся к первому вопросу - какой алгоритм вы на самом деле хотите использовать для поиска? Преимущество этого итеративного поиска O (N) состоит в том, что его легко программировать, и он не требует никакой инициализации каких-либо структур данных во время выполнения - вы можете просто вызвать его. Однако, как уже отмечалось, это O (N). Альтернативный выбор - использовать объект std::map; вы можете использовать подобное рекурсивное определение, чтобы инициализировать его во время выполнения, а затем использовать его. Это может выглядеть примерно так: 

// Make a typedef to save some typing.
typedef std::map<unsigned int, size_t> Map_type;
typedef std::pair<unsigned int, size_t> Map_value;

// Define a recursion to add hashes to the map.
template<int i> struct add_hash
{
  void add(Map_type& hashmap)
  {
    hashmap.insert(
      Map_value(hash_tag<i>::value, 
                GetTag<hash_tag<i>::type>));
    add_hash<i-1>::add(hashmap);
  }
};

// Make sure the recursion terminates.
template<> struct lookup<0>
{
  void add(Map_type&) {}
};

// Now, create a class to initialize the std::map and do lookup.
class Hash_lookup
{
  Hash_lookup() { add_hash<last_hash_number>(map_); }
  int result(unsigned int j) { return map_[j]; }
private:
  Map_type map_;
}

Лично я, вероятно, совмещал бы это с вашей идеей GetTagByHash<> и дал бы Hash_loop функцию «результат вычислений во время выполнения», как я описал, а также функцию «результат вычислений во время компиляции», которая принимает шаблон аргумент, а не аргумент функции. Но, в целом, это основная идея для выполнения поиска во время выполнения - вы помещаете значения, которые вы хотите найти, в набор шаблонных классов, которые вы можете рекурсивно повторять во время компиляции, а затем вы используете эту рекурсивную итерацию для определения функцию поиска или инициализируйте структуру времени выполнения, которую вы можете использовать для поиска.

...