Есть ли конкретная цель для разнородных списков?

13

Исходя из C # и Java, я привык к тому, что мои списки однородны, и это имеет смысл для меня. Когда я начал подбирать Lisp, я заметил, что списки могут быть разнородными. Когда я начал разбираться с dynamicключевым словом в C #, я заметил, что, начиная с C # 4.0, также могут быть разнородные списки:

List<dynamic> heterogeneousList

Мой вопрос в чем смысл? Кажется, что гетерогенный список будет иметь гораздо больше накладных расходов при выполнении обработки, и что если вам нужно хранить разные типы в одном месте, вам может потребоваться другая структура данных. Моя наивность воспитывает свое уродливое лицо, или есть действительно времена, когда полезно иметь разнородный список?

Jetti
источник
1
Вы имели в виду ... Я заметил, что списки могут быть разнородными ...?
Мировой инженер
Чем List<dynamic>отличается (по вашему вопросу) от простого дела List<object>?
Питер К.
@WorldEngineer да, я делаю. Я обновил свой пост. Благодарность!
Джетти
@PeterK. Я думаю, для повседневного использования нет никакой разницы. Тем не менее, не каждый тип в C # является производным от System.Object, поэтому существуют крайние случаи, когда есть различия.
Джетти

Ответы:

16

Статья Олега Киселева, Ральфа Ламмеля и Кина Шупке « Сильно типизированные гетерогенные коллекции » содержит не только реализацию гетерогенных списков в Haskell, но и мотивирующий пример того, когда, почему и как вы будете использовать HLists. В частности, они используют его для безопасного доступа к базе данных во время компиляции. (Подумайте, на самом деле LINQ, статья, на которую они ссылаются, - статья Эрика Мейера и др. На Haskell, приведшая к LINQ.)

Цитата из вступительного абзаца статьи HLists:

Вот открытый список типичных примеров, которые требуют гетерогенных коллекций:

  • Таблица символов, в которой предполагается хранить записи разных типов, неоднородна. Это конечная карта, где тип результата зависит от значения аргумента.
  • Элемент XML является гетерогенно типизированным. Фактически, элементы XML являются вложенными коллекциями, которые ограничены регулярными выражениями и свойством 1-неоднозначности.
  • Каждая строка, возвращаемая запросом SQL, является гетерогенной картой от имен столбцов до ячеек. Результатом запроса является однородный поток разнородных строк.
  • Добавление расширенной объектной системы к функциональному языку требует разнородных коллекций такого типа, которые объединяют расширяемые записи с подтипами и интерфейсом перечисления.

Обратите внимание, что примеры, которые вы привели в своем вопросе, на самом деле не являются неоднородными списками в том смысле, в котором это слово обычно используется. Это слабо типизированные или нетипизированные списки. Фактически, это фактически однородные списки, так как все элементы имеют одинаковый тип: objectили dynamic. Затем вы вынуждены выполнять приведения или непроверенные instanceofтесты или что-то в этом роде, чтобы действительно иметь возможность эффективно работать с элементами, что делает их слабо типизированными.

Йорг Миттаг
источник
Спасибо за ссылку и ваш ответ. Вы делаете хорошее замечание, что списки действительно не неоднородны, а слабо типизированы. Я с нетерпением жду, чтобы прочитать эту газету (вероятно, завтра, я получил среднесрочную сегодня вечером :))
Jetti
5

Короче говоря, гетерогенные контейнеры демонстрируют гибкость во время выполнения. Если вы хотите иметь «список вещей» безотносительно к конкретному типу вещей, гетерогенность - это путь. Лиспы типично динамически типизированы, и большинство из них в любом случае представляет собой объединенный список значений в штучной упаковке, поэтому ожидается небольшое снижение производительности. В мире Lisp производительность программиста считается более важной, чем производительность во время выполнения.

В динамически типизированном языке гомогенные контейнеры фактически будут иметь небольшие накладные расходы по сравнению с гетерогенными, потому что все добавленные элементы должны будут проверяться типом.

Ваша интуиция о выборе лучшей структуры данных налицо. Вообще говоря, чем больше контрактов вы можете заключить в своем коде, тем больше вы знаете о том, как он работает, и тем более надежным, поддерживаемым и т. Д. это становится. Однако иногда вам действительно нужен гетерогенный контейнер, и вам нужно иметь его, если он вам нужен.

Джон Перди
источник
1
«Однако иногда вам действительно нужен гетерогенный контейнер, и вам нужно иметь его, если он вам нужен». - Но почему? Это мой вопрос. Зачем вам когда-нибудь просто собирать данные в случайный список?
Джетти
@Jetti: скажем, у вас есть список пользовательских настроек различных типов. Вы можете создать интерфейс IUserSettingи реализовать его несколько раз, или сделать универсальный UserSetting<T>, но одна из проблем статической типизации заключается в том, что вы определяете интерфейс до того, как точно знаете, как он будет использоваться. То, что вы делаете с целочисленными настройками, вероятно, сильно отличается от того, что вы делаете с строковыми настройками, так что какие операции имеет смысл поместить в общий интерфейс? Пока вы не знаете наверняка, лучше разумно использовать динамическую типизацию и конкретизировать ее позже.
Джон Перди
Видите, вот где я сталкиваюсь с проблемами. Мне это кажется плохим дизайном, когда я что-то делаю до того, как узнаешь, что он будет использовать. Кроме того, в этом случае вы можете создать интерфейс с возвращаемым значением объекта. Делает то же самое, что и гетерогенный список, но более понятен и легче исправить, если вы точно знаете, какие типы используются в интерфейсе.
Джетти
@Jetti: Это, по сути, та же проблема, хотя универсальный базовый класс не должен существовать в первую очередь, потому что, независимо от того, какие операции он определяет, найдется тип, для которого эти операции не имеют смысла. Но если C # облегчает использование, objectа не a dynamic, то обязательно используйте первое.
Джон Перди
1
@Jetti: Вот что такое полиморфизм. Список содержит несколько «разнородных» объектов, даже если они могут быть подклассами одного суперкласса. С точки зрения Java, вы можете получить правильные определения класса (или интерфейса). Для других языков (LISP, Python и т. Д.) Нет смысла делать все объявления правильными, поскольку нет практической разницы в реализации.
S.Lott
2

В функциональных языках (таких как lisp) вы используете сопоставление с образцом, чтобы определить, что происходит с конкретным элементом в списке. Эквивалентом в C # будет цепочка операторов if ... elseif, которые проверяют тип элемента и выполняют основанную на этом операцию. Нет необходимости говорить, что функциональное сопоставление с образцом более эффективно, чем проверка типов во время выполнения.

Использование полиморфизма будет ближе к сопоставлению с образцом. То есть наличие объектов списка соответствует определенному интерфейсу и вызов функции на этом интерфейсе для каждого объекта. Другой альтернативой может быть предоставление ряда перегруженных методов, которые принимают определенный тип объекта в качестве параметра. Метод по умолчанию, принимающий Object в качестве параметра.

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

Этот подход обеспечивает приближение к сопоставлению с шаблоном Lisp. Шаблон посетителей (реализованный здесь, является отличным примером использования для разнородных списков). Другим примером может быть диспетчеризация сообщений, когда в очереди с приоритетами находятся прослушиватели для определенных сообщений, и, используя цепочку ответственности, диспетчер передает сообщение, а первый обработчик, соответствующий сообщению, обрабатывает его.

Обратная сторона уведомляет всех, кто регистрируется на сообщение (например, шаблон Event Aggregator, обычно используемый для слабой связи ViewModels в шаблоне MVVM). Я использую следующую конструкцию

IDictionary<Type, List<Object>>

Единственный способ добавить в словарь - это функция

Register<T>(Action<T> handler)

(и объект фактически является WeakReference для переданного в обработчик). Так что здесь я должен использовать List <Object>, потому что во время компиляции я не знаю, каким будет закрытый тип. Однако во время выполнения я могу убедиться, что именно этот тип является ключевым для словаря. Когда я хочу запустить событие, я звоню

Send<T>(T message)

и снова я разрешаю список. Нет никакого преимущества в использовании List <dynamic>, потому что мне все равно нужно его привести. Итак, как вы видите, у обоих подходов есть свои достоинства. Если вы собираетесь динамически отправлять объект, используя перегрузку метода, динамический способ это сделать. Если вы вынуждены разыгрывать независимо, также можете использовать Object.

Майкл Браун
источник
При сопоставлении с образцом случаи (обычно - по крайней мере, в ML и Haskell) устанавливаются непосредственно после объявления типа данных, с которым сопоставлены. Списки, содержащие такие типы, также не являются гетерогенными.
Я не уверен насчет ML и Haskell, но Эрланг может сравниться с любым, что означает, что если вы пришли сюда, потому что другие матчи не были выполнены, сделайте это.
Майкл Браун
@MikeBrown - это хорошо, но не охватывает ПОЧЕМУ можно использовать гетерогенные списки и не всегда работать со списком <dynamic>
Jetti
4
В C # перегрузки разрешаются во время компиляции . Таким образом, ваш пример кода будет вызываться всегдаDoSomething(Object) (по крайней мере, при использовании objectв foreachцикле; dynamicэто совсем другое).
Хайнци
@ Heinzi, ты прав ... я сегодня сонный: P исправлено
Майкл Браун
0

Вы правы, что неоднородность несет накладные расходы времени выполнения, но, что более важно, это ослабляет гарантии времени компиляции, предоставляемые средством проверки типов. Тем не менее, есть некоторые проблемы, когда альтернативы являются еще более дорогостоящими.

По моему опыту, имея дело с необработанными байтами через файлы, сетевые сокеты и т. Д., Вы часто сталкиваетесь с такими проблемами.

Чтобы привести реальный пример, рассмотрим систему распределенных вычислений с использованием фьючерсов . Рабочий на отдельном узле может порождать работу любого сериализуемого типа, создавая будущее этого типа. За кулисами система отправляет работу коллеге, а затем сохраняет запись, связывающую эту единицу работы с конкретным будущим, которая должна быть заполнена, как только ответ на эту работу вернется.

Где можно хранить эти записи? Интуитивно понятно, что вы хотите что-то вроде a Dictionary<WorkId, Future<TValue>>, но это ограничивает вас в управлении только одним типом фьючерсов во всей системе. Более подходящий тип Dictionary<WorkId, Future<dynamic>>, поскольку работник может привести к соответствующему типу, когда он форсирует будущее.

Примечание : этот пример взят из мира Haskell, где у нас нет подтипов. Я не удивлюсь, если есть более идиоматическое решение для этого конкретного примера в C #, но, надеюсь, оно все еще иллюстративно.

Адам
источник
0

Истр , что Lisp не имеет структуры данных , кроме списка, так что если вам нужен любой тип агрегатного объекта данных, это будет иметь , чтобы быть гетерогенным список. Как уже отмечали другие, они также полезны для сериализации данных для передачи или хранения. Одна приятная особенность заключается в том, что они также являются открытыми, поэтому их можно использовать в системе на основе аналогии с конвейерами и фильтрами, а последовательные этапы обработки увеличивают или исправляют данные, не требуя ни фиксированного объекта данных, ни топологии рабочего процесса. ,

TMN
источник