Como Ricardo mencionó en su respuesta, para encontrar el número más alto real en una matriz, se deben verificar todos los elementos de la matriz. No hay forma de evitar eso. Esta encendido). Y tiene mucha razón sobre que es fácil de ejecutar en paralelo.
Sin embargo, si la matriz es lo suficientemente grande, supongamos que estamos tratando con una matriz infinita, es posible que verificar todos los elementos simplemente no sea factible, incluso con múltiples procesadores. En ese caso, puede emplear un método aleatorio. Verifique n elementos aleatorios en la matriz y use el más alto. Ya no se garantiza que encuentre el máximo real, pero puede estar lo suficientemente cerca como para que no importe. Aquí hay un ejemplo trivial, en Python. La primera función muestra cómo encontrar el máximo real, haciendo un bucle sobre todos los elementos de la matriz. El segundo muestra cómo encontrar algo lo suficientemente cerca mirando un subconjunto aleatorio de la matriz.
def max_correct (matriz):
# inicializa la variable max con el primer elemento
m = matriz [0]
para v en la matriz [1:]:
# para cada elemento en la matriz luego, verifique si
# ese valor es más alto que el máximo actual
m = v si v> m más m
volver m
- ¿Cuál es el mejor menor para una especialización en informática? ¿Un menor le dará una 'ventaja' en la fuerza laboral?
- ¿Qué significa la informática teórica?
- ¿Cómo se usan las matemáticas en informática?
- ¿Existe un término en matemáticas como 'real-complete' para describir una función que mapea todos los elementos de un conjunto (número real por ejemplo) a otro conjunto, o 'posibilidad-completa' para describir un algoritmo que maneja todas las posibilidades de entrada? ?
- ¿Qué es un punto flotante?
def max_montecarlo (matriz, n):
tamaño = len (matriz)
n = min (n, tamaño)
# inicializa la variable max con un elemento aleatorio
m = matriz [random.randint (0, tamaño)]
para _ en rango (n):
# para un número dado de iteraciones, seleccione
# un elemento al azar y ver si es más grande
v = matriz [random.randint (0, tamaño)]
m = v si v> m más m
volver m
Este método generalmente no se usa para encontrar el máximo, sino el promedio. Se llama integración de Monte Carlo, y es excepcionalmente útil cuando se trata con tantos datos que simplemente no es factible verificarlos todos, o si tiene una función que no se puede integrar exactamente, y varias otras situaciones. Se utiliza en renderizado 3D no en tiempo real todo el tiempo. Un método comúnmente utilizado para la representación 3D es rastrear los diversos caminos que la luz puede atravesar una escena. Esto representa un conjunto infinito de intensidades de luz. No puede calcular todos los valores en una matriz infinita o recorrerlo para encontrar el promedio o el máximo, pero puede verificar un subconjunto finito elegido al azar, y si marca suficientes, estará lo suficientemente cerca como para que se produzca el error. ser irrelevante Esta es también la base para cosas como encuestas a clientes. Como no es factible preguntar a todos los clientes, simplemente elige un grupo de ellos de forma semialeatoria y extrapola. Mismo principio
Algunas notas
- Los ejemplos de Python podrían hacerse mucho más compactos y rápidos mediante el uso de ciertas funciones en el módulo aleatorio . Lo escribí de esta manera para que sea más fácil de entender para los lectores sin conocimiento de Python.
- Para matrices pequeñas y / o valores grandes para n , es más probable que un elemento se verifique más de una vez. Esto es fácil de optimizar. Puede usar un selector de números semialeatorio que está garantizado para no generar el mismo número más de una vez, por ejemplo, o mantener un registro de todos los elementos que ya están marcados, o construir el subarreglo en una estructura que no permita duplicados .
- La calidad y fiabilidad de este tipo de enfoque depende en gran medida de la calidad de sus números aleatorios.
- Ambos métodos son igualmente multiproceso.
editar: reparó un error en el código de ejemplo
