Улучшить std :: sort performance

Question

У меня есть индекс, содержащий около 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); 
} 

Somwhere в моем коде:

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

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

Answer 1

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

• ваша функция создает две новые строки при каждом вызове. Это может быть очень дорого, и

• использовать два операнда форму std::tolower; эта функция должна извлечь ctype Facet каждый раз, когда она вызывается (и вы построить новый временный экземпляр локали каждый раз, когда вы вызова 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>. Это позволит избежать необходимости в любых элементах данных вообще в сравнении.

• Наконец, хотя я не уверен, что стоит что-то как маленьких, как 10K элементов, вы могли бы рассмотреть векторы с каноническими формами струн (уже ниже обсаженных и т.п.), сортировкой тех, используя только < на строках, а затем переупорядочивая оригинальные векторы в соответствии с этим.

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

Answer 2

Вы можете определенно сделать это намного быстрее. Решение состоит в том, чтобы избежать выделения памяти и вместо этого сравнивать строки без учета регистра, преобразовывая один символ за раз, используя 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(); 
} 

Сообщите нам, как быстро это происходит. :)

Answer 3

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

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

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

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