algorithm - sustitución - Algoritmo óptimo para devolver valores de k superiores de una matriz de longitud N

explique cómo funciona el método de sustitución de páginas llamado de segunda oportunidad

Question

Tengo una serie de n flotadores y deseo devolver la parte superior k (en mi caso n ~ 100, k ~ 10)

¿Existe una ruta de solución óptima conocida para este problema?

¿Podría alguien proporcionar un algoritmo C?

EDIT: en realidad hay dos problemas aquí: ordenados y sin clasificar. Estoy interesado en sin clasificar, que debería ser más rápido!

Answer 1

A continuación se presenta una solución elegante basada en el montón en Java con complejidad O (nlogK). No es el más eficiente, pero creo que es bastante fácil de entender. Puede cambiar Integer a Float si desea una solución basada en float

import java.util.Arrays;
import java.util.PriorityQueue;

public class FindKLargest {

public static void find(int[] A, int k) {

    PriorityQueue<Integer> pq = new PriorityQueue<>(k);// Min heap because the element has to be greater
                                                        // than the smallest element in the heap in order
                                                        // to be qualified to be a member of top k elements.
    for (int i = 0; i < A.length; i++) {
        if (i < k) // add until heap is filled with k elements.
            pq.add(A[i]);
        else if (pq.peek() < A[i]) { // check if it''s bigger than the
                                        // smallest element in the heap.
            pq.poll();
            pq.add(A[i]);
        }
    }
    int[] topK = new int[pq.size()];
    int index = 0;
    while (index != k)
        topK[index++] = pq.poll();
    System.out.println(Arrays.toString(topK));
}

public static void main(String[] args) {
    int[] arr = { 1, -2, -3, -4, -5 };
    find(arr, 4);
}

}

Answer 2

Eche un vistazo al algoritmo de ordenación rápida parcial discutido hacia el final de "Selección eficiente y clasificación parcial basada en ordenación rápida" .

Answer 3

Puede hacer esto en O(n) utilizando un algoritmo de selección . Encuentra el elemento k más grande con el algoritmo de partición, luego todos los elementos después de que sean más grandes que él, y esos son tus mejores k .

Si necesita esos top k en orden, puede ordenarlos en O(k log k) .

Answer 4

Respuesta corta: no.

Respuesta más larga: sí, se conocen varias soluciones óptimas incompatibles entre sí. Depende de n, k y qué propiedades de la matriz puede garantizar.

Si no sabe nada acerca de la matriz, el límite inferior de complejidad es obviamente O (n), ya que todos los elementos de la matriz de origen deben examinarse para ver si encajan en el top 10. Si sabe algo sobre la matriz de origen que permite elementos para ser saltado de forma segura debe utilizar ese conocimiento.

De manera similar, el límite de complejidad superior es O (n.log (n)) porque siempre podría elegir encontrar la respuesta ordenando la matriz (O (n.log (n)) y devolviendo los primeros 10 elementos (O (1)) .

Una búsqueda lineal que compara cada elemento con el décimo más alto encontrado hasta ahora e insertándolo en el lugar apropiado en la lista de los elementos más altos encontrados hasta el momento si es necesario tiene una complejidad similar para los escenarios promedio y de mejor caso y tiene un peor -caja de O (kn) que es significativamente mejor que O (n-cuadrado). Para los tamaños que estimas, espero que este método funcione bien.

Si n fuera mucho más grande (~ 10000) y k se incrementara en la misma proporción, probablemente valdría la pena implementar el algoritmo de selección rápida. Quickselect realiza mejor los elementos que desee. Sin embargo, si k no aumentara su escala con n, debería seguir con la búsqueda lineal. Quickselect y amigos modifican la matriz original, por lo que son menos adecuados si no puede hacer esto en su lugar porque necesita un montón más de almacenamiento y mucha copia que la complejidad del algoritmo no incluye.

Si n es enorme (~ 1e20), querría encontrar la k más grande de cada una de varias particiones de la matriz de entrada y luego encontrar la k más grande de la suma de esos resultados, para que no esté tratando de analizar más Datos de los que puede caber en la memoria a la vez, y para permitir que la operación se paralice de manera eficiente.

Answer 5

Si tienes un Gpu de lujo, puedo decirte cómo calcular la gran cantidad de k de enormes n instancias al mismo tiempo, así que extiéndelas en una textura, por instancia, y agrega la mezcla en una textura con su "altura". Como la posición a lo largo de la textura.

Pero tenga en cuenta que tiene que adivinar un rango aceptable o saberlo, o no se extenderá al máximo que podría haber tenido.

clonas posiciones. (debería obtener un 2, si hay 2 en él, 10 si hay 10 en él) en todas las instancias. (solo diga todo en una textura de 8192x8192, 64x64 de estas cajas de "altura") y también salta ranuras con 0 cuentas.

luego haga una jerarquía de agregados comprimidos, excepto que lo hace como un árbol binario, solo lo trata como su dimensión 1, así que tome los 2 números anteriores y súmelos, y continúe haciéndolo para cada mip binario.

luego usamos estos mips (que han recopilado recuentos) para descubrir la ubicación aproximada de la k, usando todos los mips en el proceso, haga esto en un hilo final, sacará grandes trozos de él, y luego use lentamente los mips más detallados para encuentra el valor por píxel, en el que se encuentra k.

tiene más sentido hacer esto, si todo se creara una instancia nuevamente, entonces es un hilo por descubrimiento de umbral. (solo diga que estuvo ejecutando un ANN 128x128 veces a la vez, (¿alguien con una traslación de traducción?) entonces tiene mucho sentido.

y logre el umbral de altura para ese conteo, pero es aproximado ... así obtendrá una k aproximada. para n listas.

Puedes hacer un poco más de trabajo para obtener el k exacto, pero en una coincidencia de similitud, pero si puedes lograr que sea aproximado, como si recibiera las activaciones top ~ k, entonces no te preocupes por eso.

Answer 6

Método 1

Como k es pequeño, puedes usar el método del torneo para encontrar el k más grande. Este método se describe en El arte de la programación de Knuth, volumen 3, página 212.

Primero crea un torneo en n-k + 2 elementos. Algo así como un torneo de tenis eliminatorio. Primero, se dividen en pares y se comparan los miembros de los pares (como si esos dos jugaran un partido y uno perdido). Luego los ganadores, se dividen en parejas nuevamente y así sucesivamente, hasta que tengan un ganador. Puedes verlo como un árbol, con el ganador en la parte superior.

Esto toma n-k + 1 compara exactamente.

Ahora el ganador de estos n-k + 2 no puede ser tu kth elemento más grande. Considera su camino para subir al torneo.

De los k-2 restantes, elija uno y siga por el camino P que le dará un nuevo más grande. Básicamente, se trata de rehacer el torneo con el ganador anterior siendo reemplazado por uno de los elementos k-2. Sea P el camino del nuevo ganador. Ahora elige otro del k-3 y sigue el nuevo camino hacia arriba y así sucesivamente.

Al final, después de agotar el k-2, reemplaza el más grande con el infinito y el más grande del torneo será el más grande. Los elementos que has desechado son los elementos superiores de k-1.

Esto toma como máximo n - k + (k-1) [log (n-k+2)] comparaciones para encontrar la parte superior de k. Sin embargo, utiliza memoria O (n).

En términos de número de comparaciones, esto debería probablemente superar cualquier algoritmo de selección.

Método 2

Como alternativa, puedes mantener un mínimo de k elementos.

Primero insertar k elementos. Luego, para cada elemento de la matriz, si es menor que el elemento min del montón, deséchelo. De lo contrario, elimine-min del montón e inserte el elemento de la matriz.

Al final, el montón contendrá los k elementos superiores. Esto tomará O(n log k) compara.

Por supuesto, si n es pequeño, solo ordenar la matriz debería ser lo suficientemente bueno. El código también será más sencillo.