Медленный цикл с векторами в С++

220
12 апреля 2018, 13:25

Здравствуйте , есть такой код :

std::vector<unsigned char> buffer;
std::vector<std::string> code_book_characters;
std::vector<size_t> codeword_length;
std::vector<double> words_dictionary;
std::vector<double> result;
... // заполнениe векторов , reserve для result
    for (int i = 0; i < 345600; ++i)
    {
        int ncode = -1;
        bool flag = false;
        while (( !flag ) && ( ncode+1 < n_code ))
        {
            ++ncode;
            std::vector<unsigned char> val_1 { &buffer[m_buffer],&buffer[m_buffer + codeword_length[ncode]] };
            std::vector<unsigned char> tmp_compare (code_book_characters[ncode].begin(), code_book_characters[ncode].end()); 
            flag = std::equal(val_1.begin(), val_1.end(), tmp_compare.begin());
        }
        m_buffer += codeword_length[ncode];
        result.emplace_back(words_dictionary[ncode]);
    } return result;

Что делает:

  1. Создали вектор val_1 из большого buffer(используя m_buffer как начало нового вектора и размер codeword из codeword_length)
  2. Создали и заполнили второй вектор tmp_compare ( из словаря code_book_characters)
  3. Проверили сходится ли val_1 и tmp_compare
    Да - 3.1.переходим к следующему слову из buffer
    Нет - Шаг 2 с новым словом из словаря

Все это повторяеться пока в bufferе есть данные.

Можно ли его переписать/изменить более оптимально с точки зрения скорости , потому что на производство каждого result уходит ~10 секунд.

EDIT: Изменение

std::vector<unsigned char> tmp_compare;
                for (auto c : code_book_characters[ncode])
                {
                    tmp_compare.emplace_back(c);
                }  

на

std::vector<unsigned char> tmp_compare (code_book_characters[ncode].begin(), code_book_characters[ncode].end());

Уменьшило время с 10 до 3 секунд .

Answer 1

То есть задача сводится к тому, чтобы в одной строке (пусть и большой) найти слова, помещенные в массиве строк? И ради этого Вы создаете на каждой итерации вложенного цикла динамические массивы (по 2 штуки)? Возможно, стандартный std::find() справится с задачей быстрее, особенно, если Вы объявление val_1 и tmp_compare вынесете за пределы циклов (с заданием достаточного начального размера через reserve).

Answer 2

Для эффективного поиска множества строк в одном тексте есть специальные алгоритмы - например, алгоритм Ахо-Корасик.
Для С++ нетрудно найти реализацию

Вот и другие из англ. вики:

Algorithms using a finite set of patterns
Aho–Corasick string matching algorithm (extension of Knuth-Morris-Pratt)
Commentz-Walter algorithm (extension of Boyer-Moore)
Set-BOM (extension of Backward Oracle Matching)
Rabin–Karp string search algorithm

Answer 3

Чтоб найти в последовательности другую:

string s1 = "stack overflow... we can always find a good method";
char p[] = "way";    
auto It = std::search(s1.begin(), s1.end(), p, &p[strlen(p)]);
if (It != s1.end()) cout << "word found \"" << p <<'\"';
READ ALSO
Не удаётся открыть источник файла [требует правки]

Не удаётся открыть источник файла [требует правки]

Если открываю готовый проект - не работают стандартные библиотеки

311
Хранение объектов разных типов

Хранение объектов разных типов

Есть абстрактный класс "Organism"Его наследуют 2 классa: "Animals" и "Plants"

221
как можно создавать массив из значения в обьекте

как можно создавать массив из значения в обьекте

как можно получить новый массив состоящий из name например["dima", "Anna", "Denis"], и отдельный массив из lang ["javascript", "php", "html", "css", "python", "ruby"], пробовал через...

159
Не работает browser sync

Не работает browser sync

ЗдравствуйтеНе могу разобраться никак, что не так? Все запускается при сохранении пишет Reloading Browsers, но не обновляет!

220