Comment copier efficacement des tableaux bidimensionnels d'octets dans un tableau 2D plus grand?

Question

J'ai une structure appelée Patch qui représente un tableau 2D de données. Je souhaite construire un patch plus grand à partir d'un ensemble de patchs plus petits et de leurs positions assignées. (Les correctifs ne se chevauchent pas.) La fonction ressemble à ceci:

newtype Position = (Int, Int) 

combinePatches :: [(Position, Patch)] -> Patch 
combinePatches plan = undefined 

Je vois deux sous-problèmes. D'abord, je dois définir une fonction pour traduire des copies de tableau 2D en un ensemble de copies de tableau 1D. Deuxièmement, je dois construire le dernier patch de toutes ces copies.

Notez que le patch final sera environ 4 Mo de données. C'est pourquoi je veux éviter une approche naïve.

Je suis assez confiant que je pouvais le faire horriblement inefficacement, mais je voudrais quelques conseils sur la façon de manipuler efficacement de grands tableaux 2D dans Haskell. J'ai regardé la bibliothèque "vector", mais je ne l'ai jamais utilisée auparavant.

Merci pour votre temps.

Answer 1

Si la spécification est vraiment juste une création unique d'un nouveau patch d'un ensemble de précédents et de leurs positions, alors c'est un algorithme simple passe simple. Conceptuellement, j'y penserais en deux étapes - d'abord, combiner les correctifs existants dans une structure de données avec une recherche raisonnable pour n'importe quelle position donnée. Ensuite, écrivez paresseusement votre nouvelle structure en interrogeant la structure composée. Cela devrait être approximativement O (n log (m)) - n étant la taille du nouveau tableau que vous écrivez, et m étant le nombre de patches.

C'est conceptuellement beaucoup plus simple si vous utilisez la bibliothèque Vector au lieu d'un ByteString brut. Mais c'est encore plus simple si vous utilisez simplement Data.Array.Unboxed. Si vous avez besoin de tableaux pouvant interopérer avec C, utilisez plutôt Data.Array.Storable.

Si vous fossé la pureté, au moins localement, et travailler avec un tableau ST, vous devriez être en mesure de faire ce trivialement en O (n). Bien sûr, les facteurs constants seront encore pire que d'utiliser la copie rapide de blocs de mémoire à la fois, mais il n'y a aucun moyen d'empêcher ce code de paraître de bas niveau.