sort - list<> java example

Implementación de listas que mantiene el orden.

Question

¿Existe una implementación de List en Java que mantenga el orden basado en el Comparator proporcionado?

Algo que se puede utilizar de la siguiente manera:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

para que se inserte algo de manera que el orden en la lista se mantenga de acuerdo con cmp

(En la sugerencia de @andersoj, estoy completando mi pregunta con una solicitud más)

También quiero poder recorrer la lista en orden ordenado sin eliminar los elementos, es decir:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

debe pasar

Todas las sugerencias son bienvenidas (excepto que me diga que use Collections.sort en la lista completa sin ordenar), sin embargo, preferiría algo en java.* O eventualmente org.apache.* Ya que sería difícil introducir nuevas bibliotecas en este momento.

Nota: (ACTUALIZACIÓN 4) Me di cuenta de que las implementaciones de este tipo de lista tendrían un rendimiento inadecuado. Hay dos enfoques generales:

1. Usar estructura vinculada (tipo de) árbol B o similar
2. Utilizar matriz e inserción (con búsqueda binaria)

No 1. tiene problemas con la memoria caché de la CPU.

ACTUALIZACIÓN2: TreeSet no funciona porque usa el comparador provisto ( MyComparator ) para verificar la igualdad y, en base a ello, supone que los elementos son iguales y los excluye. Necesito ese comparador solo para ordenar, no para el filtrado de "unicidad" (ya que los elementos por su orden natural no son iguales)

ACTUALIZACIÓN3: PriorityQueue no funciona como List (ya que necesito) porque no hay manera de recorrerla en el orden en que está "ordenada", para obtener los elementos en el orden ordenado que tiene que eliminarlos de la colección.

ACTUALIZAR:

Pregunta similar:
Una buena lista ordenada para Java
Lista ordenada de la matriz en Java

Answer 1

Probablemente debería estar usando un TreeSet :

Los elementos se ordenan según su orden natural, o por un Comparador proporcionado en el momento de creación del conjunto, según el constructor que se utilice.

Ejemplo:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Tenga en cuenta que este es un conjunto , por lo que no se permiten entradas duplicadas. Esto puede o no funcionar para su caso de uso específico.

Answer 2

Respuesta a nuevo requerimiento. Veo dos potenciales:

• Haga lo que dice el JavaDoc para PriorityQueue :

  Esta clase y su iterador implementan todos los métodos opcionales de las interfaces Collection e Iterator. No se garantiza que el iterador proporcionado en el método iterator() atraviese los elementos de la cola de prioridad en ningún orden en particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()) .

  Sospecho que esto dará el mejor rendimiento teniendo en cuenta sus requisitos. Si esto no es aceptable, deberá explicar mejor lo que está tratando de lograr.

• Cree una lista que simplemente se clasifique a sí misma al agregar nuevos elementos. Esto es un dolor real ... si usó una estructura vinculada, puede hacer una clasificación de inserción eficiente, pero la localidad es mala. Si usó una estructura respaldada por una matriz, la ordenación por inserción es un dolor, pero el recorrido es mejor. Si la iteración / recorrido es poco frecuente, puede mantener el contenido de la lista sin clasificar y ordenar solo a pedido.

• Considere usar un PriorityQueue como sugerí, y en el caso de que necesite iterar en orden, escriba un iterador de envoltura:

  class PqIter implements Iterator<T>
  {
     final PriorityQueue<T> pq;
     public PqIter(PriorityQueue <T> source)
     {
       pq = new PriorityQueue(source); 
     }
  
     @Override
     public boolean hasNext()
     {
       return pq.peek() != null
     }
  
     @Override
     public T next()
     { return pq.poll(); }
  
     @Override
     public void remove()
     { throw new UnsupportedOperationException(""); }
  }

• Utilice TreeMultiSet de TreeMultiSet . Probé el siguiente código con Integer y parece hacer lo correcto.

  import com.google.common.collect.TreeMultiset;
  
  public class TreeMultiSetTest { 
    public static void main(String[] args) {
      TreeMultiset<Integer> ts = TreeMultiset.create();
      ts.add(1);  ts.add(0); ts.add(2);
      ts.add(-1); ts.add(5); ts.add(2);
  
      for (Integer i : ts) {
        System.out.println(i);
      } 
    } 
  }

La siguiente información aborda el problema de singularidad / filtrado que tenía al utilizar un SortedSet . Veo que también quieres un iterador, así que esto no funcionará.

Si lo que realmente desea es una lista ordenada, puede hacer uso de un PriorityQueue .

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Tome nota de lo que dice la documentación de la API sobre las propiedades de tiempo de varias operaciones:

Nota de implementación: esta implementación proporciona tiempo O (log (n)) para los métodos de encoing y dequeing ( offer , poll , remove() y add ); tiempo lineal para los métodos remove(Object) y contains(Object) ; y tiempo constante para los métodos de recuperación ( peek , element y size ).

También debe tener en cuenta que los iteradores producidos por PriorityQueue no se comportan como se podría esperar:

No se garantiza que el Iterator proporcionado en el método iterator() atraviese los elementos de la cola de prioridad en ningún orden en particular. Si necesita un recorrido ordenado, considere usar Arrays.sort(pq.toArray()) .

Acabo de MinMaxPriorityQueue cuenta de que Guava proporciona una MinMaxPriorityQueue . Esta implementación está respaldada por una matriz, en lugar del formulario enlazado proporcionado en el PriorityQueue del JDK, y por lo tanto es probable que tenga un comportamiento de tiempo diferente. Si estás haciendo algo sensible al rendimiento, es posible que desees echar un vistazo. Si bien las notas dan tiempos de gran O ligeramente diferentes (lineales y logarítmicas), todos esos tiempos también deben estar delimitados, lo que puede ser útil.

No hay una implementación de List per se que mantenga el orden, pero lo que probablemente está buscando son implementaciones de SortedSet . Un TreeSet es el más común. La otra implementación, un ConcurrentSkipListSet es para usos más específicos. Tenga en cuenta que SortedSet proporciona pedidos, pero no permite entradas duplicadas, como lo hace una List .

Refs:

• La entrada del blog PriorityQueue iterator no está ordenada
• Así que la pregunta en PQ ordenó iterador

Answer 3

Tengo un problema similar y estoy pensando en usar un TreeSet. Para evitar la exclusión de elementos "iguales", modificaré el comparador para que, en lugar de devolver 0, devuelva un número aleatorio entre (-1,1) o devuelva siempre 1.

Si no tiene control sobre el Comparador o si lo está utilizando para otra cosa diferente a la inserción, esta solución no funcionará para usted.