eu_tomat

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

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

Кстати, была похожая программка.

Вроде бы ни к чему не относится из имеющихся разделов. Перенёс в "разное".

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

Я поленился такое проделать. Надеялся, что есть способ попроще. Для того, чтобы знать, с какими плотностями у нас могут возникнуть коллизии в каждом конкретном случае. Добавлю два условия. 1) Для оптимизации перебираем не все плотности, а те, что в пределах [min,max] с учётом диапазона шума. 2) Также нужно найти не одно, а все целые числа, чтобы проанализировать возможные коллизии.

Для фиксации результата к уже сказанным мыслям добавлю, что полученное значение шума должно быть не только целым, но и находиться в диапазоне [-128,+127]. Это правило уменьшает количество коллизий. О коллизиях теперь и остаётся рассуждать. Алгоритм, эксплуатирующий дискретную природу шума, успешно определяет лишь блоки известной плотности. Даже если первое сканирование ведёт к коллизии, то это коллизия среди известных нам плотностей. Да и коллизия эта с большим шансом разрешится повторным сканированием. Но основой успеха будут заранее известные плотности блоков или хотя бы какая-то более-менее стандартная шкала плотностей. Вопрос: существует ли возможность сравнительно простыми манипуляциями вытащить таблицу плотностей всех имеющихся блоков в конкретной сборке модов?

Полагаю, это описка. А ход рассуждений одинаков, вы оба нашли решение.

Да, копать надо здесь. Раскручиваем наш сигнал назад к исходному рандому и проверяем характеристики на соответствие исходным. Нет, тут в другом фокус. Я не ищу уязвимость ГПСЧ, т.к. нашёл уязвимость в дальнейших за ГПСЧ преобразованиях. Эта уязвимость останется актуальной, даже если бы получаемый из ГПСЧ набор чисел вдруг оказался совершенно случайным. Так что, наши подходы сейчас различны.

Нет, это @NEO предлагал найти узявимость в ГПСЧ, а я пока воздержусь от этого способа. Я же считаю, что значение шума геосканера не совсем случайно, оно содержит своего рода цифровую подпись, по которой можно всегда или почти всегда (это ещё предстоит выяснить) восстановить точное значение именно шума в общем сигнале. Но для этого требуется выполнить обратное преобразование, одним из компонентов которого является расстояние. Ладно, посмотрим, как там @Doob решит задачу, да я и выложу ответ. Всё равно никто больше не пытается решать. Кстати, @Doob, у тебя в чём затык-то? Ты не уверен в решении моей задачи? Или в общем решении подобных задач? Решение задачи уже можно выкладывать?

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

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

Методика ускоренного вычисления константы шума геосканера Предлагаю ознакомиться с методикой, позволяющий максимально быстро и абсолютно точно вычислить константу шума геосканера (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 сканирвоаний ни разу не было достигнуто за несколько сотен попыток. И это ещё не всё, что может дать знание о шуме геосканера. Пошумим, брат!

@Doob, я перестал понимать твои визуализации в двух последних постах. Я на них ничего не вижу. Я не планирую хранить хеши шумов. Может быть, подумаю о хранении расстояний, чтобы не вызывать многократно функцию извлечения квадратного корня. Но оставшаяся часть реверсивных вычислений, мне кажется, слишком проста для того, чтобы занимать память этими хешами. Но да, надо будет проверить эти предположения в реальной работе. Тогда заодно и дам свою оценку шанса коллизий. Кстати, о коллизиях. Плотности блоков чаще всего кратны единице. Но бывает и 1.5 как у камня. Чем определяется плотность того или иного блока? Насколько дробной может быть плотность, как это регламентируется? Может ли, плотность блока быть 1.618, например? Какие они вообще бывают стандартные, типичные плотности?

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

Кинь ссылочку на код этого генератора. Посмотрим.

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

Жаву и скалу я тоже читаю на уровне интуиции, и далеко не все конструкции понимаю однозначно. Есть лишь знание архитектуры Intel 8086 и каких-то других языков программирования. И если я знаю, что на выходе должно получиться отрицательное значение, а вычитания в коде нет, то отрицательно исходное значение. Тем более, в коде присутствует деление на 128 для нормализации значения. А оно как раз-таки соответствует примерным границам unsigned char, чтобы вогнать его в диапазон (-1,1). Вот как-то так в полупонятном для меня языке иногда что-то становится очевидным. Но ложные срабатывания тоже случаются, таковы издержки подхода. Upd: Но даже такую разницу можно будет использовать для ускорения множественного сканирования на длинных дистанциях.

Хорошо. Сканирование «в лоб» все более-менее понимают. Существует некоторое критическое расстояние, за пределами которого результаты сканирования становятся неочевидными. И это расстояние можно точно вычислить. За пределами же этого расстояния приходится прибегать к множественному сканированию и к помощи математики и логики. Первое, что приходит в голову, это усреднение результата множественного сканирования. Но, как многие уже смогли убедиться, эффективность такого подхода невысока. При этом существуют решения, обеспечивающие лучшую сходимость. Предлагаю найти не столь очевидные подходы в геосканировании, решая следующую задачу: Произведено три сканирования одного и того же блока, находящегося на расстоянии 30 блоков от геосканера. Известно, что это либо руда с плотностью 3, либо камень с плотностью 1.5. Доски, булыжник, свинцовую руду пока не рассматриваем для упрощения задачи. Полученные значения (округлённо): {1.295, 3.341, 1.580}. Вопросы: что за блок мы просканировали: это руда или камень? Почему? Какое количество сканирований оказалось достаточным для однозначной идентификации блока?

Это не то же самое. Оба способа имеют право на существование. Можно сказать, что @Pengoid выполнил экспериментальное исследование, а @Doob теоретическое. И так как результаты совпали, то теория, скорее всего, верна, и эксперимент тоже поставлен верно, скорее всего. Оба молодцы. Ничего удивительного в том, что теоретические выкладки дают более короткое и наглядное объяснение, и красивые графики. В этом и заключается назначение теории. Благодаря этой теме я тоже кое-что понял про геосканер. Я раньше замечал, что абсолютное значение минимальных отрицательных величин шума всегда больше абсолютного значения его максимальных положительных величин. Например, -0.06060 против +0.06013 на единичном расстоянии при стандартной константе шума. Но в код я не заглядывал и понять причину не пытался. Но когда @Doob кинул ссылку на код, и я не поленился его почитать, причина аномалии стала очевидной. Дело в том, что исходными значениями для получения шума является набор случайных байт, которые затем преобразуются в числа с плавающей точкой. Это приводит к двум последствиям: 1) Шум геосканера имеет дискретную структуру, не смотря на то, что выражается значениями с плавающей точкой. Есть всего 256 фиксированных значений шума для определённого расстояния и константы шума. 2) Минимальное значение шума всегда больше его максимального значения в абсолютном выражении, т.к. исходный байт в архитектуре Intel кодирует 128 отрицательных значений, одно нулевое и 127 положительных. Cоотношение 128/127 равно соотношению 0.06060/0.06013 с погрешностью представления. Предполагаю, что это знание пригодится для уменьшения количества сканирований, например, при оценке реального значения константы шума, либо при многократном сканировании дальних объектов.

Смотря для какой цели. И смотря насколько заново. Мне будет приятнее видеть стартовый пост более структурированным. Другие читатели, возможно, не бросят его чтение где-нибудь на середине, не дождавшись выводов. Возможно, этот текст их чему-то научит. Так что, если у тебя есть мотивация переписать текст, то я поддерживаю. Переписывать ли заново? Зависит от имеющейся мотивации. Можно переписать частично. Но по своему опыту знаю, что, бывает, я изначально планирую лишь "слегка" переписать статью, но в процессе работы у меня меняется восприятие материала, и я в итоге полностью меняю структуру статьи, перетасовываю абзацы, предложения внутри них, меняю формулировки, исходя уже из нового понимания. Возвращаясь к вопросу: я вижу смысл в доработке. А решение переписать всё заново может принять лишь автор.

Особенностью этой темы является длинный текст. Оформленный в виде длинной простыни он отпугивает читателей. Для упрощения восприятия желательно разбить текст на абзацы и смысловые блоки. Также желательно расположить их в порядке развития мысли, снабдить заголовками, выделяющимися из общего текста. Основным способом разделения абзацев на современных форумных движках является пустая строка. К заголовкам обычно применяется полужирное выделение. В первом предложении темы желательно объяснить читателю, куда он попал, зачем нужна эта тема, и к чему его может привести чтение. Например, так: в этой теме я предлагаю обсудить способность геосканера различать плотности руд с учётом шума. Или так: в этой теме я хочу описать своё исследование возможностей геосканера и оптимальных способов сканирования руд. Для примера я попробую воспроизвести своё восприятие темы. Сначала я вижу заголовок темы "Вычисление погрешности геосканера". Название интересное, но в теме может быть что угодно: программа, методика, исследование, вопрос, приглашение к обсуждению. Учитывая, что тема изначально находилась в разделе флудилки, можно было строить самые безумные предположения. Сейчас тема находится в беседке, что настраивает читателя и комментатора на более серьёзное отношение, но всё равно не понятно, чего автор ожидает от читателей темы. В начале я вижу следующее "Решил измерить зависимость погрешности геосканера от расстояния". Я не понимаю, к чему ведёт автор. Он хочет что-то спросить? Он хочет чем-то поделиться? Хочет обсудить? Я быстро просматриваю первый абзац (или что-то напоминающее абзац), вижу, что автор что-то для себя уже понял, сделал какие-то выводы. В следующем абзаце автор наконец-то рассказывает, зачем это нужно. Но до сих пор не понятно, кому это нужно: автору или его читателям. Автор всё ещё собирается что-то спросить, или проинформировать нас? Пробегаю ещё один длинный кусок текста (абзац или не абзац), и начинаю смутно представлять одну из целей автора. Но опять же, не понятно, он хочет поделиться способом достижения цели, или где-то далее по тексту попросит помощи? И так почти до самого конца этого текста я пытался понять, к чему ведёт меня автор. Но понял лишь смутно.

Гайд хороший. Но я всё же склонен считать программирование на TypeScript в среде OpenComputers экзотикой. И необходимость явного приведения типов вряд ли является значимым поводом для смены одного языка на другой.

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

Зато могут появиться другие)