Czy istnieje konkretny cel dla list heterogenicznych?

13

Pochodzę z języka C # i Java, jestem przyzwyczajony do tego, że moje listy są jednorodne i to ma dla mnie sens. Kiedy zacząłem zbierać Lisp, zauważyłem, że listy mogą być niejednorodne. Kiedy zacząłem przekręcać ze dynamicsłowem kluczowym w C #, zauważyłem, że od C # 4.0 mogą istnieć również listy heterogeniczne:

List<dynamic> heterogeneousList

Moje pytanie brzmi o co chodzi? Wydaje się, że lista heterogeniczna będzie miała znacznie większy narzut podczas przetwarzania, a jeśli chcesz przechowywać różne typy w jednym miejscu, możesz potrzebować innej struktury danych. Czy moja naiwność wychowuje brzydką twarz, czy naprawdę są chwile, kiedy warto mieć heterogeniczną listę?

Jetti
źródło
1
Czy miałeś na myśli ... Zauważyłem, że listy mogą być niejednorodne ...?
Inżynier świata
Czym List<dynamic>różni się (w przypadku twojego pytania) od zwykłego działania List<object>?
Peter K.
@WorldEngineer tak, robię. Zaktualizowałem swój post. Dzięki!
Jetti
@PeterK. Chyba do codziennego użytku, nie ma różnicy. Jednak nie każdy typ w języku C # pochodzi od System.Object, więc byłyby przypadki brzegowe, w których występują różnice.
Jetti

Odpowiedzi:

16

Artykuł „ Silnie wpisane zbiory heterogeniczne” Olega Kiselyova, Ralfa Lämmela i Keeana Schupke zawiera nie tylko implementację list heterogenicznych w Haskell, ale także motywujący przykład tego, kiedy, dlaczego i jak korzystać z list HLists. W szczególności używają go do bezpiecznego dostępu do bazy danych sprawdzonej podczas kompilacji. (Pomyśl, LINQ, w rzeczywistości, do którego się odnoszą, jest artykuł Haskella autorstwa Erika Meijera i innych, który doprowadził do LINQ.)

Cytując z wprowadzającego akapitu artykułu HLists:

Oto otwarta lista typowych przykładów, które wymagają heterogenicznych kolekcji:

  • Tablica symboli, która ma przechowywać wpisy różnych typów, jest niejednorodna. Jest to mapa skończona, w której typ wyniku zależy od wartości argumentu.
  • Element XML jest heterogenicznie wpisany. W rzeczywistości elementy XML to zagnieżdżone kolekcje, które są ograniczone wyrażeniami regularnymi i właściwością 1-niejednoznaczności.
  • Każdy wiersz zwracany przez zapytanie SQL jest heterogeniczną mapą od nazw kolumn do komórek. Rezultatem zapytania jest jednorodny strumień heterogenicznych wierszy.
  • Dodanie zaawansowanego systemu obiektowego do języka funkcjonalnego wymaga heterogenicznych kolekcji, które łączą rozszerzalne rekordy z podtytułem i interfejsem wyliczania.

Zauważ, że przykłady, które podałeś w swoim pytaniu, tak naprawdę nie są listami heterogenicznymi w tym sensie, że słowo to jest powszechnie używane. Są to listy o słabym typie lub bez typu . W rzeczywistości są one w rzeczywistości homogenicznymi listami, ponieważ wszystkie elementy są tego samego typu: objectlub dynamic. Następnie musisz wykonać rzutowania lub niesprawdzone instanceoftesty lub coś w tym rodzaju, aby faktycznie móc znacząco pracować z elementami, co powoduje, że są one słabo wpisane.

Jörg W Mittag
źródło
Dziękuję za link i twoją odpowiedź. Masz rację, że listy naprawdę nie są niejednorodne, ale słabo wpisane. Nie mogę się doczekać, aby przeczytać ten artykuł (prawdopodobnie jutro, mam dziś wieczór) :)
Jetti
5

Krótko mówiąc, heterogeniczne pojemniki wymieniają wydajność środowiska wykonawczego w celu zapewnienia elastyczności. Jeśli chcesz mieć „listę rzeczy” bez względu na konkretny rodzaj rzeczy, heterogeniczność jest dobrym rozwiązaniem. Lispy są typowo dynamicznie typowane, a większość wszystkiego i tak jest listą wad pudełkowych wartości, więc oczekuje się niewielkiego spadku wydajności. W świecie Lisp wydajność programisty jest uważana za ważniejszą niż wydajność środowiska wykonawczego.

W języku dynamicznie typowanym jednorodne kontenery faktycznie miałyby niewielki narzut w porównaniu do kontenerów heterogenicznych, ponieważ wszystkie dodane elementy musiałyby zostać sprawdzone pod względem typu.

Twoja intuicja w wyborze lepszej struktury danych jest na miejscu. Ogólnie rzecz biorąc, im więcej umów możesz zawrzeć w kodzie, tym więcej wiesz o tym, jak on działa, i tym bardziej niezawodny, łatwy w utrzymaniu i c. staje się. Czasami jednak naprawdę potrzebujesz heterogenicznego pojemnika i powinieneś mieć możliwość posiadania takiego, jeśli go potrzebujesz.

Jon Purdy
źródło
1
„Jednak czasami naprawdę potrzebujesz heterogenicznego pojemnika i powinieneś mieć możliwość posiadania takiego, jeśli go potrzebujesz”. - Dlaczego jednak? To jest moje pytanie. Dlaczego miałbyś kiedykolwiek chcieć zebrać kilka danych w losową listę?
Jetti
@Jetti: Powiedz, że masz listę różnych ustawień wprowadzonych przez użytkownika. Możesz stworzyć interfejs IUserSettingi zaimplementować go kilkakrotnie lub stworzyć ogólny UserSetting<T>, ale jednym z problemów ze statycznym pisaniem jest to, że definiujesz interfejs, zanim dokładnie wiesz, jak będzie on używany. Rzeczy, które robisz z ustawieniami liczb całkowitych, prawdopodobnie bardzo różnią się od rzeczy, które robisz z ustawieniami ciągów, więc jakie operacje mają sens, aby umieścić we wspólnym interfejsie? Dopóki się nie upewnisz, lepiej rozsądnie używać dynamicznego pisania i uczynić go konkretnym później.
Jon Purdy
Widzę, że tutaj napotykam problemy. Wydaje mi się, że to zły projekt, zrobienie czegoś, zanim się zorientujesz, co się stanie. Ponadto w takim przypadku można utworzyć interfejs z wartością zwracaną przez obiekt. Robi to samo, co lista heterogeniczna, ale jest bardziej przejrzysta i łatwiejsza do naprawienia, gdy wiadomo już, jakie typy są używane w interfejsie.
Jetti
@Jetti: Zasadniczo jest to ten sam problem - uniwersalna klasa podstawowa nie powinna istnieć przede wszystkim, ponieważ bez względu na to, jakie zdefiniuje operacje, będzie typ, dla którego te operacje nie mają sensu. Ale jeśli C # ułatwia użycie objectraczej niż a dynamic, to na pewno skorzystaj z pierwszego.
Jon Purdy
1
@Jetti: Na tym polega polimorfizm. Lista zawiera wiele „heterogenicznych” obiektów, nawet jeśli mogą być one podklasami jednej nadklasy. Z punktu widzenia Java można uzyskać prawidłowe definicje klas (lub interfejsów). W przypadku innych języków (LISP, Python itp.) Poprawne wypełnienie wszystkich deklaracji nie przynosi korzyści, ponieważ nie ma praktycznej różnicy w implementacji.
S.Lott,
2

W językach funkcjonalnych (takich jak lisp) używasz dopasowania wzorca, aby określić, co dzieje się z określonym elementem na liście. Odpowiednikiem w języku C # byłby łańcuch instrukcji if ... elseif, które sprawdzają typ elementu i wykonują na tej podstawie operację. Nie trzeba dodawać, że funkcjonalne dopasowanie wzorca jest bardziej wydajne niż sprawdzanie typu środowiska wykonawczego.

Zastosowanie polimorfizmu byłoby bliższe dopasowaniu do dopasowania wzorca. Oznacza to, że dopasowanie obiektów listy do określonego interfejsu i wywołanie funkcji w tym interfejsie dla każdego obiektu. Inną alternatywą byłoby zapewnienie serii przeciążonych metod, które przyjmują określony typ obiektu jako parametr. Domyślna metoda przyjmująca Object jako parametr.

public class ListVisitor
{
  public void DoSomething(IEnumerable<dynamic> list)
  {
    foreach(dynamic obj in list)
    {
       DoSomething(obj);
    }
  }

  public void DoSomething(SomeClass obj)
  {
    //do something with SomeClass
  }

  public void DoSomething(AnotherClass obj)
  {
    //do something with AnotherClass
  }

  public void DoSomething(Object obj)
  {
    //do something with everything els
  }
}

Takie podejście zapewnia przybliżenie dopasowania wzorca Lisp. Wzorzec odwiedzających (jak tu zaimplementowano, jest doskonałym przykładem użycia list heterogenicznych). Innym przykładem może być wysyłanie wiadomości, w której są nasłuchiwania określonych wiadomości w kolejce priorytetowej i przy użyciu łańcucha odpowiedzialności, dyspozytor przekazuje wiadomość, a pierwszy moduł obsługi, który pasuje do wiadomości, obsługuje ją.

Odwrotna strona powiadamia wszystkich, którzy zarejestrują się na wiadomość (na przykład wzorzec agregatora zdarzeń powszechnie używany do luźnego łączenia ViewModels we wzorcu MVVM). Używam następującej konstrukcji

IDictionary<Type, List<Object>>

Jedynym sposobem na dodanie do słownika jest funkcja

Register<T>(Action<T> handler)

(a obiekt jest w rzeczywistości słabym odniesieniem do przekazywanego programu obsługi). Więc muszę użyć List <Object>, ponieważ w czasie kompilacji nie wiem, jaki będzie typ zamknięty. Jednak w Runtime mogę wymusić, że to ten typ jest kluczem do słownika. Kiedy chcę odpalić wydarzenie, wzywam

Send<T>(T message)

i ponownie rozwiązuję listę. Nie ma żadnej korzyści z używania Listy <dynamicznej>, ponieważ i tak muszę ją rzucić. Jak widać, zalety obu podejść są zasadne. Jeśli zamierzasz dynamicznie wywołać obiekt za pomocą przeciążenia metody, dynamika jest na to sposobem. Jeśli jesteś zmuszony do rzucania niezależnie, równie dobrze możesz użyć Object.

Michael Brown
źródło
W przypadku dopasowania wzorca przypadki są (zwykle - przynajmniej w ML i Haskell) osadzone w kamieniu przez deklarację typu danych, który jest dopasowany. Listy zawierające takie typy również nie są heterogeniczne.
Nie jestem pewien co do ML i Haskell, ale Erlang może się z nimi równać, co oznacza, że ​​jeśli dotarłeś tutaj, ponieważ żadne inne mecze nie były spełnione, zrób to.
Michael Brown
@MikeBrown - To miłe, ale nie obejmuje DLACZEGO ktoś użyłby list heterogenicznych i nie zawsze działałby z Listą <dynamiczną>
Jetti
4
W języku C # przeciążenia są rozwiązywane w czasie kompilacji . W ten sposób twój przykładowy kod będzie zawsze wywoływał DoSomething(Object)(przynajmniej podczas używania objectw foreachpętli; dynamicto zupełnie inna sprawa).
Heinzi
@Heinzi, masz rację ... Dzisiaj jestem śpiący: P naprawiony
Michael Brown
0

Masz rację, że niejednorodność pociąga za sobą czas działania, ale co ważniejsze, osłabia gwarancje czasu kompilacji zapewniane przez moduł sprawdzania typów. Mimo to istnieją pewne problemy, w których alternatywy są jeszcze bardziej kosztowne.

Z mojego doświadczenia wynika, że ​​przy przetwarzaniu nieprzetworzonych bajtów przez pliki, gniazda sieciowe itp. Często napotykasz takie problemy.

Aby dać prawdziwy przykład, rozważ system obliczeń rozproszonych z wykorzystaniem kontraktów futures . Pracownik w pojedynczym węźle może spawnować pracę dowolnego typu możliwego do serializacji, co daje przyszłość tego typu. Za kulisami system wysyła pracę do peera, a następnie zapisuje zapis powiązania tej jednostki pracy z daną przyszłością, którą należy wypełnić po powrocie odpowiedzi na tę pracę.

Gdzie można przechowywać te zapisy? Intuicyjnie chcesz coś takiego Dictionary<WorkId, Future<TValue>>, ale ogranicza to zarządzanie tylko jednym rodzajem kontraktów terminowych w całym systemie. Bardziej odpowiedni jest typ Dictionary<WorkId, Future<dynamic>>, ponieważ pracownik może rzucić na odpowiedni typ, gdy wymusza przyszłość.

Uwaga : ten przykład pochodzi ze świata Haskell, w którym nie mamy podtytułów. Nie zdziwiłbym się, gdyby istniało bardziej idiomatyczne rozwiązanie dla tego konkretnego przykładu w języku C #, ale mam nadzieję, że nadal jest ilustracyjne.

Adam
źródło
0

ISTR, że Lisp nie ma żadnych struktur danych innych niż lista, więc jeśli potrzebujesz dowolnego typu agregowanego obiektu danych, będzie to musiała być lista heterogeniczna. Jak zauważyli inni, są one również przydatne do szeregowania danych w celu transmisji lub przechowywania. Jedną z fajnych cech jest to, że są one również otwarte, dzięki czemu można ich używać w systemie opartym na analogii potoków i filtrów, a także zwiększać kolejne etapy przetwarzania lub poprawiać dane bez konieczności posiadania stałego obiektu danych lub topologii przepływu pracy .

TMN
źródło