Tìm trung vị trong nhiều phạm vi phụ của danh sách không có thứ tự

Question

Ví dụ: đưa ra một danh sách không có thứ tự các phần tử N, tìm các giá trị trung bình cho các phạm vi con 0..100, 25..200, 400..1000, 10..500, ... Tôi không thấy cách nào tốt hơn là đi qua từng phần tử phạm vi phụ và chạy thuật toán tìm kiếm trung bình chuẩn.

Ví dụ đơn giản: [5 3 6 2 4] Giá trị trung bình cho 0,3 là 5. (Không phải 4, vì chúng tôi đang yêu cầu trung vị của ba yếu tố đầu tiên trong danh sách gốc)

Answer 1

Tôi nghĩ rằng vì số lượng phạm vi phụ tăng lên, bạn sẽ nhanh chóng tìm thấy nó nhanh hơn để sắp xếp và sau đó lấy phần tử số bạn muốn.

Trong thực tế, vì sẽ có các thói quen sắp xếp được tối ưu hóa cao mà bạn có thể gọi.

Về lý thuyết, và có lẽ trong thực tế, bởi vì vì bạn đang xử lý các số nguyên bạn không cần trả n log n cho một loại - xem http://en.wikipedia.org/wiki/Integer_sorting.

Nếu dữ liệu của bạn thực tế là điểm động và không phải là NaN, thì thực tế sẽ cho phép bạn sử dụng sắp xếp số nguyên trên chúng - từ - http://en.wikipedia.org/wiki/IEEE_754-1985#Comparing_floating-point_numbers - Biểu diễn nhị phân có đặc tính đặc biệt, trừ NaN, Các số có thể được so sánh như số nguyên và số nguyên (mặc dù với bộ xử lý máy tính hiện đại không còn trực tiếp áp dụng): nếu bit dấu là khác nhau, số âm trước số dương (ngoại trừ số âm và số 0 dương cần được xem là bằng nhau) , nếu không, thứ tự tương đối giống với thứ tự từ điển, nhưng đảo ngược cho hai số âm; các vấn đề về tính cuối cùng được áp dụng. Vì vậy, bạn có thể kiểm tra NaN và các funnies khác, giả sử các số dấu chấm động là dấu + số nguyên, trừ khi tiêu cực để sửa thứ tự cho các số âm, và sau đó xử lý như 2s bổ sung thông thường đã ký, sắp xếp, và sau đó đảo ngược quá trình.

Answer 2

YẾU TỐ INTEGER:

Nếu loại yếu tố của bạn là các số nguyên, thì cách tốt nhất là phải có một xô cho mỗi số nằm trong bất kỳ phụ dãy của bạn, trong đó mỗi thùng được sử dụng để đếm số nguyên liên quan của nó được tìm thấy trong các yếu tố đầu vào của bạn (ví dụ: bucket[100] lưu trữ số lượng 100 s có trong chuỗi đầu vào của bạn). Về cơ bản, bạn có thể đạt được điều đó trong các bước sau:

1. tạo nhóm cho mỗi số nằm trong bất kỳ phạm vi con nào của bạn.
2. lặp qua tất cả các phần tử, cho mỗi số n, nếu chúng tôi có bucket[n], thì bucket[n]++.
3. tính trung vị dựa trên các giá trị tổng hợp được lưu trữ trong nhóm của bạn.

Đặt theo cách khác, giả sử bạn có một dải phụ [0, 10] và bạn muốn tính trung bình. Cách tiếp cận xô về cơ bản tính toán có bao nhiêu 0 s có trong đầu vào của bạn và số lượng 1 có trong đầu vào của bạn, v.v. Giả sử có n số nằm trong phạm vi [0, 10], sau đó trung bình là yếu tố lớn nhất thứ n/2, có thể được xác định bằng cách tìm các i mà bucket[0] + bucket[1] ... + bucket[i] lớn hơn hoặc bằng n/2 nhưng bucket[0] + ... + bucket[i - 1] là ít hơn n/2.

Điều tốt đẹp về điều này là ngay cả các yếu tố đầu vào của bạn được lưu trữ trong nhiều máy (tức là trường hợp phân phối), mỗi máy có thể duy trì các nhóm riêng của mình và chỉ các giá trị tổng hợp được yêu cầu để đi qua mạng nội bộ.

Bạn cũng có thể sử dụng nhóm phân cấp, bao gồm nhiều lần chuyền. Trong mỗi lần vượt qua, bucket[i] đếm số phần tử trong đầu vào của bạn nằm trong một phạm vi cụ thể (ví dụ: [i * 2^K, (i+1) * 2^K]) và sau đó thu hẹp không gian vấn đề bằng cách xác định xem phương tiện nào sẽ nằm sau mỗi bước, sau đó giảm K xuống 1 bước tiếp theo và lặp lại cho đến khi bạn có thể xác định chính xác phương tiện.

---

dấu chấm động YẾU TỐ

Toàn bộ các yếu tố có thể phù hợp với bộ nhớ:

Nếu toàn bộ các yếu tố của bạn có thể phù hợp với bộ nhớ, lần đầu tiên sắp xếp các yếu tố N và sau đó tìm trung vị cho mỗi phạm vi phụ là tùy chọn tốt nhất. The linear time heap solution cũng hoạt động tốt trong trường hợp này nếu số lượng phạm vi con của bạn nhỏ hơn logN.

Toàn bộ các yếu tố không thể phù hợp với bộ nhớ nhưng lưu trữ trong một máy duy nhất:

Nói chung, một external sort thường đòi hỏi ba đĩa quét. Do đó, nếu số lượng các phạm vi con của bạn lớn hơn hoặc bằng 3, thì trước tiên sắp xếp các phần tử N và sau đó tìm các giá trị trung bình cho mỗi phạm vi phụ bằng cách chỉ tải các phần tử cần thiết từ đĩa là lựa chọn tốt nhất. Nếu không, chỉ cần thực hiện quét cho từng phạm vi phụ và nhận các yếu tố đó trong phạm vi phụ là tốt hơn.

Toàn bộ các yếu tố được lưu trữ trong nhiều máy tính: Kể từ khi việc tìm kiếm trung bình là một nhà điều hành toàn diện, có nghĩa là bạn không thể lấy được trung bình cuối cùng của toàn bộ đầu vào dựa trên trung vị của một số bộ phận của đầu vào, đó là một vấn đề khó khăn người ta không thể mô tả giải pháp của nó trong vài câu, nhưng có những nghiên cứu (xem this làm ví dụ) đã được tập trung vào vấn đề này.

Answer 3

Ý tưởng của tôi:

• Sắp xếp danh sách vào một mảng (sử dụng bất kỳ thuật toán phân loại thích hợp)

• Đối với mỗi phạm vi, tìm ra chỉ số của sự bắt đầu và kết thúc của dãy núi này sử dụng tìm kiếm nhị phân

• Tìm trung vị bằng cách thêm chỉ mục của chúng và chia cho 2 (tức làtrung bình của dải [x,y] là thời gian arr[(x+y)/2])

tiền xử lý: O (n log n) cho một thuật toán phân loại chung chung (như nhanh chóng loại) hoặc thời gian chạy của các sắp xếp lựa chọn thường xuyên

Thời gian cho mỗi truy vấn : O (log n)

động danh sách:

Ở trên giả định rằng danh sách này là tĩnh. Nếu các phần tử có thể được thêm hoặc xóa tự do giữa các truy vấn, thì Binary Search Tree đã sửa đổi có thể hoạt động, với mỗi nút giữ số lượng con cháu của nó. Điều này sẽ cho phép cùng thời gian chạy như trên với danh sách động.

Answer 4

Câu trả lời cuối cùng sẽ là "phụ thuộc". Có nhiều cách tiếp cận khác nhau, bất kỳ phương pháp nào trong số đó có thể sẽ phù hợp với hầu hết các trường hợp bạn có thể gặp phải. Vấn đề là mỗi người sẽ thực hiện một cách khác nhau cho các đầu vào khác nhau. Trong trường hợp người ta có thể thực hiện tốt hơn cho một loại đầu vào, một loại khác sẽ hoạt động tốt hơn cho một loại đầu vào khác nhau. Ví dụ, cách tiếp cận phân loại và sau đó thực hiện tìm kiếm nhị phân trên các cực của phạm vi của bạn và sau đó tính toán trực tiếp trung vị sẽ hữu ích khi số phạm vi bạn phải kiểm tra lớn hơn log (N). Mặt khác, nếu số phạm vi nhỏ hơn log (N) thì tốt hơn là di chuyển các phần tử của một phạm vi nhất định đến đầu mảng và sử dụng thuật toán chọn thời gian tuyến tính để tìm trung vị.

Tất cả những điều này đều hướng đến việc định hình để tránh tối ưu hóa sớm. Nếu cách tiếp cận bạn thực hiện hóa ra không phải là một nút cổ chai cho hiệu năng của hệ thống của bạn, hãy tìm cách cải thiện nó sẽ không phải là một bài tập hữu ích liên quan đến việc hợp lý hóa các phần của chương trình của bạn.