Cách nhanh nhất để sắp xếp một danh sách trong Java

Question

Tôi có đoạn code sau trong Java:

public class ServerInfo { 
    int serverId; 
    int serverDataRate; 
    public ServerInfo(int serverId, int serverDataRate) { 
     this.serverId = serverId; 
     this.serverDataRate = serverDataRate; 
    } 
    public int getServerId() { 
     return serverId; 
    } 
    public double getServerDataRate() { 
     return serverDataRate; 
    } 
     public String toString(){ 
      return serverId + ":" + serverDataRate; 
     } 
    }  

    public class ServerInfoComparator implements Comparator<ServerInfo> { 

    @Override 
    public int compare(ServerInfo o1, ServerInfo o2) { 
      double datarate1=o1.getServerDataRate(); 
      double datarate2=o2.getServerDataRate(); 

      if(datarate1>datarate2) 
       return -1; 
      else if(datarate1<datarate2) 
       return +1; 
      else 
       return 0; 
    }   
} 

    public class Sample { 
    List<ServerInfo> listOfServers= new ArrayList<ServerInfo>(); 

    public void insertIntoList(){ 

     listOfServers.add(new ServerInfo(0,256)); 
     listOfServers.add(new ServerInfo(1,270)); 
     listOfServers.add(new ServerInfo(2,256)); 
     listOfServers.add(new ServerInfo(3,290)); 
     listOfServers.add(new ServerInfo(4,300)); 
     listOfServers.add(new ServerInfo(5,300)); 
     listOfServers.add(new ServerInfo(6,256)); 
     listOfServers.add(new ServerInfo(7,265)); 
     listOfServers.add(new ServerInfo(8,289)); 
     listOfServers.add(new ServerInfo(9,310)); 
    } 

    public static void main(String[] args){ 
     Sample s = new Sample(); 
     s.insertIntoList(); 
     ServerInfoComparator com = new ServerInfoComparator(); 
     Collections.sort(s.listOfServers,com); 

     for(ServerInfo server: s.listOfServers){ 
      System.out.println(server); 
     }   
    } 
} 

Tôi đang sử dụng đoạn mã trên để sắp xếp các yếu tố theo thứ tự dựa trên serverDataRate giảm dần. Ở đây, bộ mẫu khá nhỏ giả sử tôi có một bộ mẫu lớn hơn gồm 100 phần tử trong danh sách và mã phải được thực thi sau mỗi 5-10 giây. Đây có phải là cách nhanh nhất để sắp xếp danh sách hoặc có phương pháp nhanh hơn mà tôi không biết?

Answer 1

tôi đã thay đổi thử nghiệm của bạn

private final List<ServerInfo> listOfServers = new ArrayList<ServerInfo>(); 

public void insertIntoList() { 
    for (int i = 0; i < 1000000; i++) 
     listOfServers.add(new ServerInfo(i, (int) (200 + Math.random() * 200))); 
} 

public static void main(String[] args) { 
    MyApp s = new MyApp(); 
    s.insertIntoList(); 
    ServerInfoComparator com = new ServerInfoComparator(); 
    long start = System.nanoTime(); 
    Collections.sort(s.listOfServers, com); 
    long time = System.nanoTime() - start; 
    System.out.printf("Sorting %,d took %.3f seconds%n", s.listOfServers.size(), time/1e9); 

    for (ServerInfo server : s.listOfServers) { 
// System.out.println(server); 
    } 
} 

và nó in

Sorting 1,000,000 took 0.438 seconds 

Đó là nhanh hơn một chút;)

BTW: Tôi đã thay đổi double lĩnh vực được int.

Answer 2

Điều này không bình thường. Kiểm tra cách của bạn thời gian nó.

long start = System.nanoTime(); 

// Sort here 

long time = System.nanoTime() - start; 
System.out.println(time/1000000L + " Milliseconds"); 

Answer 3

100 phần tử không phải là tập hợp lớn trừ khi bước so sánh của bạn thực sự nặng (dường như không). 100 yếu tố sẽ được sắp xếp cực kỳ nhanh chóng trong bất kỳ máy hơi hiện đại nào.

Điều đó đang được nói, tôi nghĩ rằng cách tiếp cận của bạn khá gần với tiêu chuẩn và tôi sẽ không lo lắng về việc cố gắng tối ưu hóa nó trừ khi bạn thực sự cần đến nó.

Tối ưu hóa ban đầu là cha đẻ của nhiều vụ bắt vít (giả định là mẹ).

Answer 4

Bạn có thể sử dụng cấu trúc dữ liệu để thực hiện sắp xếp theo cách nhanh hơn.

BST (Cây tìm kiếm nhị phân) hoặc TRIE sẽ giúp bạn sắp xếp dữ liệu lớn theo cách nhanh hơn.

Chúng sẽ yêu cầu mã có độ dài một chút, nhưng sẽ giúp bạn trong quá trình chạy nhật ký nếu tập dữ liệu lớn.

Answer 5

Do bạn không sắp xếp thường xuyên nên tốc độ không phải là vấn đề. Ngay cả với hàng ngàn mục, Collections.sort rất nhanh.

Bạn đã thử ứng dụng của mình để xem tốc độ có phải là vấn đề không? Tối ưu hóa sớm không phải là một ý tưởng tốt :)

Hãy cảnh giác với một điều về mã của bạn: trừ khi bạn đảm bảo rằng dataRates của tất cả các máy chủ không thay đổi trong quá trình sắp xếp, bạn có thể nhận được kết quả không phù hợp! Bạn nên đồng bộ hóa các phương thức của mình để datarates không thay đổi cho đến khi toàn bộ danh sách được sắp xếp.

Answer 6

Bạn không cần phải sử dụng các cuộc gọi phương thức trong lớp, ngay cả khi trường là riêng tư mà không phải lúc nào cũng được biết - riêng tư hạn chế quyền truy cập vào một lớp, không phải đối tượng.

Kể từ khi phương pháp của bạn không làm gì nhưng trả lại thuộc tính, bạn có thể sử dụng thuộc tính trực tiếp:

@Override 
public int compare(ServerInfo o1, ServerInfo o2) { 
/* 
     double datarate1=o1.getServerDataRate(); 
     double datarate2=o2.getServerDataRate(); 
*/ 
     double datarate1=o1.serverDataRate; 
     double datarate2=o2.serverDataRate; 

     if (datarate1 > datarate2) 
      return -1; 
     else if (datarate1 < datarate2) 
      return +1; 
     else 
      return 0; 
}   

Nhưng JVM có thể tối ưu hóa các cuộc gọi chức năng, và trong khoảng 100 yếu tố, nó sẽ khó có thể đo lường được .

Phương pháp của bạn trả về gấp đôi - bạn có thể giải thích lý do không?

Với ints, bạn chỉ có thể làm:

@Override 
public int compare (ServerInfo o1, ServerInfo o2) { 
     return o2.serverDataRate - o1.serverDataRate; 
}   

Nhưng xét các giá trị extremest có thể cho câu hỏi của int quá mức và ngầm.

Answer 7

Đầu tiên, loại biến serverDataRate của bạn là int. Nhưng kiểu trả về của phương thức getter là gấp đôi. Khi bộ so sánh hoạt động, tất cả phương thức getServerDataRate sẽ chuyển đổi trường thành định dạng dữ liệu londer. Nếu phương thức getter của bạn trả về kiểu giống như kiểu trường thì thời gian so sánh sẽ ngắn hơn. Thứ hai, Không cần sử dụng if(), trong phương pháp so sánh nếu nhiệm vụ của bạn hoạt động đơn giản. Chỉ cần sử dụng phép trừ. Như thế này:

the getter: 
    public int getServerDataRate() { 
     return serverDataRate; 
    } 

in comparator: 
return o1.getServerDataRate()-o2.getServerDataRate(); // from smallest to largest value 
or 
return o2.getServerDataRate()-o1.getServerDataRate(); // from largest to smallest value