Сергей Соколов: отлично.
Ваша задача - минимизировать количество запросов.
Основное правило (... и нет, многие ему не следуют) не проверять уже проверенные значение.
0. Если число не может упасть, тогда стоит держать "под рукой" как минимум последнюю проверку (назову ее n0) и ниже нее уже не проверять.
1. Проверить [N+M; N-M] Если только N-M !< n0
Если нет в [N+M; N-M] то проверить [N-M; n0]
Если и там нет - это аномальный скачек. (или плохой расчет M) -> проверять [N+M; N+M+G] где G любое положительное число. Как и M расчет G задача ваша. Логика такая G = Nmax/2. Где Nmax - уж точно максимальное число пользователей. Пусть хоть "Over9000"/2.
2. Все таки найдя отрезок ищем в нем, деля его по полам.
Так же не нарушаем основное правило. Если в одной половине нет числа, то оно точно есть во второй. Не нужно ее проверять.
Поправка
G = Nmax/2 - M - N
А еще лучше
G = Nmax/2
А искать не в [N+M; N+M+G], а [N+M; G]
О - Оптимизация =)
Опишите ваше число, что это?
Оно постоянно растет?
Как часто бывают аномалии, явно выделяющиеся от сплайна?
Если это какая то активность пользователей, может стоит подумать о времени их активности, или... еще чего.
Людям из тостера не видно что у вас там происходит.
На данный момент ваш лучший вариант логарифмический поиск + максимально точный сплайн.
У вас уже есть некие результаты, попробуйте подогнать число M на них всех. Чтоб каждый результат был в рамках.
Ну и разумеется, что идеально вписав все уже имеющиеся результаты в рамки, нельзя быть уверенным, что что-то не пойдет по звезде и результат вы не поймаете. Т.е. можно заранее увеличить M на некий процент и сидеть сжимая кулачки. Либо обработать вариант такого исхода в алгоритме.
Сергей Соколов: В ваших интересах подобрать число M таким, чтоб оно при любом раскладе охватило истинную величину.
1 - кода в алгоритме будет меньше.
2 - проверок будет меньше.
d-stream: что факториал? Я так и не понял почему считать хеш придется 362880 раз... Даже если файлов будет 10000 (как в моем примере) то ко всем ним и придется посчитать и записать хеши в ОЗУ, на кой считать их каждый раз. Другое дело, что даже подсчет всех 10000 хешей - не очень быстро проходит.
Видимо из-за плохой постоновки вопроса, не удалось донести, что находить все хеши придется много раз и создание зарание бд не является применимы решением. (как минимум я так вижу)
Основная задача синхронизировать файлы в 2 папках указаных пользователем, причем полное удаление второй и копирование первой не самый "вкусный" вариант.