¿Cuál sería la desventaja de definir una clase como una subclase de una lista de sí misma?

48

En un proyecto mío reciente, definí una clase con el siguiente encabezado:

public class Node extends ArrayList<Node> {
    ...
}

Sin embargo, después de discutir con mi profesor de CS, declaró que la clase sería "horrible para la memoria" y "mala práctica". No he encontrado que el primero sea particularmente cierto, y el segundo sea subjetivo.

Mi razonamiento para este uso es que tuve una idea para un objeto que debía definirse como algo que podría tener una profundidad arbitraria, donde el comportamiento de una instancia podría definirse ya sea por una implementación personalizada o por el comportamiento de varios objetos similares que interactúan . Esto permitiría la abstracción de objetos cuya implementación física estaría compuesta por muchos subcomponentes que interactúan.

Por otro lado, veo cómo esto podría ser una mala práctica. La idea de definir algo como una lista de sí misma no es simple ni físicamente implementable.

¿Hay alguna razón válida por la que no debería usar esto en mi código, considerando mi uso?


¹ Si necesito explicar esto más a fondo, estaría encantado de hacerlo; Solo intento mantener esta pregunta concisa.

Addison Crump
fuente
1
Posible duplicado de patrones
mosquito
1
@gnat Esto tiene más que ver con definir estrictamente una clase como una lista de sí misma, en lugar de contener listas que contienen listas. Creo que es una variante de algo similar, pero no del todo igual. Esa pregunta se refiere a algo similar a la respuesta de Robert Harvey .
Addison Crump
16
Heredar de algo que está parametrizado por sí mismo no es inusual, como muestra el idioma CRTP comúnmente utilizado en C ++. Sin embargo, en el caso del contenedor, la pregunta clave es justificar por qué debe usar la herencia en lugar de la composición.
Christophe
1
Me gusta la idea. Después de todo, cada nodo en un árbol es un (sub) árbol. Por lo general, el árbol de un nodo se oculta de una vista de tipo (el nodo clásico no es un árbol sino un solo objeto) y en su lugar se expresa en la vista de datos (el nodo único permite el acceso a las ramas). Aquí es al revés; no veremos datos de sucursal, está en el tipo. Irónicamente, el diseño del objeto real en C ++ probablemente sería muy similar (la herencia se implementa de manera muy similar a la contención de datos), lo que me hace pensar que estamos tratando con dos formas de expresar lo mismo.
Peter - Restablece a Mónica el
1
Tal vez me falta un poco, pero ¿realmente necesita extender ArrayList<Node> , en comparación con implementar List<Node> ?
Matthias el

Respuestas:

107

Francamente, no veo la necesidad de herencia aquí. No tiene sentido Node es un ArrayList de Node?

Si esto es solo una estructura de datos recursiva, simplemente escribiría algo como:

public class Node {
    public String item;
    public List<Node> children;
}

Lo que tiene sentido; El nodo tiene una lista de hijos o nodos descendientes.

Robert Harvey
fuente
34
No es lo mismo. Una lista de una lista de una lista ad-infinitum no tiene sentido a menos que esté almacenando algo además de una nueva lista en la lista. Para eso Item está, y Itemopera independientemente de las listas.
Robert Harvey
66
Oh, ya veo ahora. Me había acercado a Node es ArrayList de Nodecomo Node contiene 0 a muchos Node objetos. Su función es la misma, esencialmente, pero en lugar de ser una lista de objetos similares, tiene una lista de objetos similares. El diseño original de la clase escrita fue la creencia de que cualquiera Nodepuede expresarse como un conjunto de sub Nodes, lo que hacen ambas implementaciones, pero este es ciertamente menos confuso. +1
Addison Crump
11
Diría que la identidad entre un nodo y una lista tiende a surgir "naturalmente" cuando escribes listas enlazadas individualmente en C o Lisp o lo que sea: en ciertos diseños el nodo principal "es" la lista, en el sentido de ser el único Lo que solía representar una lista. Por lo tanto, no puedo disipar por completo la sensación de que, en algunos contextos, tal vez un nodo "es" (no solo "tiene") una colección de nodos, aunque estoy de acuerdo en que se siente EvilBadWrong en Java.
Steve Jessop el
12
@ nl-x Que la sintaxis sea más corta no significa que sea mejor. Además, por cierto, es bastante raro acceder a elementos en un árbol como ese. Por lo general, la estructura no se conoce en el momento de la compilación, por lo que tiende a no atravesar tales árboles por valores constantes. La profundidad tampoco es fija, por lo que ni siquiera puede iterar sobre todos los valores utilizando esa sintaxis. Cuando adapta el código para usar un problema tradicional de recorrido del árbol, termina escribiendo Childrensolo una o dos veces, y generalmente es preferible escribirlo en tales casos por razones de claridad del código.
Servy
8
+1 para favorecer la composición sobre la herencia .
Menelaos Kotsollaris
57

El argumento "horrible para la memoria" es completamente erróneo, pero es objetivamente una "mala práctica". Cuando hereda de una clase, no solo hereda los campos y métodos que le interesan. En cambio, hereda todo . Cada método que declara, incluso si no es útil para usted. Y lo más importante, también hereda todos sus contratos y garantías que ofrece la clase.

El acrónimo SOLID proporciona algunas heurísticas para un buen diseño orientado a objetos. Aquí, el que Nterface Segregación Principio (ISP) y la L iskov Sustitución Pricinple (LSP) tiene algo que decir.

El ISP nos dice que mantengamos nuestras interfaces lo más pequeñas posible. Pero al heredar de ArrayList, obtienes muchos, muchos métodos. ¿Tiene algún sentido get(), remove(), set()(sustituir), o add()(insertar) un nodo hijo en un índice en particular? ¿Es sensible a ensureCapacity()la lista subyacente? ¿Qué significa para sort()un nodo? ¿Realmente se supone que los usuarios de tu clase obtienen un subList()? Como no puede ocultar los métodos que no desea, la única solución es tener ArrayList como una variable miembro y reenviar todos los métodos que realmente desee:

private final ArrayList<Node> children = new ArrayList();
public void add(Node child) { children.add(child); }
public Iterator<Node> iterator() { return children.iterator(); }

Si realmente desea todos los métodos que ve en la documentación, podemos pasar al LSP. El LSP nos dice que debemos poder usar la subclase donde se espera la clase principal. Si una función toma un ArrayListparámetro como y pasamos nuestro Nodeen su lugar, se supone que nada cambiará.

La compatibilidad de las subclases comienza con cosas simples como firmas de tipo. Cuando anula un método, no puede hacer que los tipos de parámetros sean más estrictos, ya que eso podría excluir los usos que eran legales con la clase principal. Pero eso es algo que el compilador nos busca en Java.

Pero el LSP es mucho más profundo: tenemos que mantener la compatibilidad con todo lo que promete la documentación de todas las clases e interfaces principales. En su respuesta , Lynn ha encontrado un caso en el que la Listinterfaz (que ha heredado a través de ArrayList) garantiza cómo se supone que funcionan los métodos equals()y hashCode(). Para hashCode()que se les da incluso un algoritmo particular que debe ser implementada con exactitud. Supongamos que ha escrito esto Node:

public class Node extends ArrayList<Node> {
  public final int value;

  public Node(int value, Node... children) {
    this.value = Value;
    for (Node child : children)
      add(child);
  }

  ...

}

Esto requiere que el valueno pueda contribuir al hashCode()y no pueda influir equals(). La Listinterfaz, que promete honrar heredando de ella, debe new Node(0).equals(new Node(123))ser verdadera.


Debido a que heredar de las clases hace que sea demasiado fácil romper accidentalmente una promesa que hizo una clase principal, y debido a que generalmente expone más métodos de los que pretendía, generalmente se sugiere que prefiera la composición sobre la herencia . Si debe heredar algo, se sugiere heredar solo las interfaces. Si desea reutilizar el comportamiento de una clase en particular, puede mantenerlo como un objeto separado en una variable de instancia, de esa manera no se le imponen todas sus promesas y requisitos.

A veces, nuestro lenguaje natural sugiere una relación de herencia: un automóvil es un vehículo. Una motocicleta es un vehículo. ¿Debo definir clases Cary Motorcycleque hereden de una Vehicleclase? El diseño orientado a objetos no se trata de reflejar el mundo real exactamente en nuestro código. No podemos codificar fácilmente las ricas taxonomías del mundo real en nuestro código fuente.

Un ejemplo de ello es el problema de modelado empleado-jefe. Tenemos varios correos Personelectrónicos, cada uno con un nombre y una dirección. Un Employeees un Persony tiene un Boss. A Bosses también a Person. Entonces, ¿debería crear una Personclase que sea heredada por Bossy Employee? Ahora tengo un problema: el jefe también es un empleado y tiene otro superior. Entonces parece que Bossdebería extenderse Employee. Pero el CompanyOwneres un Bosspero no es un Employee? Cualquier tipo de gráfico de herencia se descompondrá de alguna manera aquí.

OOP no se trata de jerarquías, herencia y reutilización de clases existentes, se trata de generalizar el comportamiento . OOP se trata de "Tengo un montón de objetos y quiero que hagan algo en particular, y no me importa cómo". Para eso están las interfaces . Si implementa la Iterableinterfaz para usted Nodeporque desea que sea iterable, está perfectamente bien. Si implementa la Collectioninterfaz porque desea agregar / eliminar nodos secundarios, etc., está bien. Pero heredar de otra clase porque te da todo lo que no es, o al menos no a menos que lo hayas pensado detenidamente como se describe anteriormente.

amon
fuente
10
Imprimí tus últimos 4 párrafos, los titulé Acerca de OOP y Herencia y los piné en la pared en el trabajo. Algunos de mis colegas necesitan ver que, como sé, apreciarían la forma en que lo expresas :) Gracias.
YSC
17

Extender un contenedor en sí mismo generalmente se considera una mala práctica. Realmente hay muy pocas razones para extender un contenedor en lugar de solo tener uno. Extender un contenedor de ti mismo solo lo hace extra extraño.

DeadMG
fuente
14

Además de lo que se ha dicho, hay una razón algo específica de Java para evitar este tipo de estructuras.

El contrato del equalsmétodo para listas requiere que una lista se considere igual a otro objeto

si y solo si el objeto especificado es también una lista, ambas listas tienen el mismo tamaño y todos los pares de elementos correspondientes en las dos listas son iguales .

Fuente: https://docs.oracle.com/javase/7/docs/api/java/util/List.html#equals(java.lang.Object)

Específicamente, esto significa que tener una clase diseñada como una lista de sí misma puede hacer que las comparaciones de igualdad sean costosas (y los cálculos hash también si las listas son mutables), y si la clase tiene algunos campos de instancia, estos deben ignorarse en la comparación de igualdad .

Lynn
fuente
1
Esta es una excelente razón para eliminar esto de mi código, aparte de las malas prácticas. : P
Addison Crump
3

En cuanto a la memoria:

Yo diría que esto es una cuestión de perfeccionismo. El constructor predeterminado de se ArrayListve así:

public ArrayList(int initialCapacity) {
     super();

     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

     this.elementData = new Object[initialCapacity];
 }

public ArrayList() {
     this(10);
}

Fuente . Este constructor también se usa en Oracle-JDK.

Ahora considere construir una Lista enlazada individualmente con su código. Acaba de aumentar con éxito su consumo de memoria por el factor 10x (para ser precisos, incluso marginalmente más alto). Para los árboles, esto también puede ser bastante malo sin requisitos especiales en la estructura del árbol. Usar una LinkedListu otra clase alternativamente debería resolver este problema.

Para ser sincero, en la mayoría de los casos esto no es más que un mero perfeccionismo, incluso si ignoramos la cantidad de memoria disponible. A LinkedListralentizaría un poco el código como alternativa, por lo que es una compensación entre el rendimiento y el consumo de memoria de cualquier manera. Aún así, mi opinión personal sobre esto sería no desperdiciar tanta memoria de una manera que se pueda eludir tan fácilmente como esta.

EDITAR: aclaración sobre los comentarios (@amon para ser precisos). Esta sección de la respuesta no trata el tema de la herencia. La comparación del uso de la memoria se realiza con una Lista vinculada individualmente y con el mejor uso de la memoria (en implementaciones reales, el factor puede cambiar un poco, pero aún es lo suficientemente grande como para sumar un poco de memoria desperdiciada).

En cuanto a "Mala práctica":

Seguro. Esta no es la forma estándar de implementar un gráfico por una simple razón: un nodo de gráfico tiene nodos secundarios, no es como una lista de nodos secundarios. Expresar con precisión lo que quieres decir en código es una habilidad importante. Ya sea en nombres de variables o estructuras de expresión como esta. Siguiente punto: mantener las interfaces mínimas: ha hecho que todos los métodos ArrayListestén disponibles para el usuario de la clase a través de la herencia. No hay forma de alterar esto sin romper toda la estructura del código. En su lugar, almacene la Listvariable interna y ponga a disposición los métodos necesarios a través de un método adaptador. De esta manera, puede agregar y eliminar fácilmente la funcionalidad de la clase sin estropear todo.

Pablo
fuente
1
10 veces más alto en comparación con qué ? Si tengo un ArrayList construido por defecto como un campo de instancia (en lugar de heredar de él), en realidad estoy usando un poco más de memoria, ya que necesito almacenar un puntero a ArrayList adicional en mi objeto. Incluso si estamos comparando manzanas con naranjas y comparamos la herencia de ArrayList con no usar ninguna ArrayList, tenga en cuenta que en Java siempre tratamos con punteros a objetos, nunca objetos por valor como lo haría C ++. Suponiendo que new Object[0]usa 4 palabras en total, a new Object[10]solo usaría 14 palabras de memoria.
amon
@amon No lo he declarado explícitamente, sry por eso. Aunque el contexto debería ser suficiente para ver que me estoy comparando con una LinkedList. Y se llama referencia, no puntero por cierto. Y el punto con la memoria no era acerca de si la clase se usaba por herencia o no, sino simplemente el hecho de que (casi) los no utilizados ArrayListestán eliminando bastante memoria.
Paul
-2

Esto parece parecerse a la semántica del patrón compuesto . Se utiliza para modelar estructuras de datos recursivas.

oopexpert
fuente
13
No rechazaré esto, pero es por eso que realmente odio el libro de GoF. ¡Es un árbol sangrante! ¿Por qué necesitamos inventar el término "patrón compuesto" para describir un árbol?
David Arno
3
@DavidArno Creo que es todo el aspecto del nodo polimórfico lo que lo define como "patrón compuesto", el uso de una estructura de datos de árbol es solo parte de él.
JAB
2
@RobertHarvey, no estoy de acuerdo (con sus comentarios a su respuesta y aquí). public class Node extends ArrayList<Node> { public string Item; }es la versión de herencia de tu respuesta. El suyo es más sencillo de razonar, pero ambos logran algo: definen árboles no binarios.
David Arno
2
@DavidArno: Nunca dije que no funcionaría, solo dije que probablemente no sea lo ideal.
Robert Harvey
1
@DavidArno no se trata de sentimientos y gustos aquí, sino de hechos. Un árbol está hecho de nodos y cada nodo tiene hijos potenciales. Un nodo dado es un nodo hoja solo en un momento dado en el tiempo. En un compuesto, un nodo hoja es hoja por construcción, y su naturaleza no cambiará.
Christophe