Медиана медиан на Яве
Я пытаюсь реализовать Median of Medians в Java для такого метода:
Select(Comparable[] list, int pos, int colSize, int colMed)
listсписок значений, из которых нужно найти указанную позициюposуказанная позицияcolSizeэто размер столбцов, которые я создаю на первом этапеcolMedэто позиция в тех столбцах, которые я использую в качестве medX
Я не уверен, какой алгоритм сортировки лучше всего использовать или как именно это реализовать.
5 ответов
Я не знаю, нужна ли вам еще эта проблема, но http://www.ics.uci.edu/~eppstein/161/960130.html имеет алгоритм:
select(L,k)
{
if (L has 10 or fewer elements)
{
sort L
return the element in the kth position
}
partition L into subsets S[i] of five elements each
(there will be n/5 subsets total).
for (i = 1 to n/5) do
x[i] = select(S[i],3)
M = select({x[i]}, n/10)
partition L into L1<M, L2=M, L3>M
if (k <= length(L1))
return select(L1,k)
else if (k > length(L1)+length(L2))
return select(L3,k-length(L1)-length(L2))
else return M
}
Удачи!
Вопрос, заданный для Java, поэтому вот он
import java.util.*;
public class MedianOfMedians {
private MedianOfMedians() {
}
/**
* Returns median of list in linear time.
*
* @param list list to search, which may be reordered on return
* @return median of array in linear time.
*/
public static Comparable getMedian(ArrayList<Comparable> list) {
int s = list.size();
if (s < 1)
throw new IllegalArgumentException();
int pos = select(list, 0, s, s / 2);
return list.get(pos);
}
/**
* Returns position of k'th largest element of sub-list.
*
* @param list list to search, whose sub-list may be shuffled before
* returning
* @param lo first element of sub-list in list
* @param hi just after last element of sub-list in list
* @param k
* @return position of k'th largest element of (possibly shuffled) sub-list.
*/
public static int select(ArrayList<Comparable> list, int lo, int hi, int k) {
if (lo >= hi || k < 0 || lo + k >= hi)
throw new IllegalArgumentException();
if (hi - lo < 10) {
Collections.sort(list.subList(lo, hi));
return lo + k;
}
int s = hi - lo;
int np = s / 5; // Number of partitions
for (int i = 0; i < np; i++) {
// For each partition, move its median to front of our sublist
int lo2 = lo + i * 5;
int hi2 = (i + 1 == np) ? hi : (lo2 + 5);
int pos = select(list, lo2, hi2, 2);
Collections.swap(list, pos, lo + i);
}
// Partition medians were moved to front, so we can recurse without making another list.
int pos = select(list, lo, lo + np, np / 2);
// Re-partition list to [<pivot][pivot][>pivot]
int m = triage(list, lo, hi, pos);
int cmp = lo + k - m;
if (cmp > 0)
return select(list, m + 1, hi, k - (m - lo) - 1);
else if (cmp < 0)
return select(list, lo, m, k);
return lo + k;
}
/**
* Partition sub-list into 3 parts [<pivot][pivot][>pivot].
*
* @param list
* @param lo
* @param hi
* @param pos input position of pivot value
* @return output position of pivot value
*/
private static int triage(ArrayList<Comparable> list, int lo, int hi,
int pos) {
Comparable pivot = list.get(pos);
int lo3 = lo;
int hi3 = hi;
while (lo3 < hi3) {
Comparable e = list.get(lo3);
int cmp = e.compareTo(pivot);
if (cmp < 0)
lo3++;
else if (cmp > 0)
Collections.swap(list, lo3, --hi3);
else {
while (hi3 > lo3 + 1) {
assert (list.get(lo3).compareTo(pivot) == 0);
e = list.get(--hi3);
cmp = e.compareTo(pivot);
if (cmp <= 0) {
if (lo3 + 1 == hi3) {
Collections.swap(list, lo3, lo3 + 1);
lo3++;
break;
}
Collections.swap(list, lo3, lo3 + 1);
assert (list.get(lo3 + 1).compareTo(pivot) == 0);
Collections.swap(list, lo3, hi3);
lo3++;
hi3++;
}
}
break;
}
}
assert (list.get(lo3).compareTo(pivot) == 0);
return lo3;
}
}
Вот тестовый модуль, чтобы проверить, работает ли он...
import java.util.*;
import junit.framework.TestCase;
public class MedianOfMedianTest extends TestCase {
public void testMedianOfMedianTest() {
Random r = new Random(1);
int n = 87;
for (int trial = 0; trial < 1000; trial++) {
ArrayList list = new ArrayList();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
int v = r.nextInt(256);
a[i] = v;
list.add(v);
}
int m1 = (Integer)MedianOfMedians.getMedian(list);
Arrays.sort(a);
int m2 = a[n/2];
assertEquals(m1, m2);
}
}
}
Однако приведенный выше код слишком медленный для практического использования.
Вот более простой способ получить k-й элемент, который не гарантирует производительность, но намного быстрее на практике:
/**
* Returns position of k'th largest element of sub-list.
*
* @param list list to search, whose sub-list may be shuffled before
* returning
* @param lo first element of sub-list in list
* @param hi just after last element of sub-list in list
* @param k
* @return position of k'th largest element of (possibly shuffled) sub-list.
*/
static int select(double[] list, int lo, int hi, int k) {
int n = hi - lo;
if (n < 2)
return lo;
double pivot = list[lo + (k * 7919) % n]; // Pick a random pivot
// Triage list to [<pivot][=pivot][>pivot]
int nLess = 0, nSame = 0, nMore = 0;
int lo3 = lo;
int hi3 = hi;
while (lo3 < hi3) {
double e = list[lo3];
int cmp = compare(e, pivot);
if (cmp < 0) {
nLess++;
lo3++;
} else if (cmp > 0) {
swap(list, lo3, --hi3);
if (nSame > 0)
swap(list, hi3, hi3 + nSame);
nMore++;
} else {
nSame++;
swap(list, lo3, --hi3);
}
}
assert (nSame > 0);
assert (nLess + nSame + nMore == n);
assert (list[lo + nLess] == pivot);
assert (list[hi - nMore - 1] == pivot);
if (k >= n - nMore)
return select(list, hi - nMore, hi, k - nLess - nSame);
else if (k < nLess)
return select(list, lo, lo + nLess, k);
return lo + k;
}
Я согласен с ответом / решением от Chip Uni. Я просто прокомментирую часть сортировки и предоставлю некоторые дополнительные объяснения:
Вам не нужен какой-либо алгоритм сортировки. Алгоритм подобен быстрой сортировке, с той разницей, что решается только один раздел (левый или правый). Нам просто нужно найти оптимальный круг, чтобы левая и правая части были как можно более равными, что означало бы N/2 + N/4 + N/8 ... = 2N итераций и, следовательно, временную сложность O(N). Вышеупомянутые алгоритмы, называемые медианой медиан, вычисляют медиану медиан 5, что приводит к линейной временной сложности алгоритма.
Однако алгоритм сортировки используется при поиске диапазона для n-го наименьшего / наибольшего элемента (который, я полагаю, вы реализуете с помощью этого алгоритма) для ускорения алгоритма. Сортировка вставок особенно быстрая для небольших массивов, содержащих до 7-10 элементов.
Примечание о реализации:
M = select({x[i]}, n/10)
на самом деле означает взятие медианы всех этих медиан 5-элементных групп. Вы можете сделать это, создав другой массив размера (n - 1)/5 + 1 и рекурсивно вызвать тот же алгоритм, чтобы найти n/10-й элемент (который является медианой вновь созданного массива).
@android разработчик:
for (i = 1 to n/5) do
x[i] = select(S[i],3)
действительно
for (i = 1 to ceiling(n/5) do
x[i] = select(S[i],3)
с функцией потолка, подходящей для ваших данных (например, в java 2 double). Это также влияет на медиану, просто принимая n / 10, но мы находим ближайший к среднему значению, которое встречается в массиве, а не к истинному среднему. Другое замечание: у S[i] может быть меньше 3 элементов, поэтому мы хотим найти медиану относительно длины; передача его в select с k=3 не всегда будет работать (например, n =11, у нас есть 3 подгруппы 2 w 5, 1 w 1 элемент)
Я знаю, что это очень старый пост, и вы можете не помнить об этом больше. Но мне интересно, вы измерили время выполнения вашей реализации, когда вы ее реализовали?
Я попробовал этот алгоритм и сравнил его с простым подходом, используя метод сортировки Java (Arrays.sort()), а затем выбрал k-й элемент из отсортированного массива. Результат, который я получил, состоит в том, что этот алгоритм только превосходит алгоритм сортировки Java, когда размер массива составляет около ста тысяч элементов или более. И это только примерно в 2 или 3 раза быстрее, что, очевидно, не в лог (n) раз быстрее.
Есть ли у вас какие-либо комментарии по этому поводу?