Cómo ordenar un ArrayList de dos dimensiones

Question

Tengo un ArrayList de dos dimensiones que contiene valores dobles:

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

En analogía con agrupaciones clásicas, quisiera ordenar los "cols" de esta matriz: I desea tomar los elementos que tienen el mismo índice en el sub ArrayLists, y luego ordenarlos. Como llamar a Collections.sort() para cada columna ... Por filas quiero decir que el nivel externo y el nivel interno son columnas.

¿Cuál es la forma correcta de hacerlo? Pensé en iterar sobre la matriz para invertirla y luego ordenar cada fila con Collections.sort()? pero tal vez no sea la mejor solución porque la matriz es de aproximadamente 400 * 7000.

No puedo usar matrices clásicas ya que se desconoce el tamaño de la matriz.

Gracias por la ayuda.

Answer 1

hacer algo como esto:

final int COLUMN = 5; 
    Comparator<ArrayList<Double>> myComparator = new Comparator<ArrayList<Double>>() { 
     @Override 
     public int compare(ArrayList<Double> o1, ArrayList<Double> o2) { 
      return o1.get(COLUMN).compareTo(o2.get(COLUMN)); 
     } 
    }; 
    Collections.sort(list, myComparator); 

conjunto de columnas a cualquier columna que toque lavar sucesivamente.

Actualización:

Sí, esto no funcionará en absoluto.

Me gusta la segunda sugerencia de ahanin para hacer tu propia lista que envuelve tu lista original. Debería envolver también el objeto devuelto por get() para que la variable wrappedList contenga los valores de la columna y wrappedList.get (0) también devuelva una columna de valores. Entonces la clasificación puede funcionar. Me pregunto cuáles son los métodos mínimos que debe implementar para que Collections.sort() trabaje en su Lista.

Probablemente sea más fácil simplemente tomar el quicksort de otra persona y hacerlo funcionar con su lista.

Aquí es una implementación: http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html

Answer 2

Tengo dos ideas locas: ya sea para implementar tu propio algoritmo de clasificación que sea consciente de tu estructura de matriz invertida, o escribir una implementación de Colección que envuelva tu estructura y represente la columna, que luego podría usarse como argumento para Collections.sort(). Con ArrayList esto debería ser bastante rápido.

Answer 3

Supongo que si el almacenamiento no es un problema, puede utilizar un SortedMap en su ArrayList. De esa manera, no tiene que preocuparse por ordenar los elementos.

ArrayList<SortedMap<Double,byte>> data; 

Answer 4

No estoy seguro si he entendido su Q correctamente, pero esto va a clasificar todas las "columnas" (suponiendo nivel externo son filas y nivel interno son columnas):

final ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 
    //... 

    final Integer[] rows = new Integer[data.size()]; 
    for(int i=0;i<rows.length;i++) 
     rows[i]=i; 

    int cols = data.get(0).size(); 
    for(int c=0;c<cols;c++) 
    { 
     final int colidx = c; 
     Arrays.sort(rows,new Comparator<Integer>(){ 
      @Override 
      public int compare(Integer arg0, 
        Integer arg1) { 
       return data.get(arg0).get(colidx).compareTo(data.get(arg1).get(colidx));   
      }});  

     for(int i=0;i<rows.length;i++) 
      data.get(i).add(colidx+1,data.get(rows[i]).get(colidx)); 
     for(int i=0;i<rows.length;i++) 
      data.get(i).remove(colidx); 
    } 

Answer 5

Así que aquí hay una opción que es como la idea de inversión, pero en lugar de invertir todo lo que está construyendo una columna a la vez, ordenándola y descartándola.

ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

for(int c=0; c<data.get(0).size(); c++) { 
    List<Double> col = new ArrayList<Double>(); 
    for(int r=0; r<data.size(); r++) 
     col.add(data.get(r).get(c)); 

    Collections.sort(col); 

    for(int r=0; r<col.size(); r++) 
     data.get(r).set(c, col.get(r)); 
} 

dudo que usted será capaz de conseguir algo más eficiente, además de quizás la opción de crear su propia clase que proporciona una vista de una columna de la tabla en forma de lista.

Answer 6

Deberás visitar todos los elementos para ordenarlos en cualquier caso. Entonces, ¿qué podrías hacer es esto?

int temp[] = new temp[col.length]; 
int x = 0; 
while(x < row.length) 
{ 
    for(int i = 0; i<col.length; i++) 
    { 
     temp[i] = mat[x][i]; 
    } 
    sort(temp); 
    for(int i = 0; i<col.length; i++) 
    { 
     mat[x][i] = temp[i]; 
    } 
x++; 
} 

El tiempo de ejecución en este caso sería O(n^2logn) pero ya que está ordenando a sólo 400 dobles que no llevaría mucho tiempo. y ya que usted tiene que visitar cada elemento en la matriz al menos una vez, no se puede ir por debajo de O(n^2)

Answer 7

Aquí es una aproximación a esta situación de convertir los datosen una matriz de objetos. Cambia la columna a lo que quieras.

final int column = 3; 
ArrayList<ArrayList<Double>> data = new ArrayList<ArrayList<Double>>(); 

// Convert data into an object array 
Object [] temp = data.toArray(); 

Arrays.sort(temp, new Comparator<Object>() { 
    @Override 
    public int compare(Object o1, Object o2) { 
     // Get inner arrays to be compared by type-casting 
     ArrayList<Double> temp1 = (ArrayList<Double>) o1; 
     ArrayList<Double> temp2 = (ArrayList<Double>) o2; 

     // Then compare those inner arrays' indexes 
     return temp1.get(column).compareTo(temp2.get(column)); 
    } 
}); 

// Clear the old one and add the ordered list into 
data.clear(); 

for(Object o: temp) 
{ 
    data.add((ArrayList<Double>) o); 
}