Как эффективно найти идеальное количество столбцов для строк определенной ширины?

Ответ 1

К сожалению, я считаю, что самый быстрый алгоритм, который у вас есть, - O (n ^ 2). Это связано с тем, что вы можете определить, возможна ли конфигурация для столбцов c в одном проходе списка, но вы не можете знать, насколько это необходимо для изменения c, поэтому вам просто нужно попробовать другое значение для него. Максимум ваш алгоритм будет делать это n раз.

Это псевдокод для того, как я это сделаю

for c = n.size, c > 0, c --
  remainingDist = m - c*s
  for i = 1, i <= c, i ++ 
    columnWidth = 0
    for j = i, j <= n.size; j += c
      columnWidth = max(n[j], columnWidth)
    end
    remainingDist -= columnWidth
  end
  if remainingDist >= 0
    success
    columns = c
    break
  end
end

вы могли бы перейти на полпути через цикл, предварительно вычислив средний размер элементов и нарисуя "идеальное" количество столбцов.

Ответ 2

Я не уверен точно, как сформулировать это в коде, но с гистограммой строк, отсортированных по размеру, мы можем установить теоретическую верхнюю границу числа столбцов, которая будет уточняться точным методом как wckd's. Поскольку размер столбца продиктован его самым длинным элементом, и мы обязаны делиться столбцами как можно более равномерно, если число наибольших строк до сих пор является достаточно небольшой частью общего числа, мы можем продолжать разделять столбцы с более короткие строки. Например,

size frequency
10   5
 6   10
 3   11

m = 30, s = 1

start: 30 - (10 + 1) = 19
implies 13 + 13:

10 (x5)  6 (x2) 
 6 (x8)  3 (x11)

but the portion of 6 and 3 is large enough to split the second column:

19 - (6 + 1) = 12
implies 9 + 9 + 8:

10 (x5) 6 (x6) 3 (x8)
6  (x4) 3 (x3)

but splitting again will still fit:
12 - (6 + 1) = 5
implies 7 + 7 + 6 + 6:

10 (x5) 6 (x7) 6 (x1) 3 (x6)
6  (x2)        3 (x5)

В итоге мы получим теоретически не более 4 столбцов (ясно, что сортировка строк не допускается в фактическом результате), которые могут быть уменьшены методом wckd.

В зависимости от данных мне интересно, может ли такая оптимизация быть полезной. Построение гистограммы должно занимать время O(n + k * log k) и O(k), где k - количество строковых размеров (которые вы уже ограничены w < 1000, m < 10000). И операция, которую я предлагаю, фактически не зависит от n, она зависит только от m, s и распределения k; и так как k сортируется, нам нужно только одно разделение/расчёты столбцов.

Ответ 3

Я рассмотрел первую проблему (горизонтальное заполнение) и предположил размер зазора (s) равным нулю, как вы сказали в своем редактировании.

Во-первых: я знаю, что награда закончилась, и у меня нет доказательств алгоритма, который лучше, чем O(n²).

Однако у меня есть некоторые идеи, которые могут представлять интерес.

Мой предложенный алгоритм выглядит следующим образом:

Получите верхнюю границу c в O(n) времени (я получу это позже)

Если c равно 0 или 1, или все строки соответствуют одной строке, тогда c является ответом. Стоп.

Создайте индекс ss[] на s[] по нисходящей ширине, используя сортировку отверстий голубей, в O(w+n) (с w = max(s[]), w <= m). Один элемент ss[] имеет два атрибута: width и seqNo (исходный порядковый номер, как это происходит в s[]).

Затем прокрутите ширину в порядке убывания, пока мы не получим ширину для каждого столбца в конфигурации c -column. Если сумма этих ширин еще не больше, чем m, то c является решением. Формально:

    knownColumnWidths = new Set() of column numbers
    sumWidth = 0
    for i from 0 to n-1:
        colNo = ss[i].seqNo modulo c
        if not colNo in knownColumnWidths:
            sumWidth += ss[i].width
            if sumWidth > m:
                // c is not a solution, exit for-loop
                break
            add colNo to knownColumnWidths
            if knownColumnWidths has c values:
                // solution found
                return c as solution. Stop

Если c было отклонено как решение, повторите предыдущий код с помощью c = c - 1.

Эта последняя часть алгоритма кажется O(n²). Но если for-loop имеет худшую производительность (т.е. n - c + 1 итерации), то следующие несколько раз (c/2) он будет работать, он будет близок к максимальной производительности (т.е. Близок к c итерациям). Но в конце он по-прежнему выглядит как O(n²).

Для получения хорошей верхней границы c (см. первый шаг выше), я предлагаю следующее:

Сначала заполните как можно больше строк в первой строке терминала, не превышая предела m, и возьмите это как начальный верхний предел для c. Более формально поставлено:

sumWidth = 0
c = 0
while c < n and sumWidth + s[c] <= m:
    sumWidth += s[c]
    c++

Это явно O(n).

Это может быть дополнительно улучшено следующим образом:

Возьмите сумму ширины c, но, начиная еще одну строку, и проверьте, не осталось ли это больше, чем m. Продолжайте делать это. Когда m превзойдено, уменьшите c, пока сумма ширины c не будет в порядке, и продолжите сдвиг с суммой c последовательной ширины.

Более формально, с c, начиная с вышеприведенного верхнего предела:

for i from c to n - 1:
    if s[i] > m:
        c = 0. Stop // should not happen: all widths should be <= m
    sumWidth += s[i] - s[i - c]
    while sumWidth > m:
        // c is not a solution. Improve upper limit: 
        c--
        sumWidth -= s[i - c]

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

Это завершает мой алгоритм. Я считаю, что он будет хорошо работать на случайном входе, но все равно выглядит как O(n²).

Но у меня есть несколько наблюдений, которые я не использовал в приведенном выше алгоритме:

• Когда вы нашли ширину столбца для определенного c, но общая ширина больше, чем m, тогда этот результат все равно можно использовать для случая c'=c/2. Тогда нет необходимости проходить через всю ширину строки. Достаточно взять sum(max(s[i], s[i+c']) для i in 0..c'-1. Тот же принцип справедлив и для других делителей c.

Я не использовал это, потому что, если вам нужно спуститься с c полностью на c/2, не найдя решение, вы уже потратили O(n²) на алгоритм. Но, возможно, это может служить цели в другом алгоритме...

2. Если строки с нулевой длиной не разрешены, то можно сделать алгоритм O(m.n), поскольку количество возможных решений (значения для c) ограничено m и определить, будет ли один из этих является решением, требуется только одна прокрутка по всем ширинам.

Я допустил строки с нулевой длиной.

3. Сначала я искал двоичный поиск c, разделив его на 2 и перейдя на одну из оставшихся половинок. Но этот метод не может быть использован, потому что даже когда определенное c оказывается не решением, это не исключает наличия c' > c, который является решением.

Надеюсь, что в этом ответе вы найдете что-то полезное.

Ответ 4

Очевидным способом решения этой проблемы является итерация по всем строковым строкам в некотором заданном порядке, обновлять ширину столбца, где каждая строка принадлежит и останавливается, когда сумма ширины столбцов превышает ширину терминала. Затем повторите этот процесс для уменьшения числа столбцов (или для увеличения количества строк для "упорядочить" случай) до успеха. Три возможных варианта для этого предопределенного порядок:

• по строке (рассмотрите все строки в первой строке, затем в строке 2, 3,...)
• по столбцу (рассмотрим все строки в первом столбце, затем в столбцах 2, 3,...)
• по значению (сортировать строки по длине, а затем перебирать их в отсортированном порядке, начиная с самого длинного).

Эти три подхода подходят для "подстройки" под-проблемы. Но для "устроить" суб-проблема, у всех они имеют худшую временную сложность O (n ²). И первые два методы показывают квадратичную сложность даже для случайных данных. "По значению" подход довольно хорошо для случайных данных, но легко найти худший сценарий: просто назначьте короткий строки в первую половину списка и длинные строки - во вторую половину.

Здесь я описываю алгоритм для случая "упорядочивания", который не имеет этих недостатки.

Вместо того, чтобы проверять каждую длину строки отдельно, она определяет ширину каждого столбца в O (1) времени с помощью максимального запроса диапазона (RMQ). Ширина первого столбец - это максимальное значение в диапазоне (0.. num_of_rows), ширина следующего - максимальное значение в диапазоне (num_of_rows.. 2 * num_of_rows) и т.д.

И чтобы ответить на каждый запрос в O (1) раз, нам нужно подготовить массив максимум значения в диапазонах (0.. 2 ^k), (1.. 1 + 2 ^k),..., где k равно наибольшее целое число, такое, что 2 ^k не больше текущего количества строк. Максимальный запрос каждого диапазона вычисляется как максимум две записи из этого массива. Когда количество строк становится слишком большим, мы должны обновить этот массив запросов от k до k + 1 (для каждого такого обновления требуются запросы диапазона O (n)).

Вот реализация С++ 14:

template<class PP>
uint32_t arrangeDownRMQ(Vec& input)
{
    auto rows = getMinRows(input);
    auto ranges = PP{}(input, rows);

    while (rows <= input.size())
    {
        if (rows >= ranges * 2)
        { // lazily update RMQ data
            transform(begin(input) + ranges, end(input), begin(input),
                      begin(input), maximum
            );

            ranges *= 2;
        }
        else
        { // use RMQ to get widths of columns and check if all columns fit
            uint32_t sum = 0;

            for (Index i = 0; sum <= kPageW && i < input.size(); i += rows)
            {
                ++g_complexity;
                auto j = i + rows - ranges;

                if (j < input.size())
                    sum += max(input[i], input[j]);
                else
                    sum += input[i];
            }

            if (sum <= kPageW)
            {
                return uint32_t(ceilDiv(input.size(), rows));
            }

            ++rows;
        }
    }

    return 0;
}

Здесь PP является необязательным, для простого случая этот объект функции ничего не делает и возвращает 1.

Чтобы определить худшую временную сложность этого алгоритма, обратите внимание на то, что начинается внешний цикл с rows = n * v / m (где v - средняя длина строки, m - ширина страницы) и останавливается не более rows = n * w / m (где w - наибольшая длина строки). Количество итераций в цикле "запрос" не больше числа столбцов или n / rows. Добавление этих итераций дает O(n * (ln(n*w/m) - ln(n*v/m))) или O(n * log(w/v)). Это означает линейное время с малым постоянным множителем.

Мы должны добавить здесь время для выполнения всех операций обновления, которые являются O (n log n), чтобы получить сложность всего алгоритма: O (n * log n).

Если мы не выполняем никаких операций обновления до тех пор, пока не будут выполнены какие-либо операции запроса, потребуется время для операций обновления, а также сложности алгоритма уменьшается до O(n * log(w/v)). Чтобы сделать это возможным, нам нужен какой-то алгоритм, который заполняет массив RMQ максимумами субмассивов заданной длины. Я попробовал два возможных подхода, и кажется с парой стеков немного быстрее. Вот реализация С++ 14 (части входного массива используются для реализации обоих стеков для снижения требований к памяти и для упрощения кода):

template<typename I, typename Op>
auto transform_partial_sum(I lbegin, I lend, I rbegin, I out, Op op)
{ // maximum of the element in first enterval and prefix of second interval
    auto sum = typename I::value_type{};

    for (; lbegin != lend; ++lbegin, ++rbegin, ++out)
    {
        sum = op(sum, *rbegin);
        *lbegin = op(*lbegin, sum);
    }

    return sum;
}

template<typename I>
void reverse_max(I b, I e)
{ // for each element: maximum of the suffix starting from this element
    partial_sum(make_reverse_iterator(e),
                make_reverse_iterator(b),
                make_reverse_iterator(e),
                maximum);
}

struct PreprocRMQ
{
    Index operator () (Vec& input, Index rows)
    {
        if (rows < 4)
        { // no preprocessing needed
            return 1;
        }

        Index ranges = 1;
        auto b = begin(input);

        while (rows >>= 1)
        {
            ranges <<= 1;
        }

        for (; b + 2 * ranges <= end(input); b += ranges)
        {
            reverse_max(b, b + ranges);
            transform_partial_sum(b, b + ranges, b + ranges, b, maximum);
        }

        // preprocess inconvenient tail part of the array
        reverse_max(b, b + ranges);
        const auto d = end(input) - b - ranges;
        const auto z = transform_partial_sum(b, b + d, b + ranges, b, maximum);
        transform(b + d, b + ranges, b + d, [&](Data x){return max(x, z);});
        reverse_max(b + ranges, end(input));
        return ranges;
    }
};

На практике гораздо больше шансов увидеть короткое слово, чем длинное слово. Более короткие слова превосходят более длинные в английских текстах, более короткие текстовые представления естественных чисел. Поэтому я выбрал (слегка измененное) геометрическое распределение строки длины для оценки различных алгоритмов. Здесь полная программа бенчмаркинга (в С++ 14 для gcc). Старая версия той же программы содержит некоторые устаревшие тесты и различную реализацию некоторых алгоритмов: TL; DR. И вот результаты:

Для случая "расположить в поперечнике":

• "по столбцу" подход является самым медленным
• "по значению" подходит для n = 1000..500'000'000
• "по строкам" подход лучше для небольших и очень больших размеров.

Для случая "расположить вниз":

• "по значению" подход в порядке, но медленнее, чем другие альтернативы (одна из возможностей сделать это быстрее - это реализовать деления посредством умножения), также он использует больше памяти и имеет квадратичное худшее время
• простой подход RMQ лучше
• RMQ с предварительной обработкой наилучшего: он имеет линейную временную сложность и требования к пропускной способности памяти довольно низки.

Также может быть интересно увидеть количество итераций, необходимых для каждого алгоритма. Здесь исключены все предсказуемые части (сортировка, суммирование, предварительная обработка и RMQ Обновления):