Я слышал, что логарифмы упоминаются довольно много в контексте программирования. Они, кажется, являются решением многих проблем, и все же я не могу найти реальный способ использовать их. Я прочитал запись в Википедии и что, честно говоря, не оставляет мне никого более мудрым.
Итак, где я могу узнать о проблемах программирования в реальном мире, которые решают логарифмы? Кто-нибудь получил какие-то примеры проблем, с которыми они столкнулись, которые были решены путем реализации логарифма?
Скажем, у вас есть 1000 долларов, и это сберегательный счет с 2,4% интересом.
Сколько лет вам нужно ждать, пока у вас не будет $2000, чтобы купить новый ноутбук?
1000 & times; 1.024 x= 2000
1.024 x= 2
x = log 1.024 2 = 29,23 года
Логарифмы в программировании также часто используются для описания эффективности алгоритма с использованием нотации Big O.
Например, алгоритм двоичного поиска имел бы худший сценарий O (log (n)) (на отсортированном множестве), тогда как наихудший случай линейного поиска - O (n)
В моем собственном исследовании я натолкнулся на несколько полезных ресурсов:
Это потрясающий набор уроков по логарифмам. Этот комментарий от 6-го грейдера подводит итог:
Большое вам спасибо. На этой неделе мой учитель математики сказал мне бросить вызов сам, поэтому я попробовал логарифмы. Сначала я подумал: "Я не могу этого сделать, это слишком сложно". Затем я посмотрел видео, и теперь они даже весело! Я в шестом классе, мой учитель математики впечатлен. Я не могу поблагодарить вас достаточно.
В этой статье содержится хороший пример использования базы 2 log для определения количества раундов, необходимых для завершения турнира нокаута, данного х команд.
Отличный, интуитивный (как и следовало ожидать, с учетом названия), руководство к e, базе естественного логарифма. Множество иллюстраций и примеров делают это жемчужиной статьи.
Это продолжение статьи к статье о e и обсуждается натуральный логарифм (ln), который, используя интуитивное объяснение, приведенное в статье, "дает вам время, необходимое для достижения определенного уровня роста".
На самом деле загружается хорошее содержание на сайте Лучше объяснено. Поистине, великолепный ресурс.
Еще один инструмент, с которым я столкнулся раньше, но с тех пор, как полностью забыл о нем, Instacalc. Кажется, что тот же человек - Калид Азад - кто автор сайта "Лучшее объяснение". Это действительно полезный инструмент при взломе с математикой.
Журналы - это тип метаарифметики. Это способ мышления каждого числа как (возможно, фиксированной) базы, поднятой до экспоненты. Операции выполняются только по показателям. Это означает, что вы можете делать умножение и деление, делая сложение и вычитание журналов. Другими словами, вы помещаете свои данные в пространство журналов, выполняете набор арифметических операций и возвращаете их обратно в нелокальное пространство. Если потеря точности с плавающей запятой и накладные расходы на преобразование в лог-пространстве или из него дешевы, тогда у вас может быть общий выигрыш во времени.
Один тонкий трюк, который вы можете делать с журналами, вычисляет количество символов, которое номер будет принимать при печати, взяв лог-базу-2 этого числа и разделив его на базу данных-10 (2), которая является постоянным временем по сравнению с множеством умножений.
Я видел логарифмы, используемые для отображения облаков тегов. Это страница, которая объясняет это:
Я предполагаю, что вы слышали о логарифмах с контекстами времени.
Конкретным примером могут служить алгоритмы поиска. Учитывая набор упорядоченных данных (подумайте о сортированном массиве int), вы хотите найти индексный ключ для значения в этих данных. Мы можем извлечь выгоду из того, что массив отсортирован (например, 1, 2, 6, 192, 404, 9595, 50000). Скажем, мы хотим найти индекс для значения 2. Мы можем минимизировать наше пространство поиска, отбрав (игнорируя) половину массива на каждом шаге. Мы начинаем этот поиск, проверяя значение в середине массива. В массиве 7 значений, затем мы делаем индекс 7/2 = 3.5 = 3 как int. array [3] - 192. Значение, которое мы ищем, равно 2, поэтому мы хотим продолжить поиск в нижней половине пространства поиска. Мы полностью игнорируем индекс 4, 5, 6, так как все они выше 192, а в свою очередь также выше 2. Теперь у нас есть пространство поиска, которое выглядит как (1, 2, 6). Затем мы снова индексируем на середину (повторяем процесс), и мы находим 2 моментально. Поиск завершен, индекс 2 равен 1.
Это очень маленький пример, но он показывает, как работает такой алгоритм.
Для 16 значений вам нужно выполнить поиск максимум 4 раза. Для 32 значений вы выполняете поиск максимум 5 раз, 64 значения 6 раз и т.д. 1048576 выполняется поиск по 20 шагам. Это намного быстрее, чем сравнивать каждый элемент в массиве отдельно. Конечно, это работает только для сортированных коллекций данных.
Я рекомендую e: "История номера" для хорошей основы важности логарифмов, их открытия и значимости для природных явлений.
Другой способ взглянуть на это - это посмотреть на количество базовых множителей в числе. Я уверен, что вы можете видеть, как это все относится в следующих примерах.
Десятичный (основание 10):
Двоичный (база 2):
Шестнадцатеричный (базовый 16):
Если вы хотите думать в переменных:
Многие (многие!) отношения в реальном мире логарифмичны. Например, меня не удивило бы, если распределение баллов репутации в Qaru log normal. У подавляющего большинства пользователей будет показатель репутации 1, а у нескольких людей будет недостижимо высокая репутация. Если вы примените логарифмическое преобразование к этому распределению, оно, вероятно, будет почти линейным. Быстрый просмотр https://stackoverflow.com/users?page=667 показывает, что это правда.
Возможно, вы знакомы с концепцией The Long Tail, которая является применением логарифмического распределения.
Единственная проблема, которую я могу вспомнить, - это вычислить произведение столбца в SQL. SQL Server не имеет агрегированной функции PRODUCT(), поэтому это было выполнено с использованием суммы логарифмов (с использованием функции LOG10()) каждого значения. Главный недостаток заключался в том, что все числа в столбце должны были быть положительными и ненулевыми (вы не можете вычислить логарифм на отрицательном числе или ноль).
Наиболее очевидным использованием в каждом примере программирования является точность. Проще говоря, рассмотрим сохранение целых чисел без знака. Сколько бит вам нужно для хранения X? Наилучшим образом, максимальное значение, которое вы можете сохранить в n битах, равно 2 ^ n - 1, поэтому вам может понадобиться log_2 X + 1 бит для хранения X. Теперь вы можете легко и легко выбрать короткий, int, word, long и т.д.
Один пример из многих: вычисление сложных интересов с очень малой скоростью с большим количеством периодов.
Вы можете сделать это самым простым способом, даже используя быстрое экспонирование, но точность может пострадать из-за того, как хранятся поплавки и вычисления s * r power n все еще выполняет операции O (ln (n)).
С логарифмами он несколько точнее.
A = ln (s * r power n) = ln (s) + n * ln (r)
Два поиска в вашей логарифмической базе данных дают вам ln (s) и ln (r), причем ln (r) начинаются очень малыми, а поплавки работают с максимальной точностью около 0
result = exp (A), обратный поиск здесь.
Это также единственный эффективный способ, если вы работаете с не целочисленными показателями, чтобы извлечь кубические корни, например.
Отъезд MIT Open Courseware: Введение в алгоритмы. Свободные образования. Высокий.
Одно из самых "крутых" приложений логарифмов, которые я нашел, - Spiral Storage. Это хеш-таблица, которая позволяет вам разделить одно ведро за раз по мере роста таблицы, переместив менее половины записей в этом ковше в то же самое новое ведро. В отличие от линейного хеширования, где производительность меняется циклически, и все ведра, как правило, расщепляются примерно в одно и то же время, спиральное хеширование позволяет приятно, плавно увеличивать таблицу.
Это было опубликовано около 30 лет назад GNN Martin, о котором я не смог многому научиться, кроме того, что он также изобрел Range Encoding. Кажется, умный парень! Я не смог получить копию его оригинальной статьи, но в Per-Åke Larson paper "Динамические хэш-таблицы" имеет очень четкую описание.
Логарифмы используются довольно часто в диаграммах и графиках, когда одна или обе оси охватывают большой диапазон значений.
Некоторые явления природы лучше всего выражены в логарифмической шкале; некоторые примеры - уровни звукового давления (SPL в дБ) и величина землетрясения (Шкала Рихтера).
В качестве примера того, о чем говорит Крис, алгоритм, который изменяет сложность, основанную на количестве бит в значении (вероятно), будет иметь эффективность описываемый O (log (n)).
Другой повседневный пример показателей (и, следовательно, логарифмов) находится в формате числа с плавающей точкой IEEE.
Логарифмическая функция просто обратная к экспоненциальной функции, в том же смысле, что вычитание является обратным добавлению. Так же, как это уравнение:
a = b + c
указывает тот же факт, что и это уравнение:
a - c = b
это уравнение:
b ** p = x
(где ** поднимается до степени) утверждает тот же факт, что и это уравнение:
log [base b] (x) = p
Хотя b может быть любым числом (например, log [base 10] (10,000) = 4), "естественная" база для математики - это e (2.718281828...), о которой см. здесь.
"Общие" логарифмы, используемые больше в технике, используют базу 10. Быстрое и грязное (выделение на грязную) интерпретацию общего логарифма (базового 10) некоторого числа x заключается в том, что он один меньше числа десятичных цифр, необходимых для выражения чисел размером x.
Демистификация естественного логарифма (ln) на BetterExplained - лучшее, что я нашел. Он очищает концепции от базы и помогает понять основные понятия. После этого все кажется легкой прогулкой.
Вот некоторые сайты, которые я использовал:
Я использовал логарифмы для расчета ежегодной оценки дома, чтобы определить, был ли продавец честным.
Уравнения для оценки состояния дома
Вот базовое уравнение:
p * (1 + r)^y = n
Итак, если цена 6 лет назад составляла 191 000 долларов США (путем проверки вашего сайта аутсайдера), а запрашиваемая цена составляла 284 000 долларов США, какова оценка (которая не учитывала бы затраты на единовременные улучшения)?
191,000 * (1 + r)^6 = 284,000 (1 + r)^6 = 284,000 / 191,000 = 1.486 Using a property of exponents and logarithms… 6 ( log (1 + r) ) = log 1.486 log (1 + r) = (log 1.486) / 6 = 0.02866 Using another property of exponents and logarithms… 10 0.02866 = 1 + r 1.068 = 1 + r r = 1.068 – 1 = 0.068 = 6.8% (kind of high!)
Чтобы определить, какая разумная цена будет... использовать 4% и разрешить любые улучшения, которые они сделали (которые должны быть указаны в веб-идентификаторе, они были основными... но он не включал бы реконструирование ванной/кухни и т.д.)
191,000 * (1 + 0.04)^6 = n n = 241,675 + reasonable cost of improvement which of course will depreciate over time and should not represent 100% of the cost of the improvement