Come posso ordinare le matrici in una raccolta?

Question

Ho una lista di oggetti. Questi oggetti hanno (tra gli altri) un array int privato (se aiuta, posso trasferirlo in una lista). C'è un Getter pubblico per questa matrice. Tutti gli array hanno le stesse dimensioni.

voglio ordinare l'oggetto in base alle loro array come questo:

Unsorted: 
{[0, 1, 4, 5], 
[0, 0, 2, 3], 
[0, 1, 1, 2]} 

Sorted: 
{[0, 0, 2, 3], 
[0, 1, 1, 2], 
[0, 1, 4, 5]} 

In parole (si chiama lessicografico):

• confrontare il primo int di ciascun array
• se sono uguali, confronta il prossimo int di ciascun array (e così via)
• se non sono uguali il risultato del confronto è il risultato finale.

Sono riuscito a cercarli per es. solo il primo elemento dell'array con un normale comparatore ma non so come cercarli tutti.

Answer 1

una bella soluzione Java 8 è

static final Comparator<CustomObject> COMPARATOR = (o1, o2) -> { 
    int[] arr1 = o1.getArray(); 
    int[] arr2 = o2.getArray(); 
    return IntStream.range(0, arr1.length) 
        .map(i -> Integer.compare(arr1[i], arr2[i])) 
        .filter(i -> i != 0) 
        .findFirst() 
        .orElse(0); 
}; 

Poi, dato un List<CustomObject>, si può fare

list.sort(COMPARATOR); 

(L'Comparator funziona solo per le matrici della stessa lunghezza. Si consiglia di modificare le esso).

Answer 2

Ho una collezione (preferibile una sorta di lista) di oggetti [...] Ora voglio per ordinare l'oggetto in base alle loro Array

Per essere significativo a tutti , lo Collection in questione deve essere uno che conserva l'ordine e consente di riordinare gli elementi. In termini di interfacce Collezioni di alto livello, solo List ha le proprietà richieste, quindi supponiamo che il tuo Collection sia, in effetti, un List.

Il metodo standard per ordinare uno List consiste nell'utilizzare uno dei due metodi Collections.sort(). Uno richiede gli elementi dell'elenco per implementare Comparable e l'altro, più generale, richiede di fornire un oggetto che implementa Comparator per l'utilizzo nel determinare l'ordine relativo desiderato degli oggetti.

Gli array non implementano Comparable (che equivale a dire che non hanno "ordine naturale"), ma la classe degli oggetti che li contengono potrebbe essere creata per farlo. È probabilmente una forma migliore, tuttavia, scrivere una classe separata Comparator che implementa l'ordine desiderato e utilizzare un'istanza di tale classe.

Answer 3

Se sto capendo correttamente, seguendo approccio diretto dovrebbe funzionare:

public class SortArrays { 

    public static void main(String[] args) { 
     List<int[]> listOfArrays = new ArrayList<>(4); 
     listOfArrays.add(new int[]{0, 1, 4, 5}); 
     listOfArrays.add(new int[]{0, 0, 2, 3}); 
     listOfArrays.add(new int[]{0, 1, 1, 2}); 
     Collections.sort(listOfArrays, (o1, o2) -> { 
      for (int i = 0; i < o1.length; i++) { 
       if (o1[i] < o2[i]) 
        return -1; 
       if (o1[i] > o2[i]) 
        return 1; 
      } 
      return 0; 
     }); 
     listOfArrays.forEach(a -> System.out.println(Arrays.toString(a))); 
    } 
} 

Produce:

[0, 0, 2, 3] 
[0, 1, 1, 2] 
[0, 1, 4, 5] 

ed è quello che ti sembra di aspettare.

Answer 4

Supponiamo che la tua classe assomigli a questo e che non puoi modificarla.

final class MyClass 
{ 
    private final int[] key; 

    MyClass(int[] key) 
    { 
    this.key = key.clone(); 
    } 

    public int[] getKey() 
    { 
    return key.clone(); 
    } 
} 

Quindi, è possibile definire un ordinamento per le istanze di MyClass implementando l'interfaccia Comparator. Per essere più generale, sto andando a implementare un comparatore per int[]:

final class IntArrayComparator 
    implements Comparator<int[]> 
{ 

    @Override 
    public int compare(int[] a, int[] b) 
    { 
    int n = Math.min(a.length, b.length); 
    for (int idx = 0; idx < n; ++idx) { 
     if (a[idx] != b[idx]) 
     return (a[idx] < b[idx]) ? -1 : +1; 
    } 
    return a.length - b.length; 
    } 
} 

Dato questo nuovo confronto, e il tipo esistente, è facile da risolvere:

final class Test 
{ 
    public static void main(String... arg) 
    { 
    /* Create your list somehow... */ 
    List<MyClass> list = new ArrayList<>(); 
    list.add(new MyClass(new int[]{0, 1, 4, 5})); 
    list.add(new MyClass(new int[]{0, 0, 2, 3})); 
    list.add(new MyClass(new int[]{0, 1, 1, 2})); 

    /* Now sort the list. */ 
    list.sort(Comparator.comparing(MyClass::getKey, new IntArrayComparator())); 

    /* Display the result... */ 
    list.stream().map(MyClass::getKey).map(Arrays::toString).forEach(System.out::println); 
    } 
} 

si dovrebbe ottenere il uscita:

 
[0, 0, 2, 3] 
[0, 1, 1, 2] 
[0, 1, 4, 5] 

Il metodo comparing() fabbrica sto usando prende due argomenti: un Function a "estrarre" una chiave di ogni oggetto in l'elenco e un Comparator in grado di confrontare le chiavi estratte. Se la chiave estratta ha un ordinamento naturale e implementa Comparable (ad esempio, è un String), non è necessario specificare uno Comparator.

In alternativa, se è possibile modificare MyClass, si potrebbe dare un ordine naturale implementando Comparable e spostando il confronto int[] al suo metodo compareTo(), come mostrato in altre risposte. Quindi è possibile utilizzare il metodo sort() senza argomenti.

Answer 5

Considerate questo oggetto:

public class Foo { 

    private int[] values; 

    public Foo(int[] values) { 
     this.values = values; 
    } 
} 

di fare una lista di oggetti:

ArrayList<Foo> foos = new ArrayList<>(); 
foos.add(new Foo(new int[] {0, 1, 4, 5})); 
foos.add(new Foo(new int[] {0, 0, 2, 3})); 
foos.add(new Foo(new int[] {0, 1, 1, 2})); 

Ora vogliamo ordinare la nostra lista di oggetti, quindi la prima cosa che dovremmo fare è rendere il nostro oggetto attuare Comparable. Si consiglia di leggere più what the Comparable interface is e how to implement it.

public class Foo implements Comparable<Foo> { 
    ... 
} 

A questo punto il compilatore si lamenterà di non aver implementato tutti i metodi richiesti dall'interfaccia. Quindi fallo.

public class Foo implements Comparable<Foo> { 
    ... 
    public int compareTo(Foo f) { 
     // Return a negative integer if this < f 
     // Return zero if this == f 
     // Return a positive integer if this > f 
    } 
} 

Per quanto riguarda la logica di confronto reale va, la tua domanda non è molto specifica circa le regole esatte che si utilizza per confrontare due oggetti. Tuttavia, dall'esempio, posso indovinare che queste sono le tue regole:

• Confrontare il primo numero di ogni matrice.
  • Se sono uguali, ripetere questa procedura utilizzando il numero successivo di ciascun array.
  • In caso contrario, il risultato di questo confronto è il risultato finale.

In realtà non si specifica cosa fare se un array è più corta dell'altra. Lascerò a scrivere l'algoritmo attuale (sebbene altre risposte sembrino averlo fatto per te).Tuttavia, sottolineerò che poiché i valori sono campi privati, non sarà possibile utilizzare quel campo per il confronto a meno che non si implementi un getter per il campo o lo rendano pubblico.

public int[] getValues() { return values; } 

Answer 6

Se l'array è private e vi si vuole fornire un metodo di accesso quindi implementare Comparable per la classe e fare qualcosa di simile sotto il codice.

Se si dispone di un metodo di accesso, eseguire questa operazione in un Comparator.

Questo codice does not assume arrays to be of same size funziona quindi con array di dimensioni diverse. Si prega di cambiare in base alle proprie esigenze.

PS - non compilato/testato

public int compareTo(Object o) { 
     CustomClass other = (CustomClass) o; 

     int i = 0; 
     while (i <= numbers.length && i <= other.numbers.length) { 
      if (numbers[i] < other.numbers[i]) 
       return -1; 
      else if (numbers[i] > other.numbers[i]) 
       return 1; 
      ++i; 
     } 

     if (numbers.length < other.numbers.length) 
      return -1; 
     else if (numbers.length > other.numbers.length) 
      return 1; 

     return 0; 
    } 

Answer 7

Per ordinare un elenco di array di int, si desidera una funzione che esegue un lessicografica confronto di un array di int. Questo è solitamente espresso come Comparator<int[]> in Java. Il modo usuale per implementare tale funzione è confrontare i valori corrispondenti da sinistra a destra fino a trovare una discrepanza; quella discrepanza determina l'ordine. Se viene raggiunta la fine di un array senza trovare una discrepanza, l'array più corto viene generalmente considerato inferiore a quello più lungo. Se le lunghezze sono uguali e tutti i valori sono uguali, gli array sono considerati uguali.

altre risposte hanno usato classi interne anonime o lambda per questa funzione, ma per cose come questa io preferisco un metodo ordinario che ha la "forma" a destra, cioè, che prende due int[] argomenti e restituisce un int che è il risultato del confronto. Ciò consente di utilizzarlo come destinazione di un riferimento al metodo.

int arrayCompare(int[] a, int[] b) { 
    int len = Math.min(a.length, b.length); 
    for (int i = 0; i < len; i++) { 
     int c = Integer.compare(a[i], b[i]); 
     if (c != 0) { 
      return c; 
     } 
    } 
    return a.length - b.length; 
} 

attenzione all'uso di Integer.compare() invece di sottrazione, evitando potenziali problemi con troppopieno. Utilizzo potrebbe essere la seguente:

List<int[]> arrays = Arrays.asList(
     new int[] { 0, 1, 4, 5 }, 
     new int[] { 0, 0, 2, 3 }, 
     new int[] { 0, 1, 1, 2 } 
    ); 

    arrays.sort(this::arrayCompare); 
    arrays.forEach(a -> System.out.println(Arrays.toString(a))); 

In JDK 9, sono state aggiunte funzioni di confronto di matrice lessicografico alla classe Arrays. Vedi Arrays.compare(int[], int[]). Esistono anche sovraccarichi per gli altri tipi primitivi e per i tipi di riferimento. Il int[] sovraccarico sostituisce la funzione arrayCompare ho scritto sopra, in modo da poter riscrivere la chiamata sorta come segue:

arrays.sort(Arrays::compare); 

Il vantaggio delle funzioni di confronto nella classe Arrays è che possono essere gestite appositamente dalla JVM, che può, ad esempio, utilizzare le istruzioni vettoriali per accelerare i confronti dell'array.

Per il vostro problema specifico, sembra che non si dispone di un elenco di int[], ma si dispone di un elenco di oggetti di tipo MyObject che hanno un int[] che si desidera utilizzare come chiave di ordinamento. Supponiamo che il modo per ottenere l'array sia chiamando il metodo getArray(). È possibile ordinare la lista come segue:

myObjects.sort(Comparator.comparing(MyObject::getArray, Arrays::compare));