Какой самый быстрый способ проверить, находится ли строка в статическом наборе времени компиляции?

Question

Я знаю, что хеш-коды, как правило, являются самым быстрым способом проверки динамических наборов, но мне было интересно, какой самый быстрый способ проверить, находится ли динамическая строка в наборе строк только для чтения, известном во время компиляции. (Я имею в виду в основном {length: usize; chars: &[u8]} строки, а не веревки или минусы.)

В настоящее время я обычно делаю подобные вещи, но кажется, что это будет неоптимальным:

// What I mean
let keywords = Set::new(["do", "if", "in", "for", "new", "try"]);
fun is_keyword(s: &str) { keywords.contains(s) }

// What I write
function is_keyword(s: &str) {
    match s.length() {
        2 -> s == "do" || s == "if" || s == "in",
        3 -> s == "for" || s == "new" || s == "try",
        // etc.
        _ -> false
    }
}

Есть ли что-нибудь быстрее, чем что-то полученное из этого второго варианта для наборов строк в стиле C? Или это так быстро, как я мог разумно получить?

Это не зависит от языка - мне все равно, на каких языках используются ответы. Я просто использую Rust из-за знакомства.

Answer 1

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

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

Поиск в Google найдет вам много разных способов сделать идеальное хеширование. Один из моих любимых описан здесь: http://cmph.sourceforge.net/papers/chm92.pdf

Он часто используется для сопоставления ключевых слов в компиляторах или для реализации параметра switch / case в строках на языках, которые это поддерживают.

Answer 2

Как вы сказали, похоже, самый быстрый способ - это хешировать строки. Ваш текущий способ потребует O (N) времени для поиска самой большой строки в наборе или строки, которой нет в наборе вообще.