Эффективный способ найти самые маленькие элементы от a до b в k массивах - PullRequest
Новая
       8

Эффективный способ найти самые маленькие элементы от a до b в k массивах

0 голосов
/ 08 июня 2018

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

Есть k несортированных массивов чисел длины м.Цель состоит в том, чтобы найти a-й до b-й наименьших элементов в массивах k эффективным и консервативным способом, учитывая a <<em> b <<em> m .В последующем вопросе «несортированные массивы» заменены на столбцы в разных таблицах в базе данных MySQL, какую возможную эффективную структуру данных можно использовать и каковы соответствующие алгоритмы поиска.

Приходят два возможных решенияс:

Первое: brute-force:

  1. Сначала найдите b-й наименьший элемент для каждого массива с помощью быстрого выбора.
  2. Затем найдите элементы, меньшие, чем b-й элемента каждого массива, и сохраните их в размере k * b B-дерево C .
  3. Затем найдите от a-го до b-го наименьших элементов в C .

Для первого шага по поиску b-го наименьшего элемента с помощью быстрого выбора среднее время составляет от O (км) до O (км * log (м)) всего.Шаг 2 временная сложность составляет O (км) .Последний шаг - найти элементы между a-th и b-th наименьшими элементами в C , принимая O ((ba) log (kb))) .Таким образом, всего требуется O (км) до O (км * log (м)) + O ((ba) log (kb)) во времени и O (кб) в пространстве.

Второе: рекурсивное вытаскивание наименьших элементов

Для каждого цикла выполните

  1. Найти наименьший элемент для всех k массивов, хранить в B-дереве C
  2. Найдите самый маленький элемент в C и вытолкнуть этот элемент из C , и из массива это происходит.
  3. Повторяйте до тех пор, пока не будут набраны цифры a-1 , затем перейдите к 4
  4. Сохраните значения из a до b при повторении от 1 до 2

Таким образом, вычислительная сложность составляет O (k * log (k)) + O (b * log (k)) с пространственной сложностью как O (max (k, ba)) .Кажется, это минимальная сложность пространства.

Каковы более эффективные способы сделать это?Особенно наихудший случай быстрого выбора - O (n ^ 2) , который кажется слишком большим, и для b = m / 2 прямо в медиане O (кб) в пространстве или O (b * log (k)) во времени считалось слишком большим.Для базы данных MySQL я предложил использовать B-дерево, которое дает быстрый выбор ранга в решении 1, в то время как в пространстве и времени все еще есть O (kb) , с запросами k в базу данных.,В то время как в решении 2 сказано, что b запросов в БД MySQL слишком велико, и вставка B-дерева равна O (log (m)) , где m может быть очень большим.

1 Ответ

0 голосов
/ 08 июня 2018

Один простой способ - создать максимальную кучу размером b .Затем запустите этот код: 

for arr in arrays // process each of the k arrays in turn
    for i = 0 to length(k)-1
        if heap.count < b
            heap.push(arr[i])
        else if (arr[i] < heap.peek())
            heap.pop()
            heap.push(arr[i])

Идея состоит в том, что вы заполняете максимальную кучу первыми b элементами.Затем для каждого другого элемента, если он меньше самого большого элемента в куче, вы удаляете самый большой элемент в куче с новым элементом.

Когда вы обработали все км предметов, самые маленькие b предметов находятся в куче, и, поскольку это максимальная куча, первые ba предметов, которые вы выберете, будут a th через b th элементов во всех k массивах. 

// all items have been processed, take the first *b - a* items from the max heap
for i = 0 to (b-a-1)
   result[i] = heap.pop()

Наихудший случай - O (km log b) для первого цикла и O (b log b) длявторой цикл, использующий O (b) дополнительную память.

Если вам разрешено уничтожать исходные массивы, вы можете написать собственный быстрый выбор, который индексирует массивы k как один массив,Это будет O (км) с использованием O (k) дополнительной памяти для косвенного индекса.Недостатком является то, что код индексации будет несколько медленнее.И, конечно же, эти элементы будут перемещаться между массивами.И вам, вероятно, понадобится O (b) дополнительная память для возвращаемого значения.Асимптотически это более эффективно, чем мой первоначальный выбор.Будет ли он работать быстрее - это совсем другой вопрос.

Еще одна возможность.Запустите метод build-heap для каждого из массивов k .Это было бы О (км).Затем выполните объединение, чтобы выбрать первые b элементов.Для слияния потребуется:

  • O (log m) для удаления каждого элемента из исходных массивов
  • O (log b) для добавления каждого элемента в кучу слияния
  • O (log b), чтобы удалить каждый элемент из кучи слияния

Вторым шагом будет O (b * (log m + log b + log b)).

Это дает всего O (км + b * (log m + log b + log b)), и вы будете использовать O (b) дополнительную память.Будет ли это быстрее, чем оригинальное предложение, сомнительно.Это зависит от отношений между b и m .Чем больше значение b , тем меньше вероятность, что оно будет быстрее.И код гораздо сложнее написать.

...