Karşılaştırılabilir Vs TreeSet ile Liste

Question

Seçenek 1: Karşılaştırma uygulayan bir liste oluşturun ve bir değer eklediğinizde collections.sort (Liste l) kullanarak bir sıralama yapın. Seçenek 2: Bir TreeSet yapın (her zaman kendini sıralı tutar).

Hangisi daha hızlı olacak? Bunu soruyorum, çünkü Listemde bir öğe ekleyebilmem için bana ihtiyacım olan ListIterator seçeneği veriyor.

Answer 1

en önemli farklar:

Criterion  | List with Collections.sort | TreeSet 
----------------+----------------------------+--------- 
cost of adding | O(n log n)     | O(log n) 
equal sort keys | permitted     | eliminated as duplicates 
iteration  | bidirectional, can insert | unidirectional, can not insert 

bir ConcurrentModificationException almadan yineleme zaman bir öğe eklemek için, bunu yapabilirsiniz:

for (E e : new ArrayList<E>(collection)) { 
    // some other code 

    collection.add(anotherE); 
} 

Answer 2

TreeSet'i buradan kullanın.

TreeSet'e eklenmesi, bir log(n) işlemidir. Listeye eklemek const time, ancak sıralama n log(n).

Answer 3

Collections.sort nlog ile değiştirilmiş birleştirme-tür kullanır (n) sıralama zamanı. Her ekleme yöntemini çağırırsanız, n^2log (n) saati ile sonlanabilir. TreeSet'e ekleme işlemi garanti edilir (n). Yani eğer her ekleme için çağırırsanız n.log (n) olur. Bu yüzden TreeSet'i kullanmayı öneriyorum. Ancak TreeSet kopyalarına izin vermez, bu nedenle kararınızı etkileyebilir.

Listeyi kullanıyorsanız, Collections.sort'u kullanmak yerine, optimize etmek için yapabileceğiniz bir şey var; Öğeyi listeye her eklediğinizde, listenin zaten sıralı olduğunu biliyorsunuz, bu nedenle ekleme sıralamalarını kullanmak, bu tür durumlarda ekleme sıralamalarının daha iyi performans göstermesi nedeniyle size daha iyi bir performans sunacaktır.