Улучшение производительности std :: sort

Question

Улучшение производительности std :: sort

У меня есть индекс с примерно 10 тыс. Элементов, которые должны быть отсортированы с учетом регистра лексикографически.

Это мой подход:

bool lowercomp (AbstractServiceProvider::AbstractItem*  i, AbstractServiceProvider::AbstractItem* j)

{
std::string a,b;

// lower first string
a.resize(i->title().length());
std::transform(i->title().cbegin(), i->title().cend(), a.begin(),
std::bind2nd(std::ptr_fun(&std::tolower<char>), std::locale("")));

// lower 2nd string
b.resize(j->title().length());
std::transform(j->title().cbegin(), j->title().cend(), b.begin(),
std::bind2nd(std::ptr_fun(&std::tolower<char>), std::locale("")));

return 0 > a.compare(b);
}

Где-то в моем коде:

t = new boost::timer::auto_cpu_timer;
std::sort(_index.begin(), _index.end(), lowercomp);
delete t;

Но это занимает около 4 секунд. Без части toLower это занимает около 0,003 секунды. Есть ли способ улучшить это?

0

c++performance sorting tolower

Решение

Другие решения

Вы определенно можете сделать это намного быстрее. Решение состоит в том, чтобы избежать выделения памяти и вместо этого сравнивать строки без учета регистра, преобразовывая один символ за раз, используя tolower () при выполнении сравнения. В функции сравнения не должно быть объектов класса. Что-то вроде этого:

bool lowercomp(const AbstractItem* lhs, const AbstractItem* rhs)
{
size_t size = std::min(lhs->title().size(), rhs->title().size());
for (size_t pos = 0; pos < size; ++pos) {
if (tolower(lhs->title()[pos]) < tolower(rhs->title()[pos]) {
return true;
} else if (tolower(lhs->title()[pos]) > tolower(rhs->title()[pos]) {
return false;
}
}
return lhs->title().size() < rhs->title().size();
}

Дайте нам знать, как быстро это. 🙂

4

Ваша реализация кажется мне чрезвычайно неэффективной. Я вижу несколько проблем.

Вы выполняете tolower на обеих струнах в сорт компаратора. Поскольку этот компаратор будет вызываться по порядку n log n раз ты будешь tolowering два Строки около 40К раз (?) каждая.

Я бы не хотел сравнивать строки вообще. Мало того, что порядок сравнения строк на порядок менее эффективен, чем другие методы (например, интегральное сравнение), он также подвержен ошибкам и требует очистки данных — еще один источник неэффективности.

Однако, если вы должны сравнить строки, очистите их до Вы выполняете сортировку. Это включает tolowerих В идеале, очистить данные при создании элемента. За исключением этого, вы могли бы даже вычистить это перед тем, как позвонить sort, Что бы вы ни делали, не чистите это в компараторе.

0

Источник

Accepted Answer

Пока вы не увидите вывод профилировщика, чтобы знать, где
замедление, вы не можете быть уверены, но есть ряд моментов
которые, кажется, могут вызвать замедление для меня. Два наиболее
важными являются:

Ваша функция создает две новые строки при каждом вызове. Это может
быть очень дорогой и
Вы используете форму двух операндов std::tolower; эта функция
должен извлечь ctype грань каждый раз, когда это называется (и вы
создать новый временный экземпляр локали каждый раз, когда вы
взывать lowercomp,

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

class CaseInsensitiveCompare
{
std::locale myLocale;   //  To ensure lifetime of the facet.
std::ctype<char> const& myCType;
public:
CaseInsensitiveCompare( std::locale const& locale = std::locale( "" ) )
: myLocale( locale )
, myCType( std::use_facet<std::ctype<char>>( myLocal ) )
{
}
bool operator()( AbstractItem const* lhs, AbstractItem const* rhs ) const
{
return (*this)( lhs->title(), rhs->title() );
}
bool operator()( std::string const& lhs, std::string const& rhs ) const
{
return std::lexicographical_compare(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end(),
*this);
}
bool operator()( char lhs, char rhs ) const
{
return myCType.tolower(lhs) < myCType.tolower(rhs);
}
};

Помимо этого, есть несколько других моментов, которые могут улучшить
спектакль:

Если вы уверены в жизни locale вы используете
(и вы обычно можете), бросьте myLocale член в
учебный класс; копирование локали будет самой дорогой частью
копирование экземпляров этого класса (и вызов
lexicographical_compare скопирую его хотя бы один раз).
Если вам не нужны функции локализации, рассмотрите возможность использования
tolower функция в <cctype>вместо того, чтобы в
<locale>, Это позволит избежать необходимости каких-либо членов данных вообще
в сравнении.
Наконец, хотя я не уверен, что оно того стоит
размером до 10 тысяч элементов, вы можете рассмотреть возможность создания векторов с
канонические формы струн (уже в нижнем регистре и т. д.),
сортировка тех, кто использует только < на струнах, а затем переупорядочить
оригинальные векторы в соответствии с этим.

Кроме того, я очень подозрительно
повышение :: таймера :: auto_cpu_timer». Вам действительно нужно динамическое
распределение здесь? Я подозреваю, что локальная переменная
более подходящий.

4