¿Cuál es el algoritmo más rápido para encontrar el número más grande en una matriz sin clasificar?

Como otros lo han dicho … coincidiendo exactamente con su pregunta, solo hay un algoritmo que no es “estúpido”. Y eso va a través de la matriz de un elemento a la vez, haciendo un seguimiento del elemento más grande visto hasta el momento, cuando haya llegado al final (es decir, verificado cada elemento), ese valor que utilizó para realizar un seguimiento es el más grande. Por lo tanto, es O (N). Podría optimizarlo dividiéndolo efectivamente en porciones y hacer que varios núcleos trabajen en el problema en su porción, luego combinando el resultado, pero aún sería O (N). Cualquier otro algoritmo llevaría más tiempo, más recursos o no obtendrá el resultado correcto en todos los casos.

Sin embargo, generalmente es una muy mala idea mantener sus datos en arreglos sin clasificar. Casi siempre es una mejor idea usar una estructura de datos adecuada que permita búsquedas, actualizaciones e inserciones más rápidas. La matriz no ordenada puede formar parte de esta estructura de datos (por ejemplo, tener una estructura de índice de montaje lateral como la que obtiene en los archivos de la base de datos), o puede eliminarse (por ejemplo, un árbol binario). En casi todos estos casos, terminaría con una forma mucho más rápida de obtener el número más grande, sin mencionar ningún número en particular. Lo más probable es que supere cualquier tipo de optimización que pueda hacer en la búsqueda lineal normal mencionada anteriormente, en la mayoría de los casos, muchas veces mejor.

Entonces, dependiendo de por qué desea una respuesta aquí, el único momento en que debe estar satisfecho con la O (N) normal es si se trata de una pregunta en algún curso (por ejemplo, tarea), o si los datos son tan pequeños que no hacen mucha diferencia (por ejemplo, solo unos pocos megas, o incluso un puñado de conciertos en las computadoras de hoy), pero en ese caso, ¿por qué molestarse en preguntar más rápido de todos modos? En todos los demás casos, al menos debe preguntar por qué los datos no están ordenados y si hay algunos otros accesorios no mencionados que pueden ser de ayuda.

Al menos si se tratara de una pregunta de entrevista, recibiría una calificación negativa de mi parte si no pudiera responderla con el algoritmo O (N) (en realidad, detendría la entrevista allí y le diría: “Está desperdiciando Mi tiempo”). Pero si puede pedir cosas como “¿Por qué no ordenado?” o “¿Hay algún tipo de índice?” recibiría una marca positiva; de lo contrario, solo se marcará como cero (en el mejor de los casos).

Este es un ejemplo perfecto de por qué los algoritmos no deben estudiarse de forma aislada. Como mínimo, debe aprenderlos mientras aprende las estructuras de datos. Y así es como funciona la producción en el mundo real: no solo debe contentarse con un lote de datos “aleatorios”, al menos debe preguntar por qué. Lo más probable es que encuentre que esa información se busca varias veces, cada vez que resulta en una búsqueda O (N). Por lo tanto, si no se convierte en una estructura más adecuada, no es solo su pequeño rincón del programa el que sufre, es todo.

En realidad, si me encuentro con una matriz tan aleatoria sin extras para hacer que las búsquedas sean más eficientes, comenzaría a buscar a quien lo diseñó y le haría una pregunta muy pertinente. Me gusta: “¡Dame una razón convincente por la que estos datos no se pueden colocar en una estructura de árbol, en una tabla hash, o básicamente en cualquier otra cosa, PERO una matriz desordenada!”

Para cualquier algoritmo que requiera comparaciones, el problema es O ( n ), como han señalado muchos otros.

Aquí hay una versión del algoritmo “spaghetti” que podría implementarse en hardware: si tuviera los números representados en notación unaria y una CPU con suficientes registros para contener toda la matriz (que también requiere suficientes bits por registro para contener el número más grande) ), cargue los números en los registros y gire a la izquierda hasta que uno de los registros se desborde. El registro que se desborda tiene el mayor número. Esta solución requiere menos pasos para números más grandes y n pasos si el número más grande es uno, pero no depende de la cantidad de elementos en la matriz, hasta los límites del hardware. Para las matrices más grandes que el número de registros, repita los grupos de números que encajarán en los registros disponibles, luego aplique esta estrategia de forma recursiva hasta que termine con un solo número.

Para números demasiado grandes para caber en un solo registro, en el sistema descrito anteriormente, puede optimizar comenzando solo con esos números, que presumiblemente serían fáciles de identificar porque estarían almacenados en una parte diferente del hardware. Realmente, esto equivale a tener los números parcialmente ordenados de antemano.

Es posible que pueda aplicar parte de esta estrategia en un sistema informático estándar, si está utilizando un marco que admite aritmética de precisión arbitraria: comience considerando solo Bignums, que podrían almacenarse en una parte diferente de la memoria.

Este es un ejercicio para leer todos los datos. Necesita leer todo, y la operación que necesita hacer en todo (“max”) es trivial.

En otras palabras, su cuello de botella será E / S para cualquier conjunto de datos de tamaño no trivial. Suponiendo que una CPU moderna y rápida, un código tonto, incluso un código poco optimizado, debería ser capaz de mantenerse al día con prácticamente cualquier disco individual o cualquier cosa que no sea la conexión de red más rápida.

El caso limitante: si la matriz realmente está en RAM, probablemente necesitará múltiples subprocesos. DDR3-1333 te ofrece unos 10 GB / s teóricos. Para una CPU de 3.x GHz que es de aproximadamente 3 bytes por ciclo, lo que debería ser posible en un solo hilo con un poco de optimización, principalmente captación previa y vectorización. Por otro lado, es posible que tenga una RAM más rápida en configuraciones de canal dual / tri / quad, y eventualmente necesitará una cantidad muy pequeña de subprocesos que se ejecutan en diferentes núcleos para mantenerse al día.

Algunas personas mencionaron GPU, pero eso no será más rápido en una configuración típica de estación de trabajo a menos que los datos ya estén allí para empezar. ¡El problema es que la GPU no tiene acceso lo suficientemente rápido a la memoria principal! Una sola GPU con 16x PCIe 3.0 está limitada a alrededor de 16GB / s, que será aproximadamente el límite del rendimiento de un solo hilo en la CPU. Claro, la GPU en sí misma podrá hacer este cálculo sin sudar una vez que obtenga los datos, y la memoria de GPU de gama media / alta suele ser más rápida que la memoria principal, pero el punto aquí es que el cálculo no es el embotellamiento.

Peter de Vroede es correcto. La única forma de encontrar el valor más grande en una matriz no ordenada es mirar cada valor en la matriz.

Piénsalo de esta manera. Si te diera 100 fichas con un número aleatorio en cada tarjeta, ¿cómo encontrarías el número más grande? Tendrías que pasar por todas las cartas.

Entonces, si tenías N cartas, tienes que mirar todas las N de ellas. Entonces la complejidad del tiempo es O (N).

El tipo de algoritmo que hace esto se llama algoritmo de búsqueda lineal.

TENGA EN CUENTA: Algunas respuestas dadas aquí dicen que el procesamiento en paralelo encontraría el valor máximo más rápido. Esto es verdad. Pero no importa cuántos procesadores tenga, aún necesitará ‘observar’ cada valor. Entonces el número de operaciones sigue siendo O (N).

Para ver esto, piense en tener un número aleatorio en cada una de las 200 fichas. Si está tratando de encontrar el valor máximo, debe mirar todas las 200 cartas. Ahora, supongamos que reclutas a un amigo para que te ayude. Le das a tu amigo la mitad de las cartas, y cada uno de ustedes encuentra el máximo en su mitad. Compare estos y tendrá su respuesta. Sí, llevará la mitad del tiempo, pero tanto usted como su amigo verán 100 cartas, por lo que se están mirando las 200 cartas. Por lo tanto, el número de operaciones sigue siendo O (N).

Aquí hay un algoritmo relacionado e interesante.

Repase la primera mitad de los valores en la matriz y realice un seguimiento del mayor valor en la primera mitad, H. Luego, repase la segunda mitad de la matriz. Cuando (y si) encuentre un valor mayor que H, deténgase. Llamemos a esto G.

¿Cuál es la probabilidad de que G sea el mayor valor en la matriz?

Para que esto suceda, G debe estar en la segunda mitad de la matriz. Dado que los valores de la matriz son aleatorios, hay un 50% de posibilidades de que esto suceda.

Y luego, si el segundo mayor valor de la matriz está en la primera mitad, esto garantizaría que elegiríamos el mayor valor real.

La probabilidad de que el segundo mayor valor esté en la primera mitad también es del 50%. Entonces, la probabilidad de que el segundo mayor valor esté en la primera mitad y que el mayor valor esté en la segunda mitad es 50% x 50% = 25%.

Entonces, este algoritmo nos da al menos un 25% de encontrar el mayor valor en la matriz.

¿No me impresionó? Cuando vi esto por primera vez, lo estaba.

Al ajustar esto, puede aumentar sus posibilidades de encontrar el mayor valor a aproximadamente el 37%. Y solo tiene que mirar el primer tercio de la matriz para obtener esta probabilidad.

Admitelo. Eso es interesante.

¿Quieres los detalles sangrientos? Echa un vistazo a esta entrada de Wikipedia: El problema del secretario.

La forma más rápida sería saberlo antes de que lo desee; extienda la matriz para agregar maxItemIndex y / o maxItemValue.

Agregaría una sobrecarga a todas las escrituras y eliminaciones (debe verificar si acaba de agregar o eliminar el valor máximo), pero no tiene que hacer una búsqueda completa cada vez, lo que puede ser más eficiente (solo tiene que para comparar el valor máximo solo con los elementos agregados / eliminados, en lugar de hacer una búsqueda completa, importante si su conjunto de datos es grande, es decir, la interfaz de informes o la vista de agregación de datos grandes de tipo D3).

Si extender Array funcionará más rápido que simplemente haciendo una búsqueda completa del valor máximo cada vez que lo necesite, depende de la frecuencia con la que agregue nuevos datos a la matriz y con qué frecuencia necesita saber el valor máximo después de un cambio.

Por cierto, la solución práctica óptima sería usar una colección en lugar de una matriz, porque entonces puede enviar un evento maxValueChanged, especialmente importante si el cambio será asíncrono (es decir, proviene de la interacción del usuario y / o el cambio continuo de datos y estás haciendo un tablero en tiempo real).

Y, por último, puedes notar la diferencia entre las respuestas aquí de estudiantes de matemáticas y desarrolladores de aplicaciones 🙂

En teoría, es posible en el tiempo O (√n).
El único inconveniente es que esto requiere un hardware que no existe (todavía), es decir, una computadora cuántica. El enfoque es utilizar el algoritmo de Grover. Esto utiliza un estado de superposición que podría resolverse como cualquiera de los elementos. El sistema ejecuta este estado de superposición repetidamente a través de una operación cuántica que ajusta selectivamente la mezcla de modo que la respuesta correcta se convierta en la resolución probable.

La operación actúa en todos los n estados a la vez. Eso suena similar a la computación paralela, pero difiere radicalmente: en lugar de que varias piezas de hardware (por ejemplo, los 8 núcleos de CPU en mi escritorio) funcionen a la vez, esto usaría una sola pieza de hardware, trabajando en múltiples universos posibles.

NB: el algoritmo de Grover toma la superposición de todas las respuestas como punto de partida, por lo que para llegar a O (√n) suponemos que podemos crearlo rápidamente (es decir, sin necesidad de n pasos para armarlo). Incluso si tuviera una computadora cuántica, ingresar los datos probablemente implicaría trabajar con cada elemento.

Para las computadoras convencionales no cuánticas realmente existentes (es decir, si insiste en una respuesta sensata), entonces, como otros han dicho, debe mirar cada elemento, por lo que es O (n), aunque puede hacerlo en paralelo.

Respuestas interesantes Como Tom y otros dijeron, debes mirar cada valor para asegurarte de encontrar el más grande. Muchos dijeron “cambiar los parámetros de la pregunta” y ordenar la matriz; entonces solo obtendrías el primero o el último. Valerie señaló que MUMPS ordenará los datos por usted a medida que los agregue a la matriz. Independientemente de MUMPS u otros idiomas o de cambiar los parámetros, aún observa cada valor. Es solo una cuestión de si cada valor está marcado cuando agrega un elemento a la matriz o cuando intenta encontrar el más grande en la matriz. Muy cierto que si se ordena la matriz, existen algoritmos que son más rápidos que una búsqueda lineal que encuentra el punto de inserción para cada nuevo valor. Pero aún miró todos los valores al menos una vez para ordenar la matriz durante la construcción. Y si está creando una matriz ordenada, hay más tiempo de procesamiento dedicado a mantener esa matriz.

Considere una matriz ordenada simple y está agregando un nuevo segundo al valor más grande. Su inserción puede verificar los límites más grandes y más pequeños (dos comprobaciones) y luego elegir un punto de inicio (esta es una optimización con muchas opciones, así que vamos a lo simple) en el medio. Ahora verifica si el nuevo valor es mayor o menor que ese valor medio. Ese resultado guía si te mueves a la mitad superior o inferior de la matriz, elige el nuevo valor medio y repite hasta que encuentres la ubicación para este nuevo valor. Eso es un montón de “mirar y probar” a medida que se construye la matriz. No soy matemático (incluso tuve problemas para deletrear eso), pero mi experiencia es que esto comienza a acercarse a la apariencia y prueba al menos una vez para cada elemento de la matriz. Ahora, cuando llegue el momento de obtener el mayor elemento, obtenga el último (o primer) elemento.

Entonces siempre busca y prueba todos los valores. Esto supone que la definición / intención del “algoritmo más rápido” fue el menor número de operaciones de apariencia y prueba. Nuevamente, cambiar los parámetros de la pregunta al “menor número de miradas y pruebas por procesador” resultaría en un procesamiento paralelo. Pero hay factores de control porque cuanto más paralelo obtienes, más gastos generales tienes para distribuir y recombinar los resultados. ¿Qué tan terrible sería si cada procesador solo obtuviera 3 valores? Serían 2 miradas y pruebas por procesador, pero luego debe hacer un paralelo de los resultados a medida que retrocede a la respuesta y tener muchas miradas y pruebas para encontrar el mayor de los valores entre pares de procesadores.

Cambiar los “parámetros de la pregunta” nuevamente a “qué es más rápido si no necesito una precisión del 100%” permite que algunos algoritmos nuevos e inteligentes ingresen al conjunto de soluciones, una vez más, Tom con el problema de la secretaria (¡qué bueno!) Que podría obtener al 37% del tiempo correcto?

Todo esto es bueno, pero en ningún caso no buscará y probará cada valor individual. Simplemente hacerlo temprano, más tarde, en paralelo o con menos precisión. Para 100% correcto tiene “operaciones de mirar y probar” (N).

Debe mirar cada elemento al menos una vez, para que pueda obtener el elemento más grande de la matriz en complejidad O (n).

Algoritmo:

1. Tome 2 variables “min” y “max” e inicialice min al valor más grande y max al valor más pequeño .
   int min = Integer.MAX_VALUE;
   int max = Integer.MIN_VALUE;
2. Iterar a través de la matriz y
   si el valor actual es> max, actualice max con un nuevo valor máximo.
   si el valor actual es
3. imprimir min y max.

Explicación detallada con el programa: Encuentra el número más grande y más pequeño en la matriz

En términos convencionales, el algoritmo más rápido es una búsqueda lineal, con complejidad de tiempo O (N), lo que significa que el tiempo para determinar el resultado es lineal con el número de números.

Si tiene un número limitado de procesadores, entonces la complejidad algorítmica es definitivamente O (N), y esa es la respuesta aceptada a esta pregunta. Sin embargo, parece que estamos entrando en una era en la que la ley de Amdahl tiene más influencia que la ley de Moore. La ley de Amdah respalda la respuesta de O (log (N)) para valores pequeños de N y se acerca a O (N) para N> P, siendo P el número de procesadores disponibles.

En la superficie, esto parece una respuesta graciosa, pero considere que la CPU Intel Knight’s Landing tiene 72 núcleos. Más importante aún, TaihuLight es el campeón reinante en la lista TOP500, ofreciendo la increíble cantidad de 93 petaflops en el punto de referencia de Linpack. Además de ser el sistema número uno, otro gran reclamo a la fama es que está construido casi en su totalidad a partir de componentes fabricados en China. En particular, el sistema funciona con el procesador ShenWei de 260 núcleos, conocido como SW26010. Cada uno de los 40,960 chips ShenWei de TaihuLight ofrece tres teraflops de máximo rendimiento. Eso es más de diez millones de núcleos.

Por esa razón, creo que podemos decir hoy que el mejor algoritmo es aquel que compara pares de números para encontrar el más grande, luego compara pares de esos resultados de forma recursiva hasta que solo quede un número.

** Gracias por las correcciones Jan Nienhaus.

Eso depende de lo que quieras decir con sin clasificar. Si es realmente una permutación aleatoria de los elementos, entonces sí, debe observar todos los elementos, y el algoritmo óptimo (clásico, es decir, no cuántico) es O (N), aunque altamente paralelizable.

Sin embargo, es bueno tener algo de contexto. ¿Está sin clasificar porque la clasificación normal es prohibitivamente costosa, mientras que las operaciones de tiempo lineal son aceptables? En ese caso, hay muchos ordenamientos parciales que podrían construirse útilmente en tiempo lineal utilizando algoritmos in situ, que son fáciles de preservar incluso al agregar y eliminar elementos. Por ejemplo, puede construir un montón en tiempo lineal si obtiene la matriz tal como está, o en menos tiempo de inactividad entre las entradas si los elementos provienen de unos pocos a la vez desde un flujo de entrada lento.

Con solo la matriz sin clasificar, no hay forma de hacer esto en tiempo sub-lineal. Como no sabes qué elemento es el más grande y el más pequeño, debes mirarlos a todos, por lo tanto, el tiempo lineal.

El mejor tipo que encontrará será peor que eso, probablemente en relación con n log n, por lo que será “mejor” hacer el escaneo lineal.

Hay otras formas de acelerar el proceso si se le permite almacenar más información. Puede almacenar el mínimo y el máximo utilizando las siguientes reglas:

Al agregar un valor a una lista vacía, establezca min y max en ese valor. Tiempo constante O (1).
Al agregar un valor a una lista no vacía, establezca min o max a ese valor, si corresponde. Tiempo constante O (1).
Al eliminar un valor de la lista, establezca min o max en ‘unknown’ si el valor que se elimina es igual al min o max actual. Tiempo constante O (1). También puede hacerlo más eficiente si almacena tanto el mínimo / máximo como los recuentos de ellos. En otras palabras, si su lista tiene siete copias del máximo actual y elimina una, no es necesario establecer el máximo en desconocido, solo disminuya el recuento. Solo cuando el recuento llega a cero debe marcarlo como desconocido.
Si solicita el mínimo o el máximo para una lista vacía, devuelva algún valor especial. Tiempo constante O (1).
Si solicita el mínimo o el máximo para una lista no vacía donde se conocen los valores, devuelva el valor relevante. Tiempo constante O (1).
Si solicita el mínimo o el máximo para una lista no vacía donde los valores son desconocidos, realice una búsqueda lineal para descubrirlos y luego devuelva el valor relevante. Tiempo lineal O (n).
Al hacerlo de esa manera, probablemente la gran mayoría de la recuperación de min / max es tiempo constante. Solo cuando ha eliminado un valor que era el mínimo o el máximo, la siguiente recuperación requiere tiempo lineal para una recuperación.

La próxima recuperación después de eso volverá a ser tiempo constante ya que los calculó y almacenó, suponiendo que no elimine el valor mínimo / máximo en el ínterin nuevamente.

El seudocódigo para el máximo podría ser tan simple como:

def initList ():
lista = []
maxval = 0
maxcount = 0
En ese código de inicialización anterior, simplemente creamos la lista y un valor y recuento máximos. También sería fácil agregar el valor mínimo y contar.

Para agregar a la lista, seguimos las reglas anteriores:

def addToList (val):
error de list.add (val) en caso de falla

# Detecta agregar a la lista vacía.
si list.size = 1:
maxval = val
maxcount = 1
regreso

# Si no se conoce el máximo en este punto, calcule más tarde.
si maxcount = 0:
regreso

# Agregar menos que el máximo actual, ignorar.
si val regreso

# Agregar otro de recuento actual máximo, aumento.
si val = maxval:
maxcount + = 1
regreso

# De lo contrario, nuevo máximo, establecer el valor y contar.
maxval = val
maxcount = 1
Eliminar es bastante simple. Simplemente elimine el valor. Si fue el valor máximo, disminuya el recuento de esos valores máximos. Tenga en cuenta que esto solo tiene sentido si conoce el máximo actual; de lo contrario, ya estaba en el estado en el que iba a tener que calcularlo, así que permanezca en ese estado.

El conteo que se convierte en cero indicará que el máximo ahora es desconocido (los ha eliminado todos):

def delFromList (val):
error de list.del (val) en caso de error

# Disminuya la cuenta si se conoce max y el valor es max.
# El recuento se convertirá en 0 cuando se eliminen todos los máximos.
si maxcount> 0 y val = maxval:
maxcount – = 1
Obtener el máximo es entonces una cuestión de saber cuándo debe calcularse (cuando maxcount es cero). Si no necesita ser calculado, simplemente devuélvalo:

def getMax ():
# elevar excepción si la lista está vacía.
error si list.size = 0

# Si se desconoce el máximo, calcule bajo demanda.
si maxcount = 0:
maxval = list [0]
para cada val en la lista:
si val = maxval:
maxcount + = 1
elsif val> maxval:
maxval = val
maxcount = 1

# Ahora se sabe, solo devuélvelo.
retorno maxval

Los números en las computadoras digitales se almacenan en conjuntos de bits que tienen un valor de uno o cero. Estos bits generalmente se organizan en conjuntos de 8 bits, llamados bytes. Cada bit representa una potencia de 2 que se suman. El primer bit (n = 0) tiene un valor de 2 ^ 0 = 1 o 0, dependiendo de su estado. El segundo bit (n = 1) tiene un valor de 2 ^ 1 = 2 o 0. Los siguientes bits (n) representan un valor de 2 ^ n o 0. Estos valores se suman, por lo que el valor total de 8 bits byte es SUM (n = 0 a 7) {2 ^ n * b (n)}, donde b (n) es el valor 1 o 0 del bit en la posición n.

Si tuviera que mirar un gráfico de barras de todos esos números, podría ver de inmediato cuál era el más grande. Verificará todos los números que tengan un bit en el más alto (2 ^ 7, posición 8) establecido en 1. Eso ya le indicaría qué números debe ignorar. Por supuesto, cuando todos son 0, repite lo mismo para los valores n = 6, posición 7, n = 5, n = 4, etc. A partir de eso, solo le quedarían aquellos números que tienen el valor más alto , sin tener que saber el número entero. Podrías parar cuando solo quedara uno.

Debido a la naturaleza de la arquitectura de la computadora, los bits generalmente se procesan en paralelo, en grupos de bytes. Los procesadores modernos procesan números en grupos de 8 bytes, 64 bits.

Si, por ejemplo, los números tuvieran una longitud de 64 bits, formarían 8 bytes cada uno (8 x 8 bits / byte). Si su procesador fuera un procesador de 8 bits, entonces podría comenzar a escanear los bytes más altos y solo usar los números que tienen un valor de cero desigual. Luego escanee el segundo byte más alto para los seleccionados y conserve los que tengan el valor más alto. Esto todavía sería una mejora sobre O (N).

Entonces mi argumento es que, por naturaleza, los procesadores son multitarea. Un procesador de 64 bits procesa 64 bits simultáneamente, es decir, en paralelo. Cuando tiene 8 núcleos, puede manejar 64 * 8 = 512 bits a la vez. Por lo tanto, el O (N) parece estar basado en el supuesto de que los números se procesan como un todo, que de hecho, en un sistema binario, no lo son. O (N) es verdad para un humano. Pero incluso un niño ordenaría primero los números por su tamaño y luego compararía sus valores …

Simplemente no tiene otra opción que verificar cada elemento para ver si es el más grande, como ya dice cada respuesta.

Sin embargo, solo por el bien de la novedad, posiblemente podría verificar múltiples elementos al mismo tiempo, sin la sobrecarga de los hilos iniciales. Dependiendo de si su procesador de elección tiene una unidad de vectores como SSE o VIS, entonces podría comparar 2 o 4 números al mismo tiempo, dependiendo del tamaño de los números y las capacidades de la unidad de vectores.

No sé si alguien todavía está leyendo esta pregunta, pero como dijo al menos una respuesta, depende de su suposición de una arquitectura de procesamiento. Si la matriz se almacenó en una memoria direccionable de contenido (CAM), se pueden realizar búsquedas mucho más rápidas que las búsquedas lineales. Y aunque las CAM actuales son solo para pequeños tamaños de memoria, creo que de 2 a 4 KI, esto limita los usos prácticos. He resuelto los problemas prácticos. Dado esto, se podría buscar una lista de mil millones de números, con duplicados, en aproximadamente 30 ciclos de reloj. ¡Eso significa una aceleración de aproximadamente 33 millones de veces! Esto vale mucho si el proceso se repite mucho (como en las direcciones IP, por ejemplo). Cualquier persona interesada en obtener más información sobre esto, consulte “Memoria direccionable por contenido” en la pestaña Invención en A3society.org.

Una posible solución implicaría crear un conjunto de máscaras de bits, por lo que solo está buscando el valor con el conjunto de bits superior más alto. Esto falla cuando se trabaja con valores no enteros o valores que no están limitados al tamaño de la máquina.

La solución anterior sería peor que O (N): la solución más simple de iterar sobre toda la lista es O (N) y para una porción de datos aleatorios, sin clasificar, es el mejor momento que se puede esperar. Incluso si los datos se limitaran a un tipo de longitud definida con máximos y mínimos conocidos, el tiempo de ejecución promedio sería O (N) (aunque probablemente tiende más hacia O (N / 2)) debido a los valores atípicos de los máximos que aparecen en El final de los datos. (el O (N / 2) porque tendrá los valores atípicos al inicio / final, pero la mayoría de los resultados se extienden generosamente por el medio, como la curva de campana de una prueba Z de dos colas)

Además del hecho de que realmente puede pasar por todos los valores, no hay otro método para determinar con precisión cuál es el número más grande.

Sin embargo, en algunos casos lo que desea es aproximar el número más grande. Piense en tener miles de millones de números o incluso miles de millones de ellos.

Veamos algunos enfoques que le darán una buena estimación sin tener que revisar muchos datos.

Enfoque estadístico estándar (no.1):

Basado en un subconjunto aleatorio, su media y desviación estándar.

Es posible tomar una submuestra aleatoria y evaluar la distribución. Por lo general, tendrá una distribución normal, por lo que una vez que tenga la media y la desviación estándar de la distribución, puede aproximar el número más alto en toda su matriz a aproximadamente tres desviaciones estándar de la media como la regla general dice 99.97 de todas las muestras en una distribución normal está debajo de este número.

x = media + 3 * stddev

Enfoque estadístico (no.2 – mejorado en no.1):

Según la estimación del mayor número posible de un subconjunto de solo el mayor número de otros subconjuntos aleatorios, es la media y la desviación estándar.

Saca aleatoriamente un mínimo de 30 subconjuntos de un mínimo de 30 números y toma el más grande de cada uno de estos. Tiene 30 números más grandes ahora en una pequeña matriz. Calcule la media y la desviación estándar de esos. Su aprox. El número más grande en todo el conjunto es tres veces la desviación estándar de la media de esta última matriz.

Enfoque de aprendizaje automático:

Este método se puede usar si hay varias otras matrices como esta y desea poder tener una función para hacer esto rutinariamente o si tiene distribuciones no lineales / no polinomiales, no normales.

Puede tomar algunos subconjuntos aleatorios de toda la matriz, quitarle el mayor número como una etiqueta para su problema de ML y crear un algoritmo de regresión que pueda predecir esa etiqueta. Una vez que tenga el algoritmo, tome un subconjunto más grande del conjunto que dejó fuera para la predicción final y prediga sobre eso.

Para una certeza del 100% de que ha encontrado el mayor número, tendrá que hacer una búsqueda lineal. PERO, aún puede optimizar la búsqueda. A medida que los números que encuentra se vuelven más y más grandes, comienza a comparar solo los bits más significativos.

Además, implementa el paralelismo para utilizar todas las CPU que tiene disponibles.

Si desea jugar con estadísticas y conoce la distribución de sus números, por ejemplo, normal, puede usar la teoría de muestreo para encontrar una aproximación del número más alto, sin escanear toda la matriz, con un nivel de confianza que considere satisfactorio.

Si bien la respuesta de Ken Alverson sobre las respuestas paralelas es probablemente la mejor respuesta algorítmica, y la respuesta de Tim Farage es probablemente la interpretación más literal de la pregunta … déjame darte la respuesta más pragmática.

¿Por qué pragmático? Porque estoy en operaciones y realmente vivo en el mundo real. En el mundo real, puedo realizar esta búsqueda en cero segundos, o incluso en una cantidad de tiempo negativa.

En su carrera, nunca se encontrará con la necesidad de hacer este tipo de búsqueda en total aislamiento. Los algoritmos no existen por sí solos. Se usan en el mundo real. El mundo real involucra procesos, personas y equipos. Siempre habrá algunas externalidades (cosas aparentemente no relacionadas) que puede aprovechar (aprovechar) para obtener mejores resultados que las respuestas de Ken o Tim.

Algunos ejemplos de mi carrera como administrador del sistema:

1. La lista de números será pequeña y cualquier algoritmo será “suficientemente bueno”. “Pequeño” en el mundo de hoy podría ser de 10 millones de enteros. Te sorprendería lo rápido que un procesador Intel moderno puede recorrer 10 millones de enteros. Si solo necesita hacer esta búsqueda una vez al día, esa cantidad de tiempo será insignificante. ¡DEJA DE PREOCUPARSE POR LA VELOCIDAD HASTA QUE SABAS QUE ES UN PROBLEMA! O (N) podría estar bien. No puedo decirle cuántas veces la gente se ha acercado a mí diciendo “necesitamos un EXPERTO EN GRANDES DATOS” y después de algunas discusiones, sé que su “gran” es solo 10G de datos. Puedo cargar 10G de datos en la RAM de un servidor Dell que puedo comprar con el límite de crédito de una de mis tarjetas de crédito.

2. La búsqueda puede ocultarse haciéndola en segundo plano. Si la búsqueda lleva demasiado tiempo, vea si puede obtener la matriz antes en el proceso para que pueda hacer la búsqueda en segundo plano. Tal vez haya una pantalla de título para mostrar o una interfaz de usuario para representar. ¿Puede obtener la matriz antes de que se procese para que pueda ordenar en segundo plano? Mire el panorama general y pregunte a todos los involucrados qué tan temprano puede obtener la lista. Una vez estuve en una situación en la que la matriz estaba disponible en T + 4 y la ordenamos por T + 6. Un desarrollador mejoró el algoritmo y ahora teníamos los datos en T + 5. Obtuve acceso a la matriz en T + 0 y tenía los datos listos en T + 1. ¡Es como tener una máquina del tiempo en comparación con el software v1.0!

3. ¡No busques nada! Mientras crea la lista, realice un seguimiento del valor más grande que vea. Ahora saben que el número más grande es O (nada) [eso es una broma, idiotas sin sentido de la informática. Obviamente me refiero a O (1). Sin embargo, eso no es tan divertido y … A la mierda esta explicación ha arruinado totalmente el flujo de este párrafo. ¡GRACIAS, ROBERT!]. Ve a hablar con la persona y exige que haga esto. Si no se mueven, hable con su gerente. ¿Qué gilipollas pasivo-agresivo te pide el mayor valor en SUS datos de todos modos? ¿No pueden mantener una variable de “valor más grande” porque también están eliminando y actualizando la lista? ¡Decir ah! Si es así, no deberían almacenarlo en una matriz sin clasificar porque esas actualizaciones serán mejores si usan CUALQUIER OTRA estructura de datos; y cualquier otra estructura de datos tendrá una forma de encontrar el mayor valor de manera más eficiente que O (N).

4. Aprovecha la repetición. Sí, la primera vez que vea la lista, es posible que deba realizar una búsqueda O (N) lineal. Sin embargo, los datos no desaparecen después de eso. Probablemente se usa para otras cosas, se actualiza y se revisa. Después de esos cambios, necesita encontrar el valor más grande nuevamente. Hay muchas oportunidades aquí. ¿Se puede rastrear las actualizaciones para obtener el “mayor valor”? ¿Los datos se colocan posteriormente en un árbol o se ordenan? ¿Necesita la respuesta exacta o puede usar una estimación basada en datos anteriores, mejorando la suposición con cada repetición?

Una vez vi un proceso con 5 pasos. Cada paso fue realizado por un equipo diferente. Cada equipo comenzó clasificando los datos. Si el primer equipo clasificó los datos y retuvo los datos ordenados para futuros equipos, ¡el tiempo dedicado a la clasificación habría mejorado 5 veces! ¡OMG REQUIERE PERSONAS DE UN EQUIPO PARA HABLAR CON PERSONAS DE OTRO EQUIPO! OH EL HORROR! ¡POR FAVOR, POR FAVOR! ¡NO ME HAGAS SER HUMANO! ¡QUIERO SER UN CODIFICADOR QUE VIVE EN AISLAMIENTO! No, no lo haces. Desea ser un ser humano que viva en una comunidad que desarrolle procesos increíbles impulsados ​​por el software.

Entonces, si esta pregunta era una tarea, la respuesta es O (N): haga una búsqueda lineal en la lista y examine cada elemento.

Si esta pregunta es una solicitud honesta … baje el teclado. Quítate el culo y camina por el pasillo. Hable con todas las personas involucradas y descubra cuál es la necesidad real y vuelva a examinar si realmente se necesita el “valor más grande”, cómo se necesita y si se puede mejorar todo el proceso al observarlo de manera integral. fin.

Sal de tu silo. Hablar con las personas. Siempre obtendrás mejores resultados.

Actualizar:
5. Una vez estuve en una situación en la que resultó que se necesitaba max () para asignar memoria. ¿Por qué no asignar la cantidad en función de la última vez que tuvo un conjunto de datos similar y aumentar / reducir la asignación de memoria cuando haya terminado? Resulta que el valor máximo era una constante, por lo que al hacer la pregunta al programador se le ocurrió una forma completamente diferente de hacer las cosas.

6. Averigüe si un paso MÁS TARDE necesita los datos en orden ordenado. Voluntario para ordenarlo en su paso para que pueda obtener el valor máximo simplemente eligiendo el último elemento. Ahora el algoritmo es O (n log2 n) [o lo que sea] que es más grande que O (n), pero todo el sistema es más rápido.

ACTUALIZACIÓN: convertí esta respuesta en un artículo para la revista ACM Queue. ¡Gracias a todos por su aporte! Buscar datos aleatorios no es un problema de O (N).

En el momento en que estudié computación cuántica, el algoritmo de búsqueda de Grover podía encontrar cualquier elemento en una matriz no ordenada dentro de O (sqrt (N)) pasos. La idea de una máquina cuántica es operar en el espacio matemático de Hilbert con N dimensiones, donde todos los valores sin clasificar se pueden examinar simultáneamente. Todo el espacio cuántico se modifica por completo con algunas transformaciones unitarias que conducen finalmente a una respuesta correcta ~ 99.99999%. El algoritmo de Grover se puede modificar para encontrar el máximo, manteniéndose en la misma clase de complejidad (arxiv.org/pdf/quant-ph/9911082).

Sin embargo, prácticamente las computadoras cuánticas no podían realizarse con más de unos pocos bits (bits cuánticos / qbits), actualizados. Pero una vez que se establezca un prototipo que funcione (podría tomar ~ 50 años), cambiarán la forma en que calculamos, nos comunicamos y cooperamos para siempre, ya que todos los algoritmos convencionales de seguridad y criptografía serán completamente inútiles. Salud.