Plage de Golang à travers le canal avec un comportement impair lors de la mise en place de l'algorithme de permutation de tas

Question

J'essayais d'implémenter Heap's Algorithm en utilisant go channels. Le code ci-dessous fonctionne correctement lorsque vous imprimez les tranches sur l'écran, mais lorsque vous utilisez les canaux pour fournir les tableaux à une boucle for/range sur la fonction principale, un comportement inattendu se produit et les tranches/tableaux sont imprimés en double et toutes les permutations envoyé. J'ai pensé que peut-être je ferme le canal plus tôt que la fonction principale est capable d'imprimer les résultats mais je ne m'attendrais pas à ce double impression. Pourquoi cela se passe-t-il et comment puis-je le faire fonctionner.

package main 

import "fmt" 

func perm(a []int64) { 
    var n = len(a) 
    var c = make([]int, n) 
    fmt.Println(a) 
    i := 0 
    for i < n { 
     if c[i] < i { 
      if i%2 == 0 { 
       a[0], a[i] = a[i], a[0] 
      } else { 
       a[c[i]], a[i] = a[i], a[c[i]] 
      } 
      fmt.Println(a) 
      c[i]++ 
      i = 0 
     } else { 
      c[i] = 0 
      i++ 
     } 
    } 
} 

func permch(a []int64, ch chan<- []int64) { 
    var n = len(a) 
    var c = make([]int, n) 
    ch <- a 
    i := 0 
    for i < n { 
     if c[i] < i { 
      if i%2 == 0 { 
       a[0], a[i] = a[i], a[0] 
      } else { 
       a[c[i]], a[i] = a[i], a[c[i]] 
      } 
      ch <- a 
      c[i]++ 
      i = 0 
     } else { 
      c[i] = 0 
      i++ 
     } 
    } 
    close(ch) 
} 

func main() { 
    var i = []int64{1, 2, 3} 
    fmt.Println("Without Channels") 
    perm(i) 
    ch := make(chan []int64) 
    go permch(i, ch) 
    fmt.Println("With Channels") 
    for slc := range ch { 
     fmt.Println(slc) 
    } 

} 

Answer 1

Il semble que permch modifie a en même temps que main l'imprime, de sorte que votre sortie est brouillée.

je peux penser à trois solutions faciles:

1. Accès garde à a avec un mutex.
2. Mettez une copie de a sur la chaîne:
3. ont une sorte de signal de retour de principal qu'il a imprimé et permch peut continuer. (ne recommande pas vraiment cela, mais ça marche).

numéro 2 est assez simple:

a2 := make([]int64, len(a)) 
copy(a2,a) 
ch <- a2 

et est ce que je recommande.

Pour la valeur 1, déclarez var m sync.Mutex comme variable de package et Lock chaque fois que vous lisez ou modifiez a. C'est une condition de course entre le lecteur et la prochaine modification, comme vous l'avez souligné, donc ce n'est probablement pas une bonne solution après tout.

fixed version on playground using #3

Answer 2

Votre problème est que les tranches sont des types de référence et sont accessibles dans plusieurs goroutines. Dans perm, vous imprimez a directement lorsque vous terminez le traitement à chaque étape. Dans permch, vous envoyez a sur le canal, puis vous commencez immédiatement à le modifier à nouveau. Étant donné que chaque segment envoyé sur le canal fait référence au même tableau sous-jacent, vous devez déterminer si votre prochaine itération de boucle modifie a ou si votre appel Println() dans main arrive en premier dans ce tableau.

En général, si vous rencontrez un comportement inattendu dans un programme utilisant des goroutines, vous avez probablement une condition de concurrence . Exécutez le programme avec le drapeau -race pour voir où.

Edit: aussi, la fermeture d'un canal n'a pas d'effet sur une routine lecture du canal. Un canal peut continuer à être lu jusqu'à ce que son tampon soit vide, à quel point il va commencer à retourner la valeur zéro pour ce type à la place. Les boucles de plage sur un canal ne se terminent que lorsque le canal est fermé et que son tampon est vide.