Предисловие: В этой статье будет представлена идея случайного выбора, разделяй и властвуй, уменьшай и властвуй, а также все тонкости, принципы и детали оптимизации задачи TopK, чтобы гарантировать получение прибыли.
В интервью TopK один из самых часто задаваемых вопросов.Существует несколько методов,и какие идеи по оптимизации содержатся в этих решениях?Поговорим сегодня с вами.
Голос за кадром: Я никогда не задаю ТопКу этот вопрос во время собеседования, если только школа не вербует, и все его знают по умолчанию.
описание проблемы:
Из n чисел arr[1, n] найдите наибольшее число k, что является классической задачей TopK.
каштан:
Из arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} из n=12 чисел найдите наибольшее k=5.
1. Сортировка
Сортировка — это самый простой способ придумать: после сортировки n чисел вынуть наибольшее k, что и является результатом.
Поддельный код:
sort(arr, 1, n);
return arr[1, k];
временная сложность: O (n * lg (n))
анализировать: Очевидно, нужен только ТопК, но сортируется весь мир, из-за чего сложность этого метода очень высока. Можно ли его не сортировать глобально, а только локально? Это приводит ко второму методу оптимизации.
2. Локальная сортировка
Больше никакой глобальной сортировки, сортируются только самые большие k.
Всплывание — очень распространенный метод сортировки.Каждый раз, когда всплывает пузырь, находится максимальное значение, и для получения TopK всплывает k пузырьков.
Поддельный код:
for(i=1 to k){
bubble_find_max(arr,i);
}
return arr[1, k];
временная сложность: О(п*к)
анализировать: Всплывающие, оптимизирует глобальную сортировку для локальной сортировки, элементы, не относящиеся к TopK, не нужно сортировать, что экономит вычислительные ресурсы. Многие друзья подумают, что спрос — это TopK, значит, самые большие k элементов не нужно сортировать? Это приводит к третьему методу оптимизации.
Три, куча
идеи: Найти только TopK, не сортировать TopK.
Сначала генерируются первые k элементов небольшой вершины стопки, вершина кучи для хранения small, текущий максимум из k элементов.
Затем начните сканирование с k + 1-го элемента и сравните его с вершиной кучи (самый маленький элемент в куче).Если сканируемый элемент больше, чем вершина кучи, замените элемент на вершине кучи. и отрегулируйте кучу, чтобы убедиться, что k в элементах кучи всегда является текущим наибольшим k элементов.
Пока, после сканирования всех n-k элементов, k элементов в конечной куче не будут TopK непристойного запроса.
Поддельный код:
heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
adjust_heap(heep[k],arr[i]);
}
return heap[k];
временная сложность: О (п * lg (к))
Голос за кадром: N элементов сканируются один раз, если не повезет, каждый раз, когда они помещаются в кучу, а временная сложность корректировки равна высоте кучи, то есть lg(k), поэтому общая временная сложность равна n* лг(к).
анализировать: куча, оптимизирует всплывающую сортировку TopK, чтобы TopK не сортировался, экономя вычислительные ресурсы. Куча — это классический алгоритм поиска TopK, есть ли более быстрое решение?
4. Случайный выбор
Случайный выбор — это классический алгоритм из «Введения в алгоритмы», и его временная сложность составляет O(n), что является методом линейной сложности.
Не все студенты знают этот метод. Чтобы подробно объяснить алгоритм, давайте сначала поговорим о некоторых предварительных знаниях. Классический алгоритм, с которым должны быть знакомы все программисты: быстрая сортировка.
Голос за кадром:
(1) Если друг говорит: «Я не знаю быстрой сортировки, это не мешает мне писать бизнес-код»… гм…
(2) Если только школа не набирает сотрудников, я никогда не прошу быстрой сортировки во время собеседования, и все инженеры знают об этом по умолчанию;
Его псевдокод:
void quick_sort(int[]arr, int low, inthigh){
if(low== high) return;
int i = partition(arr, low, high);
quick_sort(arr, low, i-1);
quick_sort(arr, i+1, high);
}
Основная идея алгоритма — метод «разделяй и властвуй».
разделяй и властвуй(разделяй и властвуй), превращай большую проблему в несколько подзадач (разделяй), каждая подзадача»Все«Решите, и большая проблема будет решена (Победа). Ключевое слово здесь —"Все". Как видно из псевдокода, при быстрой сортировке рекурсивно массив сначала делится на две части по разделам, и две части «обе» приходится рекурсировать заново.
Существует особый случай принципа «разделяй и властвуй», который называется сокращением и правилом.
Редукция и лечение(Reduce & Conquer), преобразовать большую проблему в несколько подзадач (Reduce), в этих подзадачах "Только«Решите одну, и будет решена большая проблема (Победа). Ключевое слово здесь —"Только".
бинарный поиск binary_search, BS, представляет собой типичный алгоритм, использующий идею вычитания и завоевания, и его псевдокод:
int BS(int[]arr, int low, inthigh, int target){
if(low> high) return -1;
mid= (low+high)/2;
if(arr[mid]== target) return mid;
if(arr[mid]> target)
return BS (arr, low, mid-1, target);
else
return BS (arr, mid+1, high, target);
}
Как видно из псевдокода, бинарный поиск, большую задачу, можно разделить на две подзадачи в левой и правой половине с помощью среднего элемента. Что касается левой и правой подзадач, то нужно решить только одну из них, а глобальную задачу бинарного поиска можно решить, рекурсив один раз.
Из описания методов «разделяй и властвуй» и «сокращай и властвуй» можно обнаружить, что сложность метода «разделяй и властвуй», как правило, выше, чем у метода «сокращай и властвуй»:
Быстрая сортировка: O(n*lg(n))
Двоичный поиск: O (lg (n))
Вернемся к теме,быстрая сортировкаЯдро:
i = partition(arr, low, high);
Для чего этот раздел?
Как следует из названия, раздел делит целое на две части.
В частности, элемент в массиве arr (по умолчанию это первый элемент t=arr[low]) используется в качестве основы деления для разделения данных arr[low, high] на два подмассива:
-
Левая половина больше, чем T
-
Правая половина меньше, чем t
-
Средняя позиция i является разделительным элементом
Взяв в качестве примера приведенный выше массив TopK, сначала используйте первый элемент t=arr[low] в качестве основы деления, просканируйте массив один раз и разделите массив на две половины:
-
Левая половина больше, чем t
-
Правая половина меньше, чем t
-
середина т
раздел возвращает конечную позицию i из t.
Легко понять, что временная сложность разбиения равна O(n).
Голос за кадром: Проведите по всему массиву, поместите большее, чем t, слева, меньшее, чем t, справа и, наконец, поместите t в середину N[i].
Какая связь между разделом и проблемой TopK?
TopK состоит в том, чтобы найти наибольшее число k в arr[1,n], тогда, если найденоk-й по величинеЕсли вы сделаете разбиение один раз, разве вы не найдете наибольшее число k за один раз?
Голос за кадром: количество k в левой половине раздела.
Задача состоит в том, чтобы найти k-е наибольшее число в arr[1, n].
оглянуться назад сновапервый разраздел после деления:
i = partition(arr, 1, n);
-
Если i больше k, это означает, что элементы слева от arr[i] больше k, поэтому рекурсивным может быть только k-й самый большой элемент в arr[1, i-1];
-
Если i меньше k, это означает, что k-й самый большой элемент находится справа от arr[i], поэтому рекурсивным может быть только k-й самый большой элемент в arr[i+1, n];
Голос за кадром: Этот абзац очень важен, поэтому прочитайте его несколько раз.
Этослучайный выборАлгоритм randomized_select, RS, его псевдокод выглядит следующим образом:
int RS(arr, low, high, k){
if(low== high) return arr[low];
i= partition(arr, low, high);
temp= i-low; //Количество элементов в первой половине массива
if(temp>=k)
Возвращаем RS(arr, low, i-1, k);//находим k-й наибольший в первой половине
else
return RS(arr, i+1, high, k-i); // находим наибольшее k-i во второй половине
}
Это типичный алгоритм сокращения и завоевания, две ветви в рекурсии, только одна будет выполнена в конце, и его временная сложность равна O(n).
Еще раз подчеркнуть:
-
разделяй и властвуй, большая проблема разбивается на маленькие задачи, а маленькие задачи должны быть рекурсивны к каждой ветке, например: быстрая сортировка
-
Редукция и лечение, большая проблема разбивается на маленькие проблемы, а маленьким проблемам нужно только рекурсивно ветку, например: бинарный поиск, случайный выбор
Путем случайного выбора (randomized_select) найдите k-е наибольшее число в arr[1, n] и снова выполните разбиение, чтобы получить результат TopK.
V. Резюме
TopK не сложен, процесс оптимизации его идей не прост:
-
глобальная сортировка, О (п * lg (п))
-
частичный заказ, сортировать только числа TopK, O(n*k)
-
куча, количество TopK не отсортировано, O(n*lg(k))
-
Метод «разделяй и властвуй», каждая ветвь «рекурсивна», например: быстрая сортировка, O (n * lg (n))
-
Метод вычитания и завоевания, «до тех пор, пока» рекурсивная одна ветвь, например: бинарный поиск O (lg (n)), случайный выбор O (n)
-
Другое решение для TopK:случайный выбор+partition
Знай это, знай почему.
Идеи важнее выводов.
Надеюсь, у всех появилось новое понимание TopK, спасибо.
Архитектор дороги- Делитесь практическими статьями об архитектуре
связанное предложение:
"Как реализовать нижний слой индекса базы данных?》В+ дерево
"Нижний слой поисковых систем, как добиться?》Перевернутый индекс
"Задача синхронизации 10 Вт, как ее достичь?》HWTimer
вырыть яму: TopK, как вы думаете, это самое быстрое решение? Слишком недооценивать дороги архитекторов, более быстрые решения и слушать очередной вопрос разложения.