algorithm - pseint - El mejor algoritmo para encontrar la diferencia absoluta mínima entre dos números en una matriz

algoritmo para determinar el mayor de 2 numeros pseint

Question

Hay una matriz que puede contener, digamos, hasta 1000 elementos. El rango de números que puede generar es de 1 to 10^10 . Ahora tengo que encontrar la minimal absolute difference entre dos números en la matriz. He pensado en dos algoritmos:

Para la primera , he definido una función de binarysearch que encuentra la posición de un número a insertar en una matriz ordenada. Ahora comienzo la matriz ordenada con solo el primer número de la matriz dada y comienzo a iterar en la matriz dada desde el segundo elemento en adelante. Para cada número, encuentro su posición en la matriz ordenada. Si el número en esa posición es este número, entonces la diferencia es 0, es el más bajo posible, así que salgo del bucle. De lo contrario, inserto el número en el arreglo ordenado en ese punto, luego verifico la diferencia entre ese número y los números anteriores y siguientes en ese arreglo. Luego almaceno el mínimo de este resultado y el resultado anterior, y continúo de esta manera.

Segundo: ordeno la matriz usando quicksort . (El rango es demasiado grande, por lo que creo que la clasificación por radix no será tan eficiente). Luego repito sobre él, rompiendo con una respuesta de 0 si dos números consecutivos son iguales, de lo contrario almacena el mínimo de la diferencia entre ese número y el número anterior y el resultado anterior.

¿Cuál será más eficiente?

¿Hay algo mejor?

Stackoverflow tiene una serie de publicaciones en este sentido, pero no ayudaron mucho. Aquí está mi código en Perl:

sub position {
    my @list   = @{$_[0]};
    my $target = $_[1];

    my ($low,$high) = (0, (scalar @list)-1);

    while ($low <= $high) {
        $mid = int(($high + $low)/2);

        if ( $list[$mid] == $target ) {

            return $mid;
        }
        elsif ( $target < $list[$mid] ) {

            $high = $mid - 1; 
        }
        else {

            $low = $mid + 1;
        }
    }
    $low;
}
sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }
sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }

$ans        = 10_000_000_000;
@numbers    = (234, 56, 1, 34...123); #given array
($max,$min) = @num[0, 0];
@sorted     = ($numbers[0]);

for ( @num[1 .. $#num] ) {
    $pos = position(/@sorted, $_);

    if ( $sorted[$pos] == $_ ) { 

        $ans = 0;
        last;
    }
    splice @sorted, $pos, 0, $_;

    if ( $#sorted == $pos ) { 

        $ans = min($_-$sorted[-2], $ans);
    }
    elsif ( 0 == $pos ) {

        $ans = min($sorted[1]-$_, $ans);
    }
    else { 

        $ans = min(min(abs($sorted[$pos-1]-$_), abs($sorted[$pos+1]-$_)), $ans);
    }
    $max = max($_, $max);
    $min = min($_, $min);
}
print "$ans/n";

Answer 1

1. copiar números de matriz en árbol negro-rojo
2. esto le permitiría probar si hay un número en cierto intervalo para log (n)
3. set d = inf
4. bucle sobre matriz con la variable i
5. si hay un número en el intervalo (id, i + d), entonces establezca d igual a | i-thatNumber |

te llevaría ~ n * ln encontrar d

Answer 2

Debido a que estamos hablando de Perl, no deberíamos preguntarnos mucho sobre el algoritmo de clasificación más eficiente: implementar algo en Perl seguramente será más lento que el uso integrado. Sólo por diversión, ejecuté este pequeño guión (destinado a la claridad):

time perl -e''
    @array = map {rand} 1..100000;
    $lastdiff=10**11;
    for(sort {$a <=> $b} @array){
        unless(defined $last){
            $last=$_;
            next
        }
        $difference = abs($last - $_);
        $last = $_;
        $lastdiff = $lastdiff < $difference ? $lastdiff : $difference;
        last if $lastdiff == 0;
    }
    print $lastdiff, "/n"
''

Configuré una matriz con 100,000 números aleatorios. Este script termina (en mi laptop lenta) dentro de 0.42 segundos. Teniendo en cuenta que uso ~ 0.12 segundos para el inicio y la inicialización de la matriz, el algoritmo principal usa aproximadamente 0.3 segundos. Suponiendo que O (n) debes terminar en <0.02 segundos ... oh, espera, eso no es mucho ... (con 5000 elementos)

Si lo necesita más rápido, escriba su algoritmo con Inline :: C.

Answer 3

El segundo algoritmo es probablemente mejor. En el primer algoritmo, está utilizando la ordenación por inserción, que es menos eficiente que otros algoritmos de clasificación.

Answer 4

Este es el problema de par más cercano en una dimensión. Tenga en cuenta que resolver este problema es al menos tan difícil como resolver el problema de singularidad del elemento , ya que si hay algún elemento duplicado, la respuesta es 0.

El problema de la unicidad del elemento requiere O(n lg n) tiempo para resolver, por lo que este problema también debe ser al menos tan difícil. Como la solución de ordenación iterativa que propuso es O(n lg n) , no existe un mejor algoritmo de caso peor asintótico disponible.

Sin embargo, como se señaló en el artículo de la wiki, hay algoritmos que tienen el peor tiempo de ejecución en el peor de los casos, pero el tiempo de ejecución lineal esperado. Uno de estos métodos se describe en este artículo , ¡parece bastante complicado!

Answer 5

La segunda será más rápida por la sencilla razón de que con la primera solución está usando una clasificación que escribió usted mismo en Perl-space, mientras que con la segunda solución tiene la oportunidad de usar la sort integrada de Perl que es Una función en C y muy rápida. Con una participación tan pequeña, será casi imposible que gane el primero, aunque tenga el potencial de hacer menos trabajo.

Answer 6

Tienes hasta 5k elementos.

Tenga en cuenta que un procesador Sandy Bridge tiene 32KB L1-Cache , asumiendo un entero de 4 bytes, lo que significa que puede contener 8192 enteros.

Intentaría evitar tanto como sea posible creando datos adicionales (excepto contadores y demás), y hacer todo en su lugar usando la misma matriz. Esto hará que la cantidad de cache-misses de cache-misses muy pequeña, y probablemente superará cualquier algoritmo.

Por lo tanto, una ordenación rápida en el lugar y una iteración sobre los elementos en el arreglo probablemente será mejor que cualquier otra solución, tanto para ser eficiente como para la caché, mientras se mantiene una complejidad asintótica decente de O(nlogn) .

Nota: aunque esta solución probablemente sea ​​más eficiente (al menos en teoría), la escala aún es muy pequeña, y a menos que vaya a hacer esta oporación muchas veces, simplemente no vale la pena optimizarla.

Consejo general: cuando se habla de problemas a pequeña escala (y hasta 5000 elementos cumplen con este criterio), la notación big-O generalmente no es suficiente. El rendimiento del caché suele ser el factor dominante en estos problemas.

Answer 7

Un algoritmo de tamiz aleatorio simple para el problema del par más cercano describe un algoritmo aleatorio O (n) para el problema del par más cercano y también hace referencia a otro documento que proporciona un algoritmo determinista O (n log log n) para el par más cercano unidimensional Problema si tienes acceso a la función de floor .