Мне тут рядом сидящий аналитик подсказал, что теоретически, при достоверных статистических сведениях о том, что количество чтений не менее чем в «100» превышает количество обновлений/записей, то при использовании gzip (хранении уже сжатых файлов и их отправки без обработки), ваш метод может показать меньшую нагрузку на файловую систему, чем методики с «склеиванием».
Брр, давайте разбираться. Продолжая опровергать бинарный поиск, скажу что при отсортированных ai/bi, R(ai/bi) отсортированным не будет, а ведь нам нужна именно его монотонность.
metar, не смешно. Даже если n = 100 000 000 000, мой серверок на Intel Atom справится с задачей, нам ведь не нужно все хранить в ОП, можем спокойно читать из файла по 1 000 000 записей, обрабатывать, освобождать…
Да, сложность линейная. Но мы уже говорили, что для бинарного поиска нужна монотонность, а функция не является монотонной на промежутке [min(ai/bi), max(ai/bi)].
И тогда нужно будет искать интервал, на котором функция не монотонная, и для этого интервала, с каким-то шагом проверять значения. Плюс обязательно проверить k = ai, bi. Когда найдется минимальное к, для него проверить k + epsilon, k — epsilon… Ну и так далее… Как-то так…
Ну если верить в дискретность времени, то теоретически можно. Другой вопрос, что хранить информацию о какой-то частичке — должно занимать столько памяти, сколько в физ. представлении не влезет в эту частичку. То бишь, одна лишь память будет размером больше всей вселенной.
/Не думаю что архивация тут уместна/