¿Hay un propósito específico para las listas heterogéneas?

13

Desde un fondo de C # y Java, estoy acostumbrado a que mis listas sean homogéneas, y eso tiene sentido para mí. Cuando comencé a recoger Lisp, noté que las listas pueden ser heterogéneas. Cuando comencé a joder con la palabra clave dynamic en C #, noté que, a partir de C # 4.0, también puede haber listas heterogéneas:

List<dynamic> heterogeneousList

Mi pregunta es ¿cuál es el punto? Parece que una lista heterogénea tendrá una sobrecarga mucho mayor al realizar el procesamiento y que si necesita almacenar diferentes tipos en un lugar, es posible que necesite una estructura de datos diferente. ¿Es mi ingenuidad tener una cara fea o hay momentos en que es útil tener una lista heterogénea?

    
pregunta Jetti 01.02.2012 - 14:59

5 respuestas

14

El documento Colecciones heterogéneas fuertemente tipeadas de Oleg Kiselyov, Ralf Lämmel y Keean Schupke no solo contiene una implementación de listas heterogéneas en Haskell, pero también un ejemplo motivador de cuándo, por qué y cómo usaría HLists. En particular, lo están utilizando para el acceso a la base de datos comprobado en tiempo de compilación seguro para el tipo. (Piense en LINQ, de hecho, el documento al que hacen referencia es el documento de Haskell de Erik Meijer y otros que llevó a LINQ).

Cita del párrafo introductorio del documento HLists:

  

Aquí hay una lista abierta de ejemplos típicos que requieren colecciones heterogéneas:

     
  • Una tabla de símbolos que se supone que almacena entradas de diferentes tipos es heterogénea. Es un mapa finito, donde el tipo de resultado depende del valor del argumento.
  •   
  • Un elemento XML se escribe de forma heterogénea. De hecho, los elementos XML son colecciones anidadas que están restringidas por expresiones regulares y la propiedad 1-ambiguity.
  •   
  • Cada fila devuelta por una consulta SQL es un mapa heterogéneo desde los nombres de las columnas hasta las celdas. El resultado de una consulta es un flujo homogéneo de filas heterogéneas.
  •   
  • Agregar un sistema de objetos avanzado a un lenguaje funcional requiere colecciones heterogéneas de un tipo que combinen registros extensibles con subtipos y una interfaz de enumeración.
  •   

Tenga en cuenta que los ejemplos que dio en su pregunta no son realmente listas heterogéneas en el sentido de que la palabra se usa comúnmente. Son listas de tipificadas débilmente o sin tipo . De hecho, en realidad son listas homogéneas , ya que todos los elementos son del mismo tipo: object o dynamic . A continuación, se le obliga a realizar conversiones o pruebas de instanceof no verificadas o algo por el estilo, para poder trabajar de manera significativa con los elementos, lo que hace que se escriban de forma débil.

    
respondido por el Jörg W Mittag 01.02.2012 - 17:18
5

Los contenedores largos y heterogéneos de larga historia intercambian el rendimiento en tiempo de ejecución por flexibilidad. Si desea tener una "lista de cosas" sin importar el tipo particular de cosas, la heterogeneidad es el camino a seguir. Los Lisps se tipifican dinámicamente de manera característica, y casi todo es una lista de valores en caja de todos modos, por lo que se espera un pequeño impacto en el rendimiento. En el mundo Lisp, la productividad del programador se considera más importante que el rendimiento en tiempo de ejecución.

En un lenguaje tipificado dinámicamente, los contenedores homogéneos en realidad tendrían una pequeña sobrecarga en comparación con los heterogéneos, porque todos los elementos agregados deberían ser revisados por el tipo.

Su intuición sobre la elección de una mejor estructura de datos está en el punto. En términos generales, cuantos más contratos pueda establecer en su código, más sepa sobre cómo funciona y más confiables, mantenibles, y amp; c. se vuelve. Sin embargo, a veces realmente quiere un contenedor heterogéneo, y debería tener uno si lo necesita.

    
respondido por el Jon Purdy 01.02.2012 - 15:39
2

En los lenguajes funcionales (como lisp), utiliza la coincidencia de patrones para determinar qué sucede con un elemento en particular en una lista. El equivalente en C # sería una cadena de sentencias if ... elseif que verifican el tipo de un elemento y realizan una operación basada en eso. No hace falta decir que la comparación de patrones funcionales es más eficiente que la verificación de tipos en tiempo de ejecución.

Usar polimorfismo sería una coincidencia más cercana a la coincidencia de patrones. Es decir, hacer que los objetos de una lista coincidan con una interfaz particular y llamar a una función en esa interfaz para cada objeto. Otra alternativa sería proporcionar una serie de métodos sobrecargados que toman un tipo de objeto específico como parámetro. El método predeterminado que toma Objeto como su parámetro.

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

Este enfoque proporciona una aproximación a la coincidencia de patrones Lisp. El patrón de visitantes (como se implementó aquí, es un gran ejemplo de uso para listas heterogéneas). Otro ejemplo sería para el envío de mensajes en el que hay escuchas para ciertos mensajes en una cola de prioridad y mediante el uso de la cadena de responsabilidad, el distribuidor pasa el mensaje y el primer controlador que coincide con el mensaje lo maneja.

La otra cara es notificar a todas las personas que se registran para recibir un mensaje (por ejemplo, el patrón de agregador de eventos que se usa comúnmente para el acoplamiento suelto de modelos de vista en el patrón MVVM). Yo uso el siguiente constructo

IDictionary<Type, List<Object>>

La única forma de agregar al diccionario es una función

Register<T>(Action<T> handler)

(y el objeto es en realidad una WeakReference a la que se pasa en el controlador). Así que aquí TENGO que usar List < Object > porque en el momento de la compilación, no sé cuál será el tipo cerrado. Sin embargo, en Runtime puedo hacer cumplir que ese tipo será la clave para el diccionario. Cuando quiero disparar el evento que llamo

Send<T>(T message)

y de nuevo resuelvo la lista. No hay ninguna ventaja al usar List < dynamic > Porque necesito lanzarlo de todos modos. Entonces, como ven, hay méritos para ambos enfoques Si va a enviar dinámicamente un objeto utilizando la sobrecarga de métodos, dinámico es la forma de hacerlo. Si está FORZADO a emitir independientemente, también puede usar Objeto.

    
respondido por el Michael Brown 01.02.2012 - 15:52
0

Usted tiene razón al afirmar que la heterogeneidad conlleva una sobrecarga de tiempo de ejecución, pero lo que es más importante, debilita las garantías de tiempo de compilación proporcionadas por el typechecker. Aun así, hay algunos problemas en los que las alternativas son aún más costosas.

En mi experiencia, lidiar con bytes en bruto a través de archivos, sockets de red, etc., a menudo te encuentras con estos problemas.

Para dar un ejemplo real, considere un sistema para el cálculo distribuido utilizando futuros . Un trabajador en un nodo individual puede generar trabajo de cualquier tipo serializable, dando como resultado un futuro de ese tipo. Detrás de escena, el sistema envía el trabajo a un compañero y luego guarda un registro que asocia esa unidad de trabajo con el futuro particular que debe completarse una vez que la respuesta a ese trabajo vuelve.

¿Dónde se pueden guardar estos registros? Intuitivamente, lo que desea es algo así como un Dictionary<WorkId, Future<TValue>> , pero esto le limita a administrar solo un tipo de futuros en todo el sistema. El tipo más adecuado es Dictionary<WorkId, Future<dynamic>> , ya que el trabajador puede convertir al tipo apropiado cuando obliga al futuro.

Nota : este ejemplo proviene del mundo de Haskell en el que no tenemos subtipos. No me sorprendería si hubiera una solución más idiomática para este ejemplo en particular en C #, pero espero que todavía sea ilustrativo.

    
respondido por el Adam 01.02.2012 - 16:40
0

ISTR indica que Lisp no tiene ninguna estructura de datos que no sea una lista, por lo que si necesita cualquier tipo de objeto de datos agregados, tendrá para ser una lista heterogénea. Como han señalado otros, también son útiles para serializar datos para transmisión o almacenamiento. Una buena característica es que también son abiertos, por lo que puede usarlos en un sistema basado en una analogía de tuberías y filtros y hacer que los pasos de procesamiento sucesivos aumenten o corrijan los datos sin requerir un objeto de datos fijo ni una topología de flujo de trabajo .

    
respondido por el TMN 01.02.2012 - 20:31

Lea otras preguntas en las etiquetas