|
|
|||||
блогер
Регистрация: Oct 2005
Адрес: Днепродзержинск - город Брежнева и других логопедов
Сообщений: 1,421
Записей в блоге: 4
|
Народ, вы чо?
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; } }
__________________
Бобры отвечают на вопросы не потому, что знают на них ответы; они отвечают потому, что их спрашивают. Последний раз редактировалось -De-; 28.06.2012 в 15:49. |
|
|||||
Modus ponens
|
Хехе, все не так просто!
Изначальный (мой) вариант делает C + ceiling(N/C) * C итераций. Где C - количество колонок, а N - количество элементов в массиве который нужно распечатать. Кроме того, space-state complexity (тета) равна 3 * C, а в предложенных вариантах - это C + N, что практически всегда будет больше. Я привел ниже код Тигры который распечатывает результат в том же формате, что и мой, чтобы было видно где именно набиратются те самые итерации: 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; } } }
__________________
Hell is the possibility of sanity |
|
|||||
блогер
Регистрация: Jun 2005
Адрес: Господи пожалуйста не Новосибирск
Сообщений: 6,598
Записей в блоге: 17
|
В каком-то методе mapconcat они набираются. Надо на выходе String сформатировать? Почему это форматирование не зашить в алгоритм, чтобы не гонять через Array?
__________________
Тут мужик танцует и поёт про флэш |
|
|||||
Modus ponens
|
Нет, mapconcat не при чем. У тебя когда ты формируешь колонки ты проходишь по всему списку / массиву оригинальных значений (т.е. продвигаешься на каждой итерации на 1 элемент вперед). Но для алгиритма это не обязательно (т.е. даже вредно) потомо что можно продвигаться по формуле:
floor(N/C) + f(mod(N,C) - i) где i - счетчик цикла, а f - функция которая возвращает 0 для негативных значений или 0 и 1 для позитивных значений.
__________________
Hell is the possibility of sanity |
|
|||||
блогер
Регистрация: Jun 2005
Адрес: Господи пожалуйста не Новосибирск
Сообщений: 6,598
Записей в блоге: 17
|
Цитата:
__________________
Тут мужик танцует и поёт про флэш |
|
|||||
Modus ponens
|
Ну вот я и говорю, что можно иначе. Т.е. не нужно пересчитывать все элементы, можно splice()'ить по нужному числу - т.как мы можем просчитать размер который нужно отрезать по формуле, вметсто того, чтобы считать по одному и ждать пока условие не выполнится
Т.е. в цикле вместо for (i = 0; i < length; i++) можно сделать for (i = 0; i < length; i += stepSize()) где setpSize() = минимальная высота колонки + (если израсходован весь остаток от последнего ряда, то 0, иначе 1). Для списков длиной в несколько миллионов, которые нужно разбить на 5-10 колонок выигрыш будет существенный
__________________
Hell is the possibility of sanity |
|
|||||
блогер
Регистрация: Jun 2005
Адрес: Господи пожалуйста не Новосибирск
Сообщений: 6,598
Записей в блоге: 17
|
Суть то не меняется. Вот вариант с splice'ом:
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); }
__________________
Тут мужик танцует и поёт про флэш |
|
|||||
Modus ponens
|
Ну, понятно, что если результат тот же, то суть не меняется. Я же не говорил, что не правельно, просто не оптимально. Ну и для больших распечаток дублировать весь массив в памяти тоже как бы не хорошо (можно обойтись памятью 2 * количество колонок), (в первом массиве хранить отступы в исходный массив, откуда печатаем, а во втором - высоту каждой колонки).
Я почему запостил: я когда только столкнулся, то подумал, что задача вообще тривиальная, а оказалось не совсем. Вот подумал, что будет интересно решить.
__________________
Hell is the possibility of sanity |
|
|||||
Цитата:
а распихать все равно можно по простому (вроде бы ) 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]); |
Часовой пояс GMT +4, время: 20:46. |
|
« Предыдущая тема | Следующая тема » |
|
|