algorithm - rangos - ¿Cómo encontrar eficientemente el conteo de columnas ideal para cadenas de cierto ancho?

formula para contar celdas en excel ingles

Question

Tengo n cadenas de diferente longitud s ₁ , s ₂ , ..., s _n que quiero mostrar en un terminal en c columnas. El terminal tiene un ancho de m caracteres. Cada columna i tiene un cierto ancho w _i que es igual al ancho de la entrada más larga en esa columna. Entre cada par de columnas hay una cierta cantidad de espacio s . El ancho total de todas las columnas, incluido el espacio entre ellas, no puede ser mayor que el ancho del terminal ( w ₁ + w ₂ + ... + w _c + ( c - 1 ) · s ≤ m ). Cada columna contendrá cadenas ⌈ n / c ⌉, excepto cuando n no sea divisible en partes iguales por c , en cuyo caso las últimas columnas serán más cortas en una entrada o solo la última columna será más corta dependiendo de si las cadenas están arregladas a través o hacia abajo.

¿Hay un algoritmo eficiente (por ejemplo, O ( n · w ) donde w = max ( w ₁ , w ₂ , ..., w _n )) para calcular la cantidad máxima de columnas que puedo encajar en c columnas, si ...

• las cuerdas se arreglan a través

  string1 string2  string3 string4
  string5 string6  string7 string8
  string9 string10

• las cuerdas se arreglan abajo

  string1 string4 string7 string10
  string2 string5 string8
  string3 string6 string9

?

Descubrimientos posteriores

Descubrí que s no importa. Cada instancia del problema donde s> 0 se puede traducir a una instancia donde s = 0 expandiendo cada cadena por s caracteres y también expandiendo el ancho de la terminal por los caracteres s para compensar los caracteres adicionales al final de la pantalla .

Answer 1

Desafortunadamente, creo que el algoritmo más rápido que puedes tener es O (n ^ 2). Esto se debe a que puedes determinar si una configuración es posible para c columnas en una sola pasada de la lista, pero no puedes saber cuánto cambiar c, así que básicamente tendrás que probar un valor diferente para ella. A lo sumo su algoritmo lo hará n veces.

Este es un pseudo-código de cómo lo haría

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

podría saltar a la mitad del ciclo calculando primero el tamaño promedio de los elementos y calcular un número "ideal" de columnas a partir de eso.

Answer 2

No estoy seguro exactamente de cómo formular esto en el código, pero con un histograma de las cadenas ordenadas por tamaño, podemos establecer un límite superior teórico en el número de columnas, que se refinará con un método exacto como el de wckd. Dado que el tamaño de columna está dictado por su elemento más largo, y estamos obligados a dividir las columnas lo más uniformemente posible, siempre que el número de cadenas más grandes hasta el momento sea una porción lo suficientemente pequeña del total, podemos continuar dividiendo las columnas con cadenas más cortas. Por ejemplo,

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)

Terminamos con un máximo de 4 columnas teóricamente (claramente, ordenar las cadenas no está permitido en el resultado real) que puede ser reducido por el método de wckd.

Dependiendo de los datos, me pregunto si tal optimización a veces podría ser útil. La construcción del histograma debe tomar O(n + k * log k) tiempo y O(k) espacio, donde k es el número de tamaños de cadena (que ya ha limitado con w < 1000, m < 10000 ). Y la operación que estoy sugiriendo es realmente independiente de n , depende solo de m , s y de la distribución de k ; y dado que k está ordenado, solo necesitamos una pasada para dividir / calcular las columnas.

Answer 3

Miré el primer problema (relleno horizontal) y asumí un tamaño de brecha ( s ) de cero, como sugirió en su edición.

Primero: sé que la recompensa ha terminado, y no tengo pruebas de un algoritmo que sea mejor que O(n²) .

Sin embargo, tengo algunas ideas para presentar que aún pueden ser de interés.

Mi algoritmo propuesto es el siguiente:

Obtenga un límite superior de c en O(n) tiempo (lo abordaré más adelante)

Si c es 0 o 1, o todas las cadenas encajan en una fila, entonces esa es la respuesta. Detener.

Cree un índice ss[] en s[] en anchuras descendentes, utilizando clasificación de barril de paloma , en O(w+n) (con w = max(s[]), w <= m ). Un elemento de ss[] tiene dos atributos: width y seqNo (el número de secuencia original, como ocurre en s[] ).

Luego, recorra los anchos en orden decreciente hasta que tengamos un ancho para cada columna en una configuración de columna c . Si la suma de estos anchos aún no es mayor que m entonces c es una solución. Más formalmente:

    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

Si se rechazó c como solución, repita el código anterior con c = c - 1 .

Esta última parte del algoritmo parece O(n²) . Pero, si el bucle for tiene el peor de los casos (es decir, n - c + 1 iteraciones), las próximas veces ( c/2 ) que se ejecutan, tendrán el mejor rendimiento (es decir, cerca de iteraciones c ). Pero al final todavía se ve como O(n²) .

Para obtener un buen límite superior de c (véase el primer paso anterior), propongo esto:

Primero llene tantas cadenas en la primera fila del terminal sin exceder el límite m , y tome eso como el límite superior inicial para c . Más formalmente puesto:

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

Esto es claramente O(n) .

Esto se puede mejorar aún más de la siguiente manera:

Tome la suma de c anchos, pero comenzando una cuerda más, y verifique si todavía no es mayor que m . Sigue haciendo este cambio. Cuando se supera m , disminuya c hasta que la suma de anchos c vuelva a estar bien y continúe el cambio con la suma de c anchuras consecutivas.

Más formalmente puesto, con c comenzando con el límite superior encontrado arriba:

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]

Esto significa que en un barrido puede tener varias mejoras para c . Por supuesto, en el peor de los casos, no mejora en absoluto.

Esto concluye mi algoritmo. Estimo que tendrá un buen rendimiento en la entrada aleatoria, pero todavía se ve como O(n²) .

Pero tengo algunas observaciones, que no he usado en el algoritmo anterior:

1. Cuando haya encontrado los anchos de columna para una cierta c , pero el ancho total es mayor que m , este resultado aún puede ser utilizado para el caso c''=c/2 . Entonces no es necesario pasar por todos los anchos de cadena. Basta con tomar la sum(max(s[i], s[i+c'']) para i in 0..c''-1 . El mismo principio se aplica a otros divisores de c .

No usé esto, porque si tienes que bajar desde c hasta c/2 sin encontrar una solución, ya has gastado O(n²) en el algoritmo. Pero tal vez puede servir un propósito en otro algoritmo ...

2. Cuando no se permiten cadenas de longitud cero, entonces se puede hacer que un algoritmo sea O(mn) , ya que el número de soluciones posibles (valores de c ) se limita a m y para determinar si una de ellas es una solución, solo requiere un barrido a través de todos los anchos.

He permitido cadenas de longitud cero.

3. Inicialmente estaba buscando una búsqueda binaria de c , dividiéndola por 2 y yendo por una de las mitades restantes. Pero este método no se puede utilizar, porque incluso cuando se encuentra que cierta c no es una solución, esto no excluye que haya una c'' > c que sea una solución.

Esperemos que haya algo en esta respuesta que encuentre útil.

Answer 4

Una forma obvia de resolver este problema es iterar a través de todas las longitudes de cadena en un orden predeterminado, actualizar el ancho de la columna a la que pertenece cada cadena y detener cuando la suma de anchuras de columna excede el ancho del terminal. A continuación, repita este proceso para disminuir el número de columnas (o para el número incrementado de filas para el caso "arreglar hacia abajo") hasta que tenga éxito. Tres opciones posibles para este orden predeterminado:

1. por fila (considere todas las cadenas en la primera fila, luego en la fila 2, 3, ...)
2. por columna (considere todas las cadenas en la primera columna, luego en la columna 2, 3, ...)
3. por valor (ordenar las cadenas por longitud, luego iterarlas en orden, empezando por la más larga).

Estos 3 enfoques están bien para el sub-problema "organizar a través de". Pero para el sub-problema de "organizar hacia abajo" todos tienen la peor complejidad de tiempo de caso O (n ² ). Y los primeros dos métodos muestran complejidad cuadrática incluso para datos aleatorios. El enfoque "por valor" es bastante bueno para los datos aleatorios, pero es fácil encontrar el peor de los casos: simplemente asigne cadenas cortas a la primera mitad de la lista y cadenas largas, a la segunda mitad.

Aquí describo un algoritmo para el caso "arreglar hacia abajo" que no tiene estas desventajas.

En lugar de inspeccionar cada longitud de cadena por separado, determina el ancho de cada columna en O (1) tiempo con la ayuda de la consulta máxima de rango (RMQ). El ancho de la primera columna es solo el valor máximo en el rango (0 .. num_of_rows), el ancho de la siguiente es el valor máximo en el rango (num_of_rows .. 2 * num_of_rows), etc.

Y para responder cada consulta en O (1) tiempo, necesitamos preparar una matriz de valores máximos en rangos (0 .. 2 ^k ), (1 .. 1 + 2 ^k ), ..., donde k es el más grande entero tal que 2 ^k no es mayor que el número actual de filas. Cada consulta máxima de rango se calcula como un máximo de dos entradas de esta matriz. Cuando el número de filas comienza a ser demasiado grande, debemos actualizar este conjunto de consultas de k a k + 1 (cada actualización necesita consultas de rango O (n)).

Aquí está la implementación de C ++ 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;
}

Aquí PP es opcional, para el caso simple, este objeto de función no hace nada y devuelve 1.

Para determinar la peor complejidad de tiempo de este algoritmo, observe que el bucle externo comienza con rows = n * v / m (donde v es la longitud promedio de la cadena, m es el ancho de página) y se detiene con la mayoría de las rows = n * w / m ( donde w es la longitud de cuerda más grande). El número de iteraciones en el ciclo "consulta" no es mayor que el número de columnas o n / rows . Al sumar estas iteraciones se obtiene O(n * (ln(n*w/m) - ln(n*v/m))) o O(n * log(w/v)) . Lo que significa tiempo lineal con pequeño factor constante.

Deberíamos agregar aquí el tiempo para realizar todas las operaciones de actualización que es O (n log n) para obtener la complejidad de todo el algoritmo: O (n * log n).

Si no realizamos operaciones de actualización hasta que se realicen algunas operaciones de consulta, el tiempo necesario para las operaciones de actualización y la complejidad del algoritmo disminuirán a O(n * log(w/v)) . Para que esto sea posible, necesitamos algún algoritmo que llene el arreglo RMQ con el máximo de sub-arrays de una longitud dada. Intenté dos enfoques posibles y parece que el algoritmo con par de pilas es ligeramente más rápido. Aquí está la implementación de C ++ 14 (las piezas de la matriz de entrada se usan para implementar ambas pilas para reducir los requisitos de memoria y simplificar el código):

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;
    }
};

En la práctica, hay muchas más posibilidades de ver una palabra corta que una palabra larga. Las palabras más cortas superan a las más largas en los textos en inglés, también prevalecen las representaciones de texto más cortas de los números naturales. Así que elegí (ligeramente modificado) la distribución geométrica de las longitudes de cadena para evaluar varios algoritmos. Aquí está todo el programa de evaluación comparativa (en C ++ 14 para gcc). La versión anterior del mismo programa contiene algunas pruebas obsoletas y una implementación diferente de algunos algoritmos: TL; DR . Y aquí están los resultados:

Para el caso "organizar a través de":

• el enfoque "por columna" es el más lento
• El enfoque "por valor" es bueno para n = 1000..500''000''000
• El enfoque "por fila" es mejor para tamaños pequeños y muy grandes

Para el caso de "organizar hacia abajo":

• El enfoque "por valor" es correcto, pero más lento que otras alternativas (una posibilidad para hacerlo más rápido es implementar divisiones mediante multiplicaciones), también usa más memoria y tiene el tiempo del peor caso cuadrático
• el enfoque RMQ simple es mejor
• RMQ con preprocesamiento de lo mejor: tiene complejidad de tiempo lineal y sus requisitos de ancho de banda de memoria son bastante bajos.

También puede ser interesante ver el número de iteraciones necesarias para cada algoritmo. Aquí se excluyen todas las partes predecibles (clasificación, suma, preprocesamiento y actualizaciones de RMQ):