¿Qué tipo de algoritmo requiere un conjunto?

En mis primeros cursos de programación me dijeron que debía usar un conjunto cada vez que tuviera que hacer cosas como eliminar duplicados de algo. Por ejemplo: para eliminar todos los duplicados de un vector, itere a través de dicho vector y agregue cada elemento a un conjunto, luego tendrá ocurrencias únicas. Sin embargo, también podría hacerlo agregando cada elemento a otro vector y verificando si el elemento ya existe. Supongo que, dependiendo del idioma utilizado, puede haber una diferencia en el rendimiento. Pero, ¿hay alguna razón para usar un conjunto diferente a ese?

Básicamente: ¿qué tipos de algoritmos requieren un conjunto y no deberían hacerse con ningún otro tipo de contenedor?

Estás preguntando sobre conjuntos específicamente, pero creo que tu pregunta es sobre un concepto más amplio: abstracción. Tiene toda la razón en que puede usar un Vector para hacer esto (si está usando Java, use ArrayList en su lugar). Pero, ¿por qué detenerse allí? ¿Para qué necesitas el Vector? Puede hacer todo esto con matrices.

Cuando necesite agregar un elemento a la matriz, simplemente puede recorrer cada elemento y, si no está allí, agregarlo al final. Pero, en realidad, primero debe verificar si hay espacio en la matriz. Si no existe, deberá crear una nueva matriz que sea más grande y copiar todos los elementos existentes de la matriz anterior a la nueva matriz y luego puede agregar el nuevo elemento. Por supuesto, también debe actualizar cada referencia a la matriz anterior para que apunte a la nueva. ¿Tienes todo eso hecho? ¡Excelente! Ahora, ¿qué estábamos tratando de lograr de nuevo?

O, en su lugar, podría usar una instancia de Set y simplemente llamar add(). La razón por la que existen los conjuntos es porque son una abstracción que es útil para muchos problemas comunes. Por ejemplo, supongamos que desea realizar un seguimiento de los elementos y reaccionar cuando se agrega uno nuevo. Llama add()a un conjunto y este regresa trueo se falsebasa en si el conjunto fue modificado. Podrías escribir todo a mano usando primitivas, pero ¿por qué?

En realidad, puede haber un caso en el que tenga una Lista y desee eliminar duplicados. El algoritmo que propone es básicamente la forma más lenta de hacerlo. Hay un par de formas más rápidas comunes: agruparlas o clasificarlas. O bien, puede agregarlos a un conjunto que implementa uno de esos algoritmos.

Al principio de su carrera / educación, el enfoque está en construir estos algoritmos y comprenderlos, y es importante hacerlo. Pero eso no es lo que los desarrolladores profesionales hacen de manera normal. Utilizan estos enfoques para construir cosas mucho más interesantes y el uso de implementaciones predefinidas y confiables ahorra grandes cantidades de tiempo.

Supongo que, dependiendo del idioma utilizado, puede haber una diferencia en el rendimiento. Pero, ¿hay alguna razón para usar un conjunto diferente a ese?

Oh sí, (pero no es rendimiento).

Use un conjunto cuando pueda usar uno porque no usarlo significa que tiene que escribir código adicional. Usar un conjunto hace que lo que haces sea fácil de leer. Todas esas pruebas de lógica de unicidad están ocultas en otro lugar donde no tienes que pensar en ello. Está en un lugar que ya ha sido probado y puede confiar en que funciona.

Escriba su propio código para hacerlo y debe preocuparse por ello. Bleh ¿Quién quiere hacer eso?

Básicamente: ¿qué tipos de algoritmos requieren un conjunto y no deberían hacerse con ningún otro tipo de contenedor?

No existe un algoritmo que "no deba hacerse con ningún otro tipo de contenedor". Simplemente hay algoritmos que pueden aprovechar los conjuntos. Es agradable cuando no tienes que escribir código extra.

Ahora no hay nada particularmente especial sobre el conjunto a este respecto. Siempre debe usar la colección que mejor se adapte a sus necesidades. En Java, he encontrado que esta imagen es útil para tomar esa decisión. Notarás que tiene tres tipos diferentes de conjuntos.

Y como señala @germi con razón, si utiliza la colección correcta para el trabajo, su código será más fácil de leer para otros.

Sin embargo, también podría hacerlo agregando cada elemento a otro vector y verificando si el elemento ya existe.

Si hace eso, entonces está implementando la semántica de un conjunto encima de la estructura de datos del vector. Está escribiendo código adicional (que podría contener errores), y el resultado será extremadamente lento si tiene muchas entradas.

¿Por qué querrías hacer eso usando una implementación de conjunto existente, probada y eficiente?

Las entidades de software que representan entidades del mundo real a menudo son conjuntos lógicos. Por ejemplo, considere un automóvil. Los autos tienen identificadores únicos y un grupo de autos forma un conjunto. La noción de conjunto sirve como una restricción en la colección de Cars que un programa puede conocer y restringir los valores de los datos es muy valioso.

Además, los conjuntos tienen un álgebra muy bien definida. Si tiene un conjunto de automóviles propiedad de George y un conjunto propiedad de Alice, entonces la unión es claramente el conjunto propiedad de George y Alice, incluso si George y Alice poseen el mismo automóvil. Entonces, los algoritmos que deberían usar conjuntos son aquellos en los que la lógica de las entidades involucradas exhibe características de conjunto. Eso resulta ser bastante común.

Cómo se implementan los conjuntos y cómo se garantiza la restricción de unicidad es otra cuestión. Uno espera poder encontrar una implementación adecuada para la lógica del conjunto que elimine los duplicados dado que los conjuntos son tan fundamentales para la lógica, pero incluso si realiza la implementación usted mismo, la garantía de unicidad es intrínseca a la inserción de un elemento en un conjunto y no debería tener que "verificar si el elemento ya existe".

Además de las características de rendimiento (que son muy significativas y no deberían descartarse tan fácilmente), los conjuntos son muy importantes como una colección abstracta.

¿Podría emular el comportamiento del conjunto (ignorando el rendimiento) con una matriz? ¡Si, absolutamente! Cada vez que inserte, puede verificar si el elemento ya está en la matriz, y luego solo agregar el elemento si aún no se ha encontrado. Pero eso es algo de lo que debe estar consciente y recordar cada vez que se inserta en su Array-Psuedo-Set. Oh, ¿qué es eso, insertaste una vez directamente, sin primero buscar duplicados? Bien, tu matriz ha roto su invariante (que todos los elementos son únicos y, de manera equivalente, que no existen duplicados).

Entonces, ¿qué harías para evitar eso? Crearía un nuevo tipo de datos, lo llamaría (por ejemplo, PsuedoSet), que envuelve una matriz interna y expone una insertoperación públicamente, que impondrá la unicidad de los elementos. Dado que solo se puede acceder a la matriz envuelta a través de esta insertAPI pública , usted garantiza que nunca se producirán duplicados. Ahora agregue un poco de hashing para mejorar el rendimiento de las containscomprobaciones, y tarde o temprano se dará cuenta de que implementó un completo Set.

También respondería con una declaración y una pregunta de seguimiento:

En mis primeros cursos de programación me dijeron que debería usar una matriz siempre que necesite hacer cosas como almacenar múltiples elementos ordenados de algo. Por ejemplo: almacenar una colección de nombres de compañeros de trabajo. Sin embargo, también podría hacerlo asignando memoria sin procesar y estableciendo el valor de la dirección de memoria dada por el puntero de inicio + algún desplazamiento.

¿Podría usar un puntero sin formato y compensaciones fijas para imitar una matriz? ¡Si, absolutamente! Cada vez que inserte, puede verificar si el desplazamiento no se desvía del final de la memoria asignada con la que está trabajando. Pero eso es algo de lo que debe estar consciente y recordar cada vez que se inserta en su Pseudo-Array. Oh, ¿qué es eso, insertaste una vez directamente, sin comprobar primero el desplazamiento? ¡Bien, hay una falla de segmentación con tu nombre!

Entonces, ¿qué harías para evitar eso? Crearía un nuevo tipo de datos, lo llamaría (digamos PsuedoArray), que envuelve un puntero y un tamaño, y expone una insertoperación públicamente, lo que obligará a que el desplazamiento no exceda el tamaño. Dado que solo se puede acceder a los datos empaquetados a través de esta insertAPI pública , usted garantiza que no se puedan producir desbordamientos del búfer. Ahora agregue algunas otras funciones de conveniencia (cambio de tamaño de matriz, eliminación de elementos, etc.), y tarde o temprano se dará cuenta de que implementó un completo Array.

Hay todo tipo de algoritmos basados ​​en conjuntos, particularmente donde necesita realizar intersecciones y uniones de conjuntos y hacer que el resultado sea un conjunto.

Los algoritmos basados ​​en conjuntos se usan mucho en varios algoritmos de búsqueda de rutas, etc.

Para obtener una introducción a la teoría de conjuntos, consulte este enlace: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Si necesita semántica de conjunto, use un conjunto. Evitará errores debido a duplicados espurios porque olvidó podar el vector / lista en algún momento, y será más rápido de lo que puede hacer podando constantemente su vector / lista.

De hecho, considero que los contenedores de conjuntos estándar son en su mayoría inútiles y prefiero usar matrices, pero lo hago de una manera diferente.

Para calcular las intersecciones establecidas, recorro la primera matriz y marco los elementos con un solo bit. Luego itero a través de la segunda matriz y busco elementos marcados. Voila, establezca la intersección en tiempo lineal con mucho menos trabajo y memoria que una tabla hash, por ejemplo, las uniones y las diferencias son igualmente simples de aplicar utilizando este método. Ayuda que mi base de código gira en torno a la indexación de elementos en lugar de duplicarlos (duplico índices a elementos, no a los datos de los elementos en sí mismos) y rara vez necesita algo para ordenar, pero no he usado una estructura de datos establecida en años un resultado.

También tengo un código C malvado que manipula los bits, incluso cuando los elementos no ofrecen ningún campo de datos para tales fines. Implica usar la memoria de los elementos mismos estableciendo el bit más significativo (que nunca uso) con el propósito de marcar elementos atravesados. Eso es bastante asqueroso, no haga eso a menos que realmente esté trabajando a nivel de ensamblaje cercano, pero solo quería mencionar cómo puede ser aplicable incluso en los casos en que los elementos no proporcionan algún campo específico para el recorrido si puede garantizar que ciertos bits nunca serán utilizados. Puede calcular una intersección establecida entre 200 millones de elementos (alrededor de 2,4 gigas de datos) en menos de un segundo en mi dinky i7. Intente hacer una intersección establecida entre dos std::setinstancias que contengan cien millones de elementos cada una al mismo tiempo; Ni siquiera se acerca.

Eso aparte ...

Sin embargo, también podría hacerlo agregando cada elemento a otro vector y verificando si el elemento ya existe.

Esa comprobación para ver si un elemento ya existe en el nuevo vector generalmente será una operación de tiempo lineal, lo que hará que la intersección del conjunto sea una operación cuadrática (cantidad explosiva de trabajo cuanto mayor sea el tamaño de entrada). Recomiendo la técnica anterior si solo desea utilizar vectores o matrices antiguos simples y hacerlo de una manera que se amplíe maravillosamente.

Básicamente: ¿qué tipos de algoritmos requieren un conjunto y no deberían hacerse con ningún otro tipo de contenedor?

Ninguno si me pregunta mi opinión parcial si lo está hablando a nivel de contenedor (como en una estructura de datos implementada específicamente para proporcionar operaciones de conjunto de manera eficiente), pero hay muchos que requieren una lógica de conjunto a nivel conceptual. Por ejemplo, supongamos que desea encontrar las criaturas en un mundo de juego que son capaces de volar y nadar, y tiene criaturas voladoras en un conjunto (ya sea que use o no un contenedor de conjunto) y otras que puedan nadar en otro . En ese caso, desea una intersección establecida. Si quieres criaturas que pueden volar o son mágicas, entonces usas una unión fija. Por supuesto, en realidad no necesita un contenedor de conjuntos para implementar esto, y la implementación más óptima generalmente no necesita o desea un contenedor específicamente diseñado para ser un conjunto.

Saliendo de la tangente

Muy bien, recibí algunas buenas preguntas de JimmyJames con respecto a este enfoque de intersección establecida. Se está desviando un poco del tema, pero bueno, estoy interesado en ver a más personas usar este enfoque intrusivo básico para establecer la intersección, de modo que no estén construyendo estructuras auxiliares completas como árboles binarios equilibrados y tablas hash solo con el propósito de establecer operaciones. Como se mencionó, el requisito fundamental es que las listas de elementos de copia superficial para que estén indexando o señalando a un elemento compartido que se puede "marcar" como atravesado por el paso a través de la primera lista o matriz no ordenada o lo que sea que luego elija en el segundo pasar por la segunda lista.

Sin embargo, esto se puede lograr prácticamente incluso en un contexto de subprocesos múltiples sin tocar los elementos siempre que:

1. Los dos agregados contienen índices de los elementos.
2. El rango de índices no es demasiado grande (digamos [0, 2 ^ 26), no miles de millones o más) y están razonablemente densamente ocupados.

Esto nos permite usar una matriz paralela (solo un bit por elemento) con el fin de establecer operaciones. Diagrama:

La sincronización de subprocesos solo necesita estar allí cuando se adquiere una matriz de bits paralela del grupo y se vuelve a liberar al grupo (hecho implícitamente cuando se sale del alcance). Los dos bucles reales para realizar la operación de configuración no necesitan involucrar ninguna sincronización de subprocesos. Ni siquiera necesitamos usar un grupo de bits paralelos si el subproceso solo puede asignar y liberar los bits localmente, pero el grupo de bits puede ser útil para generalizar el patrón en bases de código que se ajustan a este tipo de representación de datos donde a menudo se hace referencia a elementos centrales por índice para que cada hilo no tenga que molestarse con una gestión eficiente de la memoria. Los principales ejemplos de mi área son los sistemas de entidad-componente y las representaciones de malla indexadas. Con frecuencia, ambos necesitan establecer intersecciones y tienden a referirse a todo lo almacenado centralmente (componentes y entidades en ECS y vértices, bordes,

Si los índices no están densamente ocupados y escasamente dispersos, esto todavía es aplicable con una implementación razonablemente escasa de la matriz booleana / bit paralela, como una que solo almacena memoria en fragmentos de 512 bits (64 bytes por nodo desenrollado que representa 512 índices contiguos ) y omite la asignación de bloques contiguos completamente vacíos. Lo más probable es que ya esté usando algo como esto si sus estructuras de datos centrales están escasamente ocupadas por los propios elementos.

... idea similar para un conjunto de bits disperso para servir como una matriz de bits paralela. Estas estructuras también se prestan a la inmutabilidad, ya que es fácil copiar bloques gruesos que no necesitan ser copiados en profundidad para crear una nueva copia inmutable.

Una vez más, se pueden establecer intersecciones entre cientos de millones de elementos en menos de un segundo utilizando este enfoque en una máquina muy promedio, y eso está dentro de un solo hilo.

También se puede hacer en menos de la mitad del tiempo si el cliente no necesita una lista de elementos para la intersección resultante, como si solo quisieran aplicar algo de lógica a los elementos que se encuentran en ambas listas, momento en el que simplemente pueden pasar un puntero de función o functor o delegado o lo que sea que se vuelva a llamar para procesar rangos de elementos que se cruzan. Algo a este efecto:

// 'func' receives a range of indices to
// process.
set_intersection(func):
{
    parallel_bits = bit_pool.acquire()

    // Mark the indices found in the first list.
    for each index in list1:
        parallel_bits[index] = 1

    // Look for the first element in the second list 
    // that intersects.
    first = -1
    for each index in list2:
    {
         if parallel_bits[index] == 1:
         {
              first = index
              break
         }
    }

    // Look for elements that don't intersect in the second
    // list to call func for each range of elements that do
    // intersect.
    for each index in list2 starting from first:
    {
        if parallel_bits[index] != 1:
        {
             func(first, index)
             first = index
        }
    }
    If first != list2.num-1:
        func(first, list2.num)
}

... o algo por el estilo. La parte más cara del pseudocódigo en el primer diagrama está intersection.append(index)en el segundo bucle, y eso se aplica incluso para los std::vectorreservados al tamaño de la lista más pequeña de antemano.

¿Qué sucede si copio todo en profundidad?

Bueno, para eso! Si necesita establecer intersecciones, significa que está duplicando datos para intersecarlos. Lo más probable es que incluso sus objetos más pequeños no sean más pequeños que un índice de 32 bits. Es muy posible reducir el rango de direccionamiento de sus elementos a 2 ^ 32 (2 ^ 32 elementos, no 2 ^ 32 bytes) a menos que realmente necesite más de ~ 4,3 mil millones de elementos instanciados, momento en el que se necesita una solución totalmente diferente ( y eso definitivamente no está usando contenedores de conjuntos en la memoria).

Partidos clave

¿Qué hay de los casos en los que necesitamos realizar operaciones de configuración donde los elementos no son idénticos pero podrían tener claves coincidentes? En ese caso, la misma idea que la anterior. Solo necesitamos asignar cada clave única a un índice. Si la clave es una cadena, por ejemplo, las cadenas internas pueden hacer exactamente eso. En esos casos, se requiere una estructura de datos agradable, como un trie o una tabla hash, para asignar claves de cadena a índices de 32 bits, pero no necesitamos tales estructuras para realizar las operaciones establecidas en los índices de 32 bits resultantes.

Se abren una gran cantidad de soluciones algorítmicas y estructuras de datos muy baratas y sencillas como estas cuando podemos trabajar con índices a elementos en un rango muy razonable, no el rango completo de direccionamiento de la máquina, por lo que a menudo vale la pena ser capaz de obtener un índice único para cada clave única.

¡Amo los índices!

Me encantan los índices tanto como la pizza y la cerveza. Cuando tenía 20 años, realmente me metí en C ++ y comencé a diseñar todo tipo de estructuras de datos totalmente compatibles con los estándares (incluidos los trucos involucrados para desambiguar un controlador de relleno de un controlador de rango en tiempo de compilación). En retrospectiva, fue una gran pérdida de tiempo.

Si gira su base de datos para almacenar elementos centralmente en matrices e indexarlos en lugar de almacenarlos de una manera fragmentada y potencialmente en todo el rango direccionable de la máquina, entonces puede terminar explorando un mundo de posibilidades algorítmicas y de estructura de datos con solo el diseño de los contenedores y algoritmos que giran en torno a secas into int32_t. Y descubrí que el resultado final era mucho más eficiente y fácil de mantener donde no estaba transfiriendo constantemente elementos de una estructura de datos a otra a otra.

Algunos ejemplos usan casos en los que puede suponer que cualquier valor único de Ttiene un índice único y tendrá instancias que residen en una matriz central:

Tipos de radios multiproceso que funcionan bien con enteros sin signo para índices . De hecho, tengo un tipo de matriz multiproceso que tarda aproximadamente 1/10 del tiempo en clasificar cien millones de elementos como el propio sistema paralelo de Intel, y el de Intel ya es 4 veces más rápido que std::sortpara entradas tan grandes. Por supuesto, Intel es mucho más flexible, ya que se basa en la comparación y puede clasificar las cosas lexicográficamente, por lo que compara manzanas con naranjas. Pero aquí a menudo solo necesito naranjas, como podría hacer un pase de clasificación de radix solo para lograr patrones de acceso a memoria amigables con la caché o filtrar duplicados rápidamente.

Capacidad para construir estructuras vinculadas como listas vinculadas, árboles, gráficos, tablas hash de encadenamiento separadas, etc. sin asignaciones de montón por nodo . Simplemente podemos asignar los nodos en masa, paralelos a los elementos, y vincularlos con índices. Los nodos se convierten en un índice de 32 bits para el siguiente nodo y se almacenan en una gran matriz, de esta manera:

Amigable para el procesamiento en paralelo. A menudo, las estructuras vinculadas no son tan amigables para el procesamiento en paralelo, ya que al menos es incómodo tratar de lograr el paralelismo en el árbol o el recorrido de la lista vinculada en lugar de, por ejemplo, simplemente hacer un bucle paralelo para una matriz. Con la representación de matriz índice / central, siempre podemos ir a esa matriz central y procesar todo en bucles paralelos gruesos. Siempre tenemos esa matriz central de todos los elementos que podemos procesar de esta manera, incluso si solo queremos procesar algunos (en ese momento, puede procesar los elementos indexados por una lista ordenada por radix para un acceso amigable a la caché a través de la matriz central).

Puede asociar datos a cada elemento sobre la marcha en tiempo constante . Al igual que en el caso de la matriz paralela de bits anterior, podemos asociar de manera fácil y extremadamente barata datos paralelos a elementos para, por ejemplo, el procesamiento temporal. Esto tiene casos de uso más allá de los datos temporales. Por ejemplo, un sistema de malla podría permitir que los usuarios adjunten tantos mapas UV a una malla como quieran. En tal caso, no podemos simplemente codificar cuántos mapas UV habrá en cada vértice y cara utilizando un enfoque AoS. Necesitamos poder asociar dichos datos sobre la marcha, y las matrices paralelas son útiles allí y mucho más baratas que cualquier tipo de contenedor asociativo sofisticado, incluso tablas hash.

Por supuesto, las matrices paralelas están mal vistas debido a su naturaleza propensa a errores de mantener las matrices paralelas sincronizadas entre sí. Cada vez que eliminamos un elemento en el índice 7 de la matriz "raíz", por ejemplo, también tenemos que hacer lo mismo para los "hijos". Sin embargo, en la mayoría de los idiomas es bastante fácil generalizar este concepto a un contenedor de propósito general para que la lógica difícil de mantener las matrices paralelas sincronizadas entre sí solo exista en un lugar en toda la base de código, y dicho contenedor de matriz paralela puede utilice la implementación de matriz dispersa anterior para evitar desperdiciar mucha memoria para espacios vacantes contiguos en la matriz que se reclamarán en inserciones posteriores.

Más elaboración: árbol escaso de Bitset

Muy bien, recibí una solicitud para elaborar un poco más, lo que creo que fue sarcástico, ¡pero lo haré de todos modos porque es muy divertido! Si la gente quiere llevar esta idea a niveles completamente nuevos, entonces es posible realizar intersecciones establecidas sin siquiera pasar en bucle lineal a través de elementos N + M. Esta es mi última estructura de datos que he estado usando durante años y básicamente modelos set<int>:

La razón por la que puede realizar intersecciones de conjuntos sin siquiera inspeccionar cada elemento en ambas listas es porque un solo bit de conjunto en la raíz de la jerarquía puede indicar que, digamos, un millón de elementos contiguos están ocupados en el conjunto. Simplemente inspeccionando un bit, podemos saber que N índices en el rango [first,first+N)están en el conjunto, donde N podría ser un número muy grande.

De hecho, utilizo esto como un optimizador de bucle cuando recorro índices ocupados, porque digamos que hay 8 millones de índices ocupados en el conjunto. Bueno, normalmente tendríamos que acceder a 8 millones de enteros en la memoria en ese caso. Con este, puede inspeccionar algunos bits y generar rangos de índice de índices ocupados para recorrer. Además, los rangos de índices que se presentan están ordenados, lo que permite un acceso secuencial muy amigable con la caché en lugar de, por ejemplo, iterar a través de una matriz no clasificada de índices utilizados para acceder a los datos del elemento original. Por supuesto, esta técnica es peor para los casos extremadamente escasos, con el peor de los casos como que cada índice sea un número par (o cada uno sea impar), en cuyo caso no hay regiones contiguas en absoluto. Pero en mis casos de uso al menos,

Para verificar si un conjunto que contiene n elementos contiene otro elemento, X generalmente toma un tiempo constante. Para verificar si una matriz que contiene n elementos contiene otro elemento, X generalmente toma O (n) tiempo. Eso es malo, pero si desea eliminar los duplicados de n elementos, de repente se necesita O (n) a tiempo en lugar de O (n ^ 2); 100,000 artículos pondrán su computadora de rodillas.

¿Y preguntas por más razones? "Además del tiroteo, ¿disfrutó la noche, Sra. Lincoln?"