(перенесено из https://softwareengineering.stackexchange.com/questions/406813/how-to-implement-fnv-1a-in-sqlite)
Я пытаюсь изменить запрос SQLite (в Android), чтобы он возвращал результаты в псевдослучайном порядке. Как и в этот вопрос , порядок должен быть стабильным при повторных запросах (например, из-за подкачки, поворота экрана и т. Д. c.), Поэтому я не могу просто использовать ORDER BY RANDOM(). Вместо этого я хочу использовать функцию ha sh, которая зависит от пары входных значений, которые обеспечивают стабильность и достаточную уникальность. (Одно из этих значений представляет собой столбец уникальных идентификаторов таблицы, представляющий собой набор довольно близких целых чисел; другое значение больше похоже на идентификатор сеанса, также целое число, которое остается неизменным в этом запросе.)
Согласно этому хорошо изученному ответу , FNV-1 и FNV-1a - простые функции ha sh с небольшим количеством столкновений и хорошим распределением. Но, как бы они ни были просты, FNV-1 и FNV-1a включают операции XOR, а также циклическую обработку байтов ввода.
Циклирование внутри каждой строки запроса довольно неудобно. Его можно подделать, развернув l oop, особенно если задействовано всего несколько байтов. Я мог бы обойтись двумя байтами, комбинируя младшие биты из двух входных значений (val1 & 255 и val2 & 255).
XOR не поддерживается напрямую в SQLite. Я понимаю, что A ^ B может быть реализовано как (A | B) - (A & B). Но повторение ценностей в сочетании с развертыванием l oop начинает становиться громоздким. Могу ли я просто использовать + (игнорируя переполнение) вместо XOR? Мне не нужна очень качественная случайность. Орден должен выглядеть случайным для случайного наблюдателя в небольших целочисленных масштабах.
Поэтому мне интересно, кто-нибудь уже реализовал такую вещь. Учитывая, как широко использует эту функцию ha sh, это , похоже, что, вероятно, уже будет реализация для этой ситуации.
Вот моя попытка реализации FNV-1a:
SELECT ..... ORDER BY (((fnvbasis + val1 & 255) * fnvprime) + val2 & 255) * fnvprime % range;
Я игнорирую тот факт, что в FNV операция XOR (которую я заменил на +) должна влиять только на младшие 8 битов значения ha sh. Я также игнорирую любое переполнение (которое, я надеюсь, означает, что старшие биты, которые меня не волнуют, потеряны).
Для fnvbasis Я буду использовать 16777619, а для fnvprime Я буду использовать 2166136261. Это указанные значения для 32-битного ввода, так как я не вижу указанного значения для 16-битного ввода. Для range я буду использовать простое число, которое больше ожидаемого числа строк, возвращаемых этим запросом.
Так является ли это разумным способом приблизить FNV-1a в запросе SQLite? Есть ли лучшая существующая реализация? Т.е. будет ли он на самом деле производить порядок, который выглядит случайным пользователем довольно случайно, несмотря на то, что я искажал операции реального FNV-1a?