java - tutorial - para que se usa elastic search

Combinación y reordenación eficiente de listas ordenadas (7)

Esta no es la clásica pregunta de listas "fusionando dos ordenadas", que es bastante trivial en tiempo lineal.

Lo que trato de hacer es fusionar dos listas de pares (key, value) , ya ordenados por value , donde hay objetos con la misma key en ambas listas: dichos objetos deben tener su value s fusionado (agregado), que puede cambiar su orden de clasificación Principalmente estoy interesado en cómo el tipo se puede realizar de manera eficiente utilizando la información de las listas ya ordenadas, ya que el género es la parte más lenta de este algoritmo.

Tomemos un ejemplo concreto. Imagina una List de objetos Student :

class Student { final String name; final int score; ... }

Dado como entrada dos List<Student> ordenados por score , me gustaría crear una nueva lista fusionada de estudiantes, donde cualquier estudiante (identificado por Student.name ) que aparece en ambas listas aparece una vez en la lista final, con un puntaje igual a la suma de su puntaje en ambas listas. Las listas originales deben dejarse sin modificaciones.

P.ej,

List 1: {"bob", 20} {"john", 15} {"mark", 14} List 2: {"bill", 11} {"mark", 9} {"john", 1} Result: {"mark", 23} {"bob", 20} {"john", 16} {"bill", 11}

La fusión misma (identificando estudiantes que aparecen en ambas listas) se puede hacer en el tiempo O (1) esperado utilizando cualquier estructura de búsqueda / inserción O (1) como HashMap . Lo que más me interesa es el paso de ordenación (aunque no excluyo las soluciones que fusionan y clasifican al mismo tiempo).

La cuestión, sin embargo, es ¿cómo puedo reorganizar de manera eficiente una lista de este tipo? El orden de las listas existentes pone claramente algunas limitaciones en la posición final de los elementos en la lista fusionada. Por ejemplo, si un estudiante está en la posición i en la primera lista j en la segunda, debe aparecer entre los primeros estudiantes i + j en la lista combinada por un argumento simple que analiza la cantidad máxima de estudiantes que podrían tener una puntuación más alta . Sin embargo, no está claro si esta información sería útil para ordenar la lista.

Puede suponer que en muchos casos los estudiantes que obtienen puntajes altos en una lista obtienen puntajes altos en la otra. El algoritmo debería funcionar cuando ese no sea el caso, pero le brinda información adicional acerca de la distribución que puede ser útil, además del hecho de que las listas ya están ordenadas.

Parece que este tipo de operación sería común para cualquier tipo de implementación de query + sorting distribuida. Por ejemplo, imagine un tipo de consulta de tipo "seleccionar estado, contar (*) agrupar por estado" contra un sistema distribuido (para contar el número de registros en cada estado); naturalmente, obtendría una lista ordenada de (estado, recuento ) Objetos devueltos desde cada nodo, y luego desearía fusionarlos y reordenarlos durante la operación de reducción. Parece una tontería tirar todo el trabajo ya hecho en los nodos distribuidos.

Notas cuantitativas

Me interesa el caso en el que las listas que se fusionarán y reordenarán serán pequeñas: generalmente alrededor de 256 entradas. El rango de puntaje varía, de 0 a 100 en algunos casos, hasta aproximadamente 0 - 10,000,000 en otros. Por supuesto, dada la pequeña cantidad de elementos, cada operación será rápida en tiempo absoluto, incluso con algoritmos ingenuos, pero se repite miles de millones de veces.

De hecho, una de las siguientes respuestas ha demostrado que no se puede, en general, hacer esto mejor que una ordenación simple para aumentar el tamaño de las listas (es decir, tomando n como el tamaño de la lista combinada), pero en realidad estoy más interesado haciendo esto muchas veces, para listas de tamaño fijo, con buen desempeño empírico.

Mantenga un mapa que mapee algo exclusivo de la información real del estudiante.
Map<String, Student> scores = new HashMap<>();
Itere a través de todas las listas y colóquelas en el mapa de puntajes
for (Student s : list1) { if (scores.containsKey(s.name)) { scores.put(s.name, s.score + scores.get(s.name)); } else { scores.put(s.name, s.score); } }
Ordene entrySet usando las secuencias de Java 8
scores.entrySet() .stream() .sorted((s1, s2) -> (s2.getValue().score - s1.getValue().score) .map(s1 -> s1.getValue()) .collect(Collectos.toList());

Esto sigue siendo O(N Log N)

No puede ordenarlo utilizando el algoritmo de combinación estándar porque las listas contienen nombres cuya posición no es la misma. El algoritmo de combinación estándar no procesa el mismo elemento dos veces. Después de encontrar el duplicado y agregar el puntaje del estudiante, debe volver a ordenarlo. Está rompiendo la condición previa para el tipo de combinación que ambas listas están ordenadas en todo momento por sus valores.

(Descartar para fusionar primero y luego volver a clasificar,) Mi primera puñalada sería declarar las listas de entrada ordenadas (semi-estáticas) colas de prioridad y proceder en dos fases. Para evitar una ambigüedad en el término fusión , llamaré crear / alterar un objeto para representar los valores de "objetos comunes" combinación / combinación ; para reducir el desorden, denotaré la cola de prioridad PQ.

identificar objetos que aparecen en ambas / más de una "cola de entrada"
(en una forma de interés secundario aquí)
- combine (probablemente invalidando la posición en cualquier lista),
- ponerlos en otro PQ (dinámico) (si es necesario)
- eliminar / invalidar en la (s) cola (s) de entrada donde ya no estarán.
Combina las PQ de la manera habitual

Esto debería funcionar en tiempo lineal en el número n de objetos, más O (c log c) para c objetos "comunes" donde el objeto combinado estaría fuera de secuencia en lugar de cualquier objeto combinado. (... dado el tiempo constante esperado para (identificar y) combinar un (conjunto de) objeto (s) común (s) (ver comentario sobre O (1) esperado en la pregunta))
Entonces, me temo que no aborda correctamente el punto principal:

¿Hay alguna manera de aprovechar la clave final para ser un (lineal, monótona)
combinación de al menos una secuencia ordenada y "otros valores"?
(Con muchas entradas comunes, pensando en todo ).

Si la combinación disminuye la prioridad monótonamente (en el ejemplo, la adición de valores de puntuación (positivos) aumenta la prioridad), prescinde de una fase combinada y combine objetos al fusionar PQ, lo que puede reducir la memoria y el tiempo necesarios.
De lo contrario , elija un PQ para quitar objetos (disminuyendo la prioridad), para combinar potencialmente con otros objetos.
El "peor caso" parecería prioridad de los objetos combinados que no muestran correlación: me temo que la respuesta es
en general, no . (ver la respuesta del usuario2570465 para un argumento explícito)
(como señala BeeOnRope , la (secuencia de) los objetos escogidos dominados en combinación (opción desventajosa) puede convertirse en un buen caso si se puede detectar y explotar).
Por otra parte, se puede esperar que la combinación (lineal, monótona) desvíe la distribución de claves incluso sin correlación (positiva) (asumida en la pregunta): asegúrese de utilizar una implementación de PQ (dinámica) donde la inserción sea el mejor caso en orden que lo peor:
Por un lado, toma un montón implícito en una matriz (hijos del elemento en el índice i están en 2i y 2i + 1 (o 2i + 1 & 2i + 2 "no desperdicia el elemento 0", pero un poco más de manipulación del índice):
solo añada elementos (con una distribución sesgada a prioridad decreciente ) hasta el final:
el número esperado de intercambios con el padre está por debajo de 1 (sería casi 1 sin sesgo).

Intentalo:

// Clase Estudiante modificado.

public class Student { String name = ""; int score = 0; public Student(String name, int score) { this.name = name; this.score = score; } @Override public boolean equals(Object v) { if (v instanceof Student) { return this.name.equals(((Student) v).name); } else if (v instanceof String) { return this.name.equals(String.valueOf(v)); } else { return false; } } @Override public int hashCode() { int hash = 7; hash = 67 * hash + Objects.hashCode(this.name); return hash; } }

// Clase CustomComparator para ordenar una lista por objeto o STRI

public class CustomComparator implements Comparator<Object> { public int orderby = 0; @Override public int compare(Object o1, Object o2) { Student st1 = (Student)o1; Student st2 = (Student)o2; if (orderby==0){ //order by name. return st1.name.compareTo(st2.name); }else{ //order by score. Integer a=st1.score; Integer b = st2.score; return a.compareTo(b); } } }

//Ejemplo

List<Student> A = new ArrayList<Student>(); A.add(new Student("bob", 20)); A.add(new Student("john", 15)); A.add(new Student("mark", 14)); List<Student> B = new ArrayList<Student>(); B.add(new Student("bill", 11)); B.add(new Student("mark", 9)); B.add(new Student("john", 1)); List<Student> merge = new ArrayList<Student>(); merge.addAll(A); merge.addAll(B); //Copy. List<Student> result = new ArrayList<Student>(); for (Student st : merge) { if (result.contains(st)) { for (Student r : result) { if (r.equals(st)) { System.out.println(st.score + " > " +r.score); //Se the best score if (st.score > r.score) { r.score = st.score; break; } } } } else { result.add(st); } } //Sort result by name. CustomComparator comparator = new CustomComparator(); comparator.orderby=0; //1 sort by score. Collections.sort(result, comparator); for (Student r : result) { System.out.println(r.name + " = " + r.score); }

// El ejemplo resultado:

factura = 11 | bob = 20 | john = 15 | marca = 14

Me parece que cualquier solución generalmente debe caer en la categoría de complejidad O (n * log (n)) (con n = longitud (L1) + longitud (L2), o n = max (longitud (L1), longitud ( L2))).

Mi algoritmo básico sería el siguiente

Let''s use two intermediate structures: - a TreeSet R, which guarantees ordering by rank, - an HashMap M, which guarantees constant time insertion and retrieve Call R''s size n 1 for each student in each list 1.1 find the student in M by name (O(1)). 1.2 if the student is found 1.2.1 find the student in R by its rank (O(log(n)). 1.2.2 remove the student from R (O(log(n)) 1.2.3 update the student rank 1.3 else 1.3.1. put the student in M O(1) 1.4 put the student in R (O(log(n)) 2 At the end (if needed) transform the TreeSet in a list

La complejidad total O es O (n * log (n)),

Suponiendo que L1 es la más larga de las 2 listas, una pequeña optimización sería evitar encontrar al estudiante al atravesar L1, en este caso la complejidad O es la misma, pero tendrá menos operaciones en absoluto. El mejor caso es, por supuesto, cuando Len (L1) >> Len (L2).

Puede haber soluciones más complejas o mejores estructuras de datos para reducir el número de operaciones, pero no creo que haya una mejor complejidad O, ya que básicamente tienes 2 posibilidades

1- mantener la lista de resultados ordenada, por lo que escanear listas, buscar coincidencias y recalcular la posición cada vez

2- Usando un mapa intermedio para reducir la complejidad de encontrar coincidencias, luego ordena el resultado

Ambas posibilidades se calculan generalmente en O (n * log (n))

Parece que necesitas usar un algoritmo de ordenación adaptativo .

"Un algoritmo de ordenamiento pertenece a la familia de ordenamiento adaptativo si aprovecha el orden existente en su entrada. Se beneficia de la preclasificación en la secuencia de entrada, o una cantidad limitada de desorden para varias definiciones de medidas de desorden, y ordena más rápido. la clasificación generalmente se realiza modificando los algoritmos de clasificación existentes ". - Artículo de Wikipedia vinculado anteriormente.

Los ejemplos incluyen sorting de inserción y Timsort; ver el artículo anterior para más. Tenga en cuenta que en Java 8, el método de la biblioteca Arrays.sort(Object[]) utiliza un Timsort modificado.

No conozco ningún algoritmo publicado que trate los requisitos específicos de su ejemplo, pero he aquí una idea:

Realice una fusión clásica en las dos listas de entrada L1 y L2:
- Cuando fusiona un par de objetos y cambia las claves que determinan el orden, coloque el objeto fusionado en la lista temporal A.
- De lo contrario, coloque los objetos en la lista temporal B ... que permanecerá ordenada.
Ordene la lista temporal A.
Fusionar listas A y B.

Asumiendo que:

las longitudes de las listas originales L1 y L2 son M & N, respectivamente, y
el número de objetos fusionados cuyas claves cambiaron es R (que es menor que max (M, N)),

entonces la complejidad total es O (M + N + RlogR). Si R es pequeño en relación con M + N, entonces esto debería ser una mejora.

En su ejemplo, cada caso donde hay una coincidencia entre elementos en las listas de entrada es probable que mueva el elemento en el orden. Si mueve el elemento, se moverá a más adelante en el orden (y nunca antes). Entonces, otra idea es hacer una fusión tripartita entre las 2 listas originales y una cola de prioridad. Cuando obtiene una coincidencia, combina los recuentos y agrega el resultado a la cola de prioridad.

La complejidad es similar a la anterior, pero se evita el pase adicional para fusionar las listas. Y también el RlogR convierte en RlogA donde A es el tamaño promedio de la cola de prioridad.

Tenga en cuenta que estoy especialmente interesado en el caso en que R es aproximadamente igual a max (M, N), y también M == N.

(¡No lo mencionó en su pregunta! ¡Y, de hecho, no tiene ningún sentido que R sea> min (M, N)!)

En ese caso, tal vez solo use la cola de prioridad como clasificador incremental. Tire todos los registros combinados y todos los registros que no se puedan combinar en la cola, y extraiga nuestros registros si tienen una clave / puntaje menor que los encabezados actuales de las dos listas. Suponiendo que M y N son las longitudes de lista, y A es el tamaño de cola de prioridad promedio, entonces la complejidad es max (M, N) * log A). Si esto es una mejora en el reordenamiento simple dependerá de si el promedio A es significativamente menor (en términos de Big O) que máximo (M, N). Eso dependerá de las entradas ... y de la función de fusión.

El número (N) varía, pero de 256 a 1,000 es típico. Tal vez tanto como 10,000.

Para las listas de ese tamaño típico, está abajo en un nivel donde el análisis de complejidad no va a ser útil. Pero también, está abajo en un nivel donde la optimización no tiene sentido ... a menos que esté haciendo la operación muchas, muchas veces, o con un "presupuesto de tiempo ajustado".

Todo esto es muy aproximado, y mis matemáticas son "incompletas" en el mejor de los casos.

Una investigación adecuada implicaría cientos de horas para investigar, codificar, probar, comparar, analizar diversas alternativas ... y probablemente aún recibamos la respuesta de que depende del tamaño y la distribución del conjunto de datos de entrada.

Parece que quieres una combinación de O (n) como lo hacen con el tipo de fusión. Creo que tengo malas noticias para ti. Voy a (afortunadamente) demostrar que no se puede hacer mejor que O (nlog (n)) para el problema generalizado (por lo tanto, solo debe usar cualquiera de las soluciones O (nlog (n)) óptimas presentadas por otros ) Primero, comenzaré con la intuición de por qué este es el caso, y luego escribiré una prueba informal.

Intuición

La idea es convertir el problema de ordenar una lista en tu problema y mostrar que si puedes resolver tu problema más rápido que O (nlog (n)), entonces puedo ordenar cualquier lista más rápido que O (nlog (n)), que sabemos que es falso Simplemente trabajaremos con enteros para mantener las cosas simples.

Supongamos que tiene una secuencia extraña para ordenar: X = 1, 3, 2, -10, 5, 4, 7, 25 . Ahora construiré dos listas, Dec y Inc.. Comienzo con 1 = 1 + 0 (es decir, x_1 = x_1 + 0 ). Luego, después de eso, si x_{i-1} -> x_i es un aumento, restar 1 de mi valor en Dec y calcular el valor necesario en Inc para sumar x_i . Si x_{i-1} -> x_i es una disminución, entonces agrego 1 a mi valor en Inc y calculo el valor necesario en Dec para sumar a x_i . Aplicamos este algoritmo a la secuencia en la siguiente tabla:

idx x Dec Inc ---------------------- 1 | 1 = 1 + 0 2 | 3 = 0 + 3 3 | 2 = -2 + 4 4 | -10 = -15 + 5 5 | 5 = -16 + 21 6 | 4 = -18 + 22 7 | 7 = -19 + 23 8 | 25 = -20 + 45

Tenga en cuenta que puedo convertir de ordenar a su problema en O (n) - nota: invertir Inc en O (n) tiempo para obtener dos secuencias decrecientes. Entonces podemos ingresar a su problema

A = {(1, 1), (2, 0), (3, -2), (4, -15), (5, -16), (6, -18), (7, -19), (8, -20)} B = {(8, 45), (7, 23), (6, 22), (5, 21), (4, 5), (3, 4), (2, 3), (1, 0)}

Ahora, si puede combinar A y B en orden ordenado por la suma de sus valores (segundo elemento en los pares ordenados), y obtenga algo como

C = {(8, 25), (7, 7), (5, 5), (6, 4), (2, 3), (3, 2), (1, 1), (4, -10)

entonces esencialmente has hecho un argsort (ordenar por índice) de la secuencia inicial x_i . Entonces, si resuelve su problema más rápido que O (nlog (n)), entonces puedo ordenar más rápido que O (nlog (n)) resolviendo su problema primero y luego convirtiendo la solución en mi problema de ordenar una lista. En particular, ordenaría con complejidad O (n) + O (complejidad para resolver su problema)

Declaración para ser probada

Deje que sus dos listas de valores clave sean

A = [(ka_i, va_i) | i = 1..n] B = [(kb_i, vb_i) | i = 1..m]

ordenados en orden decreciente de valor. No puedes encontrar la lista combinada

C = [(ka_i, va_i + va_j) | ka_i = kb_j]

en un tiempo más rápido que O (nlog (n)).

Esquema de prueba

La única suposición que hace esta prueba es que no puede ordenar una lista más rápido que el tiempo O (nlog (n)) y esta prueba continuará proporcionando una reducción que se ejecute en O (n) desde ordenar cualquier lista arbitraria a su problema.

En esencia, mostraremos que si resolvemos su problema más rápido que O (nlog (n)), también podemos ordenar cualquier lista arbitraria más rápido que O (nlog (n)). Y ya sabemos que es imposible ordenar una lista más rápido que nlog (n), por lo que su solución deseada también debe ser imposible.

Detalles de la prueba

Para simplificar, tomaremos ordenar una lista de enteros. Deje S = x_1, x_2, ..., x_n ser cualquier secuencia de enteros. Ahora construiremos dos listas, Dec y Inc.

Tenemos tres restricciones:

Inc está aumentando estrictamente
Dec está disminuyendo estrictamente
En la iteración i del algoritmo, Inc[j] + Dec[j] = x_j for all j = 1..i-1

Como sus nombres implican, Dec disminuirá estrictamente y Inc aumentará estrictamente. Mantendremos la invariante que x_i = Dec[i] + Inc[i] for i = 1..n

Aquí está la reducción:

# (Assume 1-indexed lists) 1. Initialize Inc = [x_1] and Dec = [0] 2. For i = 2..n: a. if x[i] > x[i-1] then Dec.append(Dec[i-1] - 1) Inc.append(x_i - Dec[i]) else # We must have x[i] <= x[i-1] Inc.append(Inc[i-1] + 1) Dec.append(x_i - Inc[i]) 3. Create list A and B: A = [(i, Dec[i]) | i = 1..n] B = [(i, Inc[i]) | i = 1..n] 4. B = reverse(B) # Reverse B because B was in increasing order and we # need both lists to be in decreasing order 5. A and B are inputs to your algorithm. If your algorithm can combine A and B into sorted order, then we have also sorted S (via argsort on the keys).

Probablemente también esté hambriento de una prueba de que mi método ad hoc de elegir aumentar Inc en 1 o disminuir Dec en 1 funciona. Bueno, aquí hay una "prueba" informal (puedes formalizarla usando la inducción):

Caso x_ {i}> x_ {i-1}

Recuerde que, en este caso, optamos por decrementar Dec en 1. Nos da que x_{i} > x_{i-1} y sabemos que Dec_{i-1} + Inc_{i-1} = x_{i-1} . También podemos decir que (Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1} .

Como x_{i} > x_{i-1} , debemos tener x_{i} >= x_{i-1} + 1 . Por lo tanto, x_{i} >= (Dec_{i-1} - 1) + (Inc_{i+1} + 1) . Por lo tanto, si solo disminuimos Dec en 1, nos veremos obligados a agregar al menos 1 a Inc, por lo que Inc sigue aumentando estrictamente.

Caso x_ {i} ≤ x_ {i-1}

Recuerde que, en este caso, optamos por incrementar Inc en 1. Nos da que x_{i} <= x_{i-1} y sabemos que Dec_{i-1} + Inc_{i-1} = x_{i-1} . También podemos decir que (Dec_{i-1} - 1) + (Inc_{i+1} + 1) = x_{i-1} y dado que x_{i} <= x_{i-1} , debe sea el caso que (Dec_{i-1} - 1) + (Inc_{i+1} + 1) <= x_{i} . Por lo tanto, si agregamos 1 a Inc, estamos seguros de que debemos restar al menos 1 de Dic.

Conclusión

Su problema no puede hacerse más rápido que O (nlog (n)). Le conviene combinar en un HashMap y luego ordenar sus elementos en O (nlog (n)) porque es imposible encontrar una solución más rápida.

No dude en comentar, sin embargo, si encuentra un problema con la reducción o tiene preguntas. Estoy bastante seguro de que es correcto. Por supuesto, si me equivoco al ordenar que no sea más rápido que O (nlog (n)), esta prueba se desmorona, pero la última vez que lo verifiqué, alguien ya probó que O (nlog (n)) era la complejidad más rápida para clasificar . Comente si prefiere una reducción formal. Se está haciendo tarde para mí y me salté algunas "formalizaciones", pero puedo editarlas cuando tenga oportunidad.

Si codifica el algoritmo para crear la reducción, puede obtener una mejor comprensión.

Además: consulte esta publicación si desea una explicación para O (nlog (n)) vinculada a la ordenación. ¿Cuáles son las reglas para la "barrera Ω (n log n)" para los algoritmos de clasificación?

Según lo veo, el hecho de que la lista ya esté ordenada por puntaje no ayuda, ya que primero debemos fusionar los puntajes.

Además, si utilizo hash-map puede proporcionar una búsqueda de O (1), según mi entender, la implementación subyacente implicará que, en términos de rendimiento, que incluye la creación del hashmap, la eficiencia no será tan buena (en comparación con el de abajo).

El enfoque sería el siguiente:

Aplica inplace-binary-most-significant-bit-radix-sort en List-1 y List-2 combinados.
Los estudiantes cuya puntuación aparezca dos veces serán adyacentes, fusionarán esas entradas.
Por último, utilice inplace-binary-most-significant-bit-radix-sort (como se indica más arriba) en los puntajes de los alumnos de la lista combinada (de forma que el par de puntaje y alumno se reorganice según corresponda).

Actualización n. ° 1: el orden en el paso 1 está en el nombre del estudiante.