AT
на емаксе есть пример для 2д, он легко до 3д дополняется
но я не уверен, можно ли будет максимум сделать
но я не уверен, можно ли будет максимум сделать
спасибо
Size: a a a
2020 September 28
AT
Вас дерево отрезков деревьев отрезков не устроит?
не знаю
AT
На емаксе есть пример
спасибо
AT
Вас дерево отрезков деревьев отрезков не устроит?
по идее просто дерево отрезков, если упорядочивать по индексу для z-order curve, подойдёт
2020 September 29
q
Можно первые два слагаемых оставить
почему кст? в некоторых книжках пишут, в некоторых опускают
EZ
почему кст? в некоторых книжках пишут, в некоторых опускают
Ну по определению О(nlogn+n)=O(nlogn)
S
/report
2020 October 03
AT
Как задетектировать зацикливание в программе. Ограничение на размер цикла - S последовательных состояний. Могу получить хеш состояния. Пока придумал только создавать trie хешей и детектировать по превышению макс глубины. Это требует трекинга S указателей на ноды каждую итерацию и рост на S нод.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
AT
Состояния связаны и повторение двух подряд хешей почти наверняка означает зацикливание. Можно наверное сохранять пары и номер итерации. Когда встретится тройка пар, отстоящих через один и тот же интервал, то можно уже делать более ресурсозатратную проверку. Ведь так?
AT
Можно ещё хеши в хешмапу ограниченного размера записывать, а самый старый удалять и после того, как размер стал сокращаться и стабилизировался на каком-то значении, можно заключить, что произошло зацикливание
K
Как задетектировать зацикливание в программе. Ограничение на размер цикла - S последовательных состояний. Могу получить хеш состояния. Пока придумал только создавать trie хешей и детектировать по превышению макс глубины. Это требует трекинга S указателей на ноды каждую итерацию и рост на S нод.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
Ну, храните хэш стартового состояния, если за S+1 шагов в него не пришли - обновляйте на хэш текущего
AT
Тоже вариант
M
Как задетектировать зацикливание в программе. Ограничение на размер цикла - S последовательных состояний. Могу получить хеш состояния. Пока придумал только создавать trie хешей и детектировать по превышению макс глубины. Это требует трекинга S указателей на ноды каждую итерацию и рост на S нод.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
статически или динамически? Если статически то это не всегда разрешимая задача, а вообще этим занимается reachability analysis и это довольно сложная тема для общего случая (для тривиальных програм возможно и простая). Если же динамически (в рантайме) довольно просто, достаточно хранить мета-состояние цикла и каждую итерацию сверять текущее состояние с предыдущим, если оно вдруг стало одинаковым - у нас бесконечный цикл
M
Вот один из пример динамического детектора
https://groups.csail.mit.edu/pac/jolt/paper.pdf
https://groups.csail.mit.edu/pac/jolt/paper.pdf
A
Как задетектировать зацикливание в программе. Ограничение на размер цикла - S последовательных состояний. Могу получить хеш состояния. Пока придумал только создавать trie хешей и детектировать по превышению макс глубины. Это требует трекинга S указателей на ноды каждую итерацию и рост на S нод.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
Можно ли что-нибудь придумать здесь? Допустим можно задетектировать не сразу, а с опозданием на M циклов.
заяц и черепаха?
A
статически или динамически? Если статически то это не всегда разрешимая задача, а вообще этим занимается reachability analysis и это довольно сложная тема для общего случая (для тривиальных програм возможно и простая). Если же динамически (в рантайме) довольно просто, достаточно хранить мета-состояние цикла и каждую итерацию сверять текущее состояние с предыдущим, если оно вдруг стало одинаковым - у нас бесконечный цикл
а если зацикливается с периодом 2? просто сравнения с предыдущим не хватит
M
а если зацикливается с периодом 2? просто сравнения с предыдущим не хватит
Чир значит 2? Шаг у периода итерации может быть любой, это никак не влияет на описанный принцип
A
Ну вот находимся мы в состоянии b, предыдущее -- a. Все ок. Перешли в a -- предыдущее b. Все ок. Перешли в b -- предыдущее a. Все ок, продолжаем. А цикл-то есть на самом деле
A
Может я просто не понял, что мы храним
@N
Ну, храните хэш стартового состояния, если за S+1 шагов в него не пришли - обновляйте на хэш текущего
Цикл может далеко не с первого состояния начаться