L'ordinamento da parte di un comparatore non transitivo "funziona"?

Cosa succederà se fornisco un transitivo non transitabile Comparator a Collections.sort? Posso correre in loop infinito?L'ordinamento da parte di un comparatore non transitivo "funziona"?

Un piccolo test che ho scritto ha prodotto un'uscita, ma voglio essere sicuro che sia sempre così.

Il problema è che in alcuni casi, il mio comparatore può produrre cicli, e in questo caso voglio solo assicurarmi che non giri in loop infinito. Non mi interessa il risultato reale.

fonte

2011-10-31 duduamar

Magari postare qualche codice rilevante? – pap

Questa è una domanda generale, non rilevante per un codice specifico - la domanda è qual è il comportamento se fornisco un comparatore che non è transitivo a Collections.sort – duduamar

Il comportamento dell'utilizzo di un 'comparatore 'non transitivo' non è definito, come 'Comparator' non transitivo ** non è correttamente implementato **. In pratica, sono * abbastanza * sicuro che 'Collections.sort()' non * eseguirà * in un ciclo infinito, anche se il 'Comparator' è rotto. Ma nulla nelle specifiche * richiede * questo comportamento. –

Il Java docs afferma che è necessario assicurarsi che il proprio comparatore sia transitivo. Se fornisci un comparatore che non rispetta ciò che è stato richiesto, tutte le scommesse sono disattivate. Potrebbe funzionare per una determinata implementazione ma potrebbe bloccarsi in modo anomalo (std::sort in C++) in un'altra.

In breve, non si deve fare affidamento sul fatto che funzioni anche se lo fa per alcuni o altri esempi.

fonte

2011-10-31 08:24:51 Pablo

Sì ... ha senso. Non dovrei fare affidamento su questo, grazie. – duduamar

Ciao Pablo.Mi dispiace dirottare un commento, ma ho posto una domanda qui: https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators Tu apparentemente hanno affrontato il problema che sto affrontando oggi, dove C++ std :: sort si blocca con un comparatore non transitivo. Mi stavo chiedendo se tu sapessi perché? Ancora una volta, mi dispiace di dirottare un commento di 6 anni, ma su questo argomento esistono pochissimi dati. –

Il Collections.sort() è basato su un mergesort.

un mergesort ha un'iterazione O (logn) nel complesso, poiché la dimensione dell'array è SEMPRE divisa, quindi l'ordinamento() dovrebbe terminare, indipendentemente dal fatto che il comparatore non sia transitivo, quindi il ciclo infinito non si verificherà.

Tuttavia, non ci sono garanzie sull'ordine dell'elenco risultante.

fonte

2011-10-31 08:29:43 amit

Questo è un buon commento, ma l'implementazione potrebbe essere modificata senza preavviso ... – duduamar

Sì. È cambiato in Java 7. – vz0

Il comportamento di Collections.sort in questo caso dipende dall'implementazione. L'implementazione di Java 6 SE utilizza una combinazione di Mergesort e Insertionsort che sono entrambi deterministici con i comparatori non transitivi ma in Java 7 viene utilizzato l'algoritmo di Timsort e altre implementazioni potrebbero utilizzare Quicksort o qualcos'altro, quindi non si può essere sicuri che lavorare con tutte le implementazioni.

fonte

2011-10-31 08:30:08 x4u

Prima di tutto, ti suggerisco di pensare al confronto: l'operazione di compassione è davvero la relazione di equivalenza . Se si accetta che non lo sia e che deve essere: traccia gli oggetti confrontati in alcune variabili locali. Questa variabile locale può essere oggetto di confronto o variabile locale del thread. Questa variabile può essere l'insieme di coppie di oggetti confrontate. Dentro confrontare il controllo di chiamata del metodo se questa coppia è stata visitata - se è vera, decidere cosa fare. Ma prendi la macchina su Set di oggetti visitati - dovrebbe contenere davvero qualcosa come hash o id oggetto, perché puoi andare all'infinito in altro modo. E anche prendere in considerazione che l'archiviazione della coppia confrontata nella variabile locale richiede memoria.

fonte

2011-10-31 08:30:12 Max

Poiché Java 7 Collections.sort utilizza TimSort. L'utilizzo di un comparatore non transitivo per l'ordinamento in Java> = 7 genererà la seguente eccezione:

java.lang.IllegalArgumentException: Comparison method violates its general contract!

fonte

2014-12-04 13:50:50 Martin

L'ordinamento da parte di un comparatore non transitivo "funziona"?

risposta

Problemi correlati