Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | | | | | | | | | |
Опасения...Сняты ! 12.04.02 02:31 Число просмотров: 929
Автор: Chingachguk <Chingachguk> Статус: Member
|
Да, если наблюдается зацикливание - повторение с каким-то шагом матриц- то и переодичность сумм должна быть !
Все-ж таки я не пойму, отчего это происходит - такое впечатление, что вся система стремиться в конце-концов разбиться на набор независимых сегментов(из которых не уходят точки, и в которые не приходят), а внутри этих сегментов происходит циклическое эволюционирование - причем вариантов таких сегментов не так много ...
Может, проще пытаться найти картинки таких "сегментов" и просто при очередном шаге проверять их наличие во всей матрице ? Сегменты должны быть(по идее) симметричны относительно обеих осей...
|
|
<programming>
|
Поиск периодичности... 01.04.02 22:45
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
Есть двумерный массив "битов" и процедура его преобразующая (если кто знает-"игра жизнь Конуэя") - некоторые 0 в 1 и наоборот... и так в бесконечном цикле. Хотелось бы прервать цикл при повторении полученных ранее данных (весь массив будет менятся по циклу что не есть интересно :).
Пробовал вычислять сумму элементов и если она не меняется/меняется не более чем на N в течение M преобразований обрывал цикл. Но иногда этот метод не срабатывает.
Кто-нибудь знает способ, не сильно понижающий производительность, обнаружить такое безобразие :) ?
Кстати есть еще вариант когда массив повторит не себя а "параллельный" ему :) т.е.
1 2 3 5 6 4
4 5 6 и 8 9 7 - параллельные массивы целых чисел:))
7 8 9 2 3 1
P.S. пишу эту вещь для себя 8)
|
|
Поиск периодичности... 05.04.02 22:47
Автор: vagrant Статус: Незарегистрированный пользователь
|
Мне кажется идентифицировать массивы удобнее просто суммой занятых ячеек.
Конечно каждой сумме соответствует много кофигураций, но последовательность
массивов с совпадающими суммами маловероятна. Но это и не главное. По
настоящему важно лишь то, насколько трудоемко получение очередного ряда
конфигураций.
Если ряд генерируется относительно быстро, то проще всего считать
автокорреляционную функцию для этих сумм. Только нужно выбрать подходящий
интервал, который зависит от длины максимального интересующего Вас периода
повторений. Т.к. периоды эти коротки - не более нескольких десятков - то
сгенерировать с полсотни периодов не проблема. А на них корреляция,
сигнализирующая о повторе, видна со 100% надежностью. Останется только
повторить генерацию с начального массива или с какой-нибудь контрольной
точки, что разумнее.
А вот если ряд генерируется долго, скажем несколько дней, тогда лишний счет
поперек горла. Но другого пути нет. Автокорреляции в этом смысле средство
классическое.
|
|
А инженерный вариант пойдет ? ;) 02.04.02 11:07
Автор: PS <PS> Статус: Elderman
|
В смысле не научный...
проверять повторы в другом потоке.
Если массивы большие, то в качестве данных для хистори можно хранить md5 или CRC. паралельный поток будет просматривать хистори и при обнаружени повторов нотифицировать основной поток, что ему пора завершаться.
> Есть двумерный массив "битов" и процедура его преобразующая
> (если кто знает-"игра жизнь Конуэя") - некоторые 0 в 1 и
> наоборот... и так в бесконечном цикле. Хотелось бы прервать
> цикл при повторении полученных ранее данных (весь массив
> будет менятся по циклу что не есть интересно :).
> Пробовал вычислять сумму элементов и если она не
> меняется/меняется не более чем на N в течение M
> преобразований обрывал цикл. Но иногда этот метод не
> срабатывает.
> Кто-нибудь знает способ, не сильно понижающий
> производительность, обнаружить такое безобразие :) ?
> Кстати есть еще вариант когда массив повторит не себя а
> "параллельный" ему :) т.е.
> 1 2 3 5 6 4
> 4 5 6 и 8 9 7 - параллельные массивы
> целых чисел:))
> 7 8 9 2 3 1
>
> P.S. пишу эту вещь для себя 8)
|
|
Поиск периодичности... 02.04.02 10:53
Автор: ukv Статус: Незарегистрированный пользователь
|
Насколько я помню "Life", массив в основном будет состоять из нулей. Так что побайтовое сравнение не эффективно. Лучше считать 32-х разрядную CRC, и в последовательности CRC уже искать повторы. Стандартный метод поиска циклов неизвестной длины в подобной последовательности - с помощью двух указателей. Первый указатель сдвигается на следующий элемент каждый шаг, другой указатель сдвигается каждый второй шаг. Недостатки этого метода в данном случае - необходимость хранить как минимум половину последовательности CRC, и для выявления периодичности требуется сделать столько же шагов, что и для получения первой повторяющейся позиции. Кроме того, в силу специфики задачи желательно проверять наиболее распространенные условия прекращения эволюции - стабильные конфигурации и "моргалки" с периодом 2. Плюс к тому, нужно все же проверять, что одинаковым CRC действительно соответствуют одинаковые массивы.
Что же касается выявления движущихся конфигураций ("планеров") - тут нужна линейная операция над элементами массива - XOR или сложение, ничего лучше наверное придумать нельзя. Вопрос только в том, сколько разрядов должно быть в контрольной сумме. При 8 разрядах - велика вероятность ложных совпадений, при 16 и больше - нужно достаточно большое поле (планер будет выявлен при сдвиге на 16 клеток).
А как проверять, что при совпадении контрольной суммы в массиве действительно только "блоки", "моргалки" и "планеры" - это уже отдельная тема.
|
| |
ИМХО, черную кошку в темной комнате... 02.04.02 11:55
Автор: Zef <Alloo Zef> Статус: Elderman
|
Сигнатуры - хорошо, ни имейте ввиду, что одной сигнатуре может соответствовать МНОГО РАЗНЫХ последовательностей (число возможных последовательностей / число возможных сверток).
Единственно, чего можно добиться, подбирая полином, это апериодичности повторений при равномерном их распределении и максимализации отличия сигнатуры при минимальных различиях последовательностей.
Для начала нужно проверять совпадение 1й и N-ной последовательностей.
Дальше: правильно ли я понял, что совпаение 1й и N-ной последовательности означает совпадение всех промежуточных?
Если означает, то болше нихрена и не нужно.
Если нет - тада нужно запомнить все сигнатуры с 1й по N-ную и ждать еще цикл, сличая их по очереди, но такой подход будет только вероятностным. (хотя совпадение сигнатур двух разных "суперпоследовательностей" сверхневероятно).
|
|
поправка... 01.04.02 22:48
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
> 1 2 3 5 6 4
> 4 5 6 и 8 9 7 - параллельные массивы
> целых чисел:))
> 7 8 9 2 3 1
что-то скрипт глючит; массивы:
1,2,3__________5,6,4
4,5,6____и_____8,9,7
7,8,9__________2,3,1
P.P.S. если не туда попал, киньте ссылку на нужный форум :)
|
| |
поправка... 02.04.02 01:41
Автор: SEH Статус: Незарегистрированный пользователь
|
Если я правильно понял, то все происходит в цикле. Так почему не завести переменную, отвечающую за то, что произошло изменение. Вроде того:
bool is_changed = true;
while ( is_changed )
{
is_changed = false;
if ( /*...Необходимо изменение...*/ )
{
...Изменение...
is_changed = true;
}
}
|
| | |
А почему не так: 02.04.02 04:14
Автор: Zef <Alloo Zef> Статус: Elderman
|
сравниваешь 1е байты, если совпало (только!) 2е, потом так же 3и, и так до конца, при первом же несовпадении "отпускаешь" массив, чтобы он преобразовался в очередной раз.
Надежность 100%.
Быстродействие: по твоему методу ты каждый раз вычисляешь CRC всех байт. Здесь сравниваешь только 1. это уже выигрыш во столько раз, сколько байт в массиве. Вся остальная бодяга срабатывает 1 раз из 256. Если у тебя не сохраняется предыдущий массив, то ведь скопировать его быстрее, чем посчитать сумму.
|
| | | |
поиск продолжается... 02.04.02 22:19
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
Даже не ожидал столько ответов...
-По поводу несколькие потоков - желательно, чтоб под ДОС работало...да и синхронизация потребуется...и вообще не верю в "многозадачность" виндов :)
-По поводу хранения старого массива. Конечно вариант, но все-таки очень неэкономно по отношению к памяти, ну и опять же как часто его обновлять, хотя..
А вообще можно сделать многоуровневую проверку: сначала слабенький анализ CRC(н.р. CRC меняется 100 ходов не более чем на 3) если есть подозрения на повтор поискать периодичность CRC с периодом ~15-20 ходов ну и под конец проверить периодичность сравнением массива. Где-нибудь посередине можно добавить CRC но для нескольких случайных или неслучайных подмассивов.
По поводу планеров мигалок и прочего - не думаю, что это будет легко обнаружить.
Кстати, а что, если "обрубать" ту часть массива, где не исчезали и не появлялись организмы- ведь "скорость распространения изменения не больше ячейки за ход"- во как сказал :) И сразу же вопрос как это лучше сделать на массиве-бублике (склеены боковые края, а также верхний и нижний край)? Может поиском неизменных подряд идущих столбцов/строк?
Ну и еще вопрос напоследок: быстро ли копируются статические и динамические массивы, быстро ли выделяется память под динамические, есть ли вообще между ними разница в скорости работы?
На этом пока все, печатать уже устал :)
|
| | | | |
динамические массивы 03.04.02 04:29
Автор: Zef <Alloo Zef> Статус: Elderman
|
Если массивы объявлены заранее - разницы нет, если по ходу, то естессно на это требуется время (сколько - зависит от платформы и менеджера памяти) наихудший вариант - переполнение MFC-евого массива - объекта, т.к. в этом случае при добавлении каждого нового элемента выделяет новый массив на 1 длиннее, копирует в него предыдущий, а старый пришибает.
И я все-таки не понял: похоже ты считаешь, что нужно сравнивать любой массив с любым? Подумай: достаточно сравнить любой массив с первым! (и только тогда сравнивать остальные, если это важно)
|
| | | | | |
динамические массивы 03.04.02 14:43
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
> И я все-таки не понял: похоже ты считаешь, что нужно
> сравнивать любой массив с любым? Подумай: достаточно
> сравнить любой массив с первым! (и только тогда сравнивать
> остальные, если это важно)
Дело в том, что в общем случае (случайно заполненный массив) начальный массив может повторится с ОЧЕНЬ маленькой вероятностью. Почти всегда через несколько сотен/тысяч/... ходов массив начинает повторятся с периодом в пределах 20 (обычно меньше 6) ходов.
|
| | | | | | |
Период устанавливается не сразу? Предупреждать надо... 04.04.02 04:49
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
|
| | | | | | |
И еще такой вариант... 03.04.02 23:24
Автор: Chingachguk <Chingachguk> Статус: Member
|
|
Запоминаем начальное состояние. Каждый раз, когда мы переходим от состояния N к N+1, проигрываем от начального состояния все переходы: 1->2->..->N и каждое такое полученное состояние сравниваем с новым, N+1-м.
|
| | | | | | | |
Классный вариант... 04.04.02 14:07
Автор: PS <PS> Статус: Elderman
|
> Запоминаем начальное состояние. Каждый раз, когда мы
> переходим от состояния N к N+1, проигрываем от начального
> состояния все переходы: 1->2->..->N и каждое такое
> полученное состояние сравниваем с новым, N+1-м.
Т.е. у нас 1000 переходов. Мы переходим с 1 на 2, сравниваем, идем дальше. с 2 на 3. Теперь Запускаем переход с 1 на 2... Переходим с 5 на 6. Проигрываем ЗАНОВО 1-2, 2-3, 3-4
Ох я в камбинаторике не силен, а то бы громадную цифру привел, а всего то надо было 1000 переходов сделать.
И чего тут думать ? Это же обычный конечный автомат, состояния могут повторятся. Единственный способ узнать вернулись ли мы уже на прошедшее состояние - это запоминать их.
|
| | | | | | |
Аналитическое описание ? 03.04.02 20:23
Автор: Chingachguk <Chingachguk> Статус: Member
|
> Дело в том, что в общем случае (случайно заполненный
> массив) начальный массив может повторится с ОЧЕНЬ маленькой
> вероятностью. Почти всегда через несколько сотен/тысяч/...
> ходов массив начинает повторятся с периодом в пределах 20
> (обычно меньше 6) ходов.
Если не трудно, напиши, в чем алгоритм эволюции массива.
А нельзя ли аналитически описывать его развитие и предсказывать(вычислять) однозначно, когда массив воспроизведется опять ? ;)
|
| | | | | | | |
Алгоритм эволюции: 04.04.02 22:05
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
> Если не трудно, напиши, в чем алгоритм эволюции массива.
Переход N->N+1 осуществляется так(напомню,что массив состоит из нулей и единиц):
- Единичка остается в массиве, если у нее ровно 2 или ровно 3 соседних единички(всего соседей 8), иначе она переходит в ноль.
- Если у нолика ровно 3 соседних единицы, то он заменяется на единицу, иначе он не меняется
-детали програмной реализации опустим(тем более, что поиск периодичности еще не осуществлен), хотя если очень надо, могу запостить или выслать исходник на Паскале
Примечание: количество соседей - это количество соседей на шаге N а не в процессе преобразования массива; в моем случае клетка с правого края массива имеет 3 соседей с левого края (массив склеен по краям) аналогично для верхнего, нижнего и левого краев.
Так как переход однозначен и определяет только массивом на данном шаге, то если он один раз повторится то он будет повторяться бесконечно много раз :)
> А нельзя ли аналитически описывать его развитие и
> предсказывать(вычислять) однозначно, когда массив
> воспроизведется опять ? ;)
Надеюсь, что это можно можно предсказать ;) думаю, что для произвольного массива это непросто сделать, но если кто знает как-обязательно напишите
После многих наблюдений(массив random-ом) я обнаружил, что почти всегда массив рано или поздно начинает повторятся с периодом 2 шага. Кто может объяснить почему, жду соображений. Может кто придумает массив, который повторяется с другим периодом(для знающих- не из космических кораблей или планеров)
P.S. планер выглядит так:
010
001
111
примечателен тем,что через 4 хода сдвигается на одну клетку вправо и на одну вниз
космические корабли имеют вид:
00010
00001
10001
01111
данный сдвигается на 2 клетки вправо за 4 хода
0000010
0000001
1000001
0111111
этот движется также; при движении таких кораблей образется "мусор" в виде нескольких единиц , который живет лишь один ход и исчезает; кстати это все выполнено для массивов размером не меньше чем где-то 10x12
|
| | | | | | | | |
Алгоритм эволюции: Дык это алгоритм "Жизнь" ;) 05.04.02 02:31
Автор: Chingachguk <Chingachguk> Статус: Member
Отредактировано 05.04.02 02:36 Количество правок: 1
|
> > Если не трудно, напиши, в чем алгоритм эволюции
Спасибо, я понял. Это вроде алгоритма "Жизнь" - я как-то даже делал прогу такую - экран заселяется точками и выполняются с каждой точкой те преобразования, о которых ты гришь - именно для фиксированного состояния всех точек - на экране типа бактерий таких что-то движется ;)
По нему даже конкурс проводили - кто меньше на асме напишет такую прогу...
Пожалуй, трудновато будет предсказать аналитически, когда кадры начнут повторяться...
ЗЫ А чем тебе мой алгоритм проверки повторяемости не подошел(в этой нитке я его написал) ? - когда запоминаем первое состояние и каждый раз прокручиваем эволюцию до состояния текущее - 1 и сверяемся с ними ? Долго, что-ли ? Так можно не проверять на каждом N-ом шаге все N-1 состояний, а, как тут уже предлагали, хранить типа CRC[1]..CRC[N-1] и только в том случае, если совпали CRCN и, скажем, CRC[J], прокрутить до J-го состояния(получить его еще раз) и сравнить.
|
| | | | | | | | | |
Да это алгоритм "Жизнь"-читай начало нити ;) 05.04.02 23:00
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
|
|
| | | | | | | | | |
Итого: 05.04.02 22:55
Автор: Dmitry Ivankov[HackZone Ural] Статус: Незарегистрированный пользователь
|
> ЗЫ А чем тебе мой алгоритм проверки повторяемости не
> подошел(в этой нитке я его написал) ? - когда запоминаем
> первое состояние и каждый раз прокручиваем эволюцию до
> состояния текущее - 1 и сверяемся с ними ? Долго, что-ли ?
> Так можно не проверять на каждом N-ом шаге все N-1
> состояний, а, как тут уже предлагали, хранить типа
> CRC[1]..CRC[N-1] и только в том случае, если совпали CRCN
> и, скажем, CRC[J], прокрутить до J-го состояния(получить
> его еще раз) и сравнить.
Да, пока что кардинально другого варианта не нашлось. Еще подожду и если не будет других вариантов реализую этот.
Прием вариантов - до последнего сообщения в нитке :)
P.S. Экономнее будет при совпадении CRC[J] и CRC[N] запомнить массив и подождать N-J шагов и сравнить, так как повторная прокрутка может занять много времени; а также хранить не все CRC а лишь последние (н.р. 100 последних)
Но для такого варианта будет медленно работать вот такой случай: массив практически полностью состоит из устойчивых конфигураций(они не меняются) и в нем есть достаточно свободного пространства, в котором находится планер-каждые 4 хода планер сдвигается на одну клетку по диагонали, все остальное неизменно=> CRC повторяется каждые 4 хода=> каждые 4 хода будет сравниватся массив, а до периодичности еще может быть очень много ходов(не раньше, чем планер долетит до устойчивых конфигураций).
Как с этим бороться, пока не знаю. Может хранить CRC отдельно четных, отдельно нечетных строк, и может аналогично для столбцов? или даже CRC всего, CRC каждой второй, каждой третьей, пятой, седьмой,.. строки/столбца, сколько именно-экспериментально узнать.
Какие есть соображения по этой проблеме?
|
| | | | | | | | | | |
Итого: 08.04.02 02:58
Автор: vagrant Статус: Незарегистрированный пользователь
|
|
Боюсь мой совет остался незамеченным, благо я его нагло вставил в начало нити.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
