algorithm - saca - Encuentra el valor de la mediana de un conjunto en crecimiento

medidas de tendencia central para datos agrupados media mediana y moda

Question

Me encontré con una interesante pregunta de algoritmo en una entrevista. Di mi respuesta pero no estoy seguro de si hay alguna idea mejor. Así que doy la bienvenida a todos a escribir algo sobre sus ideas.

Tienes un set vacío. Ahora los elementos se ponen en el conjunto uno por uno. Asumimos que todos los elementos son enteros y son distintos (según la definición de conjunto, no consideramos dos elementos con el mismo valor).

Cada vez que se agrega un nuevo elemento al conjunto, se solicita el valor de la mediana del conjunto. El valor de la mediana se define igual que en matemáticas: el elemento central en una lista ordenada. Aquí, especialmente, cuando el tamaño del conjunto es par, asumiendo que el tamaño del conjunto es = 2 * x, el elemento de la mediana es el elemento x-th del conjunto.

Un ejemplo: Comience con un conjunto vacío, cuando se agregan 12, la mediana es 12, cuando se agrega 7, la mediana es 7, cuando se agrega 8, la mediana es 8, cuando se agrega 11, la mediana es 8, cuando Se agrega 5, la mediana es 8, cuando se agrega 16, la mediana es 8, ...

Tenga en cuenta que, primero, los elementos se agregan para establecerlos uno por uno y los segundos, no sabemos qué elementos se agregarán.

Mi respuesta.

Dado que se trata de encontrar una mediana, se necesita una clasificación. La solución más sencilla es utilizar una matriz normal y mantener la matriz ordenada. Cuando llegue un nuevo elemento, use la búsqueda binaria para encontrar la posición del elemento (log_n) y agregue el elemento a la matriz. Dado que es una matriz normal, se necesita cambiar el resto de la matriz, cuya complejidad de tiempo es n. Cuando se inserta el elemento, podemos obtener inmediatamente la mediana, usando el tiempo de instancia.

La complejidad del tiempo PEOR es: log_n + n + 1.

Otra solución es utilizar la lista de enlaces. La razón para usar la lista de enlaces es eliminar la necesidad de cambiar la matriz. Pero encontrar la ubicación del nuevo elemento requiere una búsqueda lineal. Agregar el elemento toma tiempo instantáneo y luego necesitamos encontrar la mediana pasando por la mitad de la matriz, lo que siempre lleva n / 2 de tiempo.

La PEOR complejidad del tiempo es: n + 1 + n / 2.

La tercera solución es utilizar un árbol de búsqueda binario. Usando un árbol, evitamos desplazar la matriz. Pero usar el árbol de búsqueda binario para encontrar la mediana no es muy atractivo. Así que cambio el árbol de búsqueda binario de forma que siempre sea el caso de que el subárbol izquierdo y el subárbol derecho estén equilibrados. Esto significa que en cualquier momento, el subárbol izquierdo y el subárbol derecho tienen el mismo número de nodos o el subárbol derecho tiene un nodo más que en el subárbol izquierdo. En otras palabras, se garantiza que, en cualquier momento, el elemento raíz sea la mediana. Por supuesto, esto requiere cambios en la forma en que se construye el árbol. El detalle técnico es similar a la rotación de un árbol rojo-negro.

Si el árbol se mantiene correctamente, se garantiza que la complejidad del tiempo PEOR es O (n).

Así que los tres algoritmos son todos lineales al tamaño del conjunto. Si no existe un algoritmo sublineal, los tres algoritmos pueden pensarse como las soluciones óptimas. Dado que no difieren mucho entre sí, lo mejor es la más fácil de implementar, que es la segunda, utilizando la lista de enlaces.

Entonces, lo que realmente me pregunto es si habrá un algoritmo sublineal para este problema y, de ser así, cómo será. ¿Alguna idea chicos?

Steve

Answer 1

1) Al igual que con las sugerencias anteriores, mantenga dos montones y almacene en caché sus respectivos tamaños. El montón izquierdo mantiene los valores por debajo de la mediana, el montón derecho mantiene los valores por encima de la mediana. Si simplemente niega los valores en el montón correcto, el valor más pequeño estará en la raíz, por lo que no es necesario crear una estructura de datos especial.

2) Cuando agrega un nuevo número, determina la nueva mediana a partir del tamaño de sus dos montones, la mediana actual y las dos raíces de los montones de L&R, que solo toman tiempo constante.

3) Llame a un método de subproceso privado para realizar el trabajo real para realizar la inserción y actualización, pero regrese inmediatamente con el nuevo valor de mediana. Solo es necesario bloquear hasta que se actualicen las raíces del montón. Luego, el hilo que hace la inserción solo necesita mantener un bloqueo en el nodo abuelo que atraviesa a medida que atraviesa el árbol; Esto permitirá que pueda insertar y reequilibrar sin bloquear otros hilos de inserción que trabajan en otras subramas.

Obtener la mediana se convierte en un procedimiento de tiempo constante, por supuesto, ahora es posible que tenga que esperar en la sincronización de más agregados.

Robar

Answer 2

Aunque Wrang-Wrang ya respondió, deseo describir una modificación de su método de árbol de búsqueda binario que es sub-lineal.

• Utilizamos un árbol de búsqueda binario que está equilibrado (AVL / Red-Black / etc), pero no está super equilibrado como lo describió. Así que agregar un artículo es O (log n)
• Una modificación del árbol: para cada nodo también almacenamos el número de nodos en su subárbol. Esto no cambia la complejidad. (Para una hoja, este recuento sería 1, para un nodo con dos hijos de hoja sería 3, etc.)

Ahora podemos acceder al elemento más pequeño Kth en O (log n) usando estos conteos:

def get_kth_item(subtree, k):
  left_size = 0 if subtree.left is None else subtree.left.size
  if k < left_size:
    return get_kth_item(subtree.left, k)
  elif k == left_size:
    return subtree.value
  else: # k > left_size
    return get_kth_item(subtree.right, k-1-left_size)

Una mediana es un caso especial de Kth elemento más pequeño (dado que conoces el tamaño del conjunto).

Entonces, en general, esta es otra solución O (log n).

Answer 3

Para encontrar la mediana en el tiempo lineal, puedes probar esto (me vino a la mente). Debe almacenar algunos valores cada vez que agregue un número a su conjunto y no necesitará ordenación. Aquí va.

typedef struct
{
        int number;
        int lesser;
        int greater;
} record;

int median(record numbers[], int count, int n)
{
        int i;
        int m = VERY_BIG_NUMBER;

        int a, b;

        numbers[count + 1].number = n:
        for (i = 0; i < count + 1; i++)
        {
                if (n < numbers[i].number)
                {
                        numbers[i].lesser++;
                        numbers[count + 1].greater++;
                }
                else
                {
                        numbers[i].greater++;
                        numbers[count + 1].lesser++;
                }
                if (numbers[i].greater - numbers[i].lesser == 0)
                        m = numbers[i].number;
        }

        if (m == VERY_BIG_NUMBER)
        for (i = 0; i < count + 1; i++)
        { 
                if (numbers[i].greater - numbers[i].lesser == -1)
                        a = numbers[i].number;
                if (numbers[i].greater - numbers[i].lesser == 1)
                        b = numbers[i].number;

                m = (a + b) / 2;
        }

        return m;
}

Lo que esto hace es que, cada vez que agregue un número al conjunto, ahora debe saber cuántos números "menores que su número" tiene y cuántos números "mayores que su número" tiene. Por lo tanto, si tiene un número con el mismo "menor que" y "mayor que", significa que su número está en la mitad del conjunto, sin tener que clasificarlo. En el caso de que tenga una cantidad par de números, puede tener dos opciones para una mediana, por lo que simplemente devuelve la media de esos dos. Por cierto, este es el código C, espero que esto ayude.

Answer 4

Para mantener la explicación breve, puede aumentar un BST de manera eficiente para seleccionar una clave de un rango específico en O (h) haciendo que cada nodo almacene el número de nodos en su subárbol izquierdo. Si puede garantizar que el árbol está equilibrado, puede reducirlo a O (log (n)). Considere el uso de una AVL que esté equilibrada en altura (o un árbol rojo-negro que esté más o menos equilibrado), luego puede seleccionar cualquier tecla en O (log (n)). Cuando inserta o elimina un nodo en la AVL, puede incrementar o disminuir una variable que realiza un seguimiento del número total de nodos en el árbol para determinar el rango de la mediana que puede seleccionar en O (log (n)).

Answer 5

Podemos diferenciar un montón mínimo y máximo para almacenar números. Además, definimos una clase DynamicArray para el conjunto de números, con dos funciones: Insertar y Getmedian. El tiempo para insertar un nuevo número es O (lgn), mientras que el tiempo para obtener la mediana es O (1).

Esta solución se implementa en C ++ de la siguiente manera:

template<typename T> class DynamicArray
{
public:
    void Insert(T num)
    {
        if(((minHeap.size() + maxHeap.size()) & 1) == 0)
        {
            if(maxHeap.size() > 0 && num < maxHeap[0])
            {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<T>());

                num = maxHeap[0];

                pop_heap(maxHeap.begin(), maxHeap.end(), less<T>());
                maxHeap.pop_back();
            }

            minHeap.push_back(num);
            push_heap(minHeap.begin(), minHeap.end(), greater<T>());
        }
        else
        {
            if(minHeap.size() > 0 && minHeap[0] < num)
            {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<T>());

                num = minHeap[0];

                pop_heap(minHeap.begin(), minHeap.end(), greater<T>());
                minHeap.pop_back();
            }

            maxHeap.push_back(num);
            push_heap(maxHeap.begin(), maxHeap.end(), less<T>());
        }
    }

    int GetMedian()
    {
        int size = minHeap.size() + maxHeap.size();
        if(size == 0)
            throw exception("No numbers are available");

        T median = 0;
        if(size & 1 == 1)
            median = minHeap[0];
        else
            median = (minHeap[0] + maxHeap[0]) / 2;

        return median;
    }

private:
    vector<T> minHeap;
    vector<T> maxHeap;
};

Para un análisis más detallado, consulte mi blog: http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html .

Answer 6

Recibí la misma pregunta de la entrevista y se me ocurrió la solución de dos pilas en el post de wrang-wrang. Como él dice, el tiempo por operación es O (log n) en el peor de los casos. El tiempo esperado también es O (log n) porque tiene que "abrir un elemento" 1/4 del tiempo asumiendo entradas aleatorias.

Posteriormente lo pensé más y descubrí cómo obtener el tiempo esperado constante; de hecho, el número esperado de comparaciones por elemento se convierte en 2 + o (1). Puedes ver mi artículo en http://denenberg.com/omf.pdf .

Por cierto, las soluciones analizadas aquí requieren espacio O (n), ya que debe guardar todos los elementos. Un enfoque completamente diferente, que requiere solo espacio O (log n), le proporciona una aproximación a la mediana (no la mediana exacta). Lo siento, no puedo publicar un enlace (estoy limitado a un enlace por publicación) pero mi artículo tiene sugerencias.

Answer 7

Su análisis de complejidad es confuso. Digamos que se agregan n artículos en total; queremos generar el flujo de n medianas (donde la i en el flujo es la mediana de los primeros i elementos) de manera eficiente.

Creo que esto se puede hacer en tiempo O (n * lg n) usando dos colas de prioridad (por ejemplo, binary o fibonacci Heap); una cola para los elementos por debajo de la mediana actual (por lo que el elemento más grande está en la parte superior), y la otra para los artículos por encima de ella (en este montón, el más pequeño está en la parte inferior). Tenga en cuenta que en los montones de Fibonacci (y otros), la inserción se amortiza con O (1); solo está haciendo estallar un elemento que es O (lg n).

Esto se denominaría un algoritmo de "selección de mediana en línea", aunque Wikipedia solo habla sobre la selección en línea mín / máx. Aquí hay un algoritmo aproximado , y un límite inferior en la selección de la mediana en línea determinista y aproximada (un límite inferior significa que no es posible un algoritmo más rápido)

Si hay un pequeño número de valores posibles en comparación con n, probablemente pueda romper el límite inferior basado en la comparación al igual que lo hace para clasificar.

Answer 8

Un árbol equilibrado (por ejemplo, un árbol R / B) con un campo de tamaño aumentado debe encontrar la mediana en tiempo de lg (n) en el peor de los casos. Creo que está en el capítulo 14 del libro de texto de algoritmo clásico.