У меня был спор с коллегой о реализации простого парсера строк.
Один «маленький», 10 строк кода с использованием c ++ и потоков, другой - 70 строк кода,
использование переключателей и итерация строки char по char.
Мы проверили это более 1 миллиона итераций и измерили скорость с помощью команды времени.
Похоже, что длинный и уродливый подход в среднем на 1 секунду быстрее.
Проблема:
Ввод: строка
"v=spf1 mx include:_spf-a.microsoft.com include:_spf-b.microsoft.com include:_spf-c.microsoft.com include:_spf-ssg-a.microsoft.com ip4:131.107.115.212 ip4:131.107.115.215 ip4:131.107.115.214 ip4:205.248.106.64 ip4:205.248.106.30 ip4:205.248.106.32 ~all a:1.2.3.4"
Выход:
map<string, list<string>> со всеми значениями для каждого ключа, такими как: ip4, include, a
пример вывода одной итерации в приведенной выше строке ввода:
ключ:
1.2.3.4,
ключ: включить
_spf-a.microsoft.com, _spf-b.microsoft.com, _spf-c.microsoft.com, _spf-ssg-a.microsoft.com,
ключ: ip4
131.107.115.212, 131.107.115.215, 131.107.115.214, 205.248.106.64, 205.248.106.30, 205.248.106.32,
Парсер "маленький - это красиво":
istringstream iss(input);
map<string, list<string> > data;
string item;
string key;
string value;
size_t pos;
while (iss.good()) {
iss >> item;
pos = item.find(":");
key = item.substr(0,pos);
data[key].push_back(item.substr(pos+1));
}
Второй более быстрый подход:
typedef enum {I,Include,IP,A,Other} State;
State state = Other;
string line = input;
string value;
map<string, list<string> > data;
bool end = false;
size_t pos = 0;
while (pos < line.length()) {
switch (state) {
case Other:
value.clear();
switch (line[pos]) {
case 'i':
state = I;
break;
case 'a':
state = A;
break;
default:
while(line[pos]!=' ' && pos < line.length())
pos++;
}
pos++;
break;
case I:
switch (line[pos]) {
case 'p':
state = IP;
break;
case 'n':
state = Include;
break;
}
pos++;
break;
case IP:
pos+=2;
for (;line[pos]!=' ' && pos<line.length(); pos++) {
value+=line[pos];
}
data["ip4"].push_back(value);
state = Other;
pos++;
break;
case Include:
pos+=6;
for (;line[pos]!=' ' && pos<line.length(); pos++) {
value+=line[pos];
}
data["include"].push_back(value);
state = Other;
pos++;
break;
case A:
if (line[pos]==' ')
data["a"].push_back("a");
else {
pos++;
for (;line[pos]!=' ' && pos<line.length(); pos++) {
value+=line[pos];
}
}
data["a"].push_back(value);
state = Other;
pos++;
break;
}
}
Я искренне верю, что «маленький - это красиво», и мне не нравится более длинный код, представленный здесь, но с этим трудно поспорить, когда код работает быстрее.
Можете ли вы предложить способы оптимизировать или полностью переписать небольшой подход, таким образом, чтобы он оставался маленьким и красивым, но при этом работал быстрее?
Обновление:
Добавлено определение состояния и инициализация.
Контекст: чем дольше подход выполняет 1 миллион итераций на одной и той же строке за 15,2 секунды, тем меньше код делает то же самое в среднем за 16,5 секунды.
обе версии скомпилированы с g ++ -O3, g ++ - 4.4,
работает на процессоре Intel® Core ™ 2 Duo E8200 с частотой 2,66 ГГц, Linux Mint 10
Хорошая сторона выиграла эту битву :) Я обнаружил небольшую ошибку в маленькой программе, она добавляла на карту даже недопустимые значения, те, у которых в строке не было двоеточия ":".
После добавления оператора if для проверки наличия двоеточия меньший код выполняется быстрее, намного быстрее. Теперь время: «маленький и красивый»: 12,3, а длинный и некрасивый: 15,2.
Маленькое - это красиво :) 1041 *