Pourquoi les listes sont-elles rarement utilisées dans Go?

Je suis nouveau à Go et très excité à ce sujet. Mais, dans tous les langages avec lesquels j’ai beaucoup travaillé: Delphi, C #, C ++, Python, les listes sont très importantes car elles peuvent être redimensionnées dynamicment, contrairement aux tableaux.

Dans Golang, il y a bien une structure list.List , mais je vois très peu de documentation à ce sujet – que ce soit dans Go By Example ou les trois livres Go que j’ai – Summerfield, Chisnal et Balbaert – ils passent tous beaucoup de temps sur des tableaux et tranches, puis passez aux cartes. Dans les exemples de code source, je trouve également peu ou pas d’utilisation de list.List .

Il semble également que, contrairement à Python, Range n’est pas pris en charge pour List, ce qui constitue un grave inconvénient. Est-ce que je manque quelque chose?

Les tranches sont certainement agréables, mais elles doivent toujours être basées sur un tableau avec une taille codée en dur. C’est là que List entre en jeu. Existe-t-il un moyen de créer un tableau / une tranche dans Go sans une taille de tableau codée en dur? Pourquoi la liste est-elle ignorée?

Presque toujours lorsque vous pensez à une liste – utilisez plutôt une tranche dans Go. Les tranches sont redimensionnées dynamicment. À la base de cela se trouve une tranche de mémoire contiguë qui peut changer de taille.

Ils sont très flexibles, comme vous le verrez si vous lisez la page du wiki SliceTricks .

Voici un extrait: –

Copie

 b = make([]T, len(a)) copy(b, a) // or b = append([]T(nil), a...) 

Couper

 a = append(a[:i], a[j:]...) 

Effacer

 a = append(a[:i], a[i+1:]...) // or a = a[:i+copy(a[i:], a[i+1:])] 

Supprimer sans conserver l’ordre

 a[i], a = a[len(a)-1], a[:len(a)-1] 

Pop

 x, a = a[len(a)-1], a[:len(a)-1] 

Pousser

 a = append(a, x) 

Mise à jour : voici un lien vers un article de blog sur les tranches de l’équipe go elle-même, qui explique bien la relation entre les tranches et les tableaux et les composants internes.

J’ai posé cette question il y a quelques mois, lorsque j’ai commencé à étudier Go. Depuis lors, je lis tous les jours à propos de Go, et codé dans Go.

Parce que je n’ai pas reçu de réponse claire à cette question (bien que j’aie accepté une réponse), je vais maintenant y répondre moi-même, en me basant sur ce que j’ai appris, puisque je lui ai demandé:

Est-il possible de créer un tableau / une tranche dans Go sans une taille de tableau codée en dur?

Oui. Les tranches ne nécessitent pas de tableau codé en dur pour slice :

 var sl []int = make([]int,len,cap) 

Ce code alloue slice sl , de taille len avec une capacité de capcap et les variables cap peuvent être affectées à l ‘exécution.

Pourquoi list.List est- list.List ignoré?

Il semble que la liste des raisons principales.Liste semble avoir peu d’attention dans Go sont:

  • Comme cela a été expliqué dans la réponse de @Nick Craig-Wood, il n’y a pratiquement rien qui puisse être fait avec des listes qui ne peuvent être faites avec des tranches, souvent plus efficaces et avec une syntaxe plus propre et plus élégante. Par exemple, la construction de la plage:

     for i:=range sl { sl[i]=i } 

    ne peut pas être utilisé avec la liste – un style C pour la boucle est requirejs. Et dans de nombreux cas, la syntaxe du style de collection C ++ doit être utilisée avec les listes: push_back etc.

  • Plus important encore, list.List n’est pas fortement typé – il est très similaire aux listes et aux dictionnaires de Python, qui permettent de mélanger différents types dans la collection. Cela semble aller à l’encontre de l’approche de Go. Go est un langage très fortement typé – par exemple, les conversions de types implicites jamais autorisées dans Go, même un upCast de int à int64 doit être explicite. Mais toutes les méthodes de list.List prennent des interfaces vides – tout est permis.

    Une des raisons pour lesquelles j’ai abandonné Python et que je suis passé sur Go est à cause de cette sorte de faiblesse dans le système de types de Python, bien que Python prétende être “fortement typé” (ce n’est pas le cas). La list.List de list.List semble être une sorte de “mongrel”, né du vector et de la List() de Python List() de C ++, et est peut-être un peu hors de propos dans Go lui-même.

Cela ne m’étonnerait pas si, dans un avenir pas trop lointain, nous trouvons list.List déconseillé dans Go, même si cela restra peut-être pour répondre aux rares situations où, même en utilisant de bonnes pratiques de conception, un problème peut être résolu avec une collection qui contient différents types. Ou peut-être existe-t-il un «pont» pour que les développeurs de familles C puissent se familiariser avec Go avant d’apprendre les nuances des tranches, uniques à Go, AFAIK. (À certains égards, les tranches semblent similaires aux classes de stream en C ++ ou Delphi, mais pas entièrement.)

Bien que venant d’un arrière-plan Delphi / C ++ / Python, dans ma première exposition à Go, j’ai trouvé list.List pour être plus familier que les tranches de Go, car je suis devenu plus à l’aise avec Go, j’ai changé toutes mes listes en tranches . Je n’ai pas encore trouvé quelque chose que la slice et / ou la map ne me permettent pas de faire, de sorte que je dois utiliser list.List .

Je pense que c’est parce qu’il n’ya pas grand chose à dire à leur sujet, car le paquet container/list les container/list est assez explicite une fois que vous avez assimilé le principal idiome de travail pour travailler avec des données génériques.

Dans Delphi (sans génériques) ou en C, vous stockeriez des pointeurs ou des TObject dans la liste, puis vous les renverriez à leurs types réels lorsque vous les obtiendriez dans la liste. En C ++, les listes STL sont des modèles et donc paramétrées par type, et dans C # (ces jours-ci), les listes sont génériques.

Dans Go, container/list stocke les valeurs de type interface{} qui est un type spécial capable de représenter des valeurs de tout autre type (réel) – en stockant une paire de pointeurs: un pour le type info de la valeur contenue et un pointeur à la valeur (ou la valeur directement, si sa taille n’est pas supérieure à la taille d’un pointeur). Donc, lorsque vous voulez append un élément à la liste, vous le faites simplement parce que les parameters de la fonction type interface{} acceptent les valeurs coo tout type. Mais lorsque vous extrayez des valeurs de la liste et que vous devez les utiliser avec leurs types réels, vous devez soit les saisir, soit les modifier. Les deux approches ne sont que des façons différentes de faire la même chose.

Voici un exemple pris ici :

 package main import ("fmt" ; "container/list") func main() { var x list.List x.PushBack(1) x.PushBack(2) x.PushBack(3) for e := x.Front(); e != nil; e=e.Next() { fmt.Println(e.Value.(int)) } } 

Ici, nous obtenons la valeur d’un élément en utilisant e.Value() , puis nous l’ e.Value() un type de la valeur insérée d’origine.

Vous pouvez lire les assertions de type et saisir les options dans “Effective Go” ou tout autre livre d’introduction. La documentation du container/list récapitule toutes les méthodes supscopes par les listes.

Notez que les tranches Go peuvent être développées via la fonction intégrée append() . Bien que cela nécessite parfois de faire une copie du tableau de sauvegarde, cela ne se produira pas à chaque fois, car Go surdimensionnera le nouveau tableau en lui donnant une capacité supérieure à la longueur signalée. Cela signifie qu’une opération d’ajout ultérieure peut être effectuée sans autre copie de données.

Alors que vous vous retrouvez avec plus de copies de données qu’avec un code équivalent implémenté avec des listes liées, vous n’avez plus besoin d’allouer des éléments dans la liste et de mettre à jour les pointeurs Next . Pour de nombreuses utilisations, l’implémentation basée sur la baie fournit des performances meilleures ou suffisantes. C’est ce qui est souligné dans le langage. Fait intéressant, le type de list standard de Python est également soutenu par des tableaux et présente des caractéristiques de performances similaires lors de l’ajout de valeurs.

Cela dit, il existe des cas où les listes liées sont un meilleur choix (par exemple, lorsque vous devez insérer ou supprimer des éléments au début / au milieu d’une longue liste), et c’est pourquoi une implémentation de bibliothèque standard est fournie. Je suppose qu’ils n’ont pas ajouté de fonctionnalités linguistiques spéciales pour travailler avec eux, car ces cas sont moins courants que ceux où des tranches sont utilisées.

À moins que la tranche ne soit mise à jour trop souvent (suppression, ajout d’éléments à des emplacements aléatoires), la contiguïté de la mémoire des tranches offrira un excellent taux d’access au cache par rapport aux listes liées.

Scott Meyer parle de l’importance du cache. https://www.youtube.com/watch?v=WDIkqP4JbkE

De: https://groups.google.com/forum/#!msg/golang-nuts/mPKCoYNwsoU/tLefhE7tQjMJ


 Cela dépend beaucoup du nombre d'éléments dans vos listes,
  si une vraie liste ou une tranche sera plus efficace
  lorsque vous devez effectuer de nombreuses suppressions au milieu de la liste.

 #1
 Plus il y a d'éléments, moins une tranche devient attrayante. 

 # 2
 Lorsque l’ordre des éléments n’est pas important,
  il est plus efficace d'utiliser une tranche et
  supprimer un élément en le remplaçant par le dernier élément de la tranche et
  re-découper la tranche pour réduire le len de 1
  (comme expliqué dans le wiki SliceTricks)

Alors
utiliser une tranche
1. Si l’ordre des éléments de la liste n’est pas important et que vous devez supprimer,
use List permute l’élément à supprimer avec le dernier élément, & re-tranche à (length-1)
2. lorsque les éléments sont plus (quel que soit le moyen)


 There are ways to mitigate the deletion problem -- eg the swap sortingck you mentioned or just marking the elements as logically deleted. But it's impossible to mitigate the problem of slowness of walking linked lists. 

Alors
utiliser une tranche
1. Si vous avez besoin de vitesse en traversée

list.List est implémenté comme une liste doublement liée. Les listes basées sur les tableaux (vecteurs en C ++, ou tranches en golang) sont un meilleur choix que les listes liées dans la plupart des conditions si vous ne l’insérez pas souvent au milieu de la liste. La complexité du temps amorti pour append est O (1) pour la liste de masortingces et la liste chaînée, même si la liste de masortingces doit étendre la capacité et copier les valeurs existantes. Les listes de tableaux ont un access aléatoire plus rapide, une empreinte mémoire plus réduite et, plus important encore, une convivialité pour le récupérateur de mémoire en raison de l’absence de pointeurs dans la structure de données.