Форум Flasher.ru

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)
-   ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)
-   -   скорость циклических проверок (http://www.flasher.ru/forum/showthread.php?t=212580)

a7s1h1 17.03.2016 13:17

алгоритм расстановки случайных чисел в одномерном массиве с условиями
 
Здравствуйте!
Пытаюсь разработать алгоритм расстановки случайных чисел в одномерном массиве, ограниченной определёнными условиями. Планировал делать это простым перебором:
1. Присваиваю ячейке случайное число, чтобы проверить, подходит ли оно
2. Проверяю условия (в-основном, это сравнение с другими ячейками)
3. Если условие выполняется - перехожу к следующему условию. Если не выполняется, уменьшаю число на 1 и повторяю проверку всех условий с самого начала
4. Если все условия выполнились, ставлю триггер успеха проверки и перехожу к следующей ячейке.

Однако прежде, чем вставлять какие-то условия, я решил на примитивном примере оценить быстродействие такой схемы:
Код AS3:

var ok:Boolean = false
trace('ok='+ok)
var n:uint = 100;
while (!ok) {
        trace('n='+n)
        if (n > 0) {
                n--
        } else {
                ok=true
        }
}
trace('ok='+ok)

Тут единственное условие, чтобы n было не больше 0. Если условие не выполняется, уменьшаем n на 1 и повторяем проверку. Получается "Число 100 равно нулю? Нет? А 99? Нет? А 98?", и т.д. В итоге получается 100 проверок.
Казалось бы, элементарные вычисления (проверок 100, но условие всего одно), но каждый раз, когда они происходят, игра зависает на пару секунд.
Объясните, пожалуйста, почему так, и какой способ циклической проверки будет более эффективен? Заранее спасибо!

caseyryan 17.03.2016 13:20

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

Не нужно делать циклы типа while(!ok). В as3 все выполняется в одном потоке и циклы не исключение. Подобное условие может либо очень долго не выполниться, либо вообще не выполниться. Зависание в этом случае гарантировано. Циклы нужно ограничивать в количестве итераций.
Но конкретно об этом цикле, я сомневаюсь, что из-за него игра зависает на пару секунд. Это просто невозможно. 100 простых итераций он отработает мгновенно. Явно дело в чем-то другом.

a7s1h1 17.03.2016 13:24

Цитата:

Сообщение от caseyryan (Сообщение 1192699)
Здесь на форуме есть теги AS3 подсветки, нужно пользоваться ими для оформления своего кода. Такой одноцветный код даже читать не охото.

Прошу прощения, не обращал внимания на этот тег. Исправил

caseyryan 17.03.2016 13:25

дополнил свой ответ

a7s1h1 17.03.2016 13:39

Цитата:

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

Я стараюсь по возможности избегать while, просто решил проверить. Действительно, попереставлял этот кусок кода в разные места, иногда тормозит, иногда нет.

Тем не менее, остаётся вопрос: какой алгоритм использовать для расстановки случайных чисел (допустим, от 0 до 9) в одномерном массиве длиной в 8 ячеек, со следующими ограничениями:
- не больше 6 чисел, отличных от 0;
- не больше 4 одинаковых чисел;
- не больше 2 одинаковых числе подряд.
Мне на ум приходит 2 варианта:
1. Присваивать по-очереди каждой ячейке случайное число и проверять, подходит ли оно, уменьшая на 1 в случае неудачи, вплоть до 0;
2. Присвоить случайные числа сразу всем ячейкам, затем проверять условия сразу по всем и, если где-то косяк, присвоить новую комбинацию - и так до тех пор, пока комбинация не окажется удачной.
Какой подход лучше: 1, 2 или есть другие?

Wolsh 17.03.2016 13:54

У Вас всего 6 ячеек, на которые 9 цифр (1..9). Так что пункты 2 и 3 можно вообще откинуть и использовать ВСЕ разные цифры по одной (кроме заранее забитых двух нулей).
Создаете массив [1, 2, 3, 4, 5, 6, 7, 8, 9], это будет массив-"пул", из которого Вы просто дергаете по рандомному индексу число (удаляете его из пула!) и добавляете в свой массив блоков. Затем рандомно вставляете два нолика.

a7s1h1 17.03.2016 14:02

Цитата:

Сообщение от Wolsh (Сообщение 1192711)
использовать ВСЕ разные цифры по одной (кроме заранее забитых двух нулей)

так не пойдёт, нужно, чтобы цифры могли повторяться (но не более 2х подряд и не более 4 одинаковых)

Wolsh 17.03.2016 15:11

"не более 4 одинаковых" — добавляйте в пул по 4 одинаковых.
"не более 2х подряд" — Узнать, что две предыдущие равны добавляемой не проблема. Проверяете последнюю в блоках, если равна то проверяете предыдущую. Последнюю можно даже хранить в переменной чтоб "далеко не ходить". Это поможет также избежать лишнего повтора на стыках "волн".

a7s1h1 17.03.2016 18:28

Попробовал сделать, как вы сказали.
Напоминаю условия:
- массив из 10 ячеек необходимо заполнить случайными цифрами от 0 до 9 с соблюдением ряда условий
- первая и последняя ячейка всегда 0
- максимальное количество не нолей - 6
- максимальная цифра известна заранее
- максимальное количество одинаковых цифр: единиц, двоек, троек по 4, 4-6 максимум по 3, 7-8 максимум по 2, девятка только одна
- максимальное количество одинаковых цифр подряд - 2

Вот что получилось:
Код AS3:

var max_level:uint = 9; // максимальная цифра - пусть сейчас это будет 9
 
// вектор, который необходимо заполнить. Заполняем его нулями
var temp_vector:Vector.<uint> = new < uint > [0,0,0,0,0,0,0,0,0,0];
 
// если максимальный уровень = 0, то ничего не проверяем, везде остаются нули
if (max_level > 0) {
        // создаём мешок с цифрами, откуда будем их вытаскивать
        var bag:Vector.<uint>;
        // в мешок суём все цифры до максимальной
        // количество каждой цифы ставим максимальное (т.к. из 10 ячеек первая и последняя точно нули, то будем проверять только 8 ячеек, соответственно суём в мешок максимально возможное количество каждой цифры: 8 нолей, остальные смотря по цифре)
        switch (max_level) {
                case 1: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1]; break; //1 не более 4
                case 2: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2]; break; //2 не более 4
                case 3: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3]; break; //3 не более 4
                case 4: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4]; break; //4 не более 3
                case 5: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5]; break; //5 не более 3
                case 6: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6]; break; //6 не более 3
                case 7: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7]; break;                //7 не более 2
                case 8: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8]; break;        //8 не более 2
                case 9: bag=new <uint>[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8,9]; break;        //9 не более 1
        }
 
        var testee:uint=0;        // проверяемая цифра
        var previous1:uint = 0; // предыдущая цифра
        var previous2:uint = 0; // предпредыдущая цифра
        var tvl:int = temp_vector.length; // длина временного вектора для ссылки в цикле
 
 
 
        // перебор каждой ячейки, кроме первой и последней (получается 8)
        for (var i:int = 1; i < tvl - 1; i++) {
                var bag_length:uint = bag.length; // длина мешка для ссылки в цикле
                // достаём из мешка случайную цифру, пока не выпадет та, которая не совпадает с предыдущими двумя
                while (testee == previous1) {
                        testee = bag[MyMath.randomRange(0, bag_length - 1)]
                        if (testee != previous2) {break        }
                }
 
                // найдя подходящую цифру,
                temp_vector[i] = testee; // заносим её в соответствующую ячейку временного вектора
                previous2 = previous1; // записываем предыдущие цифры
                previous1 = testee; // записываем предыдущие цифры
                bag.splice(i, 1); // удаляем выбранную цифру из мешка
        }
}
//проверяем, что получилось
trace('temp_vector='+temp_vector)

Код работает, как надо, только есть две проблемы:
1. Выглядит не очень, поможете оптимизировать?
2. Не соблюдается правило "не больше 6 цифр, отличных от нуля". В какой момент и как
Цитата:

Сообщение от Wolsh (Сообщение 1192711)
рандомно вставляете два нолика.

, пока не смекнул:( Подскажите, пожалуйста

Wolsh 17.03.2016 22:09

1. Конечно. Надо взять только последний, самый длинный вариант bag. А вот чтобы не брать из него дальше нужного индекса, надо всего-лишь ограничить рандом не реальной длиной массива, а максимальным для данного левела индексом (для первого — 11, для второго — 15 и тд.). Ах да, тогда придется с каждым вынутым числом менять и максимум(( Не очень красиво наверно)))
2. "Не больше шести..." — так если Вы будете брать из мешка всего шесть чисел, включая ноли, то "ненолей" больше шести никак и не получится. Берете шесть чисел из мешка, а ПОТОМ вставляете еще два ноля в рандомные индексы от 2 до 7 (чтобы не касались нолей по краям массива). И так у Вас в массиве будет минимум 4 ноля и максимум 6 ненолей.

a7s1h1 18.03.2016 01:01

Цитата:

Сообщение от Wolsh (Сообщение 1192749)
если Вы будете брать из мешка всего шесть чисел, включая ноли, то "ненолей" больше шести никак и не получится. Берете шесть чисел из мешка, а ПОТОМ вставляете еще два ноля в рандомные индексы от 2 до 7 (чтобы не касались нолей по краям массива).

Во время перебора ячеек в цикле приходится проверять предыдущие, из-за чего ячейки проверяются по-очереди. С таким подходом приходится брать из мешка все 8, т.к. если брать 6, то два нуля окажутся с краю.
Что, если сделать так: после того, как массив сформирован, пройтись по нему ещё раз, посчитать нули и, если их окажется меньше, чем нужно, заменить нулями произвольные цифры в массиве?

По остальным замечаниям исправляю

UPD: А, понял, как сделать, сейчас поменяю

Добавлено через 1 час 1 минуту
Большое спасибо, всё работает! Получилось вот что:
Код AS3:

// максимальная цифра
                        var max_level:uint=MyMath.randomRange(0,9);
 
                        // вектор для вычислений из 8 ячеек (крайние останутся нулями, а ещё 2 ноля добавим потом)
                        var temp_vector:Vector.<uint> = new < uint > [0,0,0,0,0,0,0,0];
 
                        // если максимальная цифра = 0, то ничего не проверяем
                        if (max_level > 0) {
                                // создаём мешок с цифрами, откуда будем их тянуть (rjkbxtcndj одинаковых цифр в мешке означает их максимально допустимое количество в итоговом массиве)
                                var bag:Vector.<uint> = new <uint>[0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,5,5,5,6,6,6,7,7,8,8,9];
                                var max_bag_index:uint; // максимальный индекс в мешке
                                // количество элементов мешка, которое мы будем проверять, зависит от максимальной цифры
                                switch (max_level) {
                                        case 1: max_bag_index = 9; break; // 1 не более 4 [0,0,0,0,0,0,1,1,1,1]
                                        case 2: max_bag_index = 13; break; // 2 не более 4
                                        case 3: max_bag_index = 17; break; // 3 не более 4
                                        case 4: max_bag_index = 20; break; // 4 не более 3
                                        case 5: max_bag_index = 23; break; // 5 не более 3
                                        case 6: max_bag_index = 26; break; // 6 не более 3
                                        case 7: max_bag_index = 28; break; // 7 не более 2
                                        case 8: max_bag_index = 30; break; // 8 не более 2
                                        case 9: max_bag_index = 31; break; // 9 не более 1
                                }
 
                                var testee:uint=0;        // проверяемая цифра
                                var previous1:uint = 0; // предыдущая цифра
                                var previous2:uint = 0; // препредыдущая цифра
                                var tvl:int = temp_vector.length; // длина временного вектора для ссылки в цикле
 
                                // перебор каждой ячейки, кроме первой (0) и последней(7) (получается 6)
                                for (var i:int = 1; i < tvl - 1; i++) {
                                        var ind:uint = MyMath.randomRange(0, max_bag_index); // выбираем случайную ячейку мешка
                                        testee = bag[ind]; // переносим цифру из случайной ячейки мешка  в переменную для проверки
 
                                        // если выбранное число совпадает с предыдущим
                                        while (testee == previous1) {
                                                // если при этом совпадает ещё и с предпредыдущим - ищем в мешке другое число, пока не найдём такое, которое повторяло бы одновременно 2 предыдущих цифры
                                                if (testee == previous2) {
                                                        ind = MyMath.randomRange(0, max_bag_index); // повторяем вытягивание цифры из мешка
                                                        testee = bag[ind]
                                                } else {
                                                        break
                                                }
                                        }
 
                                        // найдя подходящую цифру, заносим её в соответствую ячейку вектора , записываем предыдущие цифры и удаляем выбранную из мешка
                                        temp_vector[i] = testee; // найдя подходящую цифру, заносим её в соответствую ячейку вектора
                                        previous2 = previous1; // записываем предыдущие цифры
                                        previous1 = testee;
                                        bag.splice(ind, 1); // удаляем из мешка ячейку, из которой вытянули подходящую цифру
                                        max_bag_index--; // уменьшаем максимальный индекс мешка, чтобы не залезть в его лишние цифры, которые идут дальше
                                }
                        }
                        // получился массив из 8 ячеек, крайние равны 0
                        // добавляем 2 нуля в произвольные места массива, кроме крайних ячеек. Итого у нас в 10 ячейках 4 нуля (2 по краям, 2 в произвольных местах). Остальные цифры - случайные (в т.ч. могут быть нули)
                        temp_vector.splice(MyMath.randomRange(1, temp_vector.length - 2), 0, 0)
                        temp_vector.splice(MyMath.randomRange(1,temp_vector.length-2),0,0)
 
                        trace('temp_vector='+temp_vector)


Wolsh 18.03.2016 09:00

var max_bag_index:uint; — должен быть инт, так как подвергается декременту в теле цикла.
var bag:Vector.<uint> — по сути константа, надо объявить и инициализировать один раз, чтобы не тратить драгоценные пикосекунды.
while (testee == previous1) { if (testee == previous2) { — чтобы не делать if на каждом витке while, можно заключить while в условие if (previous1 == previous2). Это состояние неизменно и определяет необходимость проверки testee вообще — если два предыдущих не равны, то пофиг чему равен testee.

КорДум 18.03.2016 11:03

Добавлю к предыдущему своему комментарию в другой теме: необходимо ознакомиться с конвенциями именований AS3. В данном случае неверно записаны имена у локальных переменных. А еще советую польоваться автореформатом кода в той IDE, где Вы пишете код (если это не FlashIDE, конечно).

a7s1h1 18.03.2016 11:08

Цитата:

Сообщение от Wolsh (Сообщение 1192759)
var bag:Vector.<uint> — по сути константа, надо объявить и инициализировать один раз, чтобы не тратить драгоценные пикосекунды.

Константой её сделать не получится, ведь, когда из мешка достаётся цифра, соответствующая ячейка из мешка удаляется:
Код AS3:

bag.splice(ind, 1)

Добавлено через 8 минут
Цитата:

Сообщение от КорДум (Сообщение 1192763)
Добавлю к предыдущему своему комментарию в другой теме: необходимо ознакомиться с конвенциями именований AS3. В данном случае неверно записаны имена у локальных переменных.

Про конвенции я прочитал, везде, вроде исправил. Видимо, что-то упустил. Можете привести пример, где неправильно?

Цитата:

Сообщение от КорДум (Сообщение 1192763)
А еще советую польоваться автореформатом кода в той IDE, где Вы пишете код (если это не FlashIDE, конечно).

Код пишу во FlashDevelop. "Автореформат" - это Refactor-Code Formatter? Он мне всё по абзацам разбил - теперь всё выглядит предельно наглядно, но очень непривычно (например, я привык фигурные скобки ставить не на следующей строке, а сразу после условия/функции - это разве плохо?)

caseyryan 18.03.2016 11:22

Цитата:

Про конвенции я прочитал, везде, вроде исправил. Видимо, что-то упустил. Можете привести пример, где неправильно?
Пример: max_bag_index
В as3 принято использовать верблюжий регистр (camel case). То есть вместо max_bag_index, нужно писать maxBagIndex
Локальные переменные начинаются с маленькой буквы.
Публичные переменные тоже, а приватные начинаются с андерскора _

Код AS3:

// приватные
private var _someVar:Number = 0;
// публичные
public var someVar:Number = 0;
// локальные
var someLocalVar:Number = 0;


a7s1h1 18.03.2016 11:30

Цитата:

Сообщение от Wolsh (Сообщение 1192759)
чтобы не делать if на каждом витке while, можно заключить while в условие if (previous1 == previous2). Это состояние неизменно и определяет необходимость проверки testee вообще — если два предыдущих не равны, то пофиг чему равен testee.

И правда... Спасибо большое, исправил

КорДум 18.03.2016 11:32

Цитата:

например, я привык фигурные скобки ставить не на следующей строке, а сразу после условия/функции - это разве плохо?
Конкретно этот момент можно настроить где-то в настройках. Я сам не люблю, когда { на новой строке где бы то ни было, если иного не устанавливает code style команды, в которой я работаю.

a7s1h1 18.03.2016 11:38

Цитата:

Сообщение от caseyryan (Сообщение 1192767)
Пример: max_bag_index
В as3 принято использовать верблюжий регистр (camel case). То есть вместо max_bag_index, нужно писать maxBagIndex

У меня так и было раньше, но после замечания КорДума я полез вот сюда и исправил весь свой код в соответствии с рекомендациями, которые там изложены: "Все буквы в имени строчные, слова отделяются друг от друга символом подчёркивания, начинается с символа подчёркивания." Или это относится только к private, а локальные надо писать с верблюжим регистром, как методы?

КорДум 18.03.2016 11:53

По ссылке выше написано почти все неверно. https://sourceforge.net/adobe/flexsd...20Conventions/

caseyryan 18.03.2016 12:39

Цитата:

Сообщение от a7s1h1 (Сообщение 1192770)
У меня так и было раньше, но после замечания КорДума я полез вот сюда

Это хрень какая-то. Как уже написал КорДум, там почти все неверно.
Если уж не читая конвенции делать, но стоило бы посмотреть на то, как пишут сами адобовцы.

п.с. Кстати, названия интерфейсов в виде прилагательных (оканчивающихся на able) принято в Java, но не в as3. А переменные через андерскор пишут где-нибудь в php.

Цитата:

Конкретно этот момент можно настроить где-то в настройках. Я сам не люблю, когда { на новой строке где бы то ни было, если иного не устанавливает code style команды, в которой я работаю.
Tools - Program Settings - FlashDevelop - Coding Style Type - BracesOnLine

a7s1h1 18.03.2016 13:20

Цитата:

Сообщение от КорДум (Сообщение 1192771)

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

Добавлено через 2 минуты
Цитата:

Сообщение от caseyryan (Сообщение 1192773)
Tools - Program Settings - FlashDevelop - Coding Style Type - BracesOnLine

Спасибо! Теперь гораздо удобнее

Wolsh 18.03.2016 14:59

Цитата:

названия интерфейсов в виде прилагательных (оканчивающихся на able) принято в Java, но не в as3.
IBitmapDrawable
Наверное, самый известный интерфейс после IEventDispatcher :)

caseyryan 18.03.2016 15:50

Да, но где-то у Мука по-моему, было как раз про это написано. Что названия интерфейсов в AS3 образуются от названия классов, простым добавлением заглавной буквы I перед названием.
А в конвенциях джавы никакой I не требуется, зато название обязательно должно быть прилагательным

Tails 18.03.2016 15:58

Да кому нужна эта джава)

caseyryan 18.03.2016 18:07

Цитата:

Да кому нужна эта джава)
Мне, например

Tails 18.03.2016 20:19

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

undefined 18.03.2016 20:38

а разве создание байт-кода нельзя назвать компиляцией?

caseyryan 18.03.2016 20:51

Можно, джава как раз компилируемый язык

Tails 18.03.2016 21:06

Под компилируемыми языками обычно подразумеваются те, что из исходного кода переводятся в непосредственно машинные команды: https://ru.wikipedia.org/wiki/%D0%9A...BD%D0%B8%D1%8F

i.o. 18.03.2016 21:26

Опять жаву унизили))))

Впрочем тема во флуд скатилась

caseyryan 19.03.2016 06:47

Цитата:

Сообщение от Tails (Сообщение 1192788)
Под компилируемыми языками обычно подразумеваются те, что из исходного кода переводятся в непосредственно машинные команды: https://ru.wikipedia.org/wiki/%D0%9A...BD%D0%B8%D1%8F

Не надо читать только заголовки) Там же сразу
Цитата:

Классификация языков программирования на компилируемые и интерпретируемые, является неточной и весьма условной, поскольку для любого языка программирования может быть создан как компилятор, так и интерпретатор.
В джаве есть компилятор javac, так же и у as3. Было бы глупо говорить, что языки не компилируемые, если для них есть компиляторы.


Часовой пояс GMT +4, время: 13:23.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.