Sắp xếp vòng thứ hai nhanh hơn

Question

Là một phần của bài tập ở trường, tôi muốn so sánh và đối chiếu các thuật toán sắp xếp như một bài tập Java.

Tôi đã tự thực hiện các thuật toán sắp xếp và sắp xếp các đối tượng của một lớp Person thực hiện giao diện Comparable.

Cho đến nay rất tốt, nhưng những gì tôi không thể giải thích là tại sao trong lần gọi đầu tiên đến phương pháp phân loại của tôi, việc phân loại mất nhiều thời gian hơn các cuộc gọi tiếp theo?
Kết quả dưới đây thể hiện kết quả của tôi.
nhất, xấu nhất và Avg tham khảo các mảng không được phân loại được truyền cho phương thức sắp xếp:

• xuất sắc nhất: mảng đã được sắp xếp
• xấu nhất: mảng được sắp xếp theo thứ tự ngược
• Avg: các đối tượng trong mảng đang ở thứ tự ngẫu nhiên

Đây là kết quả của tôi:

1-call of the sorting methods 
InsertionSort Best:1799ms Worst:78ms Avg:789ms 
MergeSort  Best:10ms  Worst:3ms Avg:5ms  

2-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

3-call of the sorting methods 
InsertionSort Best:1066ms Worst:39ms Avg:692ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

4-call of the sorting methods 
InsertionSort Best:1065ms Worst:39ms Avg:691ms 
MergeSort  Best:3ms  Worst:2ms Avg:5ms  

JVM có thực hiện bất kỳ tối ưu hóa nào cho các cuộc gọi tiếp theo không?
Tôi bối rối và đánh giá cao sự giúp đỡ của bạn!

Chỉnh sửa: Cảm ơn bạn đã đề xuất và trả lời cho đến thời điểm này! Để thực hiện một vài điểm rõ ràng - mỗi cuộc gọi trong đầu ra của tôi tham khảo thời gian cần để phân loại hoàn toàn!
Sau mỗi lần sắp xếp, tôi thực hiện một cuộc gọi mới với các mảng UNSORTED một lần nữa!

mã nguồn của tôi có thể được tải về như một dự án nhật thực như là một file zip, tại liên kết Dropbox sau: dropbox link to eclipse project.zip

T.B. Tôi không có kinh nghiệm với profilers - nếu bạn có thể chỉ cho tôi một hướng dẫn hoặc như vậy sẽ là tuyệt vời.

Answer 1

Xử lý mảng được sắp xếp nhanh hơn xử lý mảng chưa được sắp xếp do Branch Prediction.
Điều này đã được bảo hiểm rộng rãi trong the most famous Stack Overflow question.

Answer 2

Có rất nhiều điều tại nơi làm việc ở đây, vì nhiều phản hồi cho thấy.

Nhưng thời gian chạy dài nhất của chạy đầu tiên có thể được giải thích bằng cách biên dịch JIT (just-in-time). Là discussed here, thuật toán của bạn sẽ chạy trong JVM trong một thời gian như được giải mã bytecode. Khi màn hình Hotspot xác định rằng các vòng sắp xếp của bạn là tốn kém, JVM sẽ biên dịch chúng thành mã gốc. Sau đó, chúng sẽ chạy nhanh hơn đáng kể. Chạy đầu tiên là nhận được những bất lợi của chạy trong thông dịch viên trong một thời gian cộng với các chi phí bổ sung của biên dịch. Đây là lý do tại sao "warming up" is a common term in Java benchmarks.

Sự khác biệt về hiệu suất trên các đầu vào khác nhau được gắn với thuật toán sắp xếp. Nhiều thuật toán hoạt động khác nhau dựa trên tổ chức dữ liệu ban đầu và nhiều thuật toán được cố tình tổ chức để hoạt động tốt trên dữ liệu được sắp xếp ban đầu hoặc gần như được sắp xếp. Here is a brilliant demonstration for the case of nearly sorted input. Ví dụ. sắp xếp chèn là thời gian bậc hai nói chung, nhưng thời gian tuyến tính trên đầu vào gần được sắp xếp (thực ra là O ((k + 1) n) cho đầu vào có kích thước n trong đó các phần tử không quá k vị trí được sắp xếp chính xác).

Sau đó, có vấn đề dự đoán chi nhánh đã được tham chiếu bằng liên kết. Các bộ vi xử lý hiện đại có các cơ chế khác nhau cố gắng "đoán" theo cách nào mà một nhánh (về bản chất là "if" ở mức máy) sẽ dựa trên lịch sử gần đây được thu thập khi chương trình chạy. Chi phí đoán xấu cao. Sự tốt lành của dự đoán có thể bị ảnh hưởng bởi cả thuật toán và chi tiết dữ liệu.