Sắp xếp nhanh khi đặt hàng hiếm khi thay đổi

Question

Tôi đang làm việc trên trò chơi 2D với chế độ xem cuộn (nghĩ Red Alert hoặc Zelda) nhưng tôi đang cố gắng vẽ bản vẽ.

Về cơ bản có hai loại đối tượng được vẽ trên bản đồ. Một số có vị trí cố định (như cây cối và tòa nhà) và những người khác di chuyển xung quanh (người chơi, kẻ thù, mũi tên bay).

Đối với mọi thứ xuất hiện trước mặt nhau theo cách chính xác, chúng cần được vẽ theo thứ tự cụ thể (đối tượng ở xa trước và làm việc với "máy ảnh").

Ngay bây giờ, tôi sắp xếp danh sách tất cả các đối tượng (cả hai loại) mỗi khi trò chơi cập nhật (100 lần mỗi giây) và cảm thấy như một sự lãng phí lớn thời gian của CPU. Thứ tự của các đối tượng rất hiếm khi thay đổi, và khi chúng làm chúng thường chỉ di chuyển một vị trí lên hoặc xuống trong danh sách.

Một vấn đề khác là chỉ các đối tượng trên màn hình thực sự cần được xem xét. Vì các bản đồ có thể trở nên khá lớn với 1000 đối tượng tôi không muốn sắp xếp chúng 100 lần mỗi giây.

Bạn đề nghị tôi giải quyết vấn đề này như thế nào?

Answer 1

Bubble Sort Trường hợp tốt nhất là khi các yếu tố đã được sắp xếp. Bạn sẽ nhận được O (n) so sánh trong trường hợp đó. Theo Wikipedia:

Trong đồ họa máy tính, khả năng phát hiện một lỗi rất nhỏ (như hoán đổi chỉ hai phần tử) trong các mảng gần như được sắp xếp và sửa nó chỉ phức tạp tuyến tính (2n).

Nhưng nó được coi là một thuật toán "xấu" vì nhiều lý do được đề cập trong bài viết được liên kết. Bạn có thể muốn cấu hình sự khác biệt giữa nó và Sắp xếp chèn (cũng O (n) cho danh sách được sắp xếp) để xem cái nào nhanh hơn trong thực tế.

Tùy chọn khác là sử dụng cấu trúc dữ liệu giữ các mục được sắp xếp trong đó và được thông báo khi vị trí của mục thay đổi. Nếu đối tượng không di chuyển nhiều so với tần suất chúng được vẽ lại, điều đó sẽ tiết kiệm rất nhiều thời gian xử lý vì bạn chỉ phải sắp xếp lại các yếu tố có vị trí đã thay đổi, bạn có thể tránh sắp xếp lại tại tất cả cho đến khi ít nhất một phần tử đã di chuyển.

Answer 2

Theo dõi đối tượng nào đang ở trên màn hình trong vectơ và thêm các đối tượng mới hiển thị ở cuối đối tượng. Sử dụng sắp xếp bong bóng hoặc sắp xếp chèn để sắp xếp. Điều này là không hiệu quả đáng kể cho dữ liệu ngẫu nhiên, nhưng ~ O (n) cho hầu hết các dữ liệu được sắp xếp.

Answer 3

Đồng ý với các loại bong bóng và chèn.

Tôi có các ý tưởng khác mà không sắp xếp: nếu ít khi thay đổi thứ tự, bạn chỉ có thể theo dõi lịch sử thay đổi và khôi phục thứ tự khi sắp xếp cần thiết. Hơn nữa, nếu các yếu tố không được thêm vào hoặc gỡ bỏ, chỉ cần khôi phục lại ảnh chụp của danh sách theo thứ tự ban đầu, nó sẽ rất dễ dàng và nhanh chóng. Nếu tôi hiểu rõ câu hỏi của bạn.

Answer 4

Hãy suy nghĩ về việc sử dụng PriorityQueue hoặc danh sách được liên kết kép để bạn có thể định vị lại các mục trong danh sách trực tiếp khi cần thiết thay vì cưỡng bức dựa trên thứ tự Z. Bạn cũng nên nghiên cứu kỹ các vùng clip.

Answer 5

Sắp xếp 100 đối tượng sẽ không mất nhiều thời gian. Nhưng nếu hiệu suất thực sự quan trọng và bạn biết rằng danh sách này gần như được sắp xếp, với ít mục không đúng thứ tự, thì sắp xếp hợp nhất hoặc thuật toán sắp xếp Tim có khả năng mang lại hiệu suất tốt cho bạn.Nó có hiệu suất O (N) cho một danh sách đã được sắp xếp, hoặc chỉ có một vài phần tử không đúng thứ tự.

Điều đó nói rằng, không loại bỏ thuật toán phân loại mục đích chung được cung cấp bởi thư viện Java, cho đến khi bạn đã đo hiệu suất thực tế của nó. Vì nó là mục đích chung, nên được thực hiện theo cách mang lại hiệu suất hợp lý cho một loạt các trường hợp, bao gồm cả các trường hợp khi danh sách sắp được sắp xếp.

Trong thực tế, Java tiêu chuẩn phân loại phương pháp sử dụng merge sort tối đa Java 6, và thay đổi để TimSort với Java 7.