Há alguns meses, finalmente tive que admitir que não era inteligente o suficiente para passar por alguns níveis do quebra-cabeça do
Snakebird . A única maneira de recuperar parte da auto-estima era escrever um solucionador. Então, eu poderia fingir que criar um programa para resolver o quebra-cabeça é quase o mesmo que resolvê-lo. O código para o programa C ++ resultante está disponível no
Github . A parte principal do código considerado no artigo é implementada em
search.he compress.h . Neste post, falarei principalmente sobre como otimizar a pesquisa pela primeira vez, o que exigiria de 50 a 100 GB de memória para caber em 4 GB.
Mais tarde vou escrever outro post, que descreverá as especificidades do jogo. Neste post, você precisa saber que não consegui encontrar boas alternativas à força bruta, porque nenhum dos truques usuais funcionou. O jogo tem muitos estados, porque existem muitos objetos em movimento ou empurrados, e a forma de alguns deles é importante, o que pode mudar com o tempo. Não havia heurística conservadora adequada para algoritmos como A * para restringir o espaço de pesquisa. O gráfico de pesquisa foi orientado e especificado implicitamente; portanto, a pesquisa simultânea nas direções para frente e para trás era impossível. O único movimento poderia mudar o estado de muitas maneiras não relacionadas, para que nada pudesse ser útil como fazer o
hash de Zobrist .
Estimativas aproximadas mostraram que no maior quebra-cabeça, depois de eliminar todas as posições simétricas, haverá cerca de 10 bilhões de estados. Mesmo depois de compactar as descrições de estado com densidade máxima, o tamanho do estado era de 8 a 10 bytes. Com 100 GB de memória, a tarefa seria trivial, mas não para minha máquina doméstica com 16 GB de memória. E como o Chrome precisa de 12 GB, meu suprimento de memória real está mais próximo de 4 GB. Tudo o que exceder esse volume terá que ser salvo no disco (disco rígido antigo e enferrujado).
Como ajustar 100 GB de dados em 4 GB de RAM? A) os estados precisam ser compactados para 1/20 do tamanho original já otimizado, ou b) o algoritmo deve ser capaz de salvar efetivamente os estados em disco e vice-versa, ou c) uma combinação dos dois métodos acima, ou d) preciso comprar mais RAM ou alugue uma poderosa máquina virtual por vários dias. Não considerei a opção D, porque é muito chata. As opções A e B foram excluídas após a prova de conceito usando gzip: um fragmento de uma descrição de estado de 50 MB foi compactado para apenas 35 MB. Isso é cerca de 7 bytes por estado, e minha memória tem cerca de 0,4 bytes por estado. Ou seja, a opção B permaneceu, embora a pesquisa pela primeira vez parecesse bastante inconveniente para armazenamento em unidades secundárias.
Conteúdo
Esta é uma postagem bastante longa, então aqui está uma breve visão geral das seguintes seções:
- Pesquisa da primeira largura da primeira largura - qual é o texto usual da pesquisa da primeira largura (BFS) e por que não é adequado para armazenar partes de um estado em disco?
- BFS com classificação e mesclagem - uma alteração no algoritmo para descarte eficiente de dados redundantes em lote.
- Compactação - reduzindo a quantidade de memória usada em cem vezes devido à combinação de compactação padrão e nativa.
- Oh-oh, eu trapacei! - nas primeiras seções, fiquei em silêncio sobre algo: não basta saber apenas onde está a solução, mas precisamos entender exatamente como alcançá-la. Nesta seção, atualizamos o algoritmo básico para que ele transfira dados suficientes para recriar a solução a partir do último estado.
- Classificar + mesclar com várias saídas - armazenar mais estados nega completamente os benefícios da compactação. O algoritmo de classificação + mesclagem precisa ser alterado para armazenar dois conjuntos de dados de saída: um, bem compactado, é usado durante a pesquisa e o outro é usado apenas para recriar a solução após encontrar o primeiro.
- Trocar - Trocar no Linux é muito pior do que eu pensava.
- Compactação de novos estados antes da mesclagem - até agora, as otimizações de memória funcionavam apenas com muitos estados visitados. Porém, a lista de novos estados gerados é muito maior do que você imagina. Esta seção mostra um diagrama para uma descrição mais eficiente de novos estados.
- Economizando espaço nos estados-pai - explore as vantagens e desvantagens entre usar CPU / memória para recriar a solução no final.
- O que não deu certo ou não deu certo - algumas idéias pareciam promissoras, mas, como resultado, tiveram que ser revertidas, enquanto outras, que deveriam ser pesquisadores, me parecem intuitivamente inadequadas neste caso.
Ampla pesquisa "por livro"
Como é a pesquisa pela primeira vez e por que você não deve usar um disco? Antes deste pequeno projeto, considerei apenas as opções de redação “de livros didáticos”, por exemplo, como:
def bfs(graph, start, end): visited = {start} todo = [start] while todo: node = todo.pop_first() if node == end: return True for kid in adjacent(node): if kid not in visited: visited.add(kid) todo.push_back(kid) return False
No processo de criação de novos nós candidatos pelo programa, cada nó é verificado com uma tabela de hash dos nós já visitados. Se já estiver na tabela de hash, o nó será ignorado. Caso contrário, ele será adicionado à fila e à tabela de hash. Às vezes, nas implementações, as informações "visitadas" são inseridas nos nós, e não em uma tabela estrangeira; mas essa é uma otimização arriscada e é completamente impossível se o gráfico for implicitamente especificado.
Por que o uso de uma tabela de hash é problemático? Como as tabelas de hash tendem a criar um padrão de acesso à memória completamente aleatório. Caso contrário, essa é uma função de hash incorreta e a tabela de hash provavelmente terá um desempenho ruim devido a colisões. Esse padrão de acesso aleatório pode causar problemas de desempenho, mesmo que os dados caibam na memória: o acesso a uma enorme tabela de hash provavelmente causará erros de cache e TLBs (associat translation translation buffers). Mas e se uma parte significativa dos dados estiver no disco e não na memória? As consequências serão catastróficas: algo da ordem de 10 ms por operação de pesquisa.
Com 10 bilhões de estados únicos, apenas o acesso à tabela de hash levará cerca de quatro meses para aguardar a E / S do disco. Isso não nos convém; a tarefa deve definitivamente ser transformada para que o programa possa processar grandes pacotes de dados de uma só vez.
BFS com classificação e mesclagem
Se quiséssemos integrar o máximo possível as operações de acesso a dados nos pacotes, qual seria a aproximação máxima possível? Como o programa não sabe quais nós processar em uma camada de profundidade N + 1 até que a camada N seja completamente processada, parece óbvio que é necessário deduplicar os estados pelo menos uma vez por profundidade.
Se trabalharmos com toda a camada ao mesmo tempo, podemos abandonar as tabelas de hash e descrever o conjunto de estados visitados e novos como alguns fluxos classificados (por exemplo, como fluxos de arquivos, matrizes, listas). Podemos encontrar trivialmente o novo conjunto visitado combinando os conjuntos de fluxos e é igualmente trivial encontrar todo o conjunto usando a diferença de conjuntos.
Duas operações com conjuntos podem ser combinadas para que funcionem de uma só vez com os dois encadeamentos. De fato, examinamos os dois fluxos, processamos o elemento menor e avançamos ao longo do fluxo do qual o elemento foi retirado (ou ao longo dos dois fluxos, se os elementos no início forem os mesmos). Nos dois casos, adicionamos o item ao novo conjunto visitado. Em seguida, avançamos ao longo do fluxo de novos estados e também adicionamos um elemento ao novo conjunto de tarefas:
def bfs(graph, start, end): visited = Stream() todo = Stream() visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return True for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited) return False
O padrão de acesso a dados agora é completamente linear e previsível; não há acessos arbitrários durante a fusão. Portanto, o atraso nas operações do disco não se torna importante para nós e a única coisa que permanece importante é a largura de banda.
Como será o desempenho teórico com uma distribuição simplificada de dados acima de 100 níveis de profundidade, cada um com 100 milhões de estados? O estado médio será lido e gravado 50 vezes. Isso fornece 10 bytes / estado * 5 bilhões de estados * 50 = 2,5 TB. Meu disco rígido pode presumivelmente ler e gravar a uma velocidade média de 100 MB / s, ou seja, em média a E / S levará (2 * 2,5 TB) / (100 MB / s) = ~ 50k / s = ~ 13 horas . Este é um número de pedidos menor que o resultado anterior (quatro meses)!
Também é importante notar que esse modelo simplificado não leva em consideração o tamanho dos novos estados gerados. Antes da etapa de mesclagem, eles devem ser armazenados na memória para classificação + deduplicação. Abordaremos isso nas seções abaixo.
Compressão
Na introdução, eu disse que nos experimentos iniciais, a compactação de estado não parecia promissora e a taxa de compactação era de apenas 30%. Mas, depois de fazer alterações no algoritmo, os estados foram simplificados. Eles devem ser muito mais fáceis de compactar.
Para testar essa teoria, usei o zstd com um quebra-cabeça de 14,6 milhões de estados, cada um dos quais com 8 bytes de tamanho. Após a classificação, eles foram compactados em média para 1,4 bytes por estado. Parece um passo sério em frente. Não é suficiente executar o programa inteiro na memória, mas pode reduzir o tempo de E / S do disco para apenas algumas horas.
É possível, de alguma forma, melhorar o resultado do moderno algoritmo de compactação de uso geral se soubermos algo sobre a estrutura de dados? Você pode ter quase certeza disso. Um bom exemplo disso é o formato PNG. Teoricamente, a compactação é apenas uma passagem padrão do Deflate. Mas, em vez de compactar dados brutos, a imagem é convertida primeiro usando
filtros PNG . O filtro PNG é essencialmente uma fórmula para prever o valor de um byte de dados brutos com base no valor do mesmo byte na linha anterior e / ou no mesmo byte do pixel anterior. Por exemplo, o filtro "para cima" converte cada byte subtraindo os valores da linha anterior ao compactar e executando a operação oposta ao desembalar. Dados os tipos de imagens para os quais o PNG é usado, o resultado quase sempre consistirá em zeros ou números próximos a zero. Deflate pode compactar esses dados muito melhor do que dados brutos.
Esse princípio pode ser aplicado aos registros de estado do BFS? Parece que isso deveria ser possível. Assim como no PNG, temos um tamanho de linha constante e podemos esperar que as linhas adjacentes sejam muito semelhantes. As primeiras amostras com o filtro de subtração / adição, seguidas por zstd, levaram a uma melhoria na taxa de compactação em outros 40%: 0,87 bytes por estado. As operações de filtragem são triviais, portanto, do ponto de vista do consumo de CPU, elas são praticamente "gratuitas".
Não estava claro para mim se outras melhorias poderiam ser feitas ou se esse era um limite prático. Nos dados da imagem, você pode esperar logicamente que os bytes adjacentes da mesma linha sejam semelhantes. Mas nesses estados não existe. Mas, na verdade, filtros um pouco mais sofisticados ainda podem melhorar os resultados. No final, eu vim para este sistema:
Suponha que tenhamos linhas adjacentes R1 = [1, 2, 3, 4] e R2 = [1, 2, 6, 4]. Ao emitir R2, comparamos cada byte com o mesmo byte da linha anterior, e 0 indica uma correspondência e 1 indica uma incompatibilidade: diff = [0, 0, 1, 0]. Em seguida, passamos esse bitmap, codificado como VarInt, seguido por apenas bytes que não correspondem à linha anterior. Neste exemplo, obtemos dois bytes 0b00000100 6. Por si só, esse filtro compacta os dados de referência para 2,2 bytes / estado. Mas, combinando o filtro + zstd, reduzimos o tamanho dos dados para 0,42 bytes / estado. Ou, em outras palavras, isso equivale a 3,36 bits por estado, o que é um pouco mais do que nossos indicadores calculados aproximados necessários para garantir que todos os dados se ajustem à RAM.
Na prática, as taxas de compactação melhoram porque os conjuntos classificados se tornam mais densos. Quando a pesquisa chega ao ponto em que a memória começa a causar problemas, as taxas de compactação podem ficar muito melhores. O maior problema é que, no final, temos 4,6 bilhões de estados visitados. Após a classificação, esses estados ocupam 405 MB e são compactados de acordo com o esquema apresentado acima. Isso nos dá
0,7 bits por estado . No final, a compactação e descompactação ocupam cerca de 25% do tempo de CPU do programa, mas esse é um excelente compromisso para reduzir o consumo de memória em cem vezes.
O filtro acima parece um pouco caro devido ao cabeçalho VarInt em cada linha. Parece fácil atualizar com o custo baixo da CPU ou com um ligeiro aumento na complexidade. Tentei várias opções diferentes, transpondo dados em ordem por colunas ou escrevendo máscaras de bits em blocos maiores, etc. Somente essas opções geraram taxas de compactação muito mais altas, mas não tiveram um desempenho tão bom quando a saída do filtro foi compactada pelo zstd. E não foi algum tipo de erro zstd, os resultados com gzip e bzip2 foram semelhantes. Não tenho teorias particularmente engenhosas sobre por que esse tipo específico de codificação se mostrou muito melhor em compressão do que outras opções.
Outro mistério: a taxa de compactação se mostrou muito melhor quando os dados são classificados por little-endian, em vez de big-endian. Inicialmente, pensei que isso acontecesse, porque na classificação little-endiana existem mais zeros à esquerda com a máscara de bits codificada por VarInt. Mas essa diferença persiste mesmo com filtros que não possuem essas dependências.
(Há muita pesquisa sobre a compactação de conjuntos ordenados de números inteiros, porque eles são os componentes básicos dos mecanismos de pesquisa. No entanto, não encontrei muita informação sobre a compactação de registros classificados de comprimento constante e não queria adivinhar, apresentando os dados como valores inteiros com precisão arbitrária.)
Oh-oh, eu trapacei!
Você deve ter notado que as implementações de BFS acima no pseudo-código retornam apenas valores booleanos - a solução foi encontrada / não foi encontrada. Isso não é particularmente útil. Na maioria dos casos, precisaremos criar uma lista das etapas exatas da solução, e não apenas informar sobre a disponibilidade da solução.
A princípio, parece que esse problema é fácil de resolver. Em vez de coletar conjuntos de estados, você precisa coletar relações de estado com os estados pai. Depois de encontrar a solução, você pode simplesmente voltar da lista de soluções dos pais do início ao fim. Para uma solução baseada em tabela de hash, isso seria algo como isto:
def bfs(graph, start, end): visited = {start: None} todo = [start] while todo: node = todo.pop_first() if node == end: return trace_solution(node, visited) for kid in adjacent(node): if kid not in visited: visited[kid] = node todo.push_back(kid) return None def trace_solution(state, visited): if state is None: return [] return trace_solution(start, visited[state]) + [state]
Infelizmente, isso destruirá todos os benefícios de compactação obtidos na seção anterior; eles são baseados no pressuposto de que as linhas adjacentes são muito semelhantes. Quando olhamos para os próprios estados, isso é verdade. Mas não há razão para acreditar que isso seja verdade para os estados parentais; de fato, são dados aleatórios. Em segundo lugar, uma solução de classificação + mesclagem deve ler e gravar todos os estados exibidos em cada iteração. Para salvar a ligação do estado / estado pai, precisamos ler e gravar no disco a cada iteração todos esses dados mal compactados.
Classificar + mesclar com várias saídas
No final, ao retornar à solução, o programa precisará apenas de pacotes de estados / estados principais, portanto, podemos armazenar duas estruturas de dados em paralelo. Visitados continuará sendo o conjunto de estados visitados, conforme recalculado anteriormente durante a mesclagem. Pais é pelo menos uma lista classificada de pares de estado / estado pai que não são substituídos. Após cada operação de mesclagem, o par "estado + estado pai" é adicionado aos pais.
def bfs(graph, start, end): parents = Stream() visited = Stream() todo = Stream() parents.add((start, None)) visited.add(start) todo.add(start) while True: new = [] for node in todo: if node == end: return trace_solution(node, parents) for kid in adjacent(node): new.push_back(kid) new_stream = Stream() for node in new.sorted().uniq(): new_stream.add(node) todo, visited = merge_sorted_streams(new_stream, visited, parents) return None
Isso nos permite tirar proveito de ambas as abordagens em termos de tempo de execução e conjuntos de trabalho, mas requer mais espaço de armazenamento secundário. Além disso, no futuro, por outras razões, uma cópia separada dos estados visitados será útil, agrupada por profundidade.
Trocar
Outro detalhe é ignorado no pseudo-código: não há código explícito para a E / S do disco, mas apenas a interface abstrata do Stream. O fluxo pode ser um fluxo de arquivo ou uma matriz dentro da memória, mas ignoramos esses detalhes de implementação. Em vez disso, o pseudo-código está criando um padrão de acesso à memória que permite o uso ideal do disco. Em um mundo ideal, isso seria suficiente e o restante poderia ser ocupado pelo subsistema de memória virtual do SO.
Mas isso não acontece, pelo menos no Linux. Em algum momento (antes que o conjunto de dados de trabalho pudesse ser compactado para tamanhos de memória), o programa foi executado em cerca de 11 horas e os dados foram salvos principalmente no disco. Então fiz o programa usar páginas anônimas em vez de armazenadas em arquivos, e selecionei um arquivo de troca de tamanho suficiente na mesma unidade. No entanto, três dias depois, o programa percorreu apenas um quarto do caminho e, mesmo assim, com o tempo, ficou mais lento. De acordo com minhas estimativas otimistas, ela deveria terminar o trabalho em 20 dias.
Vou esclarecer: era o mesmo código e
exatamente o mesmo padrão de acesso . A única coisa que mudou foi que a memória foi salva não como um arquivo de disco explícito, mas como uma troca. Quase não são necessárias evidências de que a troca destrua completamente o desempenho do Linux, enquanto a E / S de arquivo regular não. Sempre presumi que isso se deve ao fato de os programas tenderem a considerar a RAM como memória de acesso aleatório. Mas esse não é o caso.
Acontece que páginas para salvar arquivos e páginas anônimas são tratadas de maneira diferente pelo subsistema de máquina virtual. Eles são armazenados em caches LRU separados com políticas de expiração diferentes; além disso, parece que eles têm diferentes propriedades de leitura / carregamento de leitura antecipada.
Agora eu sei: a troca no Linux provavelmente não funcionará bem, mesmo em condições ideais. Se é provável que partes do espaço de endereço sejam descarregadas por algum tempo no disco, é melhor salvá-las manualmente em arquivos do que confiar na troca. Consegui isso implementando minha própria classe de vetores, que inicialmente funciona apenas na memória e, após exceder um determinado limite de tamanho, ele muda para o mmap em um arquivo separado temporário.
Compactação de novos estados antes da mesclagem
Em um modelo de desempenho simplificado, assumimos que 100 milhões de novas condições ocorreriam a cada profundidade. Verificou-se que isso não está muito longe da realidade (no quebra-cabeça mais complexo, um máximo de mais de 150 milhões de novos estados únicos em uma camada de profundidade). Mas isso não deve ser medido; o conjunto de trabalho antes da mesclagem está associado não apenas a estados exclusivos, mas também a todos os estados deduzidos para essa iteração. Esse número atinge 880 milhões de estados de saída por camada de profundidade. Esses 880 milhões de estados a) precisam ser processados com um padrão de acesso aleatório para classificação; b) não podem ser efetivamente compactados devido à falta de classificação; c) devem ser armazenados juntamente com o estado pai. Este conjunto de trabalho tem aproximadamente 16 GB.
A solução óbvia: use algum tipo de classificação externa. Basta gravar todos os estados no disco, executar classificação externa, desduplicar e mesclar como de costume. No começo, usei essa solução e, embora no máximo eliminasse o problema A, não conseguia lidar com B e C.
No final, adotei uma abordagem alternativa: coletei os estados em uma matriz na memória. Se a matriz se tornar muito grande (por exemplo, mais de 100 milhões de elementos), ela será classificada, deduplicada e compactada. Isso nos fornece um pacote de execuções de estado classificadas e não há duplicatas dentro de cada execução, mas elas são possíveis entre as execuções. Fundamentalmente, o código para mesclar estados novos e visitados permanece o mesmo; ainda é baseado em uma passagem gradual pelas correntes. A única diferença é que, em vez de apenas passar por dois fluxos, existe um fluxo separado para cada uma das execuções classificadas de novos estados.
Obviamente, as taxas de compactação dessas execuções de 100 milhões de estados não são tão boas quanto a compactação do conjunto de todos os estados visitados. Mas mesmo com esses indicadores, reduz significativamente o volume do conjunto de trabalho e os requisitos de E / S do disco. Você precisa de um pouco mais de recursos de CPU para processar a fila prioritária de threads, mas ainda é um grande compromisso.
Economizando espaço nos estados pai
Nesse estágio, a grande maioria do espaço ocupado pelo programa é gasta no armazenamento dos estados pais, para que, depois de encontrar a solução, possamos recriar seu processo. Provavelmente, eles dificilmente podem ser espremidos bem, mas talvez haja algum tipo de compromisso entre a CPU e a memória?
Precisamos conectar o estado S 'na profundidade D + 1 ao estado pai S na profundidade D. Se pudermos iterar todos os estados parentais possíveis S', podemos verificar se algum deles aparece na profundidade D no conjunto visitado. . (Já criamos muitas visitas, agrupadas por profundidade como um subproduto conveniente da derivação de pacotes de estado / estado parental durante a mesclagem). Infelizmente, essa abordagem não funcionará para esta tarefa; é simplesmente muito difícil para nós gerar todos os estados possíveis de S para um dado S '. No entanto, para muitas outras tarefas de pesquisa, essa solução pode funcionar.Se apenas podemos gerar transições entre estados para a frente, mas não para trás, por que não fazer isso? Vamos analisar iterativamente todos os estados na profundidade D e ver que tipo de estados de saída eles obtêm. Se algum estado na saída der S ', encontramos um S. adequado. O problema com este plano é que ele aumenta o consumo total de CPU do programa em 50%. (Não 100%, porque, em média, encontraremos S olhando a metade dos estados na profundidade D).Portanto, não gosto de nenhum dos casos limitantes, mas aqui, pelo menos, é possível um compromisso entre a CPU / memória. Existe uma solução mais aceitável em algum lugar? No final, decidi não armazenar o par (S ', S), mas o par (S', H (S)), onde H é uma função hash de 8 bits. Para encontrar S para um dado S ', repetimos iterativamente todos os estados na profundidade D. Mas antes de fazer qualquer outra coisa, calculamos o mesmo hash. Se a saída não corresponder a H (S), esse não é o estado que estamos procurando e podemos simplesmente ignorá-lo. Essa otimização significa que recálculos caros precisam ser executados apenas para 1/256 estados, o que representa um pequeno aumento na carga da CPU e, ao mesmo tempo, reduzem a quantidade de memória para armazenar estados-pai de 8 a 10 bytes a 1 byte.O que não funcionou ou pode não funcionar
Nas seções anteriores, examinamos a sequência de otimizações de alto nível que funcionaram. Tentei outras coisas que não funcionaram ou que encontrei na literatura, mas decidi que, nesse caso específico, elas não funcionariam. Aqui está uma lista parcial.Neste ponto, não recalculo o conjunto inteiro visitado em cada iteração. Em vez disso, ele era armazenado como muitas execuções classificadas, e essas execuções eram compactadas de tempos em tempos. A vantagem dessa abordagem é que menos gravações em disco e recursos da CPU são usados para compactação. A desvantagem é o aumento da complexidade do código e a taxa de compactação reduzida. Inicialmente, achei que esse esquema fazia sentido, porque no meu caso, as operações de gravação são mais caras que a leitura. Mas, no final, a taxa de compressão acabou sendo duas vezes maior. As vantagens de tal compromisso não são óbvias, portanto, como resultado, voltei a uma forma mais simples.Já foram realizados pequenos estudos sobre a realização de uma pesquisa volumétrica de largura em primeiro lugar para gráficos definidos implicitamente no armazenamento secundário. Você pode começar a explorar este tópicodeste artigo de 2008 . Como você pode imaginar, a idéia de desduplicar junto com a classificação + mesclagem no armazenamento secundário não é nova. O que é surpreendente sobre isso é que ele foi aberto apenas em 1993. Muito tarde! Existem sugestões posteriores para a pesquisa pela primeira vez no armazenamento secundário que não exigem uma etapa de classificação.Um deles era vincular estados a números inteiros e armazenar na memória um bitmap dos estados visitados. No meu caso, isso é completamente inútil, porque os tamanhos do estado codificado são muito diferentes em comparação com os espaços de estado realmente alcançáveis. E duvido muito que haja problemas interessantes nos quais essa abordagem funcionaria.Outra alternativa séria é baseada em tabelas de hash temporárias. Os estados visitados são armazenados sem classificação em um arquivo. Salvamos a saída obtida da profundidade D na tabela de hash. Em seguida, percorra os estados visitados iterativamente e procure-os na tabela de hash. Se o item for encontrado na tabela de hash, exclua-o. Depois de percorrer o arquivo inteiro de forma iterativa, apenas elementos não duplicados permanecerão nele. Eles são adicionados ao arquivo e usados para inicializar a lista de tarefas para a próxima iteração. Se a quantidade de saída for tão grande que a tabela de hash não couber na memória, os arquivos e as tabelas de hash poderão ser divididos em partes usando o mesmo critério (por exemplo, os bits de status superiores) e cada parte deverá ser processada separadamente.Embora haja benchmarksmostrando que a abordagem baseada em hash é cerca de 30% mais rápida que a classificação + mesclagem, mas parece que elas não levam em consideração a compactação. Eu simplesmente não vi como a rejeição dos benefícios da compactação pode se justificar, então nem experimentei essas abordagens.Outra área de pesquisa digna de atenção foi a otimização de consultas ao banco de dados. Parece que sim. que a tarefa de desduplicação está fortemente relacionada à junção ao banco de dados, que também possui exatamente o mesmo dilema de classificação versus hash. Obviamente, alguns desses estudos podem ser aplicados ao problema de pesquisa. A diferença pode ser que a saída do banco de dados de junção seja temporária, enquanto a saída de deduplicação do BFS é armazenada até o final do cálculo. Parece que isso está mudando o equilíbrio de compromissos: agora, ele diz respeito não apenas ao processamento mais eficiente de uma iteração, mas também à criação do formato de dados de saída mais ideal para a próxima iteração.Conclusão
Isso conclui minha conta do que aprendi de um projeto que geralmente é aplicável a outras tarefas de pesquisa por força bruta. A combinação desses truques permitiu reduzir o volume de soluções para os quebra-cabeças mais complexos do jogo de 50-100 GB para 500 MB e aumentar suavemente os custos se a tarefa exceder a memória disponível e for gravada em disco. Além disso, minha solução é 50% mais rápida que uma desduplicação ingênua de estados com base em tabelas de hash, mesmo para quebra-cabeças que se encaixam na memória.O Snakebird pode ser comprado no Steam , Google Play e App Store . Eu o recomendo para quem estiver interessado em quebra-cabeças muito complexos, mas honestos.