Я пытался решить проблему на InterviewStreet. Через некоторое время я определяю, что на самом деле трачу большую часть своего времени на чтение входных данных. Этот конкретный вопрос имел большой вклад, так что это имеет смысл. Что не имеет смысла, так это то, почему различные методы ввода имели такие разные характеристики:

Изначально у меня было:

std::string command;
std::cin >> command;

Замена сделала это заметно быстрее:

char command[5];
cin.ignore();
cin.read(command, 5);

Переписав все для использования scanf, он стал еще быстрее

char command;
scanf("get_%c", &command);

Все сказали, что я сократил время чтения ввода примерно на 1/3.

Мне интересно, есть такая разница в перфомансе между этими разными методами. Кроме того, мне интересно, почему использование gprof не выдвинуло на первый план то время, которое я тратил на ввод-вывод, а скорее показало вину за мой алгоритм.