Thuật toán phân loại hiệu quả cho danh sách được sắp xếp gần như chứa dữ liệu thời gian?

Question

Tên này nói lên tất cả. Tôi nghi ngờ rằng sắp xếp chèn là tốt nhất, vì đó là loại tốt nhất cho dữ liệu chủ yếu được phân loại nói chung. Tuy nhiên, vì tôi biết nhiều hơn về dữ liệu, có một cơ hội khác có thể nhìn thấy. Vì vậy, các phần thông tin có liên quan khác là:

1) đây là dữ liệu thời gian, có nghĩa là tôi có thể tạo băm hiệu quả cho việc sắp xếp dữ liệu. 2) Dữ liệu sẽ không tồn tại cùng một lúc. thay vào đó, tôi sẽ đọc trong các bản ghi có thể chứa một vectơ đơn lẻ, hoặc hàng chục hoặc hàng trăm vectơ. Tôi muốn xuất tất cả thời gian trong một cửa sổ 5 giây. Vì vậy, có thể là một loại sắp xếp như tôi chèn dữ liệu sẽ là một lựa chọn tốt hơn. 3) bộ nhớ không phải là một vấn đề lớn, nhưng tốc độ CPU là như thế này có thể là một nút cổ chai của hệ thống.

Với những điều kiện này, bất kỳ ai cũng có thể đề xuất một thuật toán có thể đáng xem xét ngoài việc sắp xếp chèn? Ngoài ra, Làm cách nào để xác định 'chủ yếu được sắp xếp' để quyết định lựa chọn sắp xếp tốt là gì? Những gì tôi có nghĩa là bởi vì làm thế nào để tôi nhìn vào dữ liệu của tôi và quyết định 'này không phải là sắp xếp như tôi nghĩ nó như, có thể chèn sắp xếp không còn là lựa chọn tốt nhất'? Bất kỳ liên kết đến một bài viết được coi là phức tạp quá trình mà tốt hơn xác định sự phức tạp liên quan đến dữ liệu độ được sắp xếp sẽ được đánh giá cao.

Cảm ơn

Edit: cảm ơn bạn tất cả mọi người cho thông tin của bạn. Tôi sẽ đi với một chèn dễ dàng hoặc sắp xếp hợp nhất (bất cứ điều gì tôi đã viết sẵn) cho bây giờ. Tuy nhiên, tôi sẽ thử một số phương pháp khác một lần gần với giai đoạn tối ưu hóa (vì chúng cần nhiều nỗ lực hơn để thực hiện). Tôi đánh giá cao sự giúp đỡ

Answer 1

Bạn có thể áp dụng tùy chọn (2) bạn đã đề xuất - sắp xếp dữ liệu trong khi bạn chèn phần tử.

Sử dụng skip list, được sắp xếp theo thời gian, tăng dần để duy trì dữ liệu của bạn.

• Một khi đi vào mới đến - kiểm tra xem nó lớn thì yếu tố cuối cùng (dễ dàng và nhanh chóng) nếu nó là - chỉ đơn giản là thêm nó (dễ dàng để làm trong một danh sách bỏ qua). Danh sách bỏ qua sẽ cần phải thêm 2 nút trung bình cho những trường hợp này và sẽ là O(1) trên số trung bình cho những trường hợp này.
• Nếu phần tử không lớn hơn thì phần tử cuối cùng - thêm phần tử đó vào danh sách bỏ qua làm phương thức chèn chuẩn, sẽ là O(logn).

Cách tiếp cận này sẽ mang lại cho bạn O(n+klogn) thuật toán, trong đó k là số phần tử được chèn vào theo thứ tự.

Answer 2

Tôi sẽ ném vào merge sort nếu bạn thực hiện phiên bản tự nhiên, bạn sẽ có được một trường hợp tốt nhất là O(N) với trường hợp điển hình và xấu nhất là O(N log N) nếu bạn gặp bất kỳ sự cố nào. Việc chèn bạn nhận được trường hợp xấu nhất là O(N^2) và trường hợp tốt nhất là O(N).

Answer 3

Có rất nhiều thuật toán sắp xếp thích nghi ngoài đó được thiết kế đặc biệt để sắp xếp dữ liệu được sắp xếp chủ yếu. Bỏ qua thực tế là bạn đang lưu trữ ngày, bạn có thể muốn xem smoothsort hoặc loại cây Descartes dưới dạng thuật toán có thể sắp xếp dữ liệu được sắp xếp hợp lý trong trường hợp xấu nhất O (n log n) và trường hợp tốt nhất O (n) thời gian. Smoothsort cũng có lợi thế là chỉ yêu cầu không gian O (1), như sắp xếp chèn.

Sử dụng thực tế là mọi thứ đều là ngày và do đó có thể được chuyển đổi thành số nguyên, bạn có thể muốn xem nhanh phân tách (sắp xếp theo MSX) bằng cách sử dụng lựa chọn trục trung bình. Thuật toán này có hiệu suất O (n log n) tốt nhất, nhưng có một yếu tố không đổi rất thấp khiến nó khá cạnh tranh. Trường hợp xấu nhất của nó là O (n log U), trong đó U là số bit trong mỗi ngày (có thể là 64), không quá tệ.

Hy vọng điều này sẽ hữu ích!

Answer 4

Nếu thư viện OS hoặc C của bạn cung cấp chức năng phối hợp, rất có khả năng nó đã xử lý trường hợp dữ liệu được đặt một phần (theo bất kỳ hướng nào) chạy trong thời gian O (N).

Nếu không, bạn chỉ có thể sao chép hợp nhất có sẵn từ hệ điều hành BSD yêu thích của bạn.

Answer 5

Nếu không hiểu rõ vấn đề, Timsort có thể phù hợp với hóa đơn khi bạn cho rằng dữ liệu của bạn chủ yếu được sắp xếp.

Answer 6

Bạn có thể sắp xếp danh sách kích thước n với k các yếu tố không đúng chỗ trong thời gian O(n + k lg k).

Xem: http://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of-elements-say-up-to-1-4-of-the-total-whose-positions-are-known/answer/Mark-Gordon-6?share=1

Ý tưởng cơ bản là thế này:

• lặp qua các yếu tố của mảng, xây dựng một dãy tăng (nếu các yếu tố hiện nay là lớn hơn hoặc bằng với yếu tố cuối cùng của các subsequence, gắn nó vào cuối của các subsequence. Nếu không, loại bỏ cả hai yếu tố hiện tại và các yếu tố cuối cùng của subsequence). Thao tác này mất O(n) thời gian.
• Bạn sẽ bị hủy không quá 2k yếu tố vì các phần tử k không đúng chỗ.
• Sắp xếp các yếu tố 2k bị loại bỏ bằng cách sử dụng thuật toán phân loại O(k lg k) như sắp xếp hợp nhất hoặc heapsort.
• Bây giờ bạn có hai danh sách được sắp xếp. Hợp nhất các danh sách trong O(n) thời gian như bạn sẽ làm trong bước hợp nhất sắp xếp hợp nhất.

Nhìn chung độ phức tạp thời gian = O(n + k lg k)

Nhìn chung phức tạp không gian = O(n)

(điều này có thể được sửa đổi để chạy trong O(1) không gian nếu bạn có thể hợp nhất trong O(1) không gian, nhưng nó không phải là tầm thường)