performance - seria - ¿Cómo encontrar pareja con kth suma más grande?

edarling

Question

Dados dos arreglos ordenados de números, queremos encontrar el par con la quinta suma más grande posible. (Un par es un elemento de la primera matriz y un elemento de la segunda matriz). Por ejemplo, con matrices.

• [2, 3, 5, 8, 13]
• [4, 8, 12, 16]

Las parejas con mayores sumas son

• 13 + 16 = 29
• 13 + 12 = 25
• 8 + 16 = 24
• 13 + 8 = 21
• 8 + 12 = 20

Así que el par con la cuarta suma más grande es (13, 8). ¿Cómo encontrar el par con la kth suma más grande posible?

Además, ¿cuál es el algoritmo más rápido? Las matrices ya están ordenadas y los tamaños M y N.

Ya estoy al tanto de la solución O (Klogk) , utilizando Max-Heap here .

También es una de las preguntas favoritas de la entrevista de Google , y exigen una solución O (k) .

También he leído en alguna parte que existe una solución O (k) , que no puedo entender.

Alguien puede explicar la solución correcta con un pseudocódigo.

PS Por favor, NO publique this enlace como respuesta / comentario. NO contiene la respuesta.

Answer 1

El algoritmo max-heap en la otra pregunta es simple, rápido y correcto. No lo golpees. Está muy bien explicado también. https://stackoverflow.com/a/5212618/284795

Puede que no haya ningún algoritmo O (k). Está bien, O (k log k) es casi tan rápido.

Answer 2

Si las dos últimas soluciones estaban en (a1, b1), (a2, b2), entonces me parece que solo hay cuatro soluciones candidatas (a1-1, b1) (a1, b1-1) (a2-1, b2 ) (a2, b2-1). Esta intuición podría estar equivocada. Seguramente hay como máximo cuatro candidatos para cada coordenada, y el siguiente más alto está entre los 16 pares (a en {a1, a2, a1-1, a2-1}, b en {b1, b2, b1-1, b2- 1}). Está bien).

(No, no lo es, todavía no estoy seguro de si eso es posible).

Answer 3

tl; dr: Si mira hacia adelante y mira hacia atrás en cada iteración, puede comenzar con el final (que es el más alto) y volver a trabajar en el tiempo O(K) .

Aunque la idea subyacente a este enfoque es, creo, acertada, el código de abajo no es del todo correcto en la actualidad (ver comentarios).

Veamos: en primer lugar, los arreglos están ordenados. Por lo tanto, si las matrices son a y b con longitudes M y N , y como las ha ordenado, los elementos más grandes están en las ranuras M y N respectivamente, el par más grande siempre será a[M]+b[N] .

Ahora, ¿cuál es el segundo par más grande? Tendrá quizás uno de {a[M],b[N]} (no puede tener ambos, porque es solo el par más grande otra vez), y al menos uno de {a[M-1],b[N-1]} . PERO, también sabemos que si seleccionamos a[M-1]+b[N-1] , podemos hacer que uno de los operandos sea más grande al elegir el número más alto de la misma lista, por lo que tendrá exactamente un número del última columna, y una de la penúltima columna.

Considere las siguientes dos matrices: a = [1, 2, 53]; b = [66, 67, 68] a = [1, 2, 53]; b = [66, 67, 68] . Nuestro par más alto es 53+68 . Si perdemos el menor de esos dos, nuestro par es 68+2 ; si perdemos el más grande, es 53+67 . Entonces, tenemos que mirar hacia adelante para decidir cuál será nuestro próximo par. La estrategia de búsqueda anticipada más simple es simplemente calcular la suma de ambos pares posibles. Eso siempre costará dos adiciones y dos comparaciones para cada transición (tres porque necesitamos tratar el caso en que las sumas son iguales); llamémoslo costo Q ).

Al principio, tuve la tentación de repetir ese K-1 veces. PERO hay un problema: el siguiente par más grande podría ser el otro par que podemos hacer válidamente desde {{a[M],b[N]}, {a[M-1],b[N-1]} . Por lo tanto, también tenemos que mirar hacia atrás.

Entonces, vamos a codificar (python, debería ser 2/3 compatible):

def kth(a,b,k):
    M = len(a)
    N = len(b)
    if k > M*N:
       raise ValueError("There are only %s possible pairs; you asked for the %sth largest, which is impossible" % M*N,k)
    (ia,ib) = M-1,N-1 #0 based arrays
    # we need this for lookback
    nottakenindices = (0,0) # could be any value
    nottakensum = float(''-inf'')
    for i in range(k-1):
        optionone = a[ia]+b[ib-1]
        optiontwo = a[ia-1]+b[ib]
        biggest = max((optionone,optiontwo))
        #first deal with look behind
        if nottakensum > biggest:
           if optionone == biggest:
               newnottakenindices = (ia,ib-1)
           else: newnottakenindices = (ia-1,ib)
           ia,ib = nottakenindices
           nottakensum = biggest
           nottakenindices = newnottakenindices
        #deal with case where indices hit 0
        elif ia <= 0 and ib <= 0:
             ia = ib = 0
        elif ia <= 0:
            ib-=1
            ia = 0
            nottakensum = float(''-inf'')
        elif ib <= 0:
            ia-=1
            ib = 0
            nottakensum = float(''-inf'')
        #lookahead cases
        elif optionone > optiontwo: 
           #then choose the first option as our next pair
           nottakensum,nottakenindices = optiontwo,(ia-1,ib)
           ib-=1
        elif optionone < optiontwo: # choose the second
           nottakensum,nottakenindices = optionone,(ia,ib-1)
           ia-=1
        #next two cases apply if options are equal
        elif a[ia] > b[ib]:# drop the smallest
           nottakensum,nottakenindices = optiontwo,(ia-1,ib)
           ib-=1
        else: # might be equal or not - we can choose arbitrarily if equal
           nottakensum,nottakenindices = optionone,(ia,ib-1)
           ia-=1
        #+2 - one for zero-based, one for skipping the 1st largest 
        data = (i+2,a[ia],b[ib],a[ia]+b[ib],ia,ib)
        narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
        print (narrative) #this will work in both versions of python
        if ia <= 0 and ib <= 0:
           raise ValueError("Both arrays exhausted before Kth (%sth) pair reached"%data[0])
    return data, narrative

Para aquellos que no tienen python, aquí hay una idea: http://ideone.com/tfm2MA

En el peor de los casos, tenemos 5 comparaciones en cada iteración y K-1, lo que significa que este es un algoritmo O (K).

Ahora, podría ser posible explotar información acerca de las diferencias entre los valores para optimizar esto un poco, pero esto logra el objetivo.

Aquí hay una implementación de referencia (no O(K) , pero siempre funcionará, a menos que haya un caso de esquina con casos donde los pares tengan sumas iguales):

import itertools
def refkth(a,b,k):
    (rightia,righta),(rightib,rightb) = sorted(itertools.product(enumerate(a),enumerate(b)), key=lamba((ia,ea),(ib,eb):ea+eb)[k-1]
    data = k,righta,rightb,righta+rightb,rightia,rightib
    narrative = "%sth largest pair is %s+%s=%s, with indices (%s,%s)" % data
    print (narrative) #this will work in both versions of python
    return data, narrative

Esto calcula el producto cartesiano de los dos arreglos (es decir, todos los pares posibles), los ordena por suma y toma el elemento kth. La función de enumerate decora cada elemento con su índice.

Answer 4

EDITAR: Esto no funciona. Les dejo la respuesta, ya que aparentemente no soy el único que podría tener este tipo de idea; Vea la discusión a continuación. Un contraejemplo es x = (2, 3, 6), y = (1, 4, 5) y k = 3, donde el algoritmo da 7 (3 + 4) en lugar de 8 (3 + 5).

Sean x e y las dos matrices, ordenadas en orden decreciente; Queremos construir la K mayor suma.

Las variables son: i el índice en la primera matriz (elemento x[i] ), j el índice en la segunda matriz (elemento y[j] ), y k el "orden" de la suma ( k en 1..K ), en el sentido de que S(k)=x[i]+y[j] será la suma k mayor que satisfaga sus condiciones (este es el bucle invariante).

Comience desde (i, j) igual a (0, 0) : claramente, S(1) = x[0]+y[0] .

para k de 1 a K-1 , haz:

• si x[i+1]+ y[j] > x[i] + y[j+1] , entonces i := i+1 ( j no cambia); de lo contrario j:=j+1

Para ver que funciona, considera que tienes S(k) = x[i] + y[j] . Entonces, S(k+1) es la suma más grande que es menor (o igual) a S(k) , y como por lo menos un elemento ( i o j ) cambia. No es difícil ver que exactamente uno de i o j debería cambiar. Si i cambia, la suma mayor que puede construir que es menor que S(k) es estableciendo i=i+1 , porque x está disminuyendo y todas las x[i''] + y[j] con i'' < i son mayor que S(k) . Lo mismo se aplica a j , que muestra que S(k+1) es x[i+1] + y[j] o x[i] + y[j+1] .

Por lo tanto, al final del bucle encontraste la suma K -th mayor.

Answer 5

Empiezo con un algoritmo simple pero no bastante lineal. Elegimos algún valor entre array1[0]+array2[0] y array1[N-1]+array2[N-1] . Luego, determinamos cuántas sumas de pares son mayores que este valor y cuántas de ellas son menores. Esto se puede hacer mediante la iteración de las matrices con dos punteros: el puntero a la primera matriz se incrementó cuando la suma es demasiado grande y el puntero a la segunda matriz disminuyó cuando la suma es demasiado pequeña. Repitiendo este procedimiento para diferentes valores y utilizando la búsqueda binaria (o la búsqueda binaria de un lado) podríamos encontrar Kth suma más grande en tiempo O (N log R), donde N es el tamaño de la matriz más grande y R es el número de valores posibles entre la array1[N-1]+array2[N-1] y array1[0]+array2[0] . Este algoritmo tiene una complejidad de tiempo lineal solo cuando los elementos de la matriz son números enteros delimitados por pequeñas constantes.

El algoritmo anterior puede mejorarse si detenemos la búsqueda binaria tan pronto como el número de sumas de pares en el rango de búsqueda binaria disminuya de O (N ² ) a O (N). Luego llenamos la matriz auxiliar con estas sumas de pares (esto puede hacerse con un algoritmo de dos puntos ligeramente modificado). Y luego usamos el algoritmo de selección rápida para encontrar la suma más grande de Kth en esta matriz auxiliar. Todo esto no mejora la complejidad del caso más desfavorable porque todavía necesitamos pasos binarios de búsqueda O (registro R). ¿Qué sucede si mantenemos la parte de selección rápida de este algoritmo pero (para obtener el rango de valores adecuado) utilizamos algo mejor que la búsqueda binaria?

Podríamos estimar el rango de valores con el siguiente truco: obtenga cada segundo elemento de cada matriz e intente encontrar la suma del par con rango k/4 para estas medias matrices (utilizando el mismo algoritmo de forma recursiva). Obviamente, esto debería dar alguna aproximación para el rango de valores necesarios. Y, de hecho, la variante ligeramente mejorada de este truco proporciona un rango que contiene solo elementos O (N). Esto se demuestra en el siguiente documento: "Selección en X + Y y matrices con filas y columnas ordenadas" por A. Mirzaian y E. Arjomandi . Este documento contiene una explicación detallada del algoritmo, la prueba, el análisis de complejidad y el pseudocódigo para todas las partes del algoritmo, excepto la selección Quickselect . Si se requiere complejidad lineal en el peor de los casos, Quickselect puede aumentarse con el algoritmo Mediana de medianas .

Este algoritmo tiene complejidad O (N). Si una de las matrices es más corta que la otra (M <N), podemos suponer que esta matriz más corta se extiende al tamaño N con algunos elementos muy pequeños para que todos los cálculos en el algoritmo utilicen el tamaño de la matriz más grande. En realidad, no necesitamos extraer pares con estos elementos "agregados" y enviarlos a selección rápida, lo que hace que el algoritmo sea un poco más rápido pero no mejora la complejidad asintótica.

Si k <N podríamos ignorar todos los elementos de la matriz con un índice mayor que k. En este caso la complejidad es igual a O (k). Si N <k <N (N-1) solo tenemos mejor complejidad que la solicitada en OP. Si k> N (N-1), deberíamos resolver el problema opuesto: k''th suma más pequeña.

Subí la implementación simple de C ++ 11 a ideone . El código no está optimizado y no ha sido probado a fondo. Traté de hacerlo lo más cerca posible para pseudocodificar en papel vinculado. Esta implementación utiliza std::nth_element , que permite una complejidad lineal solo en promedio (no en el peor de los casos).

Un enfoque completamente diferente para encontrar la suma K''th en el tiempo lineal se basa en la cola de prioridad (PQ). Una variación es insertar el par más grande en PQ, luego quitar repetidamente la parte superior de PQ y en su lugar insertar hasta dos pares (uno con índice decrementado en una matriz, otro con índice decrementado en otra matriz). Y tomar algunas medidas para evitar la inserción de pares duplicados. Otra variación es insertar todos los pares posibles que contengan el elemento más grande de la primera matriz, luego eliminar repetidamente la parte superior de PQ y en su lugar insertar el par con el índice disminuido en la primera matriz y el mismo índice en la segunda matriz. En este caso, no hay necesidad de preocuparse por los duplicados.

OP menciona la solución O (K log K) donde PQ se implementa como max-heap. Pero en algunos casos (cuando los elementos de la matriz son enteros distribuidos uniformemente con un rango limitado y la complejidad lineal es necesaria solo en promedio, no en el peor de los casos), podemos usar la cola de prioridad O (1), por ejemplo, como se describe en este documento: " Una cola de prioridad O (1) de complejidad para simulaciones de dinámica molecular impulsadas por eventos "por Gerald Paul . Esto permite O (K) complejidad de tiempo esperado.

La ventaja de este enfoque es la posibilidad de proporcionar primeros elementos K en orden ordenado. Las desventajas son una elección limitada del tipo de elemento de la matriz, algoritmo más complejo y más lento, peor complejidad asintótica: O (K)> O (N).

Answer 6

[2, 3, 5, 8, 13]
[4, 8, 12, 16]

Combine las 2 matrices y anote los índices en la matriz ordenada. Aquí se ve la matriz de índice (comenzando desde 1 no 0)

[1, 2, 4, 6, 8] [3, 5, 7, 9]

Ahora empieza de punta y haz tuplas. Suma los elementos en la tupla y elige la quinta suma más grande.