Как эффективно найти 10 самых больших чисел из миллиардов чисел?

Постановка задачи: Найти 10 максимальное число из файла, который содержит миллиарды чиселКак эффективно найти 10 самых больших чисел из миллиардов чисел?

Вход: 97911 98855 12345 78982 ..... .....

Я на самом деле придумал ниже решение, которое имеет

лучший сложность случая O(n) - Когда файл имеет номера в порядке убывания
wors т случай сложности O(n*10) ~ O(n) Если файл имеет номера в порядке возрастания
Средняя сложность ~ O(n)

Пространство сложности во всех случаях

Я читаю этот файл с помощью ридера файла и отсортированный массив O(1) который хранит максимум 10 номеров. Я проверю, является ли currentLine больше, чем самый маленький элемент в массиве. Если это так будет вставляться в правильное положение путем замены.

Scanner sc = new Scanner(new FileReader(new File("demo.txt"))); 
int[] maxNum = new int[10]; 
    while(sc.hasNext()){ 
    int phoneNumber = Integer.parseInt(sc.nextLine()); 
    if(phoneNumber>maxNum[9]){ 
     maxNum[9] = phoneNumber; 
     for(int i =9;i>0;i--){ 
      if(maxNum[i]>maxNum[i-1]){ 
       int temp = maxNum[i]; 
       maxNum[i] = maxNum[i-1]; 
       maxNum[i-1] = temp; 
      } 
     } 
    } 
    }

Я ищу обратную связь, если есть более эффективные способы реализации этого

источник

2017-01-15 AdityaReddy

FYR, 'O (n * 10)' - это то же самое, что и 'O (n)'. – DyZ

Вы можете использовать встроенные методы, чтобы найти максимальное значение, всякий раз, когда вы нашли максимальное значение, сохраните это значение, затем удалите его, а затем повторите его 10 раз. – Null

@Null. .Когда вы построили метод, вы предлагаете .. ему не потребуется несколько проходов и больше итераций. – AdityaReddy

Если файл не отсортирован, вы должны смотреть, по крайней мере один раз в каждом номере в файл, так как это может быть одним из 10 крупнейших. Поэтому O (n) - лучшее, что вы можете достичь.

Возможна некоторая оптимизация (без изменения асимптотической сложности) путем замены массива maxNum на мини-кучу. Это будет работать быстрее, если количество найденных чисел достаточно велико (скажем, вы ищете 100 самых больших номеров). Это, вероятно, еще не окупится на 10.

источник

2017-01-15 07:43:08 Henry

Yupp, Thats true, если maxNumbers необходимо больше .. Но для 10 чисел, как вы сказали, массивы будут намного быстрее – AdityaReddy

Я не вижу причин, почему бы не использовать 'min heap' здесь, эта реализация имеет * путь * больше затрат для операций подкачки нет необходимости держать их в упорядоченном порядке, просто делайте это * один раз * при опросе с вершины кучи. – Xlee

@ Xlee. .Конечно . . запустим некоторые базовые тесты и увидим разницу. – AdityaReddy

В общем, найти K наибольшее число из N чисел:

Сортировка чисел в O (N Lg N) времени, а затем взять K по величине. Если на диске имеется миллиард номеров, вам придется выполнять внешнюю (на диске) сортировку, такую как внешний MergeSort.
Используйте Min-Heap емкости K и сканируйте значения N. Сохраняйте K наибольшие значения в куче, из которых наименьшее из этих значений находится вверху. Время работы: O (N lg K). Вы можете сохранить Min-кучу в памяти при сканировании чисел с диска.
Используйте алгоритм выбора, чтобы найти (N-K) th наибольшее значение в ожидаемое время O (N). Алгоритм Quickselect, который использует алгоритм разделения Quicksort, также разбивает значения, такие, что наибольшие значения K находятся на одной стороне (N-K) -ой самой большой. Ожидаемое время работы: O (N). Однако этот алгоритм выбора находится в памяти.

источник

2017-01-15 08:30:04 stackoverflowuser2010

В ответе отсутствует главное дело с большими файлами и вместо этого предоставляется какая-то информация о википедии. Это только общая информация. –

@SaeedAmiri: В каждом из трех пунктов я четко упоминаю, как алгоритмы могут применяться к большим данным на диске. – stackoverflowuser2010

Я имею в виду, что основной задачей является сделать это параллельно, а не только одноразовый последовательный. –

Вы можете улучшить алгоритм с помощью многопоточности и распараллеливания. Это означает запуск, например. 20 потоков и разбить файл на 20 файлов и в каждой части найти самые большие 10 номеров. В конце найдите самые большие 10 чисел из этих 20 массивов (каждая из 10), которые вы поддерживали.

Дело в том, что операция считывается из файла или базы данных, не записывающей. Таким образом, возможно иметь доступ к различным частям файла через разные потоки параллельно. Даже если ваш вход был в памяти, это было быстрее, чем наивный поиск. Это все еще O (n), но в зависимости от количества потоков, которые они работают параллельно (например, t), он использует около n/t сравнения. и это означает, что это примерно t раз быстрее, чем наивный алгоритм.

В конце я должен сказать, что оптимизация бит в малом массиве бесполезна, так как основное время и главное - поддерживать большой файл, не поддерживающий небольшой массив.

источник

2017-01-15 09:52:43

Как эффективно найти 10 самых больших чисел из миллиардов чисел?

ответ

Смежные вопросы