Category: Algorithms

Корозия Миталлляя

Корозия точности

Корозия Миталлляя

По оценкам специалистов различных стран эти потери в промышленно развитых странах составляют от 2 до 4 % валового национального продукта. При этом потери металла, включающие массу вышедших из строя металлических конструкций, изделий, оборудования, составляют от 10 до 20 % годового производства стали.

В компьютерных вычислениях тоже есть своя коррозия — «коррозия» точности при операциями над числами с плавающей точнкой. Об этом знают все, но всё равно обжигались:

Операции над двоичными числами (а в компьютере все они двоичные) вызывают много сюрпризов которые кажутся странными людям привыкшим к десятичной системе счисления:

не все десятичные числа имеют двоичное представление с плавающей запятой. Например, число «0,2» будет представлено как «0,200000003». Соответственно, «0,2 + 0,2 ≈ 0,4». Абсолютная погрешность в отдельном случае может и не высока, но если использовать такую константу в цикле, можем получить накопленную погрешность.

Поэтому когда считают что-то важное (например бабло) то используют хитрые классы обвёртки, типа BigDecimal, потому факап с примитивными типами неизбежен. Потому что есть ещё чудеса с переполнением, а в Си ещё и со знаком и эндингом. Естественно, скорости и удобства это не прибавляет. Хотя в Groovy с этим проще.
Кстати, если в контексте денег, то попробуйте новый JSR 354 — Currency and Money или на крайний случай его предшественник Joda Money. Ну и Фаулера почитайте для матчасти.

Так вот, в годы своей юности я написал калькулятор на Delphi, внутри которого был прикольный класс TFractNumber который мог считать без потери точности. Вообще. И никаких проблем как тут у него не было. И когда я через него, например, делил один на три а потом умножал на три то получал снова один а не 0,999999999…
Как такое возможно?
Я хранил число в виде обыкновенной дроби с числительным и знаменателем, все операции приводил к единому знаменателю, и сокращал дробь. Как в школе, помните?

Т.е. вместо десятичной дроби (а в случае процессора двоичной), в знаменателе которой может быть только десять в определённой степени, у нас мы может использовать любое число.

Так вот, такая запись позволяет записывать периодическую дробь и работать над нею как над целым числом.
Т.е. обычно в записи когда пишут 0.0909090909 можно отобразить через период 0,(09), и если привести к обычной дроби, то мы получим 1/11.

Правда с иррациональными числами проблемы так и останутся. Радует что на практике они не так часто попадаются.
Из недостатка у этого способа представления чисел то что оно требует больше места. Но я думаю, это не очень страшно в современном то мире — всё равно почти везде уже используются double и long вместо float.
А ещё, я думаю что любой студент сможет написать диплом с реализацией сопроцессора для обыкновенных дробей, чтобы увеличить производительность.

Это был кстати вообще один из первых классов в моей жизни с которого я начал погружение в ООП. Блин, да мне было лет пятнадцать.
Почему этого до сих пор не сделано в компьютерах, когда ракеты продолжают падать а банки терять деньги, я не так и не понял 😦

Мысли про компараторы

Компараторы возвращают отрицательное значение (не важно какой величины, чаще -1) если элемент меньше, нулевое если они на одном уровне, и положительное если уровнем больше.

Можно сделать более продвинутый компаратор который с учётом величины чем который бы позволил более эффективно использовать сравнение.
Например элемент который меньше на -3 сразу переместить ниже элемента который меньше на -2.

Также нулевое значение значит что он одинаков по уровню, а не одинаковый по значению. хотя зачастую так оно и есть.
Этот фактор тоже можно использовать для оптимизации.

Небольшая оптимизация инкрементального поиска

Инкрементальный поиск это когда вы пишете и сразу же происходит поиск после ввода каждой новой буквы. Как правило он всегда ещё и с автодополнением. Вы можете увидеть инкрементальность поиск по этой странице (Ctrl+F) и набирая по одной букве слово «информационные».

Длина слова Макс. совпадения букв (с начала слова)
1 информатор 10 7
2 информация 10 9
3 информационный 14 13
4 инфляция 8 3
5 инагурация 10 2
6 ингалятор 9 2
7 дезинформация 13 0
8 информационные 14 14

А в чём проблема?

Допустим что во время набора вы случайно сделали ошибку и затёрли предыдущею букву чтобы исправить её на правильную.
В этот момент произойдёт новый поиск. Или допустим вы ищите «информационные технологии», уже написали «информационные», оно вам нашлось но вы на автомате продолжаете набирать « технологии». Хоть такого совпадения точно нет, на каждое новое ваше нажатие тоже будет происходить новый поиск.
Если поиск занимает не много времени, то пользователь этого не заметит.
Но теперь представьте что операция поиска у вас дорогая. Например вы ищете по очень большому тексту, или допустим у вас автодополнение и для каждого поиска дёргается запрос на сервер.
Для таких случаев следует сделать проверку имеет ли смысл вообще продолжать поиск.

Для этого нужно сохранять результат максимального совпадения от предыдущих поисков:

  1. Набираем «информ», максимальное совпадение 6 первых символов в словах «информатор», «информация», «информационный», «информационные».
  2. Теперь делаем ошибку «информиц». Поиск не удался, смотрим предыдущее максимальное совпадение — 6, а мы уже набрали 8 букв, т.е. если дальше набирать фразу то можно даже не пытаться что-то найти.
  3. Замечаем, жмём ← Backspace, получаем «информи» — 7 букв, а у нас максимальное предыдущее 6, опять не делаем поиск.
  4. Исправили до «информ» и продолжили поиск снова каждый раз проверяя предыдущий результат.

Техническая реализация

Обратите внимание что мы предполагаем что пользователем будет меняться только концовка критерия поиска. А пользователь взял, скопировал откуда то слово и вставил его в строку поиска. Поменялся сразу весь критерий поиска а не просто его концовка.
Чтобы разрулить такую ситуацию сохраняйте не просто число, а и весь найденный фрагмент целиком и сверять с ним.

Для такого поиска нужно будет написать специальную функцию которая рассчитает максимальное совпадение:

function maxIntersect(string, subString) {
 for (i = 0; i < string.length && i < subString.length; i++) {
  if (string[i] != subString[i]) {
   return i + 1;
  }
 }
 return i + 1;
}

Когда-то я делал поиск в Firefox’е по тексту закона и таких тормоза я очень заметил. Chrome таким вроде не грешит.

З.Ы. Файл Excel иллюстрирующий работу механизма.