Comment mémoriser une méthode de génération de tableau multidimensionnelle

Question

J'ai une méthode table_data utilisée pour créer un tableau multidimensionnel pour une table de multiplication. La première ligne et la première colonne de la table sont les mêmes, chaque cellule contenant le produit pour la ligne et la colonne correspondantes. Heres ce qu'il imprime finalement:

2 3 4 . . n 

2 4 6 8 

3 6 9 12 

4 8 12 16 
. 
. 
n 

Comme vous pouvez le voir, il y a beaucoup de doublons qui peuvent être memoized. Voici le code pour générer le tableau multidimensionnel:

def table_data(n) 
    table_header(n).map do |x| 
    table_header(n).map do |y| 
     x*y 
    end 
    end 
end 

def table_header(n) 
    @header_data ||= (1..n).to_a 
end 

Le procédé table_data prend du temps quadratique; il fait le double du travail nécessaire (pour x*y et y*x). Comment puis-je mémoriser et/ou modifier cette méthode pour réduire le temps d'exécution?

Answer 1

En termes de réduction du temps d'exécution, cela dépend si vous considérez x*y comme une opération négligeable ou non. Si vous le remplacez par une sorte de requête SQL ou quelque chose avec un coût plus tangible, la mise en cache aurait du sens. Mais en termes de grande complexité O, la variable dynamique est ici la largeur/hauteur de la table, par ex. nombre d'itérations que je ne vois pas un bon moyen de réduire.

Quoi qu'il en soit, pour mettre en cache x*y vous pouvez faire une classe d'aide comme celui-ci

class MultiplicationCache 
    def initialize 
    @cache = {} 
    end 
    def multiply(a,b) 
    @cache[[a,b].sort] ||= a * b 
    end 
end 

# usage 
cache = MultiplicationCache.new 
puts cache.multiply(1,2) # => 2 

Encore une fois, il ne fait pas vraiment de sens de le faire, sauf si vous remplacez x*y avec quelque chose qui est vraiment cher informatiquement.