Эффективность алгоритма: поиск 5 самых больших элементов в массиве

typedef std::map<uint16_t, uint32_t> TSrcMap;
TPSrcMap sp;
TSrcMap::iterator its;
/*Code to populate the array_start.*/

/*Code to populate the array_end.*/

typedef struct port_count
{
        uint32_t port_number;
        uint32_t port_count;
}port_count_t;

port_count_t pcount[5];
memset(pcount,0,sizeof(pcount));
size_t structs_len = sizeof(pcount)/sizeof(port_count_t);
for(its = stcp.begin(); its != stcp.end();its++)
{
      if(pcount[smallest_index].port_count < (*its).second)
      {
            pcount[smallest_index].port_count = (*its).second;
            pcount[smallest_index].port_number = (*its).first;
#ifdef USEQSORT
            qsort(pcount, structs_len, sizeof(port_count_t), struct_cmp_by_port_count);
#else
            std::sort(pcount,(pcount+structs_len),cmp_by_port_count);
#endif
      }
}


#ifdef USEQSORT
/* qsort struct comparision function compare port frequency*/
int struct_cmp_by_port_count(const void *a, const void *b)
{
        port_count_t *ia = (port_count_t *)a;
        port_count_t *ib = (port_count_t *)b;
        return (ia->port_count - ib->port_count);
}
#else
/* qsort struct comparision function compare port frequency*/
int cmp_by_port_count(const port_count_t& a, const port_count_t& b)
{
        return (a.port_count < b.port_count);
}
#endif

У меня есть большая структура std::map, которая отображает port_count на port_number. Я должен найти 5 самых больших элементов, основанных на port_count. (Где key это номер_порта). У меня есть один цикл анализа, приведенный выше, который вызывает алгоритм сортировки (qsort или std::sort) для массива размером 5. Это самый эффективный способ достичь этого? С точки зрения количества обращений к функции сортировки. Есть ли лучший способ сделать это с точки зрения вычислительной эффективности? Кроме того, я попробовал и qsort, и std:: sort, и они, похоже, работают примерно одинаково. Это потому, что размер сортируемого массива слишком мал, чтобы оказать существенное влияние. Я пытаюсь понять этот алгоритм в Условия его сложности. Любые мысли будут оценены.

Источник

6 ответов

Решение

Вы должны взглянуть на один из моих любимых часто пропускаемых алгоритмов STL: nth_element ( ссылка) Он частично сортирует данные в среднем по O(N) по сравнению с O(N log (N)) для быстрой сортировки, так что точка поворота (n-й элемент) больше, чем все элементы на одной стороне, и меньше, чем все элементы на другой, Ускорение по сравнению с быстрой сортировкой может быть весьма значительным при больших входах.

РЕДАКТИРОВАТЬ: если вы хотите отсортировать определенный диапазон, например, 5 самых больших элементов, вы можете использовать partial_sort ( ссылка):

std::partial_sort(large_container.begin(), large_container.begin() + 5, large_container.end(), comparison_function);

Частично отсортирует large_container по O (n + 5 * log (5)), так что первые пять элементов являются самыми большими элементами в large_container в порядке убывания (или наименьшими элементами в порядке возрастания в зависимости от функции сравнения). Это, вероятно, заменит значительную часть вашего кода выше.

Источник

Начните с полученной в результате deque, который изначально пуст и будет сохраняться отсортированным в течение всего алгоритма:

  1. Траверса
  2. Для текущего элемента:
    • Вставьте его в правильное место в получившейся деке, чтобы порядок был сохранен.
    • Если получившаяся дека содержит более 5 элементов, удалите минимальный элемент. Поскольку deque сортируется, это всегда первый элемент (или последний, в зависимости от "направления" сортировки).

В конце концов, получившаяся дека содержит (до) 5 самых больших элементов. По сути, это алгоритм O(n).

Вместо deque, вы можете использовать вектор с нисходящими элементами и удалить из конца, или даже связанный список (хотя погоня за указателем никогда не влияет на производительность).

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

Источник

Почему вы сортируете? Вы делаете это намного сложнее, чем нужно.

Создайте дерево из 5 элементов - это ваши 5 самых больших элементов. (Используйте std::set) Просто зациклите содержимое, и каждый раз, когда вы найдете число, большее, чем наименьшее число в дереве, добавьте его в дерево и удалите любое переполнение (числа один раз в верхних 5, больше не существует).)

Вот что я нарисовал в блокноте за две минуты, без компиляции:

#include <set>
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
    int unordered[] = {7, 12, 11, 19, 88, 42, 3, 1, 22};

    set<int> biggest5;
    int smallest = -1;

    for(int i = 0; i < sizeof(unordered)/sizeof(int); ++i)
    {
        if (unordered[i] >= smallest)
        {
            biggest5.insert(unordered[i]);

            if(biggest5.size() > 5)
                biggest5.erase(biggest5.begin());

            smallest = *biggest5.begin();
        }
    }

    //All done
    cout << "Set: ";
    for (set<int>::reverse_iterator i = biggest5.rbegin(); i != biggest5.rend(); ++i)
    {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

Это должно напечатать

Set: 88 42 22 19 12

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

Источник

Другое решение, о котором я подумал, - это использовать priority_queue, который имеет смысл, учитывая, что вы ищете элементы с более высоким приоритетом.

    #include <queue>

    int main(){
       priority_queue<int> q;
       int a[] = {7, 12, 11, 19, 88, 42, 3, 1, 22};
       for(int i=0;i<sizeof(a)/sizeof(int);i++){
                q.push(a[i]);
       }
       for(int i=0;i<5;i++){
         cout<<q.top()<<endl;
         q.pop();
       }
       return 0;
    }

Обратите внимание, что priority_queue внутренне реализован как куча, а pop_heap работает в логарифмическом времени.

Источник

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

Источник

std::sort, скорее всего, будет использовать QuickSort или, по крайней мере, вариант QuickSort, называемый IntroSort, который "вырождается" в HeapSort, когда рекурсия идет слишком глубоко. Так что оба будут работать за O(nlogn) время. Поэтому не имеет значения, какой из них вы выберете (если ваша собственная быстрая сортировка реализована правильно).

Источник
Другие вопросы по тегам