comportamiento asintótico de métodos Scala

Question

¿Hay algún sitio donde pueda averiguar la esperada tiempo y espacio complejidades de las operaciones en colecciones como HashSet, TreeSet, lista y así sucesivamente?

¿Se espera que uno sepa esto de las propiedades de los abstract-data-types mismos?

Sé de Performance characteristics for Scala collections, pero esto solo menciona algunas operaciones muy básicas. Tal vez el resto de las operaciones para estas colecciones se generen únicamente a partir de un pequeño conjunto básico, pero luego, parece que solo se espera que sepa que las han implementado de esta manera.

Answer 1

Las características de rendimiento de los otros métodos es realmente difícil de afirmar.Considere lo siguiente:

• Todos estos métodos se implementan en base a foreach o iterator, y por lo general a niveles muy altos en la jerarquía. Vector 's map se implementa en collection.TraversableLike, por ejemplo. Para colmo de males, qué implementación de método se utiliza depende de la linealización de la herencia de clase. Esto también se aplica a cualquier método llamado como ayudante. Ha sucedido antes de que los cambios aquí causen problemas imprevistos de rendimiento. Dado que foreach y iterator son ambos O(n), cualquier rendimiento mejorado depende de la especialización en otros métodos, como size y slice.
• Para muchos de ellos, existe una mayor dependencia de las características de rendimiento del generador que se proporcionó, que depende del sitio de llamadas en lugar del sitio de definición.

El resultado es que el lugar donde se define y documenta el método no tiene información suficiente para establecer sus características de rendimiento y puede depender no solo de cómo otros métodos son implementados por la herencia colección, pero incluso por las características de rendimiento de un objeto, Builder, obtenido de CanBuildFrom, que se pasa en el sitio de llamada .

En el mejor de los casos, dicha documentación se describiría en términos de otros métodos. Lo cual no significa que no valga la pena, pero no es fácil de hacer, y las tareas difíciles en los proyectos de código abierto dependen de los voluntarios, que generalmente trabajan en lo que les gusta, no en lo que se necesita.

Answer 2

La guía para los otros métodos debería ser, simplemente piense cómo debería ser una implementación eficiente.

La mayoría de otras operaciones masivas en colecciones (operaciones que procesan cada elemento de la colección) son O(n), por lo que no se mencionan allí. Ejemplos de ello son filter, map, foreach, indexOf, reverse, find ...

Métodos iteradores que regresan o arroyos como combinations y permutations son generalmente O(1).

Los métodos que implican 2 colecciones suelen ser O(max(n, m)) o O(min(n, m)). Estos son zip, zipAll, sameElements, corresponds, ...

Métodos union, diff y intersect son O(n + m).

Las variantes de clasificación son, naturalmente, O(nlogn). El groupBy es O(nlogn) en la implementación actual. El indexOfSlice utiliza el algoritmo KMP y es O(m + n), donde m y n son longitudes de las cadenas.

Métodos como +:, :+ o patch son generalmente O(n), así, a no ser que se trata de un caso específico de una colección inmutable para los que la operación en cuestión es más eficiente - por ejemplo, anteponiendo un elemento en un funcional List o agregando un elemento a Vector. Los métodos toX generalmente son O(n), ya que tienen que iterar todos los elementos y crear una nueva colección. Una excepción es toStream que construye la colección perezosamente, por lo que es O(1). Además, cada vez que X es el tipo de la colección toX, simplemente devuelve this, que es O(1).

Las implementaciones de Iterator deben tener un O(1) (amortizado) next y hasNext operaciones. La creación del iterador debe ser el peor de los casos O(logn), pero O(1) en la mayoría de los casos.