C ++ более быстрый разбор строк? - PullRequest
Новая
       8

C ++ более быстрый разбор строк?

0 голосов
/ 08 февраля 2012

Я пытаюсь написать синтаксический анализатор для разбора этого набора данных: http://research.microsoft.com/en-us/projects/mslr/

Я написал код (ниже) .. Однако он слишком медленный .. Требуется почти полная минута, чтобы разобрать несколькосотни мегабайт данных.

Я запустил профилировщик, и он сказал, что большую часть времени была потрачена на boost :: split (30%) и boost :: lexical_cast (40%) ... любые предложения о том, какускорить код?

Спасибо. 

  std::ifstream train("letor/Fold1/train.txt", std::ifstream::in | std::ifstream::binary);

  m_train.clear();

  for (std::size_t i = 0; i < 10000 && train.good(); i++) {
    std::size_t query;
    boost::numeric::ublas::vector<double> features;
    double label;

    features.resize(get_feature_size(), false);

    // 2 qid:1 1:3 2:3 3:0 4:0 5:3 6:1 7:1 8:0 9:0 10:1 11:156 12:4 13:0 14:7 15:167 16:6.931275 17:22.076928 18:19.673353 19:22.255383 20:6.926551 21:3 22:3 23:0 24:0 25:6 26:1 27:1 28:0 29:0 30:2 31:1 32:1 33:0 34:0 35:2 36:1 37:1 38:0 39:0 40:2 41:0 42:0 43:0 44:0 45:0 46:0.019231 47:0.75000 48:0 49:0 50:0.035928 51:0.00641 52:0.25000 53:0 54:0 55:0.011976 56:0.00641 57:0.25000 58:0 59:0 60:0.011976 61:0.00641 62:0.25000 63:0 64:0 65:0.011976 66:0 67:0 68:0 69:0 70:0 71:6.931275 72:22.076928 73:0 74:0 75:13.853103 76:1.152128 77:5.99246 78:0 79:0 80:2.297197 81:3.078917 82:8.517343 83:0 84:0 85:6.156595 86:2.310425 87:7.358976 88:0 89:0 90:4.617701 91:0.694726 92:1.084169 93:0 94:0 95:2.78795 96:1 97:1 98:0 99:0 100:1 101:1 102:1 103:0 104:0 105:1 106:12.941469 107:20.59276 108:0 109:0 110:16.766961 111:-18.567793 112:-7.760072 113:-20.838749 114:-25.436074 115:-14.518523 116:-21.710022 117:-21.339609 118:-24.497864 119:-27.690319 120:-20.203779 121:-15.449379 122:-4.474452 123:-23.634899 124:-28.119826 125:-13.581932 126:3 127:62 128:11089534 129:2 130:116 131:64034 132:13 133:3 134:0 135:0 136:0
    std::string line;
    getline(train, line);

    boost::algorithm::trim(line);
    std::vector<std::string> tokens;
    boost::split(tokens, line, boost::is_any_of(" "));

    assert(tokens.size() == 138);

    label = boost::lexical_cast<double>(tokens[0]);
    query = boost::lexical_cast<std::size_t>(tokens[1].substr(tokens[1].find(":") + 1, tokens[1].size()));

    for (std::size_t i = 2; i < tokens.size(); i++) {
      features[i - 2] = boost::lexical_cast<double>(tokens[i].substr(tokens[i].find(":") + 1, tokens[i].size()));
    }

    m_train.push_back(query, features, label);

    train.peek();
  }

Ответы [ 3 ]

5 голосов
/ 08 февраля 2012

Если я правильно понимаю ваш формат, каждая строка начинается с числа, за которым следуют пары, разделенные двоеточиями. Первая пара в каждой строке имеет особое значение и состоит из std::string и size_t, тогда как все остальные пары состоят из индекса (который игнорируется) и double. Нет никакой причины использовать Boost для этого вообще: используйте IOStreams напрямую: 

std::streamsize    max(std::numeric_limits<std::streamsize>::max());
std::string        line;
std::istringstream in;
for (std::size_t i(0); i < 1000 && std::getline(train, line); ++i) {
    double label;
    size_t query;
    in.clear();
    in.str(line)
    if ((in >> label).ignore(max, ':') >> query) {
         boost::numeric::ublas::vector<double> features;
         while (in.ignore(max, ':') >> feature) {
              features.push_back(feature);
         }
         assert(features.size() == 136);
         m_train.push_back(query, features, label);
    }
}

Обратите внимание, что этот код тщательно проверяет, действительно ли чтение прошло успешно. Ваш код проверен заранее, если чтение будет успешным, но это не работает надежно. Например, если ваша последняя строка состоит только из паразитного пробела, ваш assert() сработает, что вряд ли вам нужно.

2 голосов
/ 08 февраля 2012

Многократное прерывание строки требует выделения памяти и освобождения. Вы можете использовать старые добрые strtod и указатели на символы, чтобы избежать разбиения строки. Это позаботится о 30% расходов на токенизацию строк. Что касается 40% при преобразовании ударов в удвоения, это, вероятно, не может быть значительно улучшено.

Если вы хотите сделать быстрое, грязное и удивительно уродливое, но, возможно, самое быстрое решение, предназначенное только для C, попробуйте это. Этот тест завершился примерно за 35 секунд на процессоре E8300 с частотой 2,83 ГГц. Предполагая, что все строки имеют одинаковый формат. 

#include "stdio.h"

void main ()
{
    const char* test_str = "2 qid:1 1:3 2:3 3:0 4:0 5:3 6:1 7:1 8:0 9:0 10:1 11:156 12:4 13:0 14:7 15:167 16:6.931275 17:22.076928 18:19.673353 19:22.255383 20:6.926551 21:3 22:3 23:0 24:0 25:6 26:1 27:1 28:0 29:0 30:2 31:1 32:1 33:0 34:0 35:2 36:1 37:1 38:0 39:0 40:2 41:0 42:0 43:0 44:0 45:0 46:0.019231 47:0.75000 48:0 49:0 50:0.035928 51:0.00641 52:0.25000 53:0 54:0 55:0.011976 56:0.00641 57:0.25000 58:0 59:0 60:0.011976 61:0.00641 62:0.25000 63:0 64:0 65:0.011976 66:0 67:0 68:0 69:0 70:0 71:6.931275 72:22.076928 73:0 74:0 75:13.853103 76:1.152128 77:5.99246 78:0 79:0 80:2.297197 81:3.078917 82:8.517343 83:0 84:0 85:6.156595 86:2.310425 87:7.358976 88:0 89:0 90:4.617701 91:0.694726 92:1.084169 93:0 94:0 95:2.78795 96:1 97:1 98:0 99:0 100:1 101:1 102:1 103:0 104:0 105:1 106:12.941469 107:20.59276 108:0 109:0 110:16.766961 111:-18.567793 112:-7.760072 113:-20.838749 114:-25.436074 115:-14.518523 116:-21.710022 117:-21.339609 118:-24.497864 119:-27.690319 120:-20.203779 121:-15.449379 122:-4.474452 123:-23.634899 124:-28.119826 125:-13.581932 126:3 127:62 128:11089534 129:2 130:116 131:64034 132:13 133:3 134:0 135:0 136:0";

    const char* format = "%lf qid:%lf 1:%lf 2:%lf 3:%lf 4:%lf 5:%lf 6:%lf 7:%lf 8:%lf 9:%lf 10:%lf 11:%lf 12:%lf 13:%lf 14:%lf 15:%lf 16:%lf 17:%lf 18:%lf 19:%lf 20:%lf 21:%lf 22:%lf 23:%lf 24:%lf 25:%lf 26:%lf 27:%lf 28:%lf 29:%lf 30:%lf 31:%lf 32:%lf 33:%lf 34:%lf 35:%lf 36:%lf 37:%lf 38:%lf 39:%lf 40:%lf 41:%lf 42:%lf 43:%lf 44:%lf 45:%lf 46:%lf 47:%lf 48:%lf 49:%lf 50:%lf 51:%lf 52:%lf 53:%lf 54:%lf 55:%lf 56:%lf 57:%lf 58:%lf 59:%lf 60:%lf 61:%lf 62:%lf 63:%lf 64:%lf 65:%lf 66:%lf 67:%lf 68:%lf 69:%lf 70:%lf 71:%lf 72:%lf 73:%lf 74:%lf 75:%lf 76:%lf 77:%lf 78:%lf 79:%lf 80:%lf 81:%lf 82:%lf 83:%lf 84:%lf 85:%lf 86:%lf 87:%lf 88:%lf 89:%lf 90:%lf 91:%lf 92:%lf 93:%lf 94:%lf 95:%lf 96:%lf 97:%lf 98:%lf 99:%lf 100:%lf 101:%lf 102:%lf 103:%lf 104:%lf 105:%lf 106:%lf 107:%lf 108:%lf 109:%lf 110:%lf 111:%lf 112:%lf 113:%lf 114:%lf 115:%lf 116:%lf 117:%lf 118:%lf 119:%lf 120:%lf 121:%lf 122:%lf 123:%lf 124:%lf 125:%lf 126:%lf 127:%lf 128:%lf 129:%lf 130:%lf 131:%lf 132:%lf 133:%lf 134:%lf 135:%lf 136:%lf";

    double data[138];

    for (int i = 0; i < 500000; i++)
    {
        sscanf(test_str, format, 
            data+0, data+1, data+2, data+3, data+4, data+5, 
            data+6, data+7, data+8, data+9, data+10, data+11, 
            data+12, data+13, data+14, data+15, data+16, data+17, 
            data+18, data+19, data+20, data+21, data+22, data+23, 
            data+24, data+25, data+26, data+27, data+28, data+29, 
            data+30, data+31, data+32, data+33, data+34, data+35, 
            data+36, data+37, data+38, data+39, data+40, data+41, 
            data+42, data+43, data+44, data+45, data+46, data+47, 
            data+48, data+49, data+50, data+51, data+52, data+53, 
            data+54, data+55, data+56, data+57, data+58, data+59, 
            data+60, data+61, data+62, data+63, data+64, data+65, 
            data+66, data+67, data+68, data+69, data+70, data+71, 
            data+72, data+73, data+74, data+75, data+76, data+77, 
            data+78, data+79, data+80, data+81, data+82, data+83, 
            data+84, data+85, data+86, data+87, data+88, data+89, 
            data+90, data+91, data+92, data+93, data+94, data+95, 
            data+96, data+97, data+98, data+99, data+100, data+101, 
            data+102, data+103, data+104, data+105, data+106, data+107, 
            data+108, data+109, data+110, data+111, data+112, data+113, 
            data+114, data+115, data+116, data+117, data+118, data+119, 
            data+120, data+121, data+122, data+123, data+124, data+125, 
            data+126, data+127, data+128, data+129, data+130, data+131, 
            data+132, data+133, data+134, data+135, data+136, data+137);
    }
}

C99 имеет vsscanf, что бы выглядело лучше. Строка формата может быть предварительно сгенерирована динамически один раз перед циклом, в зависимости от формата набора данных. Убедитесь, что в данном примере возвращаемое значение sscanf равно 138.

РЕДАКТИРОВАТЬ: решение Dietmar Kühl выглядит чистым, и не должно быть значительно, если вообще медленнее, чем один scscanf. Лучше всего использовать приведенный выше код только в качестве эталона.

0 голосов
/ 08 февраля 2012

Трудно сказать без каких-либо экспериментов, но ...

Я бы начал с отбрасывания boost::split.Это делает std::vector<std::string>, что, в свою очередь, включает в себя много динамического выделения и копирования.Вероятно, вы захотите написать какой-то итератор над строкой, в которой ++ переходит к следующему токену, а * возвращает пару итераторов, определяющих текущий токен.Это позволяет избежать промежуточной структуры данных.

Затем вы можете определить оператор << для этой пары, например: 

std::ostream&
operator<<( std::ostream& dest, TextRange const& token )
{
    std::copy( token.begin(), token.end(),
               std::ostream_iterator<char>( dest ) );
    return dest;
}

Сократить время, используемое boost::lexical_cast, будет сложнее.,По сути, boost::lexical_cast использует << для вставки источника в std::stringstream и >> для его извлечения.Вы можете написать что-то похожее, но используя свой собственный streambuf, основанный на паре итераторов (очень просто), поэтому, учитывая пару итераторов, 1) вам не нужно вообще использовать <<, так как пара итераторовстановится потоком, и 2) вы полностью избегаете создания какого-либо промежуточного звена std::string.(Вы не хотите переопределить процедуры преобразования в std::istream.)

...