Il y a quelques mois, j'ai finalement dû admettre que je n'étais pas assez intelligent pour parcourir certains niveaux du puzzle
Snakebird . La seule façon de retrouver une partie de l'estime de soi était d'écrire un solveur. Je pourrais donc prétendre que créer un programme pour résoudre le casse-tête équivaut presque à le résoudre moi-même. Le code du programme C ++ résultant est disponible sur
Github . La partie principale du code considéré dans l'article est implémentée dans
search.h et
compress.h . Dans cet article, je parlerai principalement de l'optimisation d'une recherche en premier lieu qui nécessiterait 50-100 Go de mémoire pour s'adapter à 4 Go.
Plus tard, j'écrirai un autre article, qui décrira les spécificités du jeu. Dans ce post, vous devez savoir que je n'ai trouvé aucune bonne alternative à la force brute, car aucune des astuces habituelles n'a fonctionné. Le jeu a de nombreux états, car il y a beaucoup d'objets en mouvement ou poussés, et la forme de certains d'entre eux est importante, ce qui peut changer avec le temps. Il n'y avait pas d'heuristique conservatrice appropriée pour les algorithmes comme A * pour réduire l'espace de recherche. Le graphique de recherche était orienté et spécifié implicitement; par conséquent, la recherche simultanée dans les directions avant et arrière était impossible. Le seul mouvement pourrait changer l'état de nombreuses manières indépendantes, donc rien ne pourrait être utile comme
hacher Zobrist .
Des estimations approximatives ont montré que dans le plus grand casse-tête, après l'élimination de toutes les positions symétriques, il y aurait environ 10 milliards d'États. Même après avoir compressé les descriptions d'état avec une densité maximale, la taille de l'état était de 8 à 10 octets. Avec 100 Go de mémoire, la tâche serait triviale, mais pas pour ma machine domestique avec 16 Go de mémoire. Et comme Chrome en a besoin de 12 Go, ma mémoire réelle est plus proche de 4 Go. Tout ce qui dépassera ce volume devra être enregistré sur le disque (ancien disque dur rouillé).
Comment intégrer 100 Go de données dans 4 Go de RAM? Soit a) les états doivent être compressés à 1/20 de leur taille d'origine, déjà optimisée, ou b) l'algorithme devrait être capable d'enregistrer efficacement les états sur le disque et vice versa, ou c) une combinaison des deux méthodes ci-dessus, ou d) je dois acheter plus RAM ou louer une puissante machine virtuelle pendant plusieurs jours. Je n'ai pas envisagé l'option D, car elle est trop ennuyeuse. Les options A et B ont été exclues après la preuve de concept à l'aide de gzip: un fragment d'une description d'état de 50 Mo a été compressé à seulement 35 Mo. Cela représente environ 7 octets par état, et ma mémoire est d'environ 0,4 octet par état. Autrement dit, l'option B est restée, même si la recherche en premier lieu semblait plutôt gênante pour le stockage sur des disques secondaires.
Table des matières
Il s'agit d'un article assez long, voici donc un bref aperçu des sections suivantes:
- Recherche en largeur d'abord dans un manuel - quelle est la formulation habituelle de recherche en largeur en premier (BFS), et pourquoi ne convient-elle pas pour enregistrer des parties d'un état sur le disque?
- BFS avec tri et fusion - un changement dans l'algorithme pour l'élimination efficace des lots de données redondantes.
- Compression - réduire la quantité de mémoire utilisée par cent fois en raison de la combinaison de la compression standard et native.
- Oh-oh, j'ai triché! - dans les premières sections, j'ai gardé le silence sur quelque chose: il ne nous suffit pas de savoir où se trouve la solution, mais nous devons comprendre exactement comment y parvenir. Dans cette section, nous mettons à jour l'algorithme de base afin qu'il transfère suffisamment de données pour recréer la solution à partir du dernier état.
- Trier + fusionner avec plusieurs sorties - le stockage de plus d'états annule complètement les avantages de la compression. L'algorithme de tri + fusion doit être modifié de sorte qu'il stocke deux ensembles de données de sortie: l'un, bien compressé, est utilisé pendant la recherche, et l'autre n'est utilisé que pour recréer la solution après avoir trouvé la première.
- Swap - Swap sur Linux est bien pire que ce que je pensais.
- Compression de nouveaux états avant la fusion - jusqu'à présent, les optimisations de mémoire ne fonctionnaient qu'avec un grand nombre d'états visités. Mais il s'est avéré que la liste des nouveaux états générés est beaucoup plus longue que vous ne le pensez. Cette section présente un diagramme pour une description plus efficace des nouveaux états.
- Économiser de l'espace sur les états parents - explorez les compromis entre l'utilisation du processeur / de la mémoire pour recréer la solution à la fin.
- Ce qui n'a pas fonctionné ou peut ne pas fonctionner - certaines idées semblaient prometteuses, mais en conséquence elles ont dû être annulées, tandis que d'autres, qui étaient censées être des chercheurs, me semblent intuitivement inappropriées dans ce cas.
Recherche large «par manuel»
À quoi ressemble la recherche en premier et pourquoi ne pas y utiliser un disque? Avant ce petit projet, je ne considérais que les options de formulation «à partir des manuels», par exemple, telles que:
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
En cours de création de nouveaux nœuds candidats par le programme, chaque nœud est vérifié avec une table de hachage des nœuds déjà visités. S'il se trouve déjà dans la table de hachage, le nœud est ignoré. Sinon, il est ajouté à la file d'attente et à la table de hachage. Parfois dans les implémentations, les informations «visitées» sont entrées dans les nœuds, et non dans une table étrangère; mais c'est une optimisation risquée et elle est complètement impossible si le graphique est implicitement spécifié.
Pourquoi l'utilisation d'une table de hachage est-elle problématique? Parce que les tables de hachage ont tendance à créer un modèle d'accès à la mémoire complètement aléatoire. S'ils ne le font pas, alors c'est une mauvaise fonction de hachage, et la table de hachage aura très probablement de mauvaises performances en raison de collisions. Ce modèle d'accès aléatoire peut entraîner des problèmes de performances, même si les données tiennent en mémoire: l'accès à une énorme table de hachage est susceptible de provoquer des échecs de cache et un tampon de traduction associatif (TLB). Mais que se passe-t-il si une partie importante des données se trouve sur le disque et non en mémoire? Les conséquences seront catastrophiques: quelque chose de l'ordre de 10 ms par opération de recherche.
Avec 10 milliards d'états uniques, seul l'accès à la table de hachage nous prendra environ quatre mois pour attendre les E / S disque. Cela ne nous convient pas; la tâche doit absolument être convertie pour que le programme puisse traiter de gros paquets de données en un seul passage.
BFS avec tri et fusion
Si nous voulions intégrer autant que possible les opérations d'accès aux données dans les packages, quelle serait l'approximation maximale réalisable? Puisque le programme ne sait pas quels nœuds traiter dans une couche de profondeur N + 1 jusqu'à ce que la couche N soit complètement traitée, il semble évident qu'il est nécessaire de dédupliquer les états au moins une fois par profondeur.
Si nous travaillons avec une couche entière en même temps, nous pouvons abandonner les tables de hachage et décrire l'ensemble des états visités et nouveaux comme des flux triés (par exemple, comme des flux de fichiers, des tableaux, des listes). Nous pouvons trouver trivialement le nouvel ensemble visité en combinant les ensembles de flux et il est également trivial de trouver l'ensemble à faire en utilisant la différence des ensembles.
Deux opérations avec des ensembles peuvent être combinées afin qu'elles fonctionnent en une seule passe avec les deux threads. En fait, nous examinons les deux flux, traitons le plus petit élément, puis avançons le long du flux à partir duquel l'élément a été pris (ou le long des deux flux si les éléments au début sont les mêmes). Dans les deux cas, nous ajoutons l'article au nouvel ensemble visité. Ensuite, nous avançons le long du flux de nouveaux états et ajoutons également un élément au nouvel ensemble de tâches:
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
Le modèle d'accès aux données est désormais complètement linéaire et prévisible; il n'y a pas d'accès arbitraire tout au long de la fusion. Par conséquent, le retard dans les opérations sur disque ne devient pas important pour nous, et la seule chose qui reste importante est la bande passante.
À quoi ressembleront les performances théoriques avec une distribution simplifiée des données sur 100 niveaux de profondeur, chacun ayant 100 millions d'états? L'état moyen sera lu et écrit 50 fois. Cela donne 10 octets / état * 5 milliards d'états * 50 = 2,5 To. Mon disque dur peut soi-disant lire et écrire à une vitesse moyenne de 100 Mo / s, c'est-à-dire qu'en moyenne les E / S prendront (2 * 2,5 To) / (100 Mo / s) = ~ 50k / s = ~ 13 heures . C'est quelques commandes de moins que le résultat précédent (quatre mois)!
Il convient également de noter que ce modèle simplifié ne prend pas en compte la taille des nouveaux états générés. Avant l'étape de fusion, ils doivent être stockés en mémoire pour le tri + la déduplication. Nous couvrirons cela dans les sections ci-dessous.
La compression
Dans l'introduction, j'ai dit que dans les premières expériences, la compression d'état ne semblait pas prometteuse et que le taux de compression n'était que de 30%. Mais après avoir apporté des modifications à l'algorithme, les états sont devenus rationalisés. Ils devraient être beaucoup plus faciles à comprimer.
Pour tester cette théorie, j'ai utilisé zstd avec un puzzle de 14,6 millions d'états, dont chaque état avait une taille de 8 octets. Après le tri, ils ont été compressés en moyenne à 1,4 octet par état. Cela semble être un sérieux pas en avant. Il ne suffit pas d'exécuter l'intégralité du programme en mémoire, mais cela peut réduire le temps d'E / S du disque à seulement quelques heures.
Est-il possible d'améliorer en quelque sorte le résultat de l'algorithme de compression polyvalent moderne si nous savons quelque chose sur la structure des données? Vous pouvez en être presque sûr. Un bon exemple de ceci est le format PNG. Théoriquement, la compression n'est qu'une passe de dégonflage standard. Mais au lieu de compresser les données brutes, l'image est d'abord convertie à l'aide de
filtres PNG . Le filtre PNG est essentiellement une formule pour prédire la valeur d'un octet de données brutes sur la base de la valeur du même octet dans la ligne précédente et / ou du même octet du pixel précédent. Par exemple, le filtre «up» convertit chaque octet en soustrayant les valeurs de la ligne précédente lors de la compression et en effectuant l'opération inverse lors du déballage. Étant donné les types d'images pour lesquels PNG est utilisé, le résultat sera presque toujours composé de zéros ou de nombres proches de zéro. Dégonfler peut compresser ces données bien mieux que les données brutes.
Ce principe peut-il être appliqué aux enregistrements d'état BFS? Il semble que cela devrait être possible. Comme avec PNG, nous avons une taille de ligne constante et nous pouvons nous attendre à ce que les lignes adjacentes soient très similaires. Les premiers échantillons avec le filtre de soustraction / addition, suivis de zstd, ont conduit à une amélioration du taux de compression de 40% supplémentaires: 0,87 octets par état. Les opérations de filtrage sont triviales, donc, du point de vue de la consommation CPU, elles sont pratiquement «gratuites».
Il n'était pas clair pour moi si d'autres améliorations pouvaient être apportées ou s'il s'agissait d'une limite pratique. Dans les données d'image, vous pouvez logiquement vous attendre à ce que les octets adjacents de la même ligne soient similaires. Mais dans ces États, il n'y a rien de tel. Mais en réalité, des filtres légèrement plus sophistiqués peuvent encore améliorer les résultats. À la fin, je suis arrivé à ce système:
Supposons que nous ayons des rangées adjacentes R1 = [1, 2, 3, 4] et R2 = [1, 2, 6, 4]. Lors de la sortie de R2, nous comparons chaque octet avec le même octet de la ligne précédente, et 0 indiquera une correspondance et 1 indiquera une incompatibilité: diff = [0, 0, 1, 0]. Ensuite, nous transmettons ce bitmap, codé en VarInt, suivi uniquement des octets qui ne correspondent pas à la ligne précédente. Dans cet exemple, nous obtenons deux octets 0b00000100 6. En soi, ce filtre compresse les données de référence à 2,2 octets / état. Mais en combinant le filtre + zstd, nous avons réduit la taille des données à 0,42 octets / état. Ou, pour le dire autrement, cela représente 3,36 bits par état, ce qui est juste un peu plus que nos indicateurs calculés approximatifs nécessaires pour garantir que toutes les données tiennent dans la RAM.
En pratique, les taux de compression s'améliorent car les ensembles triés deviennent plus denses. Lorsque la recherche atteint le point où la mémoire commence à causer des problèmes, les taux de compression peuvent s'améliorer considérablement. Le plus gros problème est qu'en fin de compte, 4,6 milliards d'États sont visités. Après tri, ces états occupent 405 Mo et sont compressés selon le schéma présenté ci-dessus. Cela nous donne
0,7 bits par état . Au final, la compression et la décompression occupent environ 25% du temps CPU du programme, mais c'est un excellent compromis pour réduire la consommation de mémoire d'une centaine de fois.
Le filtre ci-dessus semble un peu coûteux en raison de l'en-tête VarInt sur chaque ligne. Il semble qu'il soit facile de mettre à niveau au prix de faibles coûts de processeur ou d'une légère augmentation de la complexité. J'ai essayé plusieurs options différentes, transposant les données dans l'ordre par colonnes, ou écrivant des masques de bits dans des blocs plus grands, etc. Ces options à elles seules ont donné des taux de compression beaucoup plus élevés, mais n'ont pas donné de bons résultats lorsque la sortie du filtre a été compressée par zstd. Et ce n'était pas une sorte d'erreur zstd, les résultats avec gzip et bzip2 se sont avérés similaires. Je n'ai pas de théories particulièrement ingénieuses sur les raisons pour lesquelles ce type particulier de codage s'est avéré être bien meilleur en compression que les autres options.
Autre mystère: le taux de compression s'est avéré bien meilleur lorsque les données sont triées par petit-boutien plutôt que par gros-boutiste. Initialement, je pensais que cela s'était produit parce que dans le tri en petits caractères, il y avait plus de zéros en tête avec le masque de bits codé par VarInt. Mais cette différence persiste même avec des filtres qui n'ont pas de telles dépendances.
(Il existe de nombreuses recherches sur la compression d'ensembles triés d'entiers, car ce sont les éléments de base des moteurs de recherche. Cependant, je n'ai pas trouvé beaucoup d'informations sur la compression d'enregistrements triés de longueur constante, et je ne voulais pas deviner, présentant les données sous forme de valeurs entières avec une précision arbitraire.)
Oh-oh, j'ai triché!
Vous avez peut-être remarqué que les implémentations BFS ci-dessus dans le pseudo-code renvoient uniquement des valeurs booléennes - la solution est trouvée / introuvable. Ce n'est pas particulièrement utile. Dans la plupart des cas, nous devrons créer une liste des étapes exactes de la solution, et pas seulement signaler la disponibilité de la solution.
Au début, il semble que ce problème soit facile à résoudre. Au lieu de collecter des ensembles d'états, vous devez collecter les relations d'états avec les états parents. Ensuite, après avoir trouvé la solution, vous pouvez simplement revenir de la liste des solutions parentales de bout en bout. Pour une solution basée sur une table de hachage, cela ressemblerait à ceci:
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]
Malheureusement, cela détruira tous les avantages de compression obtenus dans la section précédente; ils sont basés sur l'hypothèse que les lignes adjacentes sont très similaires. Lorsque nous examinons simplement les États eux-mêmes, c'est vrai. Mais il n'y a aucune raison de croire que cela sera vrai pour les États parentaux; en fait, ce sont des données aléatoires. Deuxièmement, une solution sort + merge doit lire et écrire tous les états affichés à chaque itération. Pour sauvegarder la liaison de l'état / état parent, nous devons lire et écrire sur le disque à chaque itération toutes ces données mal compressées.
Trier + fusionner avec plusieurs sorties
À la toute fin, lors du retour à la solution, le programme n'aura besoin que de paquets d'états / états parents. Par conséquent, nous pouvons stocker deux structures de données en parallèle. Visité continuera d'être l'ensemble des états visités, comme précédemment recalculé lors de la fusion. Parents est au moins une liste triée de paires état / état parent qui ne sont pas écrasées. Après chaque opération de fusion, la paire «état + état parent» est ajoutée aux parents.
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
Cela nous permet de tirer parti des deux approches en termes d'exécution et d'ensembles de travaux, mais nécessite plus d'espace de stockage secondaire. De plus, il s'avère qu'à l'avenir, pour d'autres raisons, une copie séparée des états visités sera utile, groupée par profondeur.
Échanger
Un autre détail est ignoré dans le pseudo-code: il n'y a pas de code explicite pour les E / S disque, mais uniquement l'interface Stream abstraite. Le flux peut être un flux de fichiers ou un tableau dans la mémoire, mais nous avons ignoré ce détail d'implémentation. Au lieu de cela, le pseudo-code crée un modèle d'accès à la mémoire qui permet une utilisation optimale du disque. Dans un monde idéal, cela suffirait et le reste pourrait être occupé par le sous-système de mémoire virtuelle du système d'exploitation.
Mais cela ne se produit pas, du moins sous Linux. À un moment donné (avant que l'ensemble de données de travail puisse être compressé en tailles de mémoire), j'ai réussi à exécuter le programme en environ 11 heures et les données ont été enregistrées principalement sur le disque. Ensuite, j'ai fait en sorte que le programme utilise des pages anonymes plutôt que stockées dans des fichiers et j'ai sélectionné un fichier d'échange de taille suffisante sur le même lecteur. Cependant, trois jours plus tard, le programme n'a duré qu'un quart du chemin et, au fil du temps, il est devenu plus lent. Selon mes estimations optimistes, elle était censée terminer le travail dans 20 jours.
Je vais préciser - c'était le même code et
exactement le même modèle d'accès . La seule chose qui a changé est que la mémoire a été enregistrée non pas en tant que fichier disque explicite, mais en tant que swap. Presque aucune preuve n'est nécessaire que l'échange permette de détruire complètement les performances de Linux, contrairement aux E / S de fichiers ordinaires. J'ai toujours supposé que cela était dû au fait que les programmes ont tendance à considérer la RAM comme une mémoire à accès aléatoire. Mais ce n'est pas le cas.
Il s'avère que les pages d'enregistrement de fichiers et les pages anonymes sont traitées différemment par le sous-système de machine virtuelle. Ils sont stockés dans des caches LRU distincts avec des politiques d'expiration différentes; de plus, il semble qu'ils aient des propriétés de lecture anticipée en lecture / charge différentes.
Maintenant, je sais: l'échange sur Linux ne fonctionnera probablement pas bien même dans des conditions optimales. Si des parties de l'espace d'adressage sont susceptibles d'être déchargées pendant un certain temps sur le disque, il est préférable de les enregistrer manuellement dans des fichiers plutôt que de faire confiance au swap. J'ai accompli cela en implémentant ma propre classe de vecteurs, qui initialement ne fonctionne qu'en mémoire, et après avoir dépassé un certain seuil de taille, il passe en mmap dans un fichier séparé temporaire.
Compression de nouveaux états avant la fusion
Dans un modèle de performance simplifié, nous avons supposé que 100 millions de nouvelles conditions se produiraient à chaque profondeur. Il s'est avéré que ce n'est pas très loin de la réalité (dans le casse-tête le plus complexe, un maximum de plus de 150 millions de nouveaux états uniques sur une couche de profondeur). Mais cela ne doit pas être mesuré; l'ensemble de travail avant la fusion est associé non seulement à des états uniques, mais également à tous les états déduits pour cette itération. Ce chiffre atteint 880 millions d'états de sortie par couche de profondeur. Ces 880 millions d'états a) doivent être traités avec un modèle d'accès aléatoire pour le tri, b) ne peuvent pas être efficacement compressés en raison d'un manque de tri, c) doivent être stockés avec l'état parent. Ce jeu de travail fait environ 16 Go.
La solution évidente: utilisez une sorte de tri externe. Il suffit d'écrire tous les états sur le disque, d'effectuer un tri externe, de dédupliquer, puis de fusionner comme d'habitude. Au début, j'ai utilisé cette solution, et bien qu'elle ait tout au plus éliminé le problème A, je ne pouvais pas faire face à B et C.
Au final, j'ai adopté une approche alternative: j'ai collecté les états dans un tableau en mémoire. Si le tableau devient trop grand (par exemple, plus de 100 millions d'éléments), il est trié, dédupliqué et compressé. Cela nous donne un ensemble d'exécutions d'état triées, et il n'y a pas de doublons à l'intérieur de chaque exécution, mais elles sont possibles entre les exécutions. Fondamentalement, le code de fusion des États nouveaux et visités reste le même; elle repose toujours sur un passage progressif à travers les ruisseaux. La seule différence est qu'au lieu de simplement passer par deux flux, il existe un flux distinct pour chacune des séries triées de nouveaux états.
Bien sûr, les taux de compression de ces séries de 100 millions d'états ne sont pas aussi bons que la compression de l'ensemble de tous les états visités. Mais même avec de tels indicateurs, cela réduit considérablement le volume de l'ensemble de travail et les exigences d'E / S disque. Vous avez besoin d'un peu plus de ressources CPU pour traiter la file d'attente prioritaire des threads, mais c'est toujours un excellent compromis.
Économiser de l'espace sur les états parents
À ce stade, la grande majorité de l'espace occupé par le programme est consacrée au stockage des états parents, de sorte qu'après avoir trouvé la solution, nous pouvons recréer son processus. Très probablement, ils peuvent à peine être bien serrés, mais peut-être qu'il y a une sorte de compromis entre le CPU et la mémoire?
Nous devons connecter l'état S 'à la profondeur D + 1 avec son état parent S à la profondeur D. Si nous pouvons itérer sur tous les états parentaux possibles S', alors nous pouvons vérifier si l'un d'eux apparaît à la profondeur D dans l'ensemble visité . (Nous avons déjà créé un grand nombre de sites visités, regroupés par profondeur en tant que sous-produit pratique de la dérivation de bundles d'état / état parental lors de la fusion). Malheureusement, cette approche ne fonctionnera pas pour cette tâche; il est simplement trop difficile pour nous de générer tous les états possibles de S pour un S donné. Cependant, pour de nombreuses autres tâches de recherche, une telle solution pourrait fonctionner.Si nous ne pouvons générer que des transitions entre états vers l'avant, mais pas vers l'arrière, alors pourquoi ne pas simplement faire cela? Passons en revue tous les états en profondeur D et voyons quel type d'états de sortie ils obtiennent. Si un état à la sortie donne S ', alors nous avons trouvé un S. approprié. Le problème avec ce plan est qu'il augmente la consommation totale de CPU du programme de 50%. (Pas 100%, car en moyenne on trouvera S en regardant la moitié des états à la profondeur D).Par conséquent, je n'aime pas l'un des cas limitatifs, mais ici, au moins, un compromis entre le processeur / la mémoire est possible. Y a-t-il une solution plus acceptable quelque part entre les deux? En fin de compte, j'ai décidé de ne pas stocker la paire (S ', S), mais la paire (S', H (S)), où H est une fonction de hachage de 8 bits. Pour trouver S pour un S 'donné, nous parcourons à nouveau tous les états en profondeur D. Mais avant de faire autre chose, nous calculons le même hachage. Si la sortie ne correspond pas à H (S), alors ce n'est pas l'état que nous recherchons, et nous pouvons simplement le sauter. Cette optimisation signifie que des recalculs coûteux ne doivent être effectués que pour 1/256 états, ce qui représente une légère augmentation de la charge CPU, et en même temps réduit la quantité de mémoire pour le stockage des états parents de 8-10 octets à 1 octet.Ce qui n'a pas fonctionné ou peut ne pas fonctionner
Dans les sections précédentes, nous avons examiné la séquence d'optimisations de haut niveau qui a fonctionné. J'ai essayé d'autres choses qui n'ont pas fonctionné ou que j'ai trouvées dans la littérature, mais j'ai décidé que dans ce cas particulier, elles ne fonctionneraient pas. Voici une liste partielle.À ce stade, je ne recalcule pas l'ensemble entier visité à chaque itération. Au lieu de cela, il a été stocké en tant que plusieurs séries triées, et ces séries ont été compressées de temps en temps. L'avantage de cette approche est que moins d'écritures sur disque et de ressources CPU sont utilisées pour la compression. L'inconvénient est une complexité de code accrue et un taux de compression réduit. Au départ, je pensais qu'un tel schéma avait du sens, car dans mon cas, les opérations d'écriture coûtent plus cher que la lecture. Mais au final, le taux de compression s'est avéré être deux fois plus élevé. Les avantages d'un tel compromis ne sont pas évidents, par conséquent, je suis revenu à une forme plus simple.Peu de recherches ont déjà été effectuées pour effectuer une recherche volumétrique en largeur des graphiques définis implicitement dans le stockage secondaire, vous pouvez commencer à explorer ce sujetde cet article de 2008 . Comme vous pouvez le deviner, l'idée de faire la déduplication avec le tri + la fusion dans le stockage secondaire n'est pas nouvelle. Ce qui est surprenant, c'est qu'il n'a été ouvert qu'en 1993. Assez tard! Il existe des suggestions ultérieures pour une recherche en largeur dans le stockage secondaire qui ne nécessitent pas d'étape de tri.L'un d'eux consistait à lier des états à des entiers et à stocker en mémoire une image bitmap des états visités. Dans mon cas, cela est complètement inutile, car les tailles de l'état codé sont très différentes par rapport aux espaces d'états vraiment accessibles. Et je doute beaucoup qu'il existe des problèmes intéressants dans lesquels une telle approche fonctionnerait.Une autre alternative sérieuse est basée sur des tables de hachage temporaires. Les états visités sont stockés sans tri dans un fichier. Nous enregistrons la sortie obtenue de la profondeur D dans la table de hachage. Parcourez ensuite de manière itérative les États visités et recherchez-les dans la table de hachage. Si l'élément se trouve dans la table de hachage, supprimez-le. Après avoir parcouru de manière itérative l'intégralité du fichier, seuls les éléments non dupliqués y resteront. Ils sont ensuite ajoutés au fichier et utilisés pour initialiser la liste des tâches pour la prochaine itération. Si la quantité de sortie est si grande que la table de hachage ne tient pas en mémoire, les fichiers et les tables de hachage peuvent être divisés en parties en utilisant les mêmes critères (par exemple, les bits d'état supérieurs), et chaque partie doit être traitée séparément.Bien qu'il existe des repèresmontrant que l'approche basée sur le hachage est environ 30% plus rapide que le tri + la fusion, mais il semble qu'ils ne prennent pas en compte la compression. Je n'ai tout simplement pas vu comment le rejet des avantages de la compression peut se justifier, alors je n'ai même pas expérimenté de telles approches.Un autre domaine de recherche digne d'attention était l'optimisation des requêtes de bases de données. Ça ressemble. que la tâche de déduplication est fortement liée à la jointure de la base de données, qui a également exactement le même dilemme de tri par rapport au hachage. De toute évidence, certaines de ces études peuvent être appliquées au problème de recherche. La différence peut être que la sortie de la base de données de jointure est temporaire, tandis que la sortie de déduplication BFS est stockée jusqu'à la fin du calcul. Il semble que cela modifie l'équilibre des compromis: il s'agit désormais non seulement du traitement le plus efficace d'une itération, mais également de la création du format de données de sortie le plus optimal pour la prochaine itération.Conclusion
Ceci conclut mon récit de ce que j'ai appris d'un projet qui est généralement applicable à d'autres tâches de recherche par force brute. La combinaison de ces astuces a permis de réduire le volume de solutions aux puzzles les plus complexes du jeu de 50-100 Go à 500 Mo et d'augmenter en douceur les coûts si la tâche dépasse la mémoire disponible et est écrite sur le disque. De plus, ma solution est 50% plus rapide qu'une déduplication naïve d'états basée sur des tables de hachage, même pour des puzzles qui tiennent en mémoire.Snakebird peut être acheté sur Steam , Google Play et l' App Store . Je le recommande à tous ceux qui s'intéressent aux puzzles très complexes mais honnêtes.