Методика ускоренного вычисления константы шума геосканера

[eu_tomat 2 154]

Методика ускоренного вычисления константы шума геосканера

Предлагаю ознакомиться с методикой, позволяющий максимально быстро и абсолютно точно вычислить константу шума геосканера (geolyzerNoise в config/OpenComputers.cfg).

 

Методика и скрипты тестировались в среде OpenComputers-MC1.7.10-1.7.5.1290-universal.jar. Сохранит ли эта методика свою актуальность в будущем, вселцело зависит от авторов мода.

Зачем знать константу шума геосканера?

Не на всех серверах параметр geolyzerNoise сохраняет значение по умолчанию. Алгоритмы же поиска руд, использующие для своей работы геосканер, в большинстве своём эффективны лишь при определённых параметрах шума. При увеличении или уменьшении зашумлённости будут эффективны другие алгоритмы. Поэтому знание точных параметров шума геосканера поможет использовать наиболее эффективные алгоритмы поиска руд на конкретном сервере в конкретных условиях шума.

Традиционный алгоритм

Традиционный алгоритм использует выполнение многократного сканирования плотности блока, поиск минимального и максимального значений и вычисление разницы между ними. Плюсом алгоритма является его простота. Минусом является низкая точность. Для повышения точности используется увеличение кратности сканирования, но даже очень большая кратность не даёт гарантии абсолютной точности. Всегда есть небольшой шанс, что шум окажется немного больше найденного алгоритмом.

Дискретная структура шума

Как было обнаружено в недавнем обсуждении про вычисление погрешности геосканера, шум имеет дискретную природу. Согласно коду OpenComputers для каждого из сканируемых расстояний существует 256 возможных значений шума. Знание этого факта позволяет нам считать результат достигнутым, как только сканер выдаст 256 уникальных значений плотности одного и того же блока. Плюсом такого подхода будет абсолютная точность. Главный же минус заключается в том, что получение всех 256 значений может занять даже больше времени, чем получение реальных минимума и максимума плотности. В моих экспериментах на получение всех 256 значений уходит примерно 10-20k попыток сканирования.

 

Вот скрипт для наглядности:

-- демонстрация: шум геосканера имеет 256 фиксированных значений
-- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc

local scan = require'component'.geolyzer.scan

local uniqTbl = {}
local uniqCnt = 0
local v

for i=1,1e4 do
  v = scan(0,0,-1, 1,1,1)[1]
  if not uniqTbl[v] then
    uniqTbl[v] = true
    uniqCnt = uniqCnt + 1
    print(("try: %d, uniqCnt: %d"):format( i, uniqCnt ))
  end
  os.sleep(0)   -- ^C для останова
end

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

Оптимизация поиска

Оптимизировать вычисления нам поможет знание о том, что все 256 значений шума расположены равномерно, расстояния между смежными значениями одинаковы, и они ровно в 256 раз меньше расстояния между максимальным и минимальным из значений. В пределах погрешности вычислений, разумеется.

 

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

 

Уменьшать количество значений в рабочей таблице следует ровно до того момента, пока это не мешает обнаружению двух смежных значений. Можно сказать и наоборот: пополнять таблицу новыми значениями следует ровно до тех пор, пока смежные значения не удаётся обнаружить с абсолютной точностью.

 

Самое очевидное, что приходит в голову, это набрать ровно 129 уникальных значений, и найти среди них ближайших соседей. Почему 129, а не 128? Потому что при 128 уникальных значениях возможна редкая ситуация, когда эти найденные значения находятся в полной таблице ровно через одно. Это маловероятно, но возможно. Зачем рисковать? Тем более, 129 элементов почти всегда находятся примерно за 200 попыток сканирований, что можно увидеть, наблюдая за работой демонстрационного скрипта.

 

Но внимательный читатель наверняка заметит, что может быть достаточно использовать и 128 значений при условии, что они размещены неравномерно относительно друг друга. Почти всегда 129-ое значение оказывается необязательным. И если развить эту мысль, то выяснится, что и 127 значений почти всегда будет достаточно при введении дополнительных условий. Тем же путём можно перейти к 126 значениям и т.д. В итоге окажется, что роль играет не равномерность расположения значений относительно друг друга, а расстояние между крайними элементами и между двумя ближайшими. А для этой цели может быть достаточно даже трёх найденных значений. В лучшем случае. Но в худшем могут потребоваться и все 129 значений.

Оптимальный алгоритм

В общем виде алгоритм сводится к циклическому получению очередного значения от геосканера и поиску разницы между всеми найденными значениями. И если соотношение максимальной разницы к минимальной превысит 128, то результат достигнут: минимальная разница между найденными значениями обязана быть равной разнице между смежными значениями в полной таблице. Результатом умножения минимальной разницы на 128*33 будет искомая нами константа geolyzerNoise из файла конфигурации.

 

Результирующий код может выглядеть, например, так:

-- измеритель шума геосканера (константы geolyzerNoise в config/OpenComputers.cfg)
-- установка: любой блок, сверху блок геосканера, на него спавним комп /oc_sc

local abs = require'math'.abs
local scan = require'component'.geolyzer.scan

-- округление до сотых долей для сокрытия погрешностей
local function round( v )
  return (v*1e2+0.5)//1/1e2
end
-- множитель для восстановления значения шума до справочного
local mul = 128*33

local uniqTbl = {}
local uniqCnt = 0

-- текущее значение, разница с другим значением, минимальная и максимальная разница
local val, dif, min, max
-- флаг обновления экстремумов
local fUpd

for i=1,99 do
  os.sleep(0)
  val = scan(0,0,-1, 1,1,1)[1]

  fUpd = false
  -- обрабатывать только новые уникальные значения
  if not uniqTbl[val] then
    -- обновить информацию о минимальной и максимальной разнице
    for v,_ in pairs(uniqTbl) do
      dif = abs( val-v )
      if not min or min>dif then min=dif fUpd=true end
      if not max or max<dif then max=dif fUpd=true end
    end
    -- пополнить таблицу уникальных значений
    uniqTbl[val] = true
    uniqCnt = uniqCnt + 1
  end

  -- при обновлении вывести информацию на экран
  if fUpd then
    print(("uniq:%2d/%2d |  min:%7.3f | max:%7.3f | max/min:%7.3f"):format( uniqCnt,i, round(min*mul), round(max*mul), round(max/min) ))
  end
  -- закончить по достижении результата
  if fUpd and max/min > 128 then
    break
  end
end

-- сообщить результат
if fUpd and max/min > 128 then
  print(("Congratulations! geolyzerNoise = %f"):format( round(min*mul) ))
else
  print("Failure! Tray again please!")
end

 

Результат

Знание об особенностях генерации шума геосканера, позволило достичь абсолютно точных результатов при очень малом времени сканирования при вычислении константы шума геосканера. В лучшем случае результат можно получить за три сканирования. В типичном случае требуется около 20 сканирований, что требует около одной секунды времени. Самый худший случай не ограничен ничем, но использованное в моём скрипте ограничение в 99 сканирвоаний ни разу не было достигнуто за несколько сотен попыток.

 

И это ещё не всё, что может дать знание о шуме геосканера. Пошумим, брат!

[eu_tomat Автор темы 2 154]

Прошу всех, кто заметил странности в форматировании этой темы, сообщить мне об этом. Использован экспериментальный подход. Основное форматирование было выполнено в asciidoc, отформатированный текст перенесён на форум, после чего осталось вручную раздвинуть абзацы и оформить куски кода тегами. Ссылки вроде бы сохранились, заголовки тоже. Красота. Но всё равно скучаю по старому движку с поддержкой BBCode и продолжаю искать способы быстро публиковать на форуме статьи с более-менее сложным форматированием.

[eu_tomat Автор темы 2 154]

Предложенная в теме методика вычисления константы шума весьма эффективна. Но она ещё не исчерпала весь потенциал возможных оптимизаций. Позже я подробно расскажу о найденных мною решениях, но сейчас предлагаю всем, кто любит решать задачи самостоятельно, ответить на вопрос: как ещё сильнее сократить кратность сканирования, не жертвуя при этом точностью результата?

 

Я нашёл три решения. Два из решений основаны на общем принципе и очевидны для тех, кто активно пользуется геосканером. Одно даёт лучшую сходимость за счёт усложнения установки. Другое же не столь эффективно, но и установка не усложняется. Зато третье решение эффективно, при это не требует усложнения установки, но эксплуатирует некоторые особенности реализации шума геосканера, которые мы ещё не обсуждали.

 

У кого есть варианты ответов?

 

Upd:

Третье из найденных мной решений оказалось ошибочным. Код генератора шума не позволит объединить преимущества первых двух решений.

[hohserg 197]

Чем дальше блок от геосканера, тем выше шанс и амплитуда погрешность измерения. Поэтому, возможно, имеет смысл сканировать блоки на разном расстоянии.

[eu_tomat Автор темы 2 154]

4 часа назад, hohserg сказал:

Чем дальше блок от геосканера, тем выше шанс и амплитуда погрешность измерения. Поэтому, возможно, имеет смысл сканировать блоки на разном расстоянии.

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

 

Просканировать блоки на разном расстоянии, конечно, можно, но что нам это даст после нормализации шума?

[eu_tomat Автор темы 2 154]

Я нашёл ещё один способ оптимизации алгоритма чисто математическими средствами.

 

До этого я говорил, будто бы для полной гарантии решения задачи требуется найти минимальную и максимальную разницу между всем значениями, полученными от геосканера, а задача считалась решённой при условии max/min > 128. Взглянув на эту задачу под новым углом, я считаю, что это условие достаточно, но не является необходимым для решения задачи. Существует подход, обеспечивающий ещё более быструю сходимость к результату.

 

Желающим размять мозги предлагаю два примера:

Имеем массив значений: {10, 12, 280}. Условие (max/min>128) соблюдено. Константа шума равна 2.
Имеем массив значений: {10, 18, 280}. Условие (max/min>128) не соблюдено, но существует решение и для этого случая тоже.

 

Вопрос: как решить задачу во втором примере?

Для решения достаточно знаний школьного курса математики. Другое дело, что это не типовая задача, скорее всего.

[NEO 542]

17 минут назад, eu_tomat сказал:

(max/min>128)

Что является мах и мин? В первом массиве 280/10 = 28, что во втором 280/10 = 28.

[eu_tomat Автор темы 2 154]

9 минут назад, NEO сказал:

Что является мах и мин? В первом массиве 280/10 = 28, что во втором 280/10 = 28.

Нужен минимум и максимум не самих значений, а разниц между ними:

22 минуты назад, eu_tomat сказал:

требуется найти минимальную и максимальную разницу между всем значениями, полученными от геосканера, а задача считалась решённой при условии max/min > 128.

 

[hohserg 197]

3 часа назад, eu_tomat сказал:

max/min

Т.е. это не деление? 280-10>128?

[eu_tomat Автор темы 2 154]

2 минуты назад, hohserg сказал:

Т.е. это не деление? 280-10>128?

В данном случае это как раз-таки деление. Я не давал подробных пояснений именно к этой задаче, надеясь на то, что внимательно читавшие методику и сопровождающей её код, и так все поймут.

В 25.04.2020 в 19:27, eu_tomat сказал:

В общем виде алгоритм сводится к циклическому получению очередного значения от геосканера и поиску разницы между всеми найденными значениями. И если соотношение максимальной разницы к минимальной превысит 128, то результат достигнут: минимальная разница между найденными значениями обязана быть равной разнице между смежными значениями в полной таблице. Результатом умножения минимальной разницы на 128*33 будет искомая нами константа geolyzerNoise из файла конфигурации.

Следом за этим абзацем идёт код, реализующий описанный алгоритм.

 

Если моё описание методики в чём-то непонятно, то критикуйте, пожалуйста. Например, я мог опустить очевидные для себя вещи, где-то совершив слишком резкий логический переход. А для читателей это может быть и вовсе неочевидным. Просто спросите, а почему из того следует это. Я дам свой ответ, а позже внесу правки в описание. Или не внесу, чтобы не раздувать описание.

 

Но вернёмся к задачкам. Описанный алгоритм был для меня актуальным в момент написания методики. Теперь его надо расширить, чтоб решать менее очевидные случаи, не требуя от геосканера новых данных.

 

Для начала я поясню свои примеры:

4 часа назад, eu_tomat сказал:

Имеем массив значений: {10, 12, 280}. Условие (max/min>128) соблюдено. Константа шума равна 2.
Имеем массив значений: {10, 18, 280}. Условие (max/min>128) не соблюдено, но существует решение и для этого случая тоже.

Первый пример: Вычисляем расстояния между всеми парами значений:

{abs(10-12), abs(10-280), abs(12-280)}

{2, 270, 268}

min(2, 270, 268)=2

max(2, 270, 268)=270

max/min = 270/2 = 135 > 128

Задача решена:

geolyzerNoise = min = 2

 

Во втором примере:

{abs(10-18), abs(10-280), abs(18-280)}

{8, 270, 262}

min(8, 270, 268)=8

max(8, 270, 268)=270

max/min = 270/8 = 33.75 < 128

Задача не решается описанным алгоритмом, но небольшое усложнение вычислений обеспечит решение и этого примера тоже.

 

А теперь я дам намёк на решение: Значения шума геосканера не случайны. Их всего 256. Расстояния между значениями равны. Всегда повторяется один фиксированный интервал. И какие бы два значения шума мы ни выбрали, расстояние между ними всегда будет кратно этому интервалу.

[hohserg 197]

Если есть n вариантов сканирования(при n>3) такие, что для них всех существует единственный общий делитель, то этот делитель является расстоянием между соседними шумами

Изменено 29 апреля, 2020 пользователем hohserg

[eu_tomat Автор темы 2 154]

7 минут назад, hohserg сказал:

Если есть n вариантов сканирования(при n>3) такие, что для них всех существует единственный общий делитель, то этот делитель является расстоянием между соседними шумами

Да, именно так, находим минимальное расстояние через НОД. И уже это, найденное через НОД расстояние считаем за минимальное, и проверяем соотношение максимальной разницы уже с ним. Максимум разницы я пока продолжаю искать традиционным способом. Я не уверен, что там уместны подобные трюки, и пока не занимался этим.

 

Сейчас я пытаюсь решить другую проблему. Поиск НОД хорошо работает только для целых чисел, а константа шума не обязана быть целым числом. Пока я считал в scalc, где есть хорошая точность вычислений, всё было просто, понятно и наглядно, даже для константы шума с тысячным долями. А в Lua поиск НОД для вещественного числа пока что выдаёт нестабильные результаты. Сейчас я заменил алгоритм Евклида на его расширенную версию, доработав с целью минимизации накопления погрешности. Пришлось увеличить количество операций в коде, чтобы уменьшить количество операций в отдельно взятой цепочке вычислений. То есть, длинные цепочки каждый раз пересчитываются заново с использованием сокращённой записи. Погрешности пока ещё велики, но и не все вычисления я успел привести к оптимальному виду.

 

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

[eu_tomat Автор темы 2 154]

Идея избавиться от всех длинных цепочек вычислений оказалась верной. Моя модификация расширенного алгоритма Евклида выдаёт два целочисленных коэффициента (слегка модифицированные коэффициенты Безу), и для получения результата остаётся лишь разделить длинный интервал на целое число. Дополнительная погрешность возникает только при однократной операции деления вещественного числа на целочисленное.

 

Итог: благодаря поиску минимального интервала через НОД удалось достичь заметного ускорения вычислений. Теперь результат часто находится за три сканирования, и очень редко требуется больше 10 сканирований.

 

А ещё я не уверен, можно ли применять термин НОД применительно к вещественным числам. С другой стороны, последовательность целых чисел с единичным шагом является частным случаем математической прогрессии, которая может иметь произвольный шаг. Вот, и вся разница по идее-то. Есть у нас на форуме кто-то хорошо владеющий математической терминологией? Как правильно называть то, что я назвал наибольшим общим делителем?

[hohserg 197]

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

Также, если приемлемо юзать интернет-карту, можно обращаться к апи scalc(если есть), чтобы получить НОД

Изменено 3 мая, 2020 пользователем hohserg

[eu_tomat Автор темы 2 154]

1 час назад, hohserg сказал:

Также, если приемлемо юзать интернет-карту, можно обращаться к апи scalc(если есть), чтобы получить НОД

Моей сисадминской части сознания этот вариант кажется достойным внимания. Но программистская часть сознания требует более изящного решения.

1 час назад, hohserg сказал:

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

В общем, да. Можно производить вычисления повышенной точности с помощью соответствующих библиотек. Но я пошёл иным путём.

 

Можно доработать алгоритм. Чем плох базовый алгоритм Евклида? Он производит серию манипуляций с числами, накапливая погрешность с каждой итерацией вычислений. Для целых чисел, ясное дело, погрешность не накапливается, но нам нужны вещественные числа. Кроме базового алгоритма Евклида существует его расширенная версия, которая также не предназначена для вещественных чисел, но содержит в себе намёк на то, как не накапливать погрешность вычислений от итерации к итерации.

[NEO 542]

По идеи можно вычислить погрешность из самого представления вещественных чисел в эвм.

[eu_tomat Автор темы 2 154]

12 минуты назад, NEO сказал:

По идеи можно вычислить погрешность из самого представления вещественных чисел в эвм.

Погрешность-то мы вычислим, это не проблема. Но нам для сохранения точности требуется знать конкретное, вносимое погрешностью значение в каждом отдельном случае.

 

Вот, разделил ты какое-то число на 9, да округлил до двух знаков после запятой. Получилось, к примеру, 0.22. И как ты теперь узнаешь, какое из чисел было исходным? Может быть, 2.00, а может, и 1.99.