Ищете лучший способ сортировки данных

У меня есть алгоритм, который обрабатывает файл по 6 различным переменным параметрам. Алгоритм создает истинный/ложный результат для файла для каждого набора параметров. Я запускаю этот алгоритм через набор файлов, получая в результате true/false в векторе (а также некоторые дополнительные, нерелевантные данные).Ищете лучший способ сортировки данных

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

while(!results.isEmpty()){ //results being a vector of the individual file results 
    for (long i = 0; i < params.size(); i++){ //params being a vector of the parameters 
    if (results.first().params... == params[i].params...){ 
     params[i].numFiles++; 
     if (results.first().result){ 
     params[i].numTrue++; 
     } 
     results.pop_front(); 
     break; 
    } 
    } 
}

Это выполняет свою работу, но теперь, когда я оптимизирован мой алгоритм, это последний перегруженный в моем коде, и я ищу пути к ускорьте это. Каким будет лучший способ опрокинуть эти данные? Если это актуально, на данный момент я использую Qt, а мои векторы в настоящее время QVector.

источник

2015-09-03 user3830784

Является ли 'results' a [' std :: vector'] (http://en.cppreference.com/w/cpp/container/vector)? Затем просто используйте ['std :: sort'] (http://en.cppreference.com/w/cpp/algorithm/sort). Если это контейнер Qt, я уверен, что у Qt есть и некоторые функции сортировки. –

Даже с Qt-контейнерами, поскольку Qt 5 рекомендуется использовать STL поверх Qt Algos. [Источник] (http://doc.qt.io/qt-5/qtalgorithms.html) –

quicksort может помочь вам – mryuso92

Ваш алгоритм имеет сложность O (NxM), где N - размер результата, а M - размер параметра.

Если то, что вы сравниваете здесь:

if (results.first().params... == params[i].params...){

поддерживает меньше оператора вы можете сортировать Params перед первой петлей. И вместо того, чтобы проходить через все его элементы, просто выполните двоичный поиск. Сложностью будет тогда O (Nxlog (M)).

источник

2015-09-03 14:37:06 Brahim

Если есть готовые PARAMS для сравнения

если (results.first(). PARAMS ... == Титулы [я] .params ...)

в каждом результате вы можете хранить 6 Params в хэш-таблице и поиска с помощью хэш-таблицы каждой итерации

время (! results.isEmpty())

, который дает сложность O (N)

но фактически реальное исполнение зависит от хеш-функции. Иногда O (N log M) может быть лучше; это зависит от времени операции. Так что лучше проверить эффективность на практике после оптимизации.

Дополнительная информация: текущая сложность O (N) в любом случае потому, что число параметров (6 параметров) является константой.

источник

2015-09-03 14:54:31 Sparrow

Ищете лучший способ сортировки данных

ответ

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