Каким будет наилучшее решение найти вершину N (например, 10) элементов в неупорядоченном списке (скажем, 100).
Решение, которое пришло мне в голову, состояло в том, чтобы 1. отсортировать его с помощью быстрого сортировки, 2. получить верх 10.
Но есть ли лучшая альтернатива?
Время может быть уменьшено до линейного времени:
Используйте алгоритм выбора который эффективно находит k-й элемент в неупорядоченном массиве в линейном времени. Вы можете использовать вариант быстрого сортировки или более надежные алгоритмы.
Получите верхний k, используя точку поворота, полученную на шаге 1.
Как насчет делегирования всего на Java;)
function findTopN(Array list, int n)
{
Set sortedSet<Integer> = new TreeSet<>(Comparators.naturalOrder());
// add all elements from list to sortedSet
// return the first n from sortedSet
}
Я не пытаюсь сказать, что это лучший способ. Я до сих пор считаю, что наилучшим ответом является метод Инь Чжу для нахождения k-го наибольшего элемента.
Если вы имеете дело с простыми элементами, такими как целые числа фиксированной длины, то при условии, что вы можете зарезервировать буфер памяти того же размера, что и входные данные, сортировка может быть выполнена в O (n) раз, используя сортировки в виде ковша или радикса, и это будет самым быстрым.
Хотя существуют алгоритмы выбора по линейному времени, скрытая константа очень высока - около 24. Это означает, что алгоритм O (nlog n) будет обычно быстрее для менее чем нескольких миллионов элементов.
В противном случае, в общем случае, когда вы можете сравнить только 2 элемента и определить, что больше, проблему лучше всего решить с помощью структуры данных кучи.
Предположим, вы хотите, чтобы верхние k из n элементов. Для всех решений, основанных на полной сортировке данных, требуется время O (nlog n), а для использования кучи требуется только время O (nlog k) - просто создайте кучу на первых элементах k, а затем добавьте элемент и удалите максимум. Это оставит вас с кучей, содержащей наименьшие k элементов.
Да, вы можете сделать это в O (n), просто сохранив (отсортированный) список запусков сверху N. Вы можете отсортировать список, используя обычные функции библиотеки, или сортировка сети. Например. простая демонстрация с использованием 3 и отображение элементов в списке выполнения, изменяющих каждую итерацию.
5 2 8 7 9
i = 0
top[0] <= 5
i = 1
top[1] <= 2
i = 2
top[2] <= top[1] (2)
top[1] <= top[0] (5)
top[0] <= 8
i = 3
top[2] <= top[1] (5)
top[1] <= 7
i = 4
top[2] <= top[1] (7)
top[1] <= top[0] (8)
top[0] <= 9
Лучшее решение - использовать любые средства, которые предлагает ваш выбранный язык, который облегчит вашу жизнь.
Однако, если предположить, что это был вопрос, связанный с тем, какой алгоритм вы должны выбрать, я собираюсь предложить другой подход здесь. Если вы говорите о 10 из 100, вы не должны слишком беспокоиться о производительности, если вы не хотите делать это много раз в секунду.
Например, этот код C (который примерно такой же неэффективный, как я могу сделать, не будучи глупым) по-прежнему занимает десятую часть секунды для выполнения. Этого недостаточно, чтобы я даже подумал о том, чтобы получить кофе.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SRCSZ 100
#define DSTSZ 10
int main (void) {
int unused[SRCSZ], source[SRCSZ], dest[DSTSZ], i, j, pos;
srand (time (NULL));
for (i = 0; i < SRCSZ; i++) {
unused[i] = 1;
source[i] = rand() % 1000;
}
for (i = 0; i < DSTSZ; i++) {
pos = -1;
for (j = 0; j < SRCSZ; j++) {
if (pos == -1) {
if (unused[j]) {
pos = j;
}
} else {
if (unused[j] && (source[j] > source[pos])) {
pos = j;
}
}
}
dest[i] = source[pos];
unused[pos] = 0;
}
printf ("Source:");
for (i = 0; i < SRCSZ; i++) printf (" %d", source[i]);
printf ("\nDest:");
for (i = 0; i < DSTSZ; i++) printf (" %d", dest[i]);
printf ("\n");
return 0;
}
Запуск через time дает вам (я немного отформатировал вывод, чтобы сделать его доступным для чтения, но не повлиял на результаты):
Source: 403 459 646 467 120 346 430 247 68 312 701 304 707 443
753 433 986 921 513 634 861 741 482 794 679 409 145 93
512 947 19 9 385 208 795 742 851 638 924 637 638 141
382 89 998 713 210 732 784 67 273 628 187 902 42 25
747 471 686 504 255 74 638 610 227 892 156 86 48 133
63 234 639 899 815 986 750 177 413 581 899 494 292 359
60 106 944 926 257 370 310 726 393 800 986 827 856 835
66 183 901
Dest: 998 986 986 986 947 944 926 924 921 902
real 0m0.063s
user 0m0.046s
sys 0m0.031s
Только когда количество чисел становится большим, если вы обычно беспокоитесь. Не поймите меня неправильно, я не говорю, что вы не должны думать о производительности. То, что вы не должны делать, это потратить слишком много времени на оптимизацию вещей, которые не имеют значения - YAGNI и весь этот джаз.
Как и во всех вопросах оптимизации, измерение не угадывает!
Ну, вы можете создать кучу из несортированного массива в O (n) времени, и вы можете получить верхний элемент из кучи в O (log (n)) времени. Таким образом, ваша общая продолжительность выполнения - O (n + k * log (n)).
Написано ниже как сортировка сортировки, так и вставка. Для большего набора данных я предлагаю сортировку вставки лучше, чем сортировка сортировки
public interface FindTopValues
{
int[] findTopNValues(int[] data, int n);
}
Реализация сортировки вставки:
public class FindTopValuesInsertionSortImpl implements FindTopValues {
/**
* Finds list of the highest 'n' values in the source list, ordered naturally,
* with the highest value at the start of the array and returns it
*/
@Override
public int[] findTopNValues(int[] values, int n) {
int length = values.length;
for (int i=1; i<length; i++) {
int curPos = i;
while ((curPos > 0) && (values[i] > values[curPos-1])) {
curPos--;
}
if (curPos != i) {
int element = values[i];
System.arraycopy(values, curPos, values, curPos+1, (i-curPos));
values[curPos] = element;
}
}
return Arrays.copyOf(values, n);
}
}
Выбор Сортировка:
public class FindTopValuesSelectionSortImpl implements FindTopValues {
/**
* Finds list of the highest 'n' values in the source list, ordered naturally,
* with the highest value at the start of the array and returns it
*/
@Override
public int[] findTopNValues(int[] values, int n) {
int length = values.length;
for (int i=0; i<=n; i++) {
int maxPos = i;
for (int j=i+1; j<length; j++) {
if (values[j] > values[maxPos]) {
maxPos = j;
}
}
if (maxPos != i) {
int maxValue = values[maxPos];
values[maxPos] = values[i];
values[i] = maxValue;
}
}
return Arrays.copyOf(values, n);
}
}
Вы можете использовать List и можете использовать класс guava Comparators для получения желаемых результатов. Это высоко оптимизированное решение. Пожалуйста, см. Образец ниже, который получает 5 лучших номеров. Api можно найти здесь.
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collector;
import org.junit.Test;
import com.google.common.collect.Comparators;
import com.google.common.collect.Lists;
public class TestComparator {
@Test
public void testTopN() {
final List<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0);
final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5,
Comparator.<Integer>naturalOrder());
final List<Integer> top = numbers.stream().collect(collector);
System.out.println(top);
}
}
Выход: [9, 8, 7, 6, 5]
Да, есть способ сделать лучше, чем quicksort. Как указал Инь Чжу, вы можете сначала сначала найти k-й наибольший элемент, а затем использовать это значение элемента в качестве свода, чтобы разделить массив
В интервью мне был задан тот же алгоритм. Я сделал это, если кто-то может сравнить это с самым быстрым алгоритмом в Java - будет очень полезно.
public int[] findTopNValues(int[] anyOldOrderValues, int n) {
if (n < 0) {
return new int[]{};
}
if (n == 1) {
return new int[]{findMaxValue(anyOldOrderValues)};
}
int[] result = new int[n + 1];
for (int i = 0; i < Math.min(n, anyOldOrderValues.length); i++) {
result[i] = anyOldOrderValues[i];
}
Arrays.sort(result);
int max = result[0];
for (int i = n - 1; i < anyOldOrderValues.length; i++) {
int value = anyOldOrderValues[i];
if (max < value) {
result[n] = value;
Arrays.sort(result);
int[] result1 = new int[n + 1];
System.arraycopy(result, 1, result1, 0, n);
result = result1;
max = result[0];
}
}
return convertAndFlip(result, n);
}
public static int[] convertAndFlip(int[] integers, int n) {
int[] result = new int[n];
int j = 0;
for (int i = n - 1; i > -1; i--) {
result[j++] = integers[i];
}
return result;
}
и протестируйте это:
public void testFindTopNValues() throws Exception {
final int N = 100000000;
final int MAX_VALUE = 100000000;
final int returnArray = 1000;
final int repeatTimes = 5;
FindTopValuesArraySorting arraySorting = new FindTopValuesArraySorting();
int[] randomArray = createRandomArray(N, MAX_VALUE);
for (int i = 0; i < repeatTimes; i++) {
long start = System.currentTimeMillis();
int[] topNValues = arraySorting.findTopNValues(randomArray, returnArray);
long stop = System.currentTimeMillis();
System.out.println("findTopNValues() from " + N + " elements, where MAX value=" + (MAX_VALUE - 1) + " and return array size " + returnArray + " elements : " + (stop - start) + "msec");
// System.out.println("Result list = " + Arrays.toString(topNValues));
}
}
private static int[] createRandomArray(int n, int maxValue) {
Random r = new Random();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = r.nextInt(maxValue);
}
return arr;
}
Результат выглядит примерно так:
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 395msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 311msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 473msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 380msec
findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 406msec
~ 400msc средний результат, для получения 1000 max целых чисел из массива из 100.000.000 исходных элементов. не плохо!
Просто попробовал установить выше:
findTopNValues() from 101 elements and return array size 10 elements : 1msec
Result list = [998, 986, 986, 986, 947, 944, 926, 924, 921, 902]
Original list = [403, 459, 646, 467, 120, 346, 430, 247, 68, 312, 701, 304, 707, 443, 753, 433, 986, 921, 513, 634, 861, 741, 482, 794, 679, 409, 145, 93, 512, 947, 19, 9, 385, 208, 795, 742, 851, 638, 924, 637, 638, 141, 382, 89, 998, 713, 210, 732, 784, 67, 273, 628, 187, 902, 42, 25, 747, 471, 686, 504, 255, 74, 638, 610, 227, 892, 156, 86, 48, 133, 63, 234, 639, 899, 815, 986, 750, 177, 413, 581, 899, 494, 292, 359, 60, 106, 944, 926, 257, 370, 310, 726, 393, 800, 986, 827, 856, 835, 66, 183, 901]
Наилучший алгоритм будет сильно зависеть от размера K. Если K мало, то просто следуя алгоритму BubbleSort и итерации внешнего цикла K раз будет давать верхние значения K. Сложностью будет O (n * k).
Однако для значений K, близких к n, сложность будет приближаться к O (n ^ 2). В таком случае быстрая сортировка может быть хорошей альтернативой.
public class FindTopValuesSelectionSortImpl implements FindTopValues {
/**
* Finds list of the highest 'n' values in the source list, ordered naturally,
* with the highest value at the start of the array and returns it
*/
@Override
public int[] findTopNValues(int[] values, int n) {
int length = values.length;
for (int i=0; i<=n; i++) {
int maxPos = i;
for (int j=i+1; j<length; j++) {
if (values[j] > values[maxPos]) {
maxPos = j;
}
}
if (maxPos != i) {
int maxValue = values[maxPos];
values[maxPos] = values[i];**strong text**
values[i] = maxValue;
}
}
return Arrays.copyOf(values, n);
}
}
Интуитивно понятный подход, если вы хотите, чтобы N элементов были отсортированы, и разрешать дублирование, заключается в использовании класса PriorityQueue:
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.stream.IntStream;
public class UpToNLargestNumbersFromArray {
public static int[] upToNLargestNumbersFromArray(int[] arr, int N) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : arr) {
pq.offer(num);
if (pq.size() > N) {
pq.poll();
}
}
int[] result = new int[pq.size()];
int i = 0;
while (!pq.isEmpty()) {
result[i] = pq.remove();
i++;
}
return result;
}
public static void main(String[] args) {
int[] example10randomIntsArray = IntStream.generate(() -> new Random().nextInt(1000)).limit(10).toArray();
System.out.println("example10randomIntsArray: " + Arrays.toString(example10randomIntsArray));
// Example usage where N <= the number of elements in the array
int[] upTo3largestFromExampleArray = upToNLargestNumbersFromArray(example10randomIntsArray, 3);
System.out.println("upTo3largestFromExampleArray: " + Arrays.toString(upTo3largestFromExampleArray));
// Example usage where N > the number of elements in the array
int[] upTo15largestFromExampleArray = upToNLargestNumbersFromArray(example10randomIntsArray, 15);
System.out.println("upTo15largestFromExampleArray: " + Arrays.toString(upTo15largestFromExampleArray));
}
}
Пример использования вывода:
example10randomIntsArray: [342, 78, 297, 35, 20, 911, 602, 835, 495, 104]
upTo3largestFromExampleArray: [602, 835, 911]
upTo15largestFromExampleArray: [20, 35, 78, 104, 297, 342, 495, 602, 835, 911]