Круглые числа.
(или «Зачем программисту логарифм»)
Начнем с постановки практической задачи: Необходимо организовать удобный интерфейс для ввода диапазона числовых значений.
На практике это может потребоваться при создании «фильтров» для товарных каталогов: подвергаться фильтрации могут такие характеристики, как «диагональ телевизора», «минимальная температура в морозильной камере холодильника», «частота процессора».
В самом общем случае это могут быть положительные и отрицательные, целые и дробные числа, покрывающие некоторое недискретное пространство значений.
Очевидное и самое простое в реализации решение:
Такой интерфейс обладает рядом недостатков, среди которых выделим три наиболее важных:
- пользователь вынужден обращаться к клавиатуре
- пользователь может ошибиться при вводе (например, дробных значений)
- пользователь не информирован о диапазоне чисел, имеющих смысл в контексте фильтра
Все эти недостатки легко устраняются применением инструмента «слайдер» из состава большого количества современных javascript фреймворков. Мы для примера возьмем один из наиболее популярных: jQuery UI Slider.
Воспользовавшись примером из документации, получаем легкое и удобное решение:
Отсюда и далее все примеры будем приводить на базе этих трех характеристик: целочисленной, целочисленной отрицательной и дробной
Хорошо. Все три недостатка мы устранили. Но можно лучше. Избавим пользователя от необходимости «прицеливаться» ползунком, оглядываясь на значение числового индикатора. Для этого нанесем шкалу значений:
Ещё лучше. Но что-то в этих числах явно не так — это не те числа, которыми привык пользоваться человек. Это не круглые числа! На их месте так и просится что-то вроде: «500, 800, 1100, 1400, …», «-24, -22, -20, -18, …»
Википедия нам говорит о двух близких, по сути, трактовках термина «Круглые числа»: «10, 100, 1000, …» и «10, 20, 30, …». В общем виде круглое число в десятичной системе счисления имеет вид ±N×10k, где N — десятичная цифра, а k любое натуральное число. Для нашей задачи мы вынуждены будем расширить понятие круглого числа множеством чисел с отрицательными k (0.1, 0.2, …, 0.007, …), т.к. исчислять коэффициент аэродинамического сопротивления целыми числами не представляется возможным.
Итак, для построения «правильной» шкалы нам потребуется научиться вычислять такие минимальное и максимальное значения, а также величину шага, чтобы каждая метка на шкале была круглым числом.
Очевидно, что в этом случае наша шкала станет немного шире или уже, т.к. граничные значения сместятся в круглые позиции. Сужать — недопустимо: мы не можем позволить себе «выкинуть товар» из поиска. Следовательно, левую границу будем округлять до меньшего, правую границу и шаг — до большего круглого числа.
Важно также понимать, что для нашей задачи, при вычислении минимального значения, говорить о ближайшем круглом для, например, 517, — в отрыве от всего диапазона не имеет смысла. На его роль могло бы пойти число 500, будь у нас интервал от 517 до 3000 или, например, 510, будь у нас интервал от 517 до 550.
Верным решением задачи будем считать такой набор значений минимального (MINo), максимального числа (MAXo) и величины шага (STEPo), который удовлетворяет условиям:
MINo ≤ MIN // новый минимум не больше исходного
MAXo ≥ MAX // новый максимум не меньше исходного
STEPo × N = MAXo - MINo
Поиск круглого шага сводится к поиску ближайшего большего или равного круглого числа. Для этого исходный шаг необходимо разложить в экспоненциальную запись:
STEP = (MAX-MIN) / N
STEP_EXP = floor( log10(STEP) )
STEP_POWER = 10STEP_EXP
STEP_MANTISSA = STEP / STEP_POWER
// STEP = STEP_MANTISSA * 10STEP_EXP
Затем округлить мантиссу до меньшего целого и увеличить на 1
STEPo = (floor(STEP_MANTISSA) + 1) * STEP_POWER
Минимальное значение получим, округлив исходное значение до ближайшего меньшего числа, кратного STEP_POWER. Максимально значение вычислим из минимального и шага
MINo = floor(MIN / STEP_POWER) * STEP_POWER
MAXo = MINo + STEPo × N
Левая граница и величина шага будут соответствовать условиям задачи по способу их получения. А вот правая граница нуждается в дополнительной проверке, так как в общем случае она может оказаться меньше исходного максимума.
STEP = (MAX-MIN) / N
VALID = false; // флаг «верное решение найдено»
while not VALID
begin
STEP_EXP = floor( log10(STEP) )
STEP_POWER = 10STEP_EXP
STEP_MANTISSA = STEP / STEP_POWER
STEPo = (floor(STEP_MANTISSA) + 1) * STEP_POWER
MINo = floor(MIN / STEP_POWER) * STEP_POWER
MAXo = MINo + STEPo × N
VALID = MAXo ≥ MAX
STEP = STEPo// для перехода следующему круглому числу на следующей итерации цикла
end
Применяя этот алгоритм, получаем:
Такой интерфейс уже можно назвать user friendly, но в нём возник новый недостаток, не свойственный предыдущим примерам: при некоторых значениях MIN, MAX и количества засечек может возникать ситуация, когда интервалы между несколькими последними засечками выходят за пределы [MIN: MAX].
Примером такой ситуации может служить попытка отобразить диапазон значений [0 : 110] на шкале с десятью интервалами (11 засечек): шаг по 10 не покроет весь диапазон, а шаг по 20 сделает пустыми правые интервалы. Простого решения этой проблемы нет, однако, есть способ существенно снизить вероятность появления таких отрезков за счет расширения понятия круглого числа.
В текущем решении круглыми являются только те числа, мантисса которых входит в множество натуральных чисел от 1 до 9. Т.е. круглыми считаются только числа:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
| 100 | 200 | 300 | 400 | 500 | 600 | 700 | 800 | 900 |
| … | … | … | … | … | … | … | … | … |
А что, если расширить это множество числами, с мантиссой 1.2, 1.5 и 2.5? В тех самых случаях «пустого» отрезка мы получим более короткие значения (например, округлив 135, вместо 200 — получим 150)
| 1 | 1.2 | 1.5 | 2 | 2.5 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 12 | 15 | 20 | 25 | 30 | 40 | 50 | 60 | 70 | 80 | 90 |
| 100 | 120 | 150 | 200 | 250 | 300 | 400 | 500 | 600 | 700 | 800 | 900 |
| … | … | … | … | … | … | … | … | … | … | … | … |
Описывать алгоритм поиска ближайшего круглого по «новым правилам» не буду, полагая, что это не будет сложной задачей. Сразу покажу результат такого апгрейда:
Итог
Я мог бы сам подвести итог под всем сказанным выше, но думаю, что своим глазам читатель верит больше, поэтому — сводный пример:
Details
Математика
Помимо привычной десятичной системы счисления, существуют и другие. Им не в меньшей степени свойственно понятие круглого числа. И, хотя это имеет малое практическое значение, всё сказанное действительно и для них. (0xF000 воспринимается проще, чем 0xA48C, да? :-) )
Язык программирования
Если в вашем языке программирования нет функции вычисления десятичного логарифма, но есть натуральный, как в javascript — не беда: на помощь придут свойства логарифмов.
logN(x) = ln(x) / ln(N)
log10(x) = ln(x) / ln(10)
Исходный код
Алгоритмы, описанные в этой статье, и код, иллюстрирующий применение алгоритмов в связке с jQuery UI Slider, вы можете найти реализованными на языке javascript в прилагаемой к статье библиотеке.
Future
Как говорится: совершенству нет предела. Интерфейс выбора диапазона значений всё ещё можно совершенствовать:
- В некоторых случаях может быть полезна экспоненциальная шкала. Не теряя наглядности, она позволит детализировать отдельные, значимые, насыщенные участки отрезка и, наоборот, сузить разреженные. Очевидный пример: товарный каталог с эксклюзивными позициями. Цены в таком каталоге будет сосредоточены чуть ниже среднего значения, тогда как верхние отрезки окажутся почти пустыми.
- Для некоторых физических величин обратный порядок следования значений. Температура в морозильной камере — должна начинаться с минимального по модулю значения.
Есть над чем поработать!
P.S. Показались наши примеры неудачными? Попробуйте свои значения:
Ссылки:
jQuery UI, Экспоненциальная запись, Натуральное число, Логарифм, Круглые числа, Floor and ceiling functions