помогите с эффективностью обхода карты с ++ - PullRequest
Новая
       11

помогите с эффективностью обхода карты с ++

0 голосов
/ 12 мая 2011

У меня есть карта, определенная как 

map<string,map<string,int> > subjectCodes;

каждая строка темы имеет свою собственную карту курсов

У меня также есть 2 итератора, определенных 

map<string,map<string,int> >::iterator it;
map<string,int>::iterator jt;

от одного доитерации по каждому предмету и по одному для итерации по каждому курсу по каждому предмету

Мне нужно, чтобы моя программа прочитала 50000 строк информации, отсортировала их на карте и распечатала все за менее чем 1 секунду.Я думаю, что нашел самый быстрый способ добавить все на карту, но я изо всех сил пытаюсь ускорить печать, которая в данный момент равна 0 (n в квадрате) и заставляет мою программу запускаться около 3 секунд.

вот мой печатный код: 

//print out sorted list
for(it=subjectCodes.begin();it!=subjectCodes.end();it++)
{
    cout<<it->first<<": "<<(it->second).size()<<" courses"<<endl;
    for(jt=(it->second).begin();jt!=(it->second).end();jt++)
    {
        cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<<endl;
    }
}

есть ли более эффективный способ печати карты на карте, который кто-то может показать мне?Спасибо

Ответы [ 4 ]

3 голосов
/ 12 мая 2011

Простое сохранение эффективности: 

   cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<<endl;

должно быть: 

   cout<<"  "<<jt->first<<": "<<jt->second<<" classes"<< '\n';

Манипулятор endl очищает поток, что может быть очень дорогой операцией, если вы неТебе не нужен флеш.Вы легко сможете записать 50К строк в поток за минуту, хотя, возможно, не в поток, подключенный к какому-либо терминалу (то есть к окну приглашения xterm или Windows cmd).

2 голосов
/ 12 мая 2011

Я не могу сказать, как выглядят ваши данные, но вам, возможно, повезет больше с "составными ключами".То есть вместо использования карты, полной карт, объедините два ключа вместе и используйте результат в качестве ключа в одной карте.

Кроме того, если вы не изменяете карту после ее создания, подумайтевместо этого используется отсортированный вектор (используя std::sort и std::binary_search).Когда вы выполняете итерацию данных, все они находятся в памяти и вы получаете лучшую производительность кеша.

0 голосов
/ 12 мая 2011

Если у вас проблемы с производительностью, важно идти за низко висящими фруктами. Чтобы сделать это, вам нужно выяснить, где находятся узкие места вашего алгоритма. Что занимает слишком много времени?

Как только вы выяснили, что занимает время, вы можете начать задавать более конкретные вопросы. Как правило, переходить к низко висящим фруктам означает, что вам нужно решать простые задачи, которые сильно влияют на скорость вашего алгоритма. Два примера этого уже были указаны в этом потоке (замените std :: endl на '\ n', чтобы уменьшить количество сбрасываний, и используйте printf вместо std :: cout, чтобы уменьшить количество вызовов функций / другой алгоритм).

Еще несколько возможностей:

  • Используйте поток строк и запишите это в одной операции
  • Перепроектируйте вашу структуру, чтобы она стала быстрее, чем вы обычно ее используете (можно ли использовать вектор вместо карты на втором уровне?)
  • Что-то совершенно не связанное с блоком кода, который вы написали;)
0 голосов
/ 12 мая 2011

Задумывались ли вы о распараллеливании вашего приложения, например, с потоками или OpenMP?

другой совет: функция printf() может быть быстрее, чем опция потоковой передачи.

также, вы компилировали с полной оптимизацией? это также может значительно повысить производительность.

...