найти 100 самых больших чисел из всех файлов, представленных в разных папках

Question

Недавно у меня было интервью, в котором меня задавали нижеуказанный вопрос, и он звучал довольно легко для меня, но потом, в конце концов, мне стало сложно.

Во всех папках много файлови их подпапки.Каждый файл будет иметь много номеров в каждой строке.Учитывая корневую папку, мне нужно найти 100 наибольшее число из всех этих файлов.Я пришел к следующему решению:

• Читать все файлы построчно.
• Сохранять каждое число в списке массивов.
• Сортировать его в порядке убывания.
• Теперь получите первые k чисел из списка.

Но затем интервьюер спросил меня, какова будет сложность времени для этого.Я сказал, так как мы сортируем это, так что это будет O (nlogn), а затем он спросил, как мы можем улучшить программу ниже?Так как вы храните все в памяти, а затем сортируете это - что, если вы не можете уместить все в памяти?

Тогда я был озадачен и не мог понять, существует ли какой-либо лучший / эффективный способ решения проблемы.ниже проблема.Он хотел, чтобы я написал эффективный код.Есть ли лучший способ сделать это?

Ниже приведен мой оригинальный код:

  private static final List<Integer> numbers = new ArrayList<>();

  public static void main(String[] args) {
    int k = 100;
    List<Integer> numbers = findKLargest("/home/david");

    // sort in descending order
    Collections.sort(numbers, Collections.reverseOrder());
    List<Integer> kLargest = new ArrayList<>();
    int j = 0;
    // now iterate all the numbers and get the first k numbers from the list
    for (Integer num : numbers) {
      j++;
      kLargest.add(num);
      if (j == k) {
        break;
      }
    }
    // print the first k numbers
    System.out.println(kLargest);
  }

  /**
   * Read all the numbers from all the files and load it in array list
   * @param rootDirectory
   * @return
   */
  private static List<Integer> findKLargest(String rootDirectory) {
    if (rootDirectory == null || rootDirectory.isEmpty()) {
      return new ArrayList<>();
    }

    File file = new File(rootDirectory);
    for (File entry : file.listFiles()) {
      if (entry.isDirectory()) {
        numbers.addAll(findKLargest(entry.getName()));
      } else {
        try (BufferedReader br = new BufferedReader(new FileReader(entry))) {
          String line;
          while ((line = br.readLine()) != null) {
            numbers.add(Integer.parseInt(line));
          }
        } catch (NumberFormatException | IOException e) {
          e.printStackTrace();
        }
      }
    }
    return numbers;
  }

Answer 1

При добавлении в @MBo реализация Java выглядит следующим образом:

Использование PriorityQueue

Создание минимальной кучи с использованием очереди приоритетов размером 100

int MAX = 100;
PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);

Считать числа из файлов, вставить и сбалансировать min-heap.Сравните minValue в min-heap с newValue.Если больше, то удалите minValue и вставьте newValue.

public void balanceMinHeap(int newValue) {

    if(queue.size() < MAX) {
        queue.add(newValue);
        return;
    }

    if(queue.peek() < newValue) {
        queue.remove();
        queue.add(newValue);
    }

}

Теперь вы можете получить 100 самых больших чисел из min-heap в порядке возрастания

    for(int i=0;i<100;i++) {
        System.out.println(queue.remove());
    }

Если вы хотите те же самые 100 самых большихчисла в порядке убывания, просто преобразуйте одну и ту же очередь в max-Heap (т. е. снова в PriorityQueue)

Comparator<Integer> desendingOrder = new Comparator<Integer>() {
    public int compare(Integer x, Integer y) {
         return y - x;
     }
};

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(MAX, desendingOrder);

или просто используйте встроенную Collections.reverseOrder

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(MAX, Collections.reverseOrder());

Answer 2

Вместо хранения всех значений N (общее количество чисел во всех файлах) и их сортировки, вы можете хранить только 100 значений - самые большие в каждый момент.

Удобно ибыстрая структура данных для этой задачи - приоритетная очередь (обычно на основе двоичная куча ).Создайте min -heap со 100 первыми значениями, затем для каждого нового значения проверяйте, больше ли оно вершины кучи.Если да - удалите верхнюю часть, вставьте новый элемент.

Сложность пространства O(K), сложность времени O(NlogK), здесь K=100, поэтому сложности могут оцениваться как O(1) и O(N) (без учетапостоянный член)

Пример Python, чтобы показать, как он работает:

import heapq, random

pq = [random.randint(0, 20) for _ in range(5)]  #initial values
print(pq)
heapq.heapify(pq)                               #initial values ordered in heap
print(pq)
for i in range(5):
    r = random.randint(0, 20)    # add 5 more values
    if r > pq[0]:
        heapq.heappop(pq)
        heapq.heappush(pq, r)
    print(r, pq)

[17, 22, 10, 1, 15]   //initial values
[1, 15, 10, 22, 17]   //heapified, smallest is the left
29 [10, 15, 17, 22, 29]     //29 replaces 1
25 [15, 22, 17, 29, 25]     //25 replaces 10
14 [15, 22, 17, 29, 25]      //14 is too small
8 [15, 22, 17, 29, 25]       //8 is too small
21 [17, 21, 25, 29, 22]     //21 is in the club now