ruta operaciones mas investigacion grafos ejercicios corto corta algoritmo java arrays algorithm

java - operaciones - camino mas corto dijkstra c++



Algoritmo más rápido para encontrar un elemento único entre dos matrices? (9)

EDITAR : Para cualquier persona nueva en esta pregunta, he publicado una respuesta aclarando lo que estaba pasando. La respuesta aceptada es la que mejor responde a mi pregunta tal como se publicó originalmente, pero para obtener más información, consulte mi respuesta.

NOTA : Este problema originalmente era pseudocódigo y listas usadas. Lo he adaptado a Java y arreglos. Así que, si bien me gustaría ver alguna solución que utilice trucos específicos de Java (o trucos en cualquier idioma), solo recuerda que el problema original es independiente del idioma.

El problema

Digamos que hay dos matrices de enteros sin clasificar b , con la repetición de elementos permitida. Son idénticos (con respecto a los elementos contenidos), excepto que una de las matrices tiene un elemento adicional. Como ejemplo:

int[] a = {6, 5, 6, 3, 4, 2}; int[] b = {5, 7, 6, 6, 2, 3, 4};

Diseñe un algoritmo que tome como entrada estas dos matrices y genere el único entero único (en el caso anterior, 7).

La solución (hasta ahora)

Se me ocurrió esto:

public static int getUniqueElement(int[] a, int[] b) { int ret = 0; for (int i = 0; i < a.length; i++) { ret ^= a[i]; } for (int i = 0; i < b.length; i++) { ret ^= b[i]; } return ret; }

La solución "oficial" presentada en clase:

public static int getUniqueElement(int[] a, int[] b) { int ret = 0; for (int i = 0; i < a.length; i++) { ret += a[i]; } for (int i = 0; i < b.length; i++) { ret -= b[i]; } return Math.abs(ret); }

Entonces, ambos están conceptualmente haciendo lo mismo. Y dado que a es de longitud b es de longitud n, ambas soluciones tienen un tiempo de ejecución de O (m + n).

La pregunta

Más tarde, comencé a hablar con mi maestro y él insinuó que había una forma aún más rápida de hacerlo. Honestamente, no veo cómo; para saber si un elemento es único, parece que al menos deberías mirar cada elemento. Al menos eso es O (m + n) ... ¿no?

Entonces, ¿hay una manera más rápida? Y si es así, ¿qué es?

Digamos que hay dos matrices de enteros sin clasificar ayb, con la repetición de elementos permitida. Son idénticos (con respecto a los elementos contenidos), excepto que una de las matrices tiene un elemento adicional .

Puede observar que hice hincapié en dos puntos en su pregunta original, y estoy agregando una suposición adicional de que los valores no son cero .

En C #, puedes hacer esto:

int[, , , , ,] a=new int[6, 5, 6, 3, 4, 2]; int[, , , , , ,] b=new int[5, 7, 6, 6, 2, 3, 4]; Console.WriteLine(b.Length/a.Length);

¿Ver? Cualquiera que sea el elemento adicional , siempre lo sabrás dividiendo su longitud.

Con estas afirmaciones, no almacenamos las series de enteros dados como valores para las matrices, sino como sus dimensiones .

Como quiera que se proporcione la serie más corta de enteros, cuanto más tiempo uno tenga solo un entero adicional. Entonces, no importa el orden de los enteros, sin el extra, el tamaño total de estos dos conjuntos multidimensionales es idéntico. La dimensión extra multiplicada por el tamaño de la más larga, y para dividir por el tamaño de la más corta, sabemos cuál es el entero adicional.

Esta solución funcionaría solo para este caso en particular, ya que cité su pregunta. Es posible que desee portarlo a Java.

Esto es solo un truco, ya que pensé que la pregunta en sí misma es un truco. Definitivamente no lo consideraremos como una solución para la producción.

Cuidado, es incorrecto usar la notación O (n + m). No hay más que un parámetro de tamaño que es n (en el sentido asintótico, n y n + 1 son iguales). Deberías decir O (n). [Para m> n + 1, el problema es diferente y más desafiante].

Como señalaron otros, esto es óptimo ya que debe leer todos los valores.

Todo lo que puedes hacer es reducir la constante asintótica. Hay poco margen de mejora, ya que las soluciones obvias ya son muy eficientes. El único bucle en (10) es probablemente difícil de superar. Desenrollarlo un poco debería mejorar (ligeramente) al evitar una rama.

Si su objetivo es el rendimiento absoluto, entonces debe recurrir a soluciones no portátiles como la vectorización (utilizando las instrucciones AXV, 8 entradas a la vez) y la paralelización en multinúcleo o GPGPU. En una buena y antigua C sucia y un procesador de 64 bits, podría mapear los datos a una matriz de 64 bits de entrada y xo los elementos de dos pares a la vez;)

Este es probablemente el más rápido que puede hacerlo en Java utilizando la sugerencia de HotLick en los comentarios. Supone que b.length == a.length + 1 so b es la matriz más grande con el elemento extra "único".

public static int getUniqueElement(int[] a, int[] b) { int ret = 0; int i; for (i = 0; i < a.length; i++) { ret = ret ^ a[i] ^ b[i]; } return ret ^ b[i]; }

Incluso si no se puede hacer la suposición, puede expandirla fácilmente para incluir el caso donde a o b puede ser la matriz más grande con el elemento único. Sin embargo, sigue siendo O (m + n) y solo se reduce la sobrecarga de bucle / asignación.

Editar:

Debido a los detalles de la implementación del lenguaje, esta sigue siendo (sorprendentemente) la forma más rápida de hacerlo en CPython.

def getUniqueElement1(A, B): ret = 0 for a in A: ret = ret ^ a for b in B: ret = ret ^ b return ret

He probado esto con el módulo de tiempo y timeit encontrado algunos resultados interesantes. Resulta que el retr ret = ret ^ a es de hecho más rápido en Python que la abreviatura ret ^= a . También iterar sobre los elementos de un ciclo es mucho más rápido que iterar sobre los índices y luego realizar operaciones de subíndices en Python. Es por eso que este código es mucho más rápido que mi método anterior donde intenté copiar Java.

Supongo que la moraleja de la historia es que no hay una respuesta correcta porque la pregunta es falsa de todos modos. Como el OP señaló en otra respuesta más abajo, resulta que no se puede ir más rápido que O (m + n) en esto y su maestro simplemente estaba tirando de su pierna. Por lo tanto, el problema se reduce a encontrar la forma más rápida de iterar sobre todos los elementos en las dos matrices y acumular el XOR de todos ellos. Y esto significa que es completamente dependiente de la implementación del lenguaje, y usted tiene que hacer algunas pruebas y jugar para obtener la verdadera solución "más rápida" en cualquier implementación que esté usando, porque el algoritmo general no cambiará.

Esto es un poco más rápido:

public static int getUniqueElement(int[] a, int[] b) { int ret = 0; int i; for (i = 0; i < a.length; i++) { ret += (a[i] - b[i]); } return Math.abs(ret - b[i]); }

Es O (m), pero el orden no cuenta toda la historia. La parte de bucle de la solución "oficial" tiene aproximadamente 3 * m + 3 * n operaciones, y la solución ligeramente más rápida tiene 4 * m.

(Contando el bucle "i ++" y "i <a.length" como una operación cada uno).

-Alabama.

Muy bien, aquí vamos ... disculpas a todos los que esperan una solución más rápida. Resultó que mi maestra estaba divirtiéndose un poco conmigo y me perdí por completo lo que estaba diciendo.

Debería comenzar aclarando a qué me refería con:

insinuó que había una manera aún más rápida de hacerlo

La esencia de nuestra conversación fue esta: dijo que mi enfoque XOR era interesante, y hablamos durante un tiempo sobre cómo llegué a mi solución. Me preguntó si creía que mi solución era óptima. Dije que sí (por las razones que mencioné en mi pregunta). Luego me preguntó: "¿Estás seguro ?" con una mirada en su rostro, solo puedo describirlo como "presumido". Estaba vacilante, pero dije que sí. Me preguntó si podía pensar en una mejor manera de hacerlo. Yo estaba más o menos como "¿Quieres decir que hay una manera más rápida?" pero en lugar de darme una respuesta directa, me dijo que lo pensara. Yo dije que lo haría.

Así que lo pensé, seguro de que mi maestra sabía algo que yo no sabía. Y después de no pensar en nada por un día, vine aquí.

Lo que mi maestro realmente quería que yo hiciera era defender mi solución como óptima, no tratar de encontrar una solución mejor. Como él dijo: crear un buen algoritmo es la parte fácil, la parte difícil es probar que funciona (y que es lo mejor). Pensó que era bastante divertido que pasara tanto tiempo en Find-A-Better-Way Land en lugar de encontrar una simple prueba de O (n) que hubiera tomado mucho menos tiempo (terminamos haciéndolo, ver más abajo si estás interesado).

Así que supongo, gran lección aprendida aquí. Aceptaré la respuesta de Shashank Gupta porque creo que logra responder la pregunta original, aunque la pregunta era errónea.

Los dejaré con un pequeño y delicado diseño de Python que encontré mientras escribía la prueba. No es más eficiente pero me gusta:

def getUniqueElement(a, b): return reduce(lambda x, y: x^y, a + b)

Una "prueba" muy informal

Comencemos con las dos matrices originales de la pregunta, a y b :

int[] a = {6, 5, 6, 3, 4, 2}; int[] b = {5, 7, 6, 6, 2, 3, 4};

Aquí diremos que la matriz más corta tiene una longitud n , luego la matriz más larga debe tener una longitud n + 1 . El primer paso para probar la complejidad lineal es unir las matrices en una tercera matriz (la llamaremos c ):

int[] c = {6, 5, 6, 3, 4, 2, 5, 7, 6, 6, 2, 3, 4};

que tiene longitud 2n + 1 . ¿Por qué hacer esto? Bueno, ahora tenemos otro problema por completo: encontrar el elemento que aparece un número impar de veces en c (de aquí en adelante, "número impar de veces" y "único" significan lo mismo). Esta es una pregunta de entrevista muy popular y aparentemente es donde mi maestro tuvo la idea de su problema, por lo que ahora mi pregunta tiene algún significado práctico. ¡Hurra!

Supongamos que hay un algoritmo más rápido que O (n), como O (log n). Lo que esto significa es que solo accederá a algunos de los elementos de c . Por ejemplo, un algoritmo O (log n) solo debería verificar el registro (13) ~ 4 de los elementos en nuestra matriz de ejemplo para determinar el elemento único. Nuestra pregunta es, ¿es esto posible?

Primero, veamos si podemos salimos con la eliminación de cualquiera de los elementos (al "eliminar" me refiero a no tener que acceder). ¿Qué tal si eliminamos 2 elementos, para que nuestro algoritmo solo compruebe un subcampo de c con longitud 2n - 1 ? Esto sigue siendo una complejidad lineal, pero si podemos hacer eso, entonces tal vez podamos mejorarlo aún más.

Entonces, elijamos dos elementos de c completamente al azar para eliminarlos. En realidad, hay varias cosas que podrían suceder aquí, que resumiré en casos:

// Case 1: Remove two identical elements {6, 5, 6, 3, 4, 2, 5, 7, 2, 3, 4}; // Case 2: Remove the unique element and one other element {6, 6, 3, 4, 2, 5, 6, 6, 2, 3, 4}; // Case 3: Remove two different elements, neither of which are unique {6, 5, 6, 4, 2, 5, 7, 6, 6, 3, 4};

¿Cómo se ve nuestra matriz ahora? En el primer caso, 7 sigue siendo el elemento único. En el segundo caso, hay un nuevo elemento único, 5. Y en el tercer caso, ahora hay 3 elementos únicos ... sí, es un desastre total allí.

Ahora nuestra pregunta es: ¿podemos determinar el elemento único de c simplemente mirando esta submatriz? En el primer caso, vemos que 7 es el único elemento del subcampo, pero no podemos estar seguros de que sea también el elemento único de c ; los dos elementos eliminados podrían haber sido 7 y 1. Un argumento similar se aplica para el segundo caso. En el caso 3, con 3 elementos únicos, no tenemos forma de decir cuáles de los dos no son únicos en c .

Está claro que incluso con 2n - 1 accesos, simplemente no hay suficiente información para resolver el problema. Y entonces la solución óptima es lineal.

Por supuesto, una prueba real usaría la inducción y no utilizaría la prueba por ejemplo, pero se lo dejo a alguien más :)

Puede almacenar el recuento de cada valor en una colección, como una matriz o un mapa hash. O (n) luego puede verificar los valores de la otra colección y detenerse tan pronto como sepa que tiene una coincidencia errada. Esto podría significar que solo busca la mitad del segundo conjunto en promedio.

Simplemente no hay algoritmo más rápido. Los que se presentan en la pregunta están en O (n). Cualquier "truco" aritmético para resolver esto requerirá que al menos cada elemento de ambas matrices se lea una vez, por lo que permaneceremos en O (n) (o algo peor).

Cualquier estrategia de búsqueda que se encuentre en un subconjunto real de O (n) (como O (log n)) requerirá arreglos ordenados o alguna otra estructura ordenada por preconstrucción (árbol binario, hash). Todos los algoritmos de clasificación conocidos por la humanidad son al menos O (n * log n) (Quicksort, Hashsort) a un promedio que es peor que O (n).

Por lo tanto, desde un punto de vista matemático, no hay un algoritmo más rápido . Puede haber algunas optimizaciones de código, pero no importarán a gran escala, ya que el tiempo de ejecución crecerá linealmente con la longitud de la (s) matriz (es).

Suponiendo que solo se agregó un elemento, y las matrices fueron idénticas para comenzar, puede presionar O (log (base 2) n).

La razón es que cualquier matriz está sujeta a la búsqueda binariamente O (log n). Excepto que en este caso no está buscando un valor en una matriz ordenada, está buscando el primer elemento no coincidente. En tal circunstancia a [n] == b [n] significa que es demasiado bajo, y a [n]! = B [n] significa que puede ser demasiado alto, a menos que a [n-1] == b [n-1].

El resto es búsqueda binaria básica. Verifica el elemento medio, decide qué división debe tener la respuesta y haz una búsqueda secundaria en esa división.