Dlaczego listy są rzadko używane w Go?

Jestem nowy w Go i jestem tym bardzo podekscytowany. Ale we wszystkich językach, z którymi intensywnie pracowałem: Delphi, C #, C ++, Python - listy są bardzo ważne, ponieważ mogą być dynamicznie zmieniane, w przeciwieństwie do tablic.

W Golang rzeczywiście istnieje list.Liststruktura, ale widzę bardzo mało dokumentacji na jej temat - czy to w Go By Example, czy w trzech książkach Go, które mam - Summerfield, Chisnal i Balbaert - wszystkie spędzają dużo czasu na tablicach i plasterkach i następnie przejdź do map. W przykładach kodu źródłowego również nie znajduję zastosowania list.List.

Wydaje się również, że w przeciwieństwie do Pythona Rangenie jest obsługiwany przez List - duża wada IMO. Czy coś mi brakuje?

Plasterki są z pewnością ładne, ale nadal muszą opierać się na tablicy z zakodowanym rozmiarem. I tu pojawia się lista. Czy istnieje sposób na utworzenie tablicy / wycinka w Go bez zakodowanego na stałe rozmiaru tablicy? Dlaczego lista jest ignorowana?

Prawie zawsze, gdy myślisz o liście - zamiast tego użyj wycinka w Idź. Plasterki są dynamicznie zmieniane. U ich podstaw leży ciągły fragment pamięci, który może zmieniać rozmiar.

Są bardzo elastyczne, co zobaczysz, czytając stronę wiki SliceTricks .

Oto fragment: -

Kopiuj

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

Skaleczenie

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

Usunąć

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

Usuń bez zachowywania kolejności

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

Muzyka pop

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

Pchać

a = append(a, x)

Aktualizacja : Oto link do wpisu na blogu poświęconego wycinkom samego zespołu go, który dobrze sobie radzi z wyjaśnieniem związku między plasterkami i tablicami oraz elementami wewnętrznymi plasterków.

Zadałem to pytanie kilka miesięcy temu, kiedy po raz pierwszy zacząłem badać Go. Od tamtej pory codziennie czytam o Go i programowaniu w Go.

Ponieważ nie otrzymałem jednoznacznej odpowiedzi na to pytanie (chociaż przyjąłem jedną odpowiedź), teraz odpowiem na nie sam, opierając się na tym, czego się nauczyłem, odkąd je zadałem:

Czy istnieje sposób na utworzenie tablicy / wycinka w Go bez zakodowanego na stałe rozmiaru tablicy?

Tak. Plasterki nie wymagają zakodowanej na stałe tablicy sliceod:

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

Ten kawałek przydziela kod sl, wielkości leno wydajności cap- leni capto zmienne, które można przypisać w czasie wykonywania.

Dlaczego jest list.Listignorowany?

Wydaje się, że główne powody, list.Listna które zwraca się niewielką uwagę w Go, to:

• Jak wyjaśniono w odpowiedzi @Nick Craig-Wood, praktycznie nic nie można zrobić z listami, których nie można zrobić z plasterkami, często bardziej wydajnie iz czystszą, bardziej elegancką składnią. Na przykład konstrukcja zakresu:

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

  nie można używać z listą - wymagana jest pętla for w stylu C. W wielu przypadkach składnia w stylu kolekcji C ++ musi być używana z listami: push_backitp.

• Co ważniejsze, list.Listnie jest silnie typowany - jest bardzo podobny do list i słowników Pythona, które pozwalają na mieszanie różnych typów w kolekcji. Wydaje się, że jest to sprzeczne z podejściem Go do rzeczy. Go jest językiem o bardzo silnym typie - na przykład niejawne konwersje typów nigdy nie są dozwolone w Go, nawet upCast z intdo int64musi być jawny. Ale wszystkie metody list.List przyjmują puste interfejsy - wszystko jest dozwolone.

  Jednym z powodów, dla których porzuciłem Pythona i przeniosłem się do Go, są tego rodzaju słabości w systemie typów Pythona, chociaż Python twierdzi, że jest „silnie wpisany” (IMO tak nie jest). Go list.Listwydaje się być rodzajem „mieszańca”, zrodzonego z C ++ vector<T>i Pythona List(), i być może jest trochę nie na miejscu w samym Go.

Nie zdziwiłbym się, gdybyśmy kiedyś w niezbyt odległej przyszłości znaleźli listę.Lista przestarzała w Go, choć być może pozostanie, aby uwzględnić te rzadkie sytuacje, w których nawet przy użyciu dobrych praktyk projektowych można najlepiej rozwiązać problem z kolekcją zawierającą różne typy. A może jest po to, aby zapewnić "pomost" dla programistów z rodziny C, aby mogli poczuć się komfortowo z Go, zanim nauczą się niuansów wycinków, które są unikalne dla Go, AFAIK. (Pod pewnymi względami plasterki wydają się podobne do klas strumieniowych w C ++ lub Delphi, ale nie do końca).

Chociaż wywodzę się z Delphi / C ++ / Python, w moim początkowym kontakcie z Go wydałem się list.Listbardziej znajomy niż plasterki Go, ponieważ poczułem się bardziej komfortowo z Go, wróciłem i zmieniłem wszystkie moje listy na plasterki. Nie znalazłem jeszcze niczego, co slicei / lub mapnie pozwalają mi na to, czego potrzebuję list.List.

Myślę, że to dlatego, że nie ma o nich wiele do powiedzenia, ponieważ container/listpakiet jest raczej oczywisty, gdy już przyswoisz, jaki jest główny idiom Go do pracy z danymi ogólnymi.

W Delphi (bez TObjecttypów ogólnych) lub w C można przechowywać wskaźniki lub s na liście, a następnie rzutować je z powrotem do ich rzeczywistych typów podczas uzyskiwania z listy. W języku C ++ STL listy są szablonami i dlatego są sparametryzowane według typu, aw języku C # (obecnie) listy są ogólne.

W Go container/listprzechowuje wartości typu, interface{}który jest specjalnym typem zdolnym do reprezentowania wartości dowolnego innego (rzeczywistego) typu - przechowując parę wskaźników: jeden do informacji o typie zawartej wartości i wskaźnik do wartości (lub wartość bezpośrednio, jeśli jej rozmiar nie jest większy niż rozmiar wskaźnika). Więc jeśli chcesz dodać element do listy, po prostu zrób to, ponieważ parametry funkcji typu interface{}przyjmują wartości coo dowolnego typu. Ale kiedy wyodrębniasz wartości z listy i nad czym pracować z ich prawdziwymi typami, musisz albo je potwierdzić , albo przełączyć na nich - oba podejścia są po prostu różnymi sposobami zrobienia zasadniczo tego samego.

Oto przykład wzięty stąd :

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))
    }
}

Tutaj uzyskujemy wartość elementu za pomocą, e.Value()a następnie potwierdzamy inttypem jako typ pierwotnie wstawionej wartości.

Możesz przeczytać o potwierdzeniach typu i przełącznikach typów w „Efektywne przejście” lub w dowolnej innej książce wprowadzającej. Dokumentacja container/listpakietu podsumowuje wszystkie obsługiwane listy metod.

Zwróć uwagę, że plasterki Go można rozwinąć za pomocą append()funkcji wbudowanej. Chociaż czasami będzie to wymagało wykonania kopii tablicy zapasowej, nie będzie się to zdarzało za każdym razem, ponieważ Go przeskoczy nową tablicę, dając jej większą pojemność niż zgłoszona długość. Oznacza to, że kolejna operacja dołączania może zostać zakończona bez kolejnej kopii danych.

Chociaż w efekcie otrzymujesz więcej kopii danych niż w przypadku równoważnego kodu zaimplementowanego z listami połączonymi, eliminujesz potrzebę indywidualnego przydzielania elementów na liście i aktualizację Nextwskaźników. W wielu zastosowaniach implementacja oparta na tablicach zapewnia lepszą lub dostatecznie dobrą wydajność, więc na to kładzie nacisk w języku. Co ciekawe, standardowy listtyp Pythona jest również obsługiwany przez tablicę i ma podobną charakterystykę wydajności podczas dołączania wartości.

To powiedziawszy, są przypadki, w których listy linkowane są lepszym wyborem (np. Gdy trzeba wstawić lub usunąć elementy z początku / środka długiej listy) i dlatego jest dostępna standardowa implementacja biblioteki. Wydaje mi się, że nie dodali żadnych specjalnych funkcji językowych do pracy z nimi, ponieważ te przypadki są mniej powszechne niż te, w których używane są plasterki.

O ile wycinek nie jest aktualizowany zbyt często (usuwaj, dodawaj elementy w losowych lokalizacjach), ciągłość pamięci plasterków zapewni doskonały współczynnik trafień w pamięci podręcznej w porównaniu z połączonymi listami.

Wykład Scotta Meyera na temat znaczenia pamięci podręcznej. Https://www.youtube.com/watch?v=WDIkqP4JbkE

list.Listjest zaimplementowana jako lista podwójnie połączona. Listy oparte na tablicach (wektory w C ++ lub wycinki w języku golang) są lepszym wyborem niż listy połączone w większości warunków, jeśli nie wstawiasz często na środek listy. Zamortyzowana złożoność czasowa dołączania wynosi O (1) zarówno dla listy tablic, jak i listy połączonej, mimo że lista tablic musi zwiększyć pojemność i skopiować istniejące wartości. Listy tablic mają szybszy dostęp losowy, mniejsze zużycie pamięci i, co ważniejsze, są przyjazne dla modułu odśmiecania pamięci, ponieważ nie zawierają wskaźników wewnątrz struktury danych.

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

To zależy w dużej mierze od liczby elementów na Twoich listach,
 czy prawdziwa lista czy wycinek będą bardziej wydajne
 kiedy musisz dokonać wielu operacji usunięcia „w środku” listy.

# 1
Im więcej elementów, tym mniej atrakcyjny staje się kawałek. 

# 2
Gdy kolejność elementów nie jest ważna,
 najbardziej wydajne jest użycie plasterka i
 usunięcie elementu poprzez zastąpienie go ostatnim elementem w plasterku i
 ponowne cięcie plastra, aby zmniejszyć soczewkę o 1
 (jak wyjaśniono na wiki SliceTricks)

Więc
użyj wycinka
1. Jeśli kolejność elementów na liście nie jest ważna i musisz usunąć, po prostu
użyj Lista zamień element do usunięcia z ostatnim elementem i przekrój ponownie na (length-1)
2. gdy elementów jest więcej ( cokolwiek więcej znaczy)

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

Więc
użyj plasterka
1. Jeśli potrzebujesz szybkości w przemierzaniu