Monthly Archives: Декабрь 2014

Алгоритм построения траектории при наличии фазовых ограничений

Презентация по разработанному в этом году геометрическому алгоритму построения приближённой траектории линейной управляемой системы с выпуклым множеством управления и фазовыми ограничениями, заданными в виде наборов выпуклых многогранников. Алгоритм основан на двоичных разбиениях пространства (BSP).

Ссылка на презентацию

Ссылка на презентацию

Реклама

Совершенное хэширование сверхкоротких строк

Пусть заранее задан небольшой набор сверхкоротких строк и надо сделать словарь, ключами которого могут быть эти строки. Обычным решением для произвольных строк является использование универсальной хэш-таблицы с достаточно универсальной хэш-функцией (например, Murmur или FNV) из той или иной библиотеки (например, std::unordered_map).

Однако, данное решение является очень тяжеловесным, если строки-ключи заведомо очень короткие (далее я ориентируюсь на строки не длиннее четырёх байт), и, главное, известны заранее. В такой ситуации представляется разумным хранить ассоциированные значения в обычном массиве и подобрать такой хэш, который именно на данном заранее известном наборе не даёт коллизий, — совершенный хэш.

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

Сверхкороткие строки можно хранить в одном машинном слове. Четыре байта — 32-битное целое. Пусть, при этом, строки единичной длины соответствуют ненулевому младшему байту (три остальных — нули), строки длины два — двум младшим ненулевым байтам (два остальных — нули) и так далее. Функция приведения строки к числу такого вида может быть записана следующим образом:

inline uint32_t to_number(const std::string &word)
{
  register uint32_t result = 0;
  switch (word.size())
  {
  case 4: result  = (uint32_t)word[3] << 24;
  case 3: result |= (uint32_t)word[2] << 16;
  case 2: result |= (uint32_t)word[1] << 8;
  case 1: result |= word[0];
  default: return result;
  }
}

Хэш будем искать вида

template <uint32_t N, unsigned b>
uint32_t ssphash(uint32_t word)
{
  return (word * N) >> b;
}

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

Данная программа позволяет ввести набор строк и перебором ищет подходящие N и b. Размер хэш-таблицы выбирается как степень двойки не меньшая числа строк-ключей. Например, для лексем (операторы и пунктуация) C++

+ - ! ~ # % ^ & * ( ) / // /* */ [ ] { } | ? : ; , . && || ++ -- < > " ' <= >= = == -> .* ->* << >>

получены значения N == 242653, b == 17.