algorithm - secuenciales - estructura de datos organizacion de archivos

¿Qué estructura de datos utiliza el almacenamiento O(n) con el tiempo de consulta O(registro n) que debo usar para las consultas de rango mínimo?

Question

Estoy sorprendido por la siguiente pregunta de tarea para una clase de algoritmos:

Supongamos que nos dan una secuencia de n valores x ₁ , x ₂ ... x _n , y buscamos responder rápidamente a las consultas repetidas de la forma: dados i y j, encuentre el valor más pequeño en x _i ... x _j

Diseñe una estructura de datos que utilice el espacio O (n) y responda a las consultas en tiempo O (log n).

En primer lugar, no estoy seguro de si una secuencia se refiere a un conjunto ordenado, o un conjunto sin ordenar, pero como no dice lo contrario, asumiré que la secuencia significa sin clasificar.

Entonces, me doy cuenta de que esto obviamente debe involucrar un árbol binario, si estamos hablando del tiempo de búsqueda O (log N). Básicamente, creo que tienes un conjunto S e insertas cada elemento en S en un árbol binario. El problema es que la pregunta básicamente quiere que se me ocurra una manera de responder las consultas en las que se me asigna un rango de índices en un conjunto sin clasificar , y luego determinar el valor más bajo de ese rango en tiempo O (log N). ¿Cómo es eso posible? Incluso si cada número del conjunto se inserta en el árbol, lo mejor que puedo hacer es buscar cualquier número en particular en tiempo O (registro N). Esto no me permite encontrar el valor más bajo en un rango de números sin clasificar en S

¿Alguna sugerencia?

Answer 1

¿Has considerado un árbol de intervalo?

En cuanto a la entrada de wikipedia, parece coincidir con lo que está pidiendo. http://en.wikipedia.org/wiki/Interval_tree

EDITAR:

Sí, parece que los árboles de intervalo no son adecuados para este escenario ...

Answer 2

Algunos insultos:

Supongamos que almacena, de alguna manera, el mínimo de todos los subarrays * bien alineados de longitud 1, 2, 4, 8, ...? ¿Cuántos de estos mínimos puede salirse con la mirada para devolver la respuesta correcta? ¿Cómo puede almacenarlos para poder recuperarlos de manera eficiente?

(* por ejemplo, tienda min (x ₀ ... ₃ ) y min (x ₄ ... x ₇ ), pero no min (x ₁ ... x ₄ ))

Answer 3

Bien, creo que tengo un buen comienzo para ti y aprendí algo nuevo en el proceso.

Me gustaría echar un vistazo a la entrada de Wikipedia sobre los árboles cartesianos . No voy a decirte más que eso por temor a hacer tu tarea por ti, pero pareces un tipo inteligente, así que imagino que puedes resolverlo.

¡Gracias por ayudarme a aprender una nueva estructura de datos, por cierto!

Answer 4

La definición de sequence es un set ordenado ( no ordenado).

Saber que el conjunto está ordenado le permite utilizar un árbol cartesiano, que es una estructura de datos ideal para consultas de rango mínimo .

Answer 5

Puede utilizar ''Árbol de segmentos'' . En el segmento tress tanto el tiempo de actualización como el de consulta es O (logn). Aquí están los enlaces si quieres entender cómo funciona.

1. https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
2. https://www.youtube.com/watch?v=ZBHKZF5w4YU

Answer 6

Si el conjunto estuviera ordenado, no necesitarías un árbol. El elemento más pequeño en el rango [i, j] tendría un índice i.

Entonces, supongamos que los elementos de su secuencia se almacenaron en orden de sus índices en las hojas de un árbol. ¿Puede almacenar información adicional ( ejem , quizás algún tipo de mínimo y máximo) en cada nodo interior para facilitar su consulta?

Si es así, entonces si el árbol está equilibrado, y si puede responder a su consulta observando solo las dos rutas desde la raíz hasta los dos elementos en {i, j}, logrará el costo de búsqueda de O (registro N) . Como un árbol binario equilibrado con N hojas contiene (2N-1) nodos totales, también cumplirá con su límite de almacenamiento O (N).

MÁS DETALLE: considere calcular el valor mínimo en el rango [i, j].

En cada nodo interior A del árbol, mantenga el valor mínimo para todas las hojas debajo de él. Esto se puede calcular de abajo hacia arriba cuando se construye el árbol por primera vez.

Ahora comienza en la hoja i. Suba por el árbol, manteniendo como su valor mínimo candidato el valor en i o cualquier cosa que se sepa que está a la derecha de i y a la izquierda de j. Detenga un nodo debajo del ancestro mutuo de i y j.

Comenzar de nuevo en la hoja j. Sube por el árbol, una vez más manteniendo como mínimo tu candidato el valor en j o cualquier cosa que se sepa que está tanto a la izquierda como a la derecha de i

Su mínimo para [i, j] es entonces el mínimo de los dos valores que ha calculado. Calcular el máximo es análogo. El requisito de almacenamiento total es de 2 valores por nodo interior más dos punteros por nodo interior más un valor por hoja, que es N + 4 (N-1) para un árbol completo.

El camino que recorre el árbol desde la hoja i, es el mismo camino que viajaría por el árbol si estuviera buscando la hoja i.

CÓDIGO DE C # PARA LA BÚSQUEDA:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RangeSearch
{
    public class RangeSearch
    {
        int[] tree;
        int N;

        int LeafLocation(int leafNumber) { return leafNumber + N - 1; }
        int LeafValue(int leafNumber) { return tree[ LeafLocation(leafNumber)]; }
        int LeftChild(int x) { return 2*x + 1; }
        int RightChild(int x) { return 2*x + 2; }
        int Parent(int x) { return (x-1)/2; }
        bool IsPowerOf2(int x) { while (x > 0) { if (x == 1) return true; if ((x & 1) == 1 ) return false; x = x >> 1; } return false; }
        bool IsAncestorOf( int x, int y ) { if( x>y ) return false;  return x==y || IsAncestorOf(LeftChild(x), y) || IsAncestorOf(RightChild(x),y); } // note: violating time bound for legibility, can fix by storing min/max descendant index at each node

        public RangeSearch(params int[] vals)
        {
            if (!IsPowerOf2(vals.Length))
                throw new ArgumentException("this implementation restricted to N being power of 2");
            N = vals.Length;
            tree = new int[2 * N - 1];
            // the right half of the array contains the leaves
            vals.CopyTo(tree, N - 1);
            // the left half of the array contains the interior nodes, each of which holds the minimum of all its children
            for (int i = N - 2; i >= 0; i--)
                tree[i] = Math.Min(tree[LeftChild(i)], tree[RightChild(i)]);           
        }

        public int FindMin(int a, int b)
        {
            if( a>b )
                throw new ArgumentException( "FindMin expects a range [a,b] with a<=b" );
            int x = Walk( a, true, b);
            int y = Walk( b, false, a);
            return Math.Min(x, y);
        }

        int Walk( int leafNumber, bool leftSide, int otherLeafNumber )
        {
            int minSoFar =  LeafValue(leafNumber);
            int leafLocation = LeafLocation(leafNumber);
            int otherLeafLocation = LeafLocation(otherLeafNumber);
            int parent = Parent(leafLocation);
            bool cameFromLeft = (leafLocation == LeftChild(parent));
            return Walk2(minSoFar, parent, cameFromLeft, leftSide, otherLeafLocation);
        }
        int Walk2(int minSoFar, int node, bool cameFromLeft, bool leftSide, int otherLeafLocation)
        {
            if (IsAncestorOf(node, otherLeafLocation))
                return minSoFar;
            if (leftSide)
                minSoFar = !cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[RightChild(node)]);
            else
                minSoFar = cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[LeftChild(node)]);
            return Walk2(minSoFar, Parent(node), node == LeftChild(Parent(node)), leftSide, otherLeafLocation);
        }
    }
}

CÓDIGO C # PARA PROBARLO:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace RangeSearch
{
    class Program
    {
        static void Main(string[] args)
        {
            RangeSearch rngA = new RangeSearch(9, 3, 7, 1);
            System.Diagnostics.Trace.Assert(3 == rngA.FindMin(0, 2) );
            System.Diagnostics.Trace.Assert(1 == rngA.FindMin(0, 3));
            System.Diagnostics.Trace.Assert(1 == rngA.FindMin(1, 3));

            RangeSearch rngB = new RangeSearch(1, 7, 3, 9);
            System.Diagnostics.Trace.Assert(3 == rngB.FindMin(1, 3));
            System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 3));
            System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 2));

            RangeSearch rngC = new RangeSearch(17, 21, 77, 70, 58, 79, 79, 89);
            System.Diagnostics.Trace.Assert(21 == rngC.FindMin(1, 7));

            RangeSearch rngD = new RangeSearch(94, 78, 88, 72, 95, 97, 89, 83);
            System.Diagnostics.Trace.Assert(72 == rngD.FindMin(1, 6));

            RangeSearch rngE = new RangeSearch(0, 66, 6, 43, 34, 34, 63, 49);
            System.Diagnostics.Trace.Assert(34 == rngE.FindMin(3, 4));

            Random rnd = new Random();
            for (int i = 0; i < 1000000; i++)
            {
                int[] tmp = new int[64];
                for (int j = 0; j < tmp.Length; j++)
                    tmp[j] = rnd.Next(0, 100);
                int a = rnd.Next(0, tmp.Length);
                int b = rnd.Next(a, tmp.Length);
                RangeSearch rng = new RangeSearch(tmp);
                System.Diagnostics.Trace.Assert(Min(tmp, a, b) == rng.FindMin(a, b));
            }
        }

        static int Min(int[] ar, int a, int b)
        {
            int x = ar[a];
            for (int i = a + 1; i <= b; i++)
                x = Math.Min(x, ar[i]);
            return x;
        }

    }
}