У меня есть массив n поплавков, и я хочу вернуть верхний k (в моем случае n ~ 100, k ~ 10)
Существует ли оптимальный путь решения этой проблемы?
Может ли кто-нибудь предоставить алгоритм C?
EDIT: на самом деле здесь есть две проблемы: отсортированные и несортированные. Меня интересует несортированный, который должен быть быстрее!
Метод 1
Так как k мало, вы можете использовать метод турнира, чтобы найти k-й по величине. Этот метод описан в Knuth Art of Programming, том 3, стр. 212.
Сначала создайте турнир по n-k + 2 элементам. Что-то вроде нокаутного теннисного турнира. Сначала вы разбиваетесь на пары и сравниваете членов пар (как будто эти два сыграли матч и один проиграл). Затем победители, вы разделились на пары снова и так далее, пока у вас не будет победителя. Вы можете просмотреть его как дерево, с победителем наверху.
Это точно принимает n-k + 1.
Теперь победитель этих n-k + 2 не может быть вашим k-м наибольшим элементом. Подумайте о своем пути P к турниру.
Остальные k-2 теперь выбираем один и следуем за ним по пути P, который даст вам новый самый большой. В принципе, вы переделываете турнир с предыдущим победителем, который заменяется одним из элементов k-2. Пусть P - путь нового победителя. Теперь выберите другой из k-3 и следуйте по новому пути вверх и так далее.
В конце после того, как вы исчерпаете k-2, замените самый большой на -infinity, и самый большой из турниров будет k-м по величине. Элементы, которые вы выбрали, - это верхние элементы k-1.
Это занимает не более n - k + (k-1) [log (n-k+2)] сравнений, чтобы найти верхний k. Однако он использует O (n) память.
В терминах количества сравнений это, вероятно, должно бить любые алгоритмы выбора.
Метод 2
В качестве альтернативы вы можете сохранить минимальную кучу k элементов.
Сначала вставьте элементы k. Тогда для каждого элемента массива, если он меньше минимального элемента кучи, выбросьте его. В противном случае delete-min кучи и вставьте элемент из массива.
В конце куча будет содержать верхние k элементов. Это займет O(n log k).
Конечно, если n мало, просто сортировка массива должна быть достаточно хорошей. Код также будет проще.
Вы можете сделать это в O(n) с помощью алгоритма выбора . Найдите самый большой элемент k th с алгоритмом разбиения, затем все элементы после него будут больше, чем те, которые являются вашими верхними k.
Если вам нужен верхний k в отсортированном порядке, вы можете отсортировать их в O(k log k).
Короткий ответ: нет.
Более длинный ответ: да, известны несколько взаимосовместимых оптимальных решений. Это зависит от n, k и от каких свойств массива вы можете гарантировать.
Если вы ничего не знаете о массиве, нижняя граница сложности, очевидно, O (n), потому что все элементы исходного массива должны быть проверены, чтобы увидеть, соответствуют ли они в верхней части 10. Если вы знаете что-либо о исходном массиве который позволяет безопасно пропускать элементы, вы должны использовать эти знания.
Аналогично, верхняя граница сложности - O (n.log(n)), потому что вы всегда можете найти ответ, отсортировав массив (O (n.log(n)) и вернув первые 10 элементов (O ( 1)).
Линейный поиск, сравнивающий каждый элемент с десятым наивысшим, найденным до сих пор, и вставка его в соответствующее место в списке наивысших найденных до сих пор предметов, если это необходимо, имеет схожую сложность для среднесрочных и наилучших сценариев и имеет худший случай O (kn), который значительно лучше O (n-квадрат). Для размеров, которые вы оцениваете, я ожидаю, что этот метод будет работать хорошо.
Если n было намного больше (~ 10000), а k было увеличено в том же соотношении, вероятно, было бы целесообразно реализовать алгоритм quickselect. Quickselect лучше выполняет поиск большего количества элементов. Если, однако, k не увеличивалось в масштабе с n, вы должны придерживаться линейного поиска. Quickselect и друзья меняют исходный массив, поэтому они менее подходят, если вы не можете сделать это на месте, потому что вам нужна куча большего объема памяти и много копий, что сложность алгоритма не включает.
Если n велико (~ 1e20), вы бы хотели найти k наибольший из каждого из нескольких разделов входного массива, а затем найти k-наибольший из совокупности этих результатов, чтобы вы не пытались для анализа большего количества данных, чем вы можете поместиться в память за раз, и обеспечить эффективную параллелизацию операции.
Посмотрите на частичный алгоритм быстрой сортировки, обсуждаемый в конце "Эффективный выбор и частичная сортировка на основе быстрой сортировки" .
Ниже представлено элегантное решение на основе кучи на Java со сложностью O (nlogK). Это не самый эффективный, но я думаю, что это достаточно легко понять. Вы можете изменить Integer на Float, если вы хотите использовать решение с плавающей точкой
import java.util.Arrays;
import java.util.PriorityQueue;
public class FindKLargest {
public static void find(int[] A, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(k);// Min heap because the element has to be greater
// than the smallest element in the heap in order
// to be qualified to be a member of top k elements.
for (int i = 0; i < A.length; i++) {
if (i < k) // add until heap is filled with k elements.
pq.add(A[i]);
else if (pq.peek() < A[i]) { // check if it bigger than the
// smallest element in the heap.
pq.poll();
pq.add(A[i]);
}
}
int[] topK = new int[pq.size()];
int index = 0;
while (index != k)
topK[index++] = pq.poll();
System.out.println(Arrays.toString(topK));
}
public static void main(String[] args) {
int[] arr = { 1, -2, -3, -4, -5 };
find(arr, 4);
}
}
если у вас есть причудливый gpu, я могу рассказать вам, как вычислить верхний огромный k из огромных n экземпляров в одно и то же время, поэтому распространите их на текстуру на каждый экземпляр и добавьте смесь на текстуру с их "высота" в качестве положения вдоль текстуры.
Но обратите внимание, что вы должны угадать приемлемый диапазон или знать его, или вы не будете распространяться на свои максимальные детали, которые могли бы иметь.
вы клонируете позиции. (вы должны получить 2, если на нем 2, 10, если на нем 10.) во всех случаях. (просто скажите все на текстуре 8192x8192, 64x64 из этих "высотных" боксов.), и вы также пропустите слоты с 0 отсчетами.
тогда выполните иерархию добавления mipped add, за исключением того, что вы делаете это как двоичное дерево, вы обрабатываете только его 1 измерение, поэтому возьмите 2 предыдущих числа и добавьте их вместе и продолжайте делать это для каждого бинарного mip.
то мы используем эти mips (которые собрали счетчики), чтобы обнаружить приблизительное местоположение k, используя все mips в процессе, сделайте это в последнем потоке, вы выберете из него огромные куски, затем медленно используйте больше подробные mips, чтобы найти значение пикселя, которое k сидит.
это имеет смысл сделать это, если бы все это было инстансом снова, а затем его поток за обнаружение порога. (просто скажите, что вы выполняли ANN 128x128 раз одновременно (трансляционный инвариант кто-нибудь?), тогда это имеет смысл.
и достичь пороговой высоты для этого счета, но его приблизительный... так что вы получите приблизительный k. для n списков.
Вы можете сделать немного больше работы, чтобы получить точный k, но в матче сходства, но если вам удастся приблизиться к нему, как если бы он получал активацию top ~ k, тогда не беспокойтесь об этом.