Оптимизация приоритетной очереди потоковый алгоритм в C++


Это алгоритм сортировки, который я написал для нахождения максимального \ФП\$ элементов в любой момент времени в потоке идентификаторы и целые числа неопределенной длины. Я в первую очередь делаю свою кодирования в Python, так что я не слишком хорошо знакомы с C++ лучшей практики, но я хотел написать это в C++, чтобы получить некоторую эффективность и скорость.

Для всех вас, опытных программистов C++; я следующие рекомендации здесь или нет? Если нет, то какие улучшения я могу сделать чтобы сделать это более профессионально? Наконец, есть какие-то оптимизации, что я могу сделать, чтобы увеличить его скорость?

#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <map>
#include <chrono>

// Overload comparison operator to create a min heap
struct compare
{
  bool operator()(const int& l, const int& r)
  {
    return l > r;
  }
};

int main()
{
  // Input filenames
  std::cout << "Enter a filename for the input stream: ";
  std::string filename;
  std::cin >> filename;
  std::ifstream infile(filename);

  std::cout << "Enter a filename for the output stream: ";
  std::string output;
  std::cin >> output;
  std::ofstream outfile(output);

  // Input a value for k
  std::cout << "Enter a value for k: ";
  int k;
  std::cin >> k;
  std::cout << std::endl;

  // Declare priority queue and map
  int elements = 0;
  int replacements = 0;
  int value;
  std::string id;
  std::priority_queue<int, std::vector<int>, compare> heap;
  std::map<int, std::vector<std::string>> ids;

  // Begin read/sort timer
  std::cout << "Beginning read and sort ..." << std::endl;
  auto readsortstart = std::chrono::high_resolution_clock::now();

  // Begin read and sort
  while (infile >> id >> value){
    elements++;
    if (heap.size() < k){
      ids[value].push_back(id);
      heap.push(value);
    } else if (heap.top() < value) {
      ids[value].push_back(id);
      heap.pop();
      heap.push(value);
      replacements++;
    }
  }

  // End timer
  auto readsortstop = std::chrono::high_resolution_clock::now();
  auto readduration = std::chrono::duration_cast<std::chrono::milliseconds>(readsortstop-readsortstart).count();
  std::cout << "Read and sort completed." << std::endl << std::endl;

  // Ensure that k is not larger than the total number of lines
  k = std::min(k,elements);

  // Begin write timer
  std::cout << "Beginning write ..." << std::endl;
  auto writestart = std::chrono::high_resolution_clock::now();

  // Pop k entries off of the sorted heap to retrieve the k largest results
  for (int i = 0; i < k; i++) {
    int key = heap.top();
    outfile << ids[key].back() << " " << heap.top() << std::endl;
    ids[key].pop_back();
    heap.pop();
  }

  // End write timer
  auto writestop = std::chrono::high_resolution_clock::now();
  auto writeduration = std::chrono::duration_cast<std::chrono::milliseconds>(writestop-writestart).count();
  std::cout << "Write completed." << std::endl << std::endl;

  std::cout << "----------------------- Statistics ------------------------" << std::endl 
            << "  Total number of replacements: " << replacements << std::endl
            << "  Total number of elements:     " << elements << std::endl
            << "  Read/sort time elapsed:       " << readduration << "ms" << std::endl
            << "  Write time elapsed:           " << writeduration << "ms" << std::endl;
}


223
5
задан 31 марта 2018 в 08:03 Источник Поделиться
Комментарии
1 ответ

Вы можете создать

struct Element {
int value;
std::string id;
};

и магазин, что в приоритетной очереди. Тогда вам не нужна карта. Сравнивайте ваши функции будет, конечно, только взглянуть на value компонент:

struct compare {
bool operator()(const Element& l, const Element& r) {
return l.value > r.value;
}
};

Обратите внимание, что можно использовать голую функцию, как компаратор, для этого не нужно быть функтором:

bool compare(const Element& l, const Element& r) {
return l.value > r.value;
}

std::priority_queue<Element, std::vector<Element>, decltype(compare)> heap(compare);

2
ответ дан 1 апреля 2018 в 02:04 Источник Поделиться