Que tipo de algoritmo requer um conjunto?

Nos meus primeiros cursos de programação, foi-me dito que eu deveria usar um conjunto sempre que preciso fazer coisas como remover duplicatas de algo. Por exemplo: para remover todas as duplicatas de um vetor, percorra o referido vetor e adicione cada elemento a um conjunto, e você terá ocorrências únicas. No entanto, eu também poderia fazer isso adicionando cada elemento a outro vetor e verificando se o elemento já existe. Suponho que, dependendo do idioma usado, pode haver uma diferença no desempenho. Mas existe uma razão para usar um conjunto diferente disso?

Basicamente: que tipos de algoritmos requerem um conjunto e não devem ser feitos com nenhum outro tipo de contêiner?

Você está perguntando sobre conjuntos especificamente, mas acho que sua pergunta é sobre um conceito maior: abstração. Você está absolutamente certo de que pode usar um vetor para fazer isso (se estiver usando Java, use ArrayList.) Mas por que parar aí? Para que você precisa do vetor? Você pode fazer isso tudo com matrizes.

Sempre que você precisar adicionar um item à matriz, você pode simplesmente fazer um loop sobre todos os elementos e, se ele não estiver lá, você poderá adicioná-lo no final. Mas, na verdade, você precisa primeiro verificar se há espaço na matriz. Se não houver, será necessário criar uma nova matriz maior e copiar todos os elementos existentes da matriz antiga para a nova matriz e, em seguida, você poderá adicionar o novo elemento. Obviamente, você também precisa atualizar todas as referências à matriz antiga para apontar para a nova. Já fez tudo isso? Ótimo! Agora, o que estávamos tentando realizar de novo?

Ou, em vez disso, você pode usar uma instância Set e apenas chamar add(). A razão pela qual os conjuntos existem é que eles são uma abstração útil para muitos problemas comuns. Por exemplo, digamos que você deseja rastrear itens e reagir quando um novo é adicionado. Você chama add()um conjunto e ele retorna trueou com falsebase em se o conjunto foi modificado. Você poderia escrever tudo manualmente usando primitivas, mas por quê?

Na verdade, pode haver um caso em que você possui uma lista e deseja remover duplicatas. O algoritmo que você propõe é basicamente a maneira mais lenta que você pode fazer isso. Existem algumas maneiras mais rápidas comuns: agrupá-las ou classificá-las. Ou você pode adicioná-los a um conjunto que implementa um desses algoritmos.

No início de sua carreira / educação, o foco é construir esses algoritmos e entendê-los, e é importante fazer isso. Mas não é isso que desenvolvedores profissionais fazem normalmente. Eles usam essas abordagens para criar coisas muito mais interessantes e o uso de implementações pré-criadas e confiáveis ​​economiza muito tempo.

Suponho que, dependendo do idioma usado, pode haver uma diferença no desempenho. Mas existe uma razão para usar um conjunto diferente disso?

Ah, sim, (mas não é desempenho.)

Use um conjunto quando puder usá-lo, porque não usá-lo significa que você deve escrever um código extra. Usar um conjunto facilita o que você está fazendo. Todo esse teste de lógica de exclusividade está oculto em outro lugar onde você não precisa pensar sobre isso. Está em um local que já foi testado e você pode confiar que funciona.

Escreva seu próprio código para fazer isso e você precisa se preocupar com isso. Bleh. Quem quer fazer isso?

Basicamente: que tipos de algoritmos requerem um conjunto e não devem ser feitos com nenhum outro tipo de contêiner?

Não há algoritmo que "não deva ser feito com nenhum outro tipo de contêiner". Existem simplesmente algoritmos que podem tirar proveito dos conjuntos. É bom quando você não precisa escrever um código extra.

Agora, não há nada de especial em relação a esse aspecto. Você sempre deve usar a coleção que melhor se adapta às suas necessidades. Em java, achei esta imagem útil para tomar essa decisão. Você notará que ele tem três tipos diferentes de conjuntos.

E como o @germi aponta corretamente, se você usar a coleção certa para o trabalho, seu código ficará mais fácil para outras pessoas lerem.

No entanto, eu também poderia fazer isso adicionando cada elemento a outro vetor e verificando se o elemento já existe.

Se você fizer isso, estará implementando a semântica de um conjunto na parte superior da estrutura de dados vetoriais. Você está escrevendo um código extra (que pode conter erros) e o resultado será extremamente lento se você tiver muitas entradas.

Por que você deseja fazer isso usando uma implementação de conjunto existente, testada e eficiente?

As entidades de software que representam entidades do mundo real geralmente são conjuntos logicamente. Por exemplo, considere um carro. Os carros têm identificadores exclusivos e o grupo de carros forma um conjunto. A noção de conjunto serve como uma restrição à coleta de carros que um programa pode conhecer e restringir os valores dos dados é muito valioso.

Além disso, os conjuntos têm uma álgebra muito bem definida. Se você tem um conjunto de carros pertencentes a George e um conjunto pertencente a Alice, então o sindicato é claramente o conjunto pertencente a George e Alice, mesmo que George e Alice possuam o mesmo carro. Portanto, os algoritmos que devem usar conjuntos são aqueles em que a lógica das entidades envolvidas exibe características do conjunto. Isso acaba sendo bastante comum.

Como os conjuntos são implementados e como a restrição de exclusividade é garantida é outra questão. Espera-se encontrar uma implementação apropriada para a lógica do conjunto que elimine duplicados, uma vez que os conjuntos são tão fundamentais para a lógica, mas mesmo se você fizer a implementação, a garantia de exclusividade é intrínseca à inserção de um item em um conjunto e você não deveria estar "verificando se o elemento já existe".

Além das características de desempenho (que são muito significativas e não devem ser descartadas com tanta facilidade), os Conjuntos são muito importantes como uma coleção abstrata.

Você poderia emular o comportamento de conjunto (ignorando o desempenho) com uma matriz? Sim absolutamente! Toda vez que você insere, é possível verificar se o elemento já está na matriz e, em seguida, adicionar o elemento apenas se ainda não foi encontrado. Mas é algo que você conscientemente precisa estar ciente e lembre-se sempre que inserir no seu Array-Psuedo-Set. Oh, o que é isso, você inseriu uma vez diretamente, sem primeiro procurar duplicatas? Bem, sua matriz quebrou sua invariável (que todos os elementos são únicos e, equivalentemente, que não existem duplicatas).

Então, o que você faria para contornar isso? Você criaria um novo tipo de dados, chamado (digamos PsuedoSet), que agrupa uma matriz interna e expõe uma insertoperação publicamente, o que aplicará a exclusividade dos elementos. Como a matriz agrupada é acessível apenas por meio desta insertAPI pública , você garante que nunca haverá duplicatas. Agora adicione um hash para melhorar o desempenho das containsverificações e, mais cedo ou mais tarde, você perceberá que implementou uma versão completa Set.

Eu também responderia com uma declaração e uma pergunta de acompanhamento:

Nos meus primeiros cursos de programação, foi-me dito que eu deveria usar uma matriz sempre que precisar fazer coisas como armazenar vários elementos ordenados de alguma coisa. Por exemplo: para armazenar uma coleção de nomes de colegas de trabalho. No entanto, eu também poderia fazer isso alocando memória não processada e definindo o valor do endereço de memória fornecido pelo ponteiro de início + algum deslocamento.

Você poderia usar um ponteiro bruto e compensações corrigidas para imitar uma matriz? Sim absolutamente! Toda vez que você insere, é possível verificar se o deslocamento não desaparece no final da memória alocada com a qual você está trabalhando. Mas isso é algo que você conscientemente precisa estar ciente e lembre-se sempre que inserir no seu Pseudo-Array. Oh, o que é isso, você inseriu uma vez diretamente, sem primeiro verificar o deslocamento? Welp, há uma falha de segmentação com o seu nome!

Então, o que você faria para contornar isso? Você criaria um novo tipo de dados, chamado (digamos PsuedoArray), que agrupa um ponteiro e um tamanho e expõe uma insertoperação publicamente, o que reforçará que o deslocamento não exceda o tamanho. Como os dados agrupados são acessíveis apenas por essa insertAPI pública , você garante que nenhum buffer overflow possa ocorrer. Agora adicione outras funções de conveniência (redimensionamento de matriz, exclusão de elemento etc.) e, mais cedo ou mais tarde, você perceberá que implementou uma versão completa Array.

Existem todos os tipos de algoritmos baseados em conjuntos, particularmente nos casos em que você precisa executar interseções e uniões de conjuntos e ter o resultado como um conjunto.

Os algoritmos baseados em conjuntos são muito usados ​​em vários algoritmos de localização de caminhos, etc.

Para um manual sobre teoria dos conjuntos, acesse este link: http://people.umass.edu/partee/NZ_2006/Set%20Theory%20Basics.pdf

Se você precisar de semântica de conjunto, use um conjunto. Isso evitará erros devido a duplicatas falsas, porque você esqueceu de remover o vetor / lista em algum momento, e será mais rápido do que você pode remover constantemente o vetor / lista.

Na verdade, acho que os contêineres de conjunto padrão são inúteis e prefiro usar apenas matrizes, mas faço isso de uma maneira diferente.

Para calcular interseções de conjuntos, eu percorro a primeira matriz e março os elementos com um único bit. Depois, percorro a segunda matriz e procuro por elementos marcados. Voila, defina a interseção em tempo linear com muito menos trabalho e memória que uma tabela de hash, por exemplo, uniões e diferenças são igualmente simples de aplicar usando esse método. Ajuda que minha base de código gire em torno de elementos de indexação em vez de duplicá-los (eu duplico índices em elementos, não os dados dos próprios elementos) e raramente precisa de algo para ser classificado, mas não uso uma estrutura de dados definida há anos. um resultado.

Eu também tenho algum código C de quebra de bits que eu uso mesmo quando os elementos não oferecem campo de dados para tais propósitos. Envolve o uso da memória dos próprios elementos, definindo o bit mais significativo (que eu nunca uso) para marcar os elementos atravessados. Isso é bastante nojento, não faça isso a menos que você esteja realmente trabalhando no nível de montagem próxima, mas só queria mencionar como isso pode ser aplicável mesmo nos casos em que os elementos não fornecem algum campo específico para a travessia, se você puder garantir que certos bits nunca serão usados. Ele pode calcular uma interseção definida entre 200 milhões de elementos (cerca de 2,4 GB de dados) em menos de um segundo no meu d7 i7. Tente fazer uma interseção definida entre duas std::setinstâncias que contêm cem milhões de elementos cada um ao mesmo tempo; nem chega perto.

Isso de lado ...

No entanto, eu também poderia fazer isso adicionando cada elemento a outro vetor e verificando se o elemento já existe.

Essa verificação para ver se um elemento já existe no novo vetor geralmente será uma operação de tempo linear, o que tornará a interseção do conjunto em si uma operação quadrática (quantidade explosiva de trabalho quanto maior o tamanho da entrada). Eu recomendo a técnica acima se você quiser usar vetores ou matrizes simples e antigos e fazê-lo de uma maneira que seja maravilhosa.

Basicamente: que tipos de algoritmos requerem um conjunto e não devem ser feitos com nenhum outro tipo de contêiner?

Nenhuma se você perguntar a minha opinião tendenciosa se estiver falando sobre isso no nível do contêiner (como em uma estrutura de dados implementada especificamente para fornecer operações de conjunto com eficiência), mas há muitas que exigem lógica de conjunto no nível conceitual. Por exemplo, digamos que você queira encontrar as criaturas em um mundo de jogo capazes de voar e nadar, e você tem criaturas voadoras em um conjunto (se você usa ou não um contêiner definido) e aquelas que podem nadar em outro . Nesse caso, você deseja uma interseção definida. Se você quer criaturas que podem voar ou são mágicas, use uma união definida. É claro que você realmente não precisa de um contêiner definido para implementar isso, e a implementação mais ideal geralmente não precisa ou deseja um contêiner projetado especificamente para ser um conjunto.

Saindo de Tangente

Tudo bem, recebi algumas perguntas legais do JimmyJames sobre essa abordagem de interseção. É meio que desviar de assunto, mas, bem, estou interessado em ver mais pessoas usarem essa abordagem intrusiva básica para definir interseções, para que não construam estruturas auxiliares inteiras, como árvores binárias balanceadas e tabelas de hash apenas para fins de operações de conjunto. Como mencionado, o requisito fundamental é que as listas copiem elementos rasos para que indexem ou apontem para um elemento compartilhado que possa ser "marcado" como atravessado pela passagem pela primeira lista ou matriz não classificada ou o que quer que seja captado na segunda passar pela segunda lista.

No entanto, isso pode ser realizado praticamente mesmo em um contexto de multithreading sem tocar nos elementos, desde que:

1. Os dois agregados contêm índices para os elementos.
2. O intervalo de índices não é muito grande (digamos [0, 2 ^ 26), nem bilhões ou mais) e é razoavelmente densamente ocupado.

Isso nos permite usar uma matriz paralela (apenas um bit por elemento) com a finalidade de definir operações. Diagrama:

A sincronização de encadeamentos só precisa estar presente ao adquirir uma matriz de bits paralelos do pool e liberá-lo de volta para o pool (feito implicitamente ao sair do escopo). Os dois loops reais para executar a operação definida não precisam envolver nenhuma sincronização de threads. Nem precisamos usar um pool de bits paralelo se o encadeamento puder apenas alocar e liberar os bits localmente, mas o pool de bits pode ser útil para generalizar o padrão em bases de código que se encaixam nesse tipo de representação de dados, onde os elementos centrais são frequentemente referenciados por índice para que cada thread não precise se preocupar com o gerenciamento eficiente de memória. Os principais exemplos para minha área são sistemas de componentes de entidade e representações de malha indexada. Ambas frequentemente precisam definir interseções e tendem a se referir a tudo armazenado centralmente (componentes e entidades no ECS e vértices, arestas,

Se os índices não estiverem densamente ocupados e dispersos esparsamente, isso ainda será aplicável com uma implementação esparsa razoável da matriz bit / booleana paralela, como aquela que armazena apenas memória em blocos de 512 bits (64 bytes por nó desenrolado que representa 512 índices contíguos ) e pula a alocação de blocos contíguos completamente vazios. Provavelmente, você já está usando algo assim se suas estruturas de dados centrais forem escassamente ocupadas pelos próprios elementos.

... idéia semelhante para um conjunto de bits esparso para servir como uma matriz de bits paralela. Essas estruturas também se prestam à imutabilidade, pois é fácil copiar blocos grandes de cópia superficial que não precisam ser copiados em profundidade para criar uma nova cópia imutável.

Novamente, definir interseções entre centenas de milhões de elementos pode ser feito em menos de um segundo usando essa abordagem em uma máquina muito comum, e isso está dentro de um único encadeamento.

Isso também pode ser feito em menos da metade do tempo, se o cliente não precisar de uma lista de elementos para a interseção resultante, como se ele quiser apenas aplicar alguma lógica aos elementos encontrados nas duas listas, e nesse ponto eles poderão simplesmente passar um ponteiro de função ou functor ou delegado ou qualquer outra coisa a ser chamada de volta para processar intervalos de elementos que se cruzam. Algo para esse efeito:

// '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)
}

... ou algo nesse sentido. A parte mais cara do pseudocódigo no primeiro diagrama está intersection.append(index)no segundo loop, e isso se aplica mesmo a std::vectorreservado antecipadamente ao tamanho da lista menor.

E se eu copiar profundamente tudo?

Bem, pare com isso! Se você precisar definir interseções, isso implica que você está duplicando dados para interceptar. As chances são de que mesmo os menores objetos não sejam menores que um índice de 32 bits. É muito possível reduzir o intervalo de endereçamento dos seus elementos para 2 ^ 32 (2 ^ 32 elementos, e não 2 ^ 32 bytes), a menos que você realmente precise de mais de ~ 4,3 bilhões de elementos instanciados, quando é necessária uma solução totalmente diferente ( e que definitivamente não está usando contêineres definidos na memória).

Correspondências principais

E os casos em que precisamos executar operações de conjunto em que os elementos não são idênticos, mas podem ter chaves correspondentes? Nesse caso, a mesma ideia que acima. Nós apenas precisamos mapear cada chave exclusiva para um índice. Se a chave for uma cadeia, por exemplo, as cadeias internas podem fazer exatamente isso. Nesses casos, é necessária uma boa estrutura de dados, como uma tabela trie ou hash, para mapear chaves de string para índices de 32 bits, mas não precisamos dessas estruturas para realizar as operações definidas nos índices de 32 bits resultantes.

Um monte de soluções algorítmicas e estruturas de dados muito baratas e diretas se abrem assim quando podemos trabalhar com índices para elementos em um intervalo muito razoável, não no intervalo de endereçamento completo da máquina e, portanto, muitas vezes é mais do que valer a pena capaz de obter um índice exclusivo para cada chave exclusiva.

Eu amo índices!

Eu amo índices tanto quanto pizza e cerveja. Quando eu tinha mais de 20 anos, entrei no C ++ e comecei a projetar todos os tipos de estruturas de dados totalmente compatíveis com os padrões (incluindo os truques envolvidos para desambiguar um editor de preenchimento de um editor de intervalo em tempo de compilação). Em retrospecto, foi uma grande perda de tempo.

Se você gira seu banco de dados em torno de armazenar elementos centralmente em matrizes e indexá-los, em vez de armazená-los de uma maneira fragmentada e potencialmente em todo o intervalo endereçável da máquina, poderá acabar explorando um mundo de possibilidades algorítmicas e de estrutura de dados apenas projetar contêineres e algoritmos que giram em torno de simples intou antigos int32_t. E eu achei o resultado final muito mais eficiente e fácil de manter, onde eu não estava constantemente transferindo elementos de uma estrutura de dados para outra para outra para outra.

Alguns exemplos de casos de uso em que você pode simplesmente assumir que qualquer valor exclusivo de Tpossui um índice exclusivo e terá instâncias residentes em uma matriz central:

Classificações de raiz multithread que funcionam bem com números inteiros não assinados para índices . Na verdade, eu tenho uma classificação de raiz multithread que leva cerca de 1/10 do tempo para classificar cem milhões de elementos como a classificação paralela da própria Intel, e a Intel já é 4 vezes mais rápida do que std::sortpara essas entradas grandes. É claro que a Intel é muito mais flexível, pois é uma classificação baseada em comparação e pode classificar as coisas lexicograficamente, por isso é comparar maçãs com laranjas. Mas aqui muitas vezes eu preciso apenas de laranjas, como se fosse uma passagem de classificação radix apenas para obter padrões de acesso à memória compatíveis com cache ou filtrar duplicatas rapidamente.

Capacidade de criar estruturas vinculadas, como listas vinculadas, árvores, gráficos, tabelas de hash de encadeamento separadas, etc. sem alocações de heap por nó . Podemos apenas alocar os nós em massa, paralelos aos elementos, e vinculá-los a índices. Os próprios nós se tornam um índice de 32 bits para o próximo nó e são armazenados em uma grande matriz, assim:

Amigável para processamento paralelo. Muitas vezes, as estruturas vinculadas não são tão amigáveis ​​para o processamento paralelo, pois é no mínimo estranho tentar obter paralelismo em árvore ou em lista vinculada, em vez de, digamos, apenas fazer um loop for paralelo através de uma matriz. Com a representação de índice / matriz central, sempre podemos ir para essa matriz central e processar tudo em loops paralelos. Sempre temos essa matriz central de todos os elementos que podemos processar dessa maneira, mesmo que apenas desejemos processar alguns (nesse ponto, você pode processar os elementos indexados por uma lista classificada por radix para acesso amigável ao cache por meio da matriz central).

Pode associar dados a cada elemento em tempo real, em tempo constante . Como no caso da matriz paralela de bits acima, podemos associar dados paralelos de maneira fácil e extremamente barata a elementos para, digamos, processamento temporário. Isso tem casos de uso além dos dados temporários. Por exemplo, um sistema de malha pode permitir que os usuários anexem quantos mapas UV a uma malha desejarem. Nesse caso, não podemos apenas codificar quantos mapas UV haverá em cada vértice e face usando uma abordagem AoS. Precisamos ser capazes de associar esses dados em tempo real, e matrizes paralelas são úteis e muito mais baratas do que qualquer tipo de contêiner associativo sofisticado, até tabelas de hash.

É claro que matrizes paralelas são desaprovadas devido à sua natureza propensa a erros de manter matrizes paralelas sincronizadas umas com as outras. Sempre que removemos um elemento no índice 7 da matriz "raiz", por exemplo, também precisamos fazer a mesma coisa para os "filhos". No entanto, na maioria dos idiomas, é fácil generalizar esse conceito em um contêiner de uso geral, de modo que a lógica complicada para manter matrizes paralelas sincronizadas entre si só precisa existir em um local em toda a base de código, e esse contêiner de matriz paralela pode use a implementação de matriz esparsa acima para evitar desperdiçar muita memória em espaços vazios contíguos na matriz a serem recuperados nas inserções subsequentes.

Mais elaboração: Árvore Bitset esparsa

Tudo bem, recebi um pedido para elaborar um pouco mais que acho sarcástico, mas vou fazê-lo de qualquer maneira, porque é muito divertido! Se as pessoas quiserem levar essa idéia a níveis totalmente novos, é possível executar interseções sem nem mesmo fazer um loop linear de elementos N + M. Esta é minha estrutura de dados definitiva que uso há anos e basicamente modelos set<int>:

O motivo pelo qual ele pode executar interseções de conjuntos sem inspecionar cada elemento nas duas listas é porque um único bit de conjunto na raiz da hierarquia pode indicar que, digamos, um milhão de elementos contíguos estão ocupados no conjunto. Ao inspecionar um pouco, podemos saber que N índices no intervalo [first,first+N)estão no conjunto, onde N pode ser um número muito grande.

Na verdade, eu uso isso como um otimizador de loop ao percorrer índices ocupados, porque vamos dizer que existem 8 milhões de índices ocupados no conjunto. Bem, normalmente teríamos que acessar 8 milhões de números inteiros na memória nesse caso. Com este, ele pode apenas inspecionar alguns bits e criar faixas de índice de índices ocupados para percorrer. Além disso, os intervalos de índices apresentados estão em ordem classificada, o que possibilita um acesso seqüencial muito amigável ao cache, em vez de, por exemplo, iterar através de uma matriz não classificada de índices usada para acessar os dados do elemento original. É claro que essa técnica se sai pior em casos extremamente esparsos, com o pior cenário sendo como todo índice único sendo um número par (ou todos sendo ímpares); nesse caso, não há regiões contíguas. Mas nos meus casos de uso, pelo menos,

Para verificar se um conjunto contendo n elementos contém outro elemento, X normalmente leva tempo constante. Para verificar se uma matriz que contém n elementos contém outro elemento, X normalmente leva tempo O (n). Isso é ruim, mas se você deseja remover as duplicatas de n itens, de repente leva O (n) no tempo em vez de O (n ^ 2); 100.000 itens trarão seu computador de joelhos.

E você está pedindo mais razões? "Além das filmagens, você gostou da noite, senhora Lincoln?"