Форум Flasher.ru - Задачка

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- Флейм (http://www.flasher.ru/forum/forumdisplay.php?f=53)

- - Задачка (http://www.flasher.ru/forum/showthread.php?t=181615)

Народ, вы чо?

Код AS3:

var data:Array = [1, 2, 3, 4, 5, 6, 7];

var res:Array = [];

var w:int = 5;

var minInCols:int = int(data.length / w);

var rest:int = data.length%w;

var curNum:int = 0;

for(var i:int = 0; i < w; ++i) {

        var to:int = minInCols;

        if(i < rest)

                to += 1;

        res.push([]);

        for(var j:int = 0; j < to; ++j) {

                res[i].push(curNum);

                ++curNum;

        }

}

UPD: о, Тигра вродь считай такое же запилил)

Хехе, все не так просто!
Изначальный (мой) вариант делает C + ceiling(N/C) * C итераций. Где C - количество колонок, а N - количество элементов в массиве который нужно распечатать. Кроме того, space-state complexity (тета) равна 3 * C, а в предложенных вариантах - это C + N, что практически всегда будет больше.

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

Код AS3:

package

{

        import flash.display.Sprite;

 

        public class PrintColumns extends Sprite

        {

                /**

                 * http://stackoverflow.com/questions/1...-into-x-colums

                 */

                public function PrintColumns()

                {

                        super();

                        trace(printColumns([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                        trace(printColumns2([1, 2, 3, 4, 5, 6, 7, 8, 9], 4));

                }

 

                private function printArray(source:Array):String

                {

                        return source.join(" ") + "\n";

                }

 

                private function mapconcat(arrays:Array, delimiter:String):String

                {

                        var result:String = "";

                        var args:Array = new Array(arrays.length);

                        var printed:Array;

 

                        for (var i:int = 0; i < arrays[0].length; i++)

                        {

                                for (var j:int = 0; j < arrays.length; j++)

                                {

                                        printed = arrays[j];

                                        if (printed.length > i) args[j] = printed[i];

                                        else args[j] = "";

                                }

                                result += delimiter + args.join(" ");

                        }

                        return result.substr(delimiter.length);

                }

 

                private function printColumns2(input:Array, lines:int):String

                {

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int;

                        var m:int;

                        var output:String = "";

 

                        while (c < length)

                        {

                                result[m] = [];

                                for (var i:int = 0; i < itemsInLine; i++) result[m].push(input[c++]);

                                if (outfit-- > 0) result[m].push(input[c++]);

                                m++;

                        }

 

                        return mapconcat(result, "\n");

                }

 

                private function printColumns(source:Array, numColumns:int):String

                {

                        var output:String = "";

                        var columns:Array = new Array(numColumns);

                        var printPositions:Array = new Array(numColumns);

                        var printed:Array;

                        var i:int;

                        var columnLength:int = Math.ceil(source.length / numColumns);

                        var printedAlready:int;

                        var nextBunch:int;

 

                        printPositions[0] = 0;

                        while (i < numColumns)

                        {

                                if (source.length - (printedAlready + columnLength) < numColumns - i)

                                        nextBunch = columnLength - 1;

                                else nextBunch = columnLength;

                                printPositions[i + 1] = printedAlready + nextBunch;

                                columns[i] = printPositions[i + 1] - printPositions[i];

                                printedAlready += nextBunch;

                                i++;

                        }

                        i = 0;

                        printed = new Array(numColumns);

                        while (i < columnLength)

                        {

                                for (var j:int = 0; j < numColumns; j++)

                                {

                                        if (columns[j])

                                        {

                                                printed[j] = source[printPositions[j]];

                                                printPositions[j]++;

                                                columns[j]--;

                                        }

                                        else printed[j] = " ";

                                }

                                output += printArray(printed);

                                i++;

                        }

                        return output;

                }

        }

}

В каком-то методе mapconcat они набираются. Надо на выходе String сформатировать? Почему это форматирование не зашить в алгоритм, чтобы не гонять через Array?

Нет, mapconcat не при чем. У тебя когда ты формируешь колонки ты проходишь по всему списку / массиву оригинальных значений (т.е. продвигаешься на каждой итерации на 1 элемент вперед). Но для алгиритма это не обязательно (т.е. даже вредно) потомо что можно продвигаться по формуле:
floor(N/C) + f(mod(N,C) - i)

где i - счетчик цикла, а f - функция которая возвращает 0 для негативных значений или 0 и 1 для позитивных значений.

++ медленнее /, mod, -?

Цитата:

по всему списку / массиву оригинальных значений (т.е. продвигаешься на каждой итерации на 1 элемент вперед).

А как иначе? Надо вытащить каждый элемент входной последовательности. И в примере за одно "тело" цикла я двигаюсь или на 2, или на 3, но по сути это инлайн-цикла в теле )

Ну вот я и говорю, что можно иначе. Т.е. не нужно пересчитывать все элементы, можно splice()'ить по нужному числу - т.как мы можем просчитать размер который нужно отрезать по формуле, вметсто того, чтобы считать по одному и ждать пока условие не выполнится ;)

Т.е. в цикле вместо for (i = 0; i < length; i++) можно сделать
for (i = 0; i < length; i += stepSize())

где setpSize() = минимальная высота колонки + (если израсходован весь остаток от последнего ряда, то 0, иначе 1).

Для списков длиной в несколько миллионов, которые нужно разбить на 5-10 колонок выигрыш будет существенный ;)

Суть то не меняется. Вот вариант с splice'ом:

Код AS3:

                private function init(e:Event = null):void {

                        removeEventListener(Event.ADDED_TO_STAGE, init);

                        var txt:TextField=new TextField();

                        txt.autoSize = TextFieldAutoSize.LEFT;

                        txt.multiline=true;

 

                        var input:Array = [1,2,3,4,5,6,7,8,9];

                        const lines:int = 4;

 

                        var length:int = input.length;

                        var itemsInLine:int = length / lines;

                        var outfit:int = length - itemsInLine * lines;

                        var result:Array = [];

                        var c:int = 0;

                        while (c < length){

                                var g:int = outfit-- > 0 ? itemsInLine + 1 : itemsInLine;

                                result.push(input.splice(0, g))

                                c+=itemsInLine;

                        }

 

                        for (var k:int = 0; k<result.length; k++){

                                txt.appendText(result[k]+"\n")

                        }

                        addChild(txt);

                }

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

Я почему запостил: я когда только столкнулся, то подумал, что задача вообще тривиальная, а оказалось не совсем. Вот подумал, что будет интересно решить.

Цитата:

Сообщение от wvxvw (Сообщение 1086355)

Например, когда data = [1, 2, 3, 4, 5, 6, 7, 8, 9], w = 4. В таком случае хотелось бы одну колонку делать выше остальных, а не вразнобой :)

ну так какбе другие\дополнительные условия
а распихать все равно можно по простому (вроде бы :))

Код AS3:

var i:int, j:int, k:int;

var data:Array = [1, 2, 3, 4, 5, 6, 7, 8, 9];

var res:Array = [];

 

var w:int = 4;

var len:int = data.length;

var h:int = Math.ceil(len / w);

 

 

for (i = 0; i < h; i++) res[i] = [];

 

k = 0;

for (j = 0; j < w; j++) 

{

 

        for (i = 0; i < h ; i++) 

        {

 

                res[i][j] = data[k++];

 

                // уместится ли остаток в прямоугольник

                if (len-- <= (w - j - 1) * (h - 1) + 1) break;

 

                // уместится ли в строку

                //if (--len < w - j) break;

        }

}

 

for (i = 0; i < h; i++) trace(res[i]);