Magneto903

Действительно проблема в WasmFiddle. Он генерирует код, который нуждается в функции memcpy(импорт), но не реализует её в импорте. Добавил простенькую функцию:

void* memcpy(char* dst, char* src, int count) {
  while(count--) *dst++ = *src++;
}

И чуть изменил JS-код

var wasmModule = new WebAssembly.Module(wasmCode);
var wasmInstance = new WebAssembly.Instance(wasmModule, wasmImports);
var wasm_module = wasmInstance.exports

wasm_module.main();

for (var i=0; i < 5; i++) {
  var c1 = wasm_module.get_cache_1(i);
  var c2 = wasm_module.get_cache_2(i);
  
  log(i+" " +c1 + " " + c2);
}

Выводит в точности то, что Вы ожидаете.

Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

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

И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.

Тут надо построить конечный автомат, который принимает строки, которые кончаются на заданную строку. Посмотрите эту статью, там в начале расписан этот автомат (секции перфикс функция - атомат КМП).

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

Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины n пройдет через конечное состояние ровно один раз. Для этого подсчитайте 2 вероятности: что путь из начала длины k дойдет до конечного состояния один раз, и что путь из конечного состояния длины n-k не вернется в него.

Обе эти вероятности можно подсчитать динамическим программированием:
P1(i, k) - вероятность того, что путь начиная с состояния i (i < n) за k шагов дойдет до состояния n первый раз. Это просто сумма по всем возможным переходам:

P1(i, k) = sum_{c - все символы} P1(next(i, c), k-1) * p(c)

База:

P1(m, 0) = 1
P1(m, k>0) = 0
P1(i < m, 0) = 0

Вторая вероятность: сделать k шаговиз состояния i и ни разу не войти в конечное состояние:

P2(i, k) = sum_{c - все символы, next(i,c) < m} P2(next(i, c), k-1) * p(c)

База:
P1(i, 0) = 1

Ответ к задаче - сумма по всем возможным длинам первой части пути:
sum_{k=m..n} P1(0, k) * P2(m, n-k)

Это решение через динамическое программирование будет O(n*m) по вермени и по памяти.

Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.

<select onchange='findOption(this)'>
   <option value='one'>1</option>
   <option value='two'>2</option>
   <option value='three'>3</option>
</select>

function findOption(select) {
   const option = select.querySelector(`option[value="${select.value}"]`)
   // Действия над option
}

import telebot
import requests

token = 'Токен'
bot = telebot.TeleBot(token)

@bot.message_handler(content_types=['voice','text'])
def repeat_all_message(message):
	file_info = bot.get_file(message.voice.file_id)
	file = requests.get('https://api.telegram.org/file/bot{0}/{1}'.format(token, file_info.file_path))

	with open('voice.ogg','wb') as f:
		f.write(file.content)

if __name__ == '__main__':
    bot.polling(none_stop=True)

Самый простой код. Он получает от пользователя голосовое сообщение и сохраняет в папку бота, с именем voice.ogg.
Здесь все записи перезаписываются в один файл. Так что создавайте директорию, в качестве имени указывайте id пользователя. И сохраняйте туда файлы. Думаю, разберетесь.

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

Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

Постройте граф. Вершины в графе - вершины полигонов, боты и игрок. Для каждой вершины и другого полигона найдите 2 касательные с точки на полигон - можно перебрать все отрезки из вершины на другой полигон и отбросить те, относительно которых 2 стороны второго многоугольника лежат по разные стороны. Также все эти касательные проверьте на пересечение со всеми остальными полигонами и удалите те, которые пересекаются (проверьте каждую сторону полигона, и пересеките сторону с известным отрезком-касательной).

Теперь у вас остались только касательные, по которым имеет смысл ходить. Добвьте их в граф (длины ребер равны длине отрезков).
Также добавьте в граф все ребра многоугольников. Все кратчайшие пути мужду всеми точкаим идут в этом графе. Вы или идете вдоль полигона, или идете из текущей точки по касательной к какому-то полигону. Очевидно, что это любой другой путь можно улучшать, пока он не станет состоять из этих кусков.

Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

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

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

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.

точное время выполнения одного вызова функции получить довольно сложно.

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

поэтому правильно вызывать функцию много раз и считать среднее.
так же в ноде есть process.hrtime которая дает наносекунды.

оба этих метода "в лоб" не дадут нормального результата. Почему? потому что в реальности происходит много всего интересного при выполнении кода.

в движке есть неимоверное количество оптимизаций, и функция вызванная 10 раз будет иметь совершенно другой код чем функция вызванная 100 раз. То же касается и типов параметров - например вы можете передавать целые или дробные числа.
На одну вашу написанную js-функцию движок сгенерирует несколько функций которые это реализуют. У этих функций может быть совершенно разный код с разной произодительностью.

Переключение происходит на лету и в общем виде вы не знаете когда это происходит.

поэтому само по себе замерение скорости "функции" имеет мало смысла, так как там их несколько внутри. Если интересны детали - погуглите JIT, AOT и v8 optimizations.
Сейчас важно то что есть "холодные" функции которые работают медленее но надеждее и как правило используются сразу и есть "горячие" варианты, которые компилятор начинает использовать когда видит что код вызван много раз, и условия не меняются. "Горячие" работают быстрее.

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

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

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

И тут самый главный момент - даже если вы замерите эту скорость, что вы будете делать с этим знанием? В реальной программе при выполнении этого кода скорость может быть совсем не такая как вы намеряли. Эти тесты годятся только для своего общего развития

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

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

Думаю придется переписать на webGL. Проще всего с использованием PIXIJS, для него есть готовый фильтр motion blur https://pixijs.io/pixi-filters/tools/demo/