Ответ 1
Эта реализация должна быть быстрой:
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
n = std::min(n, s.size());
std::string ret;
ret.reserve(2*n);
ret.append(s.begin(), s.begin() + n);
ret.append(s.end() - n, s.end());
return ret;
}
передает все три модульных теста.
При использовании GNU libstdС++ строка, которая объявляет и инициализирует ret, чрезвычайно быстро, потому что libstdС++ использует глобальную переменную "пустая строка". Таким образом, это просто копия указателя. Вызовы begin и end на s также бывают быстрыми, потому что они будут разрешены для версий const begin и end, begin() const и end() const, поэтому внутреннее представление s равно не "просочился". С libstdС++ std::string::const_iterator есть const char*, который является типом указателя и итератором произвольного доступа. Таким образом, когда std::string::append<const char*>(const char*, const char*) вызывает std::distance, чтобы получить длину диапазона ввода, это операция разницы указателей. Кроме того, std::string::append<const char*>(const char*, const char*) приводит к чему-то вроде memmove. Наконец, операция reserve обеспечивает достаточное количество памяти для возвращаемого значения.
EDIT:
Для любопытных, вот инициализация ret в сборочном выходе MinGW g++ 4.5.0:
movl $__ZNSs4_Rep20_S_empty_rep_storageE+12, (%ebx)
Он просто копирует указатель на глобальное "пустое представление".
EDIT2: Хорошо. Теперь я протестировал четыре варианта с g++ 4.5.0 и Visual С++ 16.00.30319.01:
Вариант 1 (вариант "c_str" ):
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
std::string::size_type s_size = s.size();
n = std::min(n, s_size);
std::string ret;
ret.reserve(2*n);
const char *s_cStr = s.c_str(), *s_cStr_end = s_cStr + s_size;
ret.append(s_cStr, s_cStr + n);
ret.append(s_cStr_end - n, s_cStr_end);
return ret;
}
Вариант 2 (вариант "строка данных" ):
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
std::string::size_type s_size = s.size();
n = std::min(n, s_size);
std::string ret;
ret.reserve(2*n);
const char *s_data = s.data(), *s_data_end = s_data + s_size;
ret.append(s_data, s_data + n);
ret.append(s_data_end - n, s_data_end);
return ret;
}
Вариант 3:
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
std::string::size_type s_size = s.size();
n = std::min(n, s_size);
std::string ret(s);
std::string::size_type d = s_size - n;
return ret.replace(n, d, s, d, n);
}
Вариант 4 (мой исходный код):
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
n = std::min(n, s.size());
std::string ret;
ret.reserve(2*n);
ret.append(s.begin(), s.begin() + n);
ret.append(s.end() - n, s.end());
return ret;
}
Результаты для g++ 4.5.0:
- Вариант 4 - это самый быстрый
- Вариант 3 второй (на 5% медленнее, чем вариант 4)
- Вариант 1 является третьим (на 2% медленнее, чем вариант 3)
- Вариант 2 является четвертым (на 0,2% медленнее, чем вариант 1)
Результаты для VС++ 16.00.30319.01:
- Вариант 1 является самым быстрым
- Вариант 2 второй (на 3% медленнее, чем вариант 1)
- Вариант 4 является третьим (на 4% медленнее, чем вариант 2)
- Вариант 3 четвертый (на 17% медленнее, чем вариант 4)
Неудивительно, что самый быстрый вариант зависит от компилятора. Однако, не зная, какой компилятор будет использоваться, я думаю, что мой вариант лучше всего потому, что он знакомый стиль С++, он самый быстрый при использовании g++, и он не намного медленнее, чем варианты 1 или 2 при использовании VС++.
Одна вещь, интересная из результатов VС++, заключается в том, что быстрее использовать c_str, а не data. Возможно, именно поэтому ваш интервьюер сказал, что есть более быстрый способ, чем ваша реализация.
EDIT3:
Собственно, я просто подумал о другом варианте:
Вариант 5:
inline std::string first_last_n(std::string::size_type n, const std::string& s)
{
n = std::min(n, s.size());
std::string ret;
ret.reserve(2*n);
std::string::const_iterator s_begin = s.begin(), s_end = s.end();
ret.append(s_begin, s_begin + n);
ret.append(s_end - n, s_end);
return ret;
}
Это точно так же, как вариант 4, за исключением того, что сохраняются итераторы начала и конца для s.
Когда вариант 5 проверен, он фактически выбивает вариант 2 (вариант строки данных) при использовании VС++:
- Вариант 1 является самым быстрым
- Вариант 5 второй (на 1,6% медленнее, чем вариант 1)
- Вариант 2 является третьим (на 1.4% медленнее, чем вариант 5)
- Вариант 4 является третьим (на 4% медленнее, чем вариант 2)
- Вариант 3 четвертый (на 17% медленнее, чем вариант 4)