Question

У меня есть строка S = "&|&&|&&&|&", где мы должны получить число '&' между 2 индексами строки. Таким образом, выходные данные с двумя индексами 1 и 8 здесь должны быть 5. А вот мой код стиля грубой силы:

std::size_t cnt = 0;
for(i = start; i < end; i++) {
    if (S[i] == '&')
        cnt++;
}
cout << cnt << endl;

Проблема, с которой я столкнулся, заключалась в том, что мой код получал тайм-аут для больших входов в платформе кодирования. Кто-нибудь может предложить лучший способ уменьшить сложность времени здесь?

JohnFilleau · Answer 1 · 14 февраля 2020

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

Я использовал std::chrono::steady_clock::now() для измерения времени реализации.

Допущения

Программа запрашивает у пользователя размер строки, символ поиска, начальный индекс и конечный индекс.
Входные данные правильно сформированы ( start <= end <= size). </li>
Строка генерируется случайным образом из равномерного распределения символов ascii между ' ' и '~'.
Основными данными в строковом объекте являются сохраняется непрерывно в памяти.

Подходы

Наивный для l oop: индексная переменная увеличивается, и строка индексируется, символ за символом, используя индекс.
Итератор l oop: используется строковый итератор, разыменовываемый на каждой итерации и сравниваемый с поисковым символом.
Под указатель на лежачие данные : указатель на базовый символьный массив строки найден, и он увеличивается в al oop. Разыменованный указатель сравнивается с поисковым символом.
Отображение индекса (согласно предложению GyuHyeon Choi) : массив типа int из max printable ascii character элементов инициализируется равным 0, и для каждого символ, встречающийся при переборе массива, соответствующий индекс увеличивается на единицу. В конце, индекс поискового символа разыменовывается, чтобы найти, сколько из этого символа было найдено.
Просто используйте std :: count (как предложено Атулом Шармой) : Просто используйте функциональность подсчета построения.
Пересчитать базовые данные как указатель на больший тип данных и выполнить итерацию : базовый указатель const char* const, который содержит данные string, повторно интерпретируется как указатель к более широкому типу данных (в данном случае указатель на тип uint64_t). Каждый разыменованный uint64_t затем XOR'ом с маской, состоящей из символа поиска, а каждый байт uint64_t маскируется с 0xff. Это уменьшает количество приращений указателя, необходимых для пошагового перемещения по всему массиву.

Results

Для поиска строки размером 1 000 000 000 от индекса 5 до 999999995, результаты каждого следующий метод:

Наивный для l oop: 843 мс
Итератор l oop: 818 мс
Базовый указатель данных : 750 мс
Отображение индекса (согласно предложению GyuHyeon Choi) : 929 мс
Просто используйте std :: count (как предложено Атул Шарма) : 819 мс
Пересчитать базовые данные в виде указателя на больший тип данных и выполнить итерацию : 664 мс

Обсуждение

Самой эффективной реализацией была моя собственная переработка указателя данных, которая заняла чуть более 75% времени, которое потребовалось для наивного решения. Самым быстрым «простым» решением является итерация указателя над базовой структурой данных. Преимущество этого метода заключается в простоте его реализации, понимания и обслуживания. Метод отображения индекса, несмотря на то, что он продается в 2 раза быстрее, чем наивное решение, не показал такого ускорения в моих тестах. Метод std::count примерно такой же быстрый, как итерация указателя вручную, и еще проще в реализации. Если скорость действительно имеет значение, подумайте о преобразовании основного указателя. В противном случае используйте std::count.

Код

#include <algorithm>
#include <iostream>
#include <random>
#include <string>
#include <functional>
#include <typeinfo>
#include <chrono>

int main(int argc, char** argv)
{
    std::random_device device;
    std::mt19937 generator(device());
    std::uniform_int_distribution<short> short_distribution(' ', '~');
    auto next_short = std::bind(short_distribution, generator);

    std::string random_string = "";
    size_t string_size;
    size_t start_search_index;
    size_t end_search_index;
    char search_char;
    std::cout << "String size: ";
    std::cin >> string_size;
    std::cout << "Search char: ";
    std::cin >> search_char;
    std::cout << "Start search index: ";
    std::cin >> start_search_index;
    std::cout << "End search index: ";
    std::cin >> end_search_index;

    if (!(start_search_index <= end_search_index && end_search_index <= string_size))
    {
        std::cout << "Requires start_search <= end_search <= string_size\n";
        return 0;
    }

    for (size_t i = 0; i < string_size; i++)
    {
        random_string += static_cast<char>(next_short());
    }

    // naive implementation
    size_t count = 0;
    auto start_time = std::chrono::steady_clock::now();
    for (size_t i = start_search_index; i < end_search_index; i++)
    {
        if (random_string[i] == search_char)
            count++;
    }
    auto end_time = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    std::cout << "Naive implementation. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";

    // Iterator solution
    count = 0;
    start_time = std::chrono::steady_clock::now();
    for (auto it = random_string.begin() + start_search_index, end = random_string.begin() + end_search_index;
        it != end;
        it++)
    {
        if (*it == search_char)
            count++;
    }
    end_time = std::chrono::steady_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    std::cout << "Iterator solution. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";

    // Iterate on data
    count = 0;
    start_time = std::chrono::steady_clock::now();
    for (auto it = random_string.data() + start_search_index,
        end = random_string.data() + end_search_index;
        it != end; it++)
    {
        if (*it == search_char)
            count++;
    }
    end_time = std::chrono::steady_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    std::cout << "Iterate on underlying data solution. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";

    // use index mapping
    count = 0;
    size_t count_array['~']{ 0 };
    start_time = std::chrono::steady_clock::now();
    for (size_t i = start_search_index; i < end_search_index; i++)
    {
        count_array[random_string.at(i)]++;
    }
    end_time = std::chrono::steady_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    count = count_array[search_char];
    std::cout << "Using index mapping. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";

    // using std::count
    count = 0;
    start_time = std::chrono::steady_clock::now();
    count = std::count(random_string.begin() + start_search_index
        , random_string.begin() + end_search_index
        , search_char);
    end_time = std::chrono::steady_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    std::cout << "Using std::count. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";

    // Iterate on larger type than underlying char
    count = end_search_index - start_search_index;
    start_time = std::chrono::steady_clock::now();
    // Iterate through underlying data until the address is modulo 4
    {
        auto it = random_string.data() + start_search_index;
        auto end = random_string.data() + end_search_index;

        // iterate until we reach a pointer that is divisible by 8
        for (; (reinterpret_cast<std::uintptr_t>(it) & 0x07) && it != end; it++)
        {
            if (*it != search_char)
                count--;
        }

        // iterate on 8-byte sized chunks until we reach the last full chunk that is 8-byte aligned
        auto chunk_it = reinterpret_cast<const uint64_t* const>(it);
        auto chunk_end = reinterpret_cast<const uint64_t* const>((reinterpret_cast<std::uintptr_t>(end)) & ~0x07);
        uint64_t search_xor_mask = 0;
        for (size_t i = 0; i < 64; i+=8)
        {
            search_xor_mask |= (static_cast<uint64_t>(search_char) << i);
        }
        constexpr uint64_t all_ones = 0xff;
        for (; chunk_it != chunk_end; chunk_it++)
        {
            auto chunk = (*chunk_it ^ search_xor_mask);
            if (chunk & (all_ones << 56))
                count--;
            if (chunk & (all_ones << 48))
                count--;
            if (chunk & (all_ones << 40))
                count--;
            if (chunk & (all_ones << 32))
                count--;
            if (chunk & (all_ones << 24))
                count--;
            if (chunk & (all_ones << 16))
                count--;
            if (chunk & (all_ones <<  8))
                count--;
            if (chunk & (all_ones <<  0))
                count--;
        }

        // iterate on the remainder of the bytes, should be no more than 7, tops
        it = reinterpret_cast<decltype(it)>(chunk_it);
        for (; it != end; it++)
        {
            if (*it != search_char)
                count--;
        }
    }
    end_time = std::chrono::steady_clock::now();
    duration = std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time);
    std::cout << "Iterate on underlying data with larger step sizes. Found: " << count << "\n";
    std::cout << "Elapsed time: " << duration.count() << "us.\n\n";
}

Пример вывода

String size: 1000000000
Search char: &
Start search index: 5
End search index: 999999995
Naive implementation. Found: 10527454
Elapsed time: 843179us.

Iterator solution. Found: 10527454
Elapsed time: 817762us.

Iterate on underlying data solution. Found: 10527454
Elapsed time: 749513us.

Using index mapping. Found: 10527454
Elapsed time: 928560us.

Using std::count. Found: 10527454
Elapsed time: 819412us.

Iterate on underlying data with larger step sizes. Found: 10527454
Elapsed time: 664338us.

Atul Sharma · Answer 2 · 13 февраля 2020

Вы можете использовать std::count из стандартной библиотеки C ++ алгоритма. Просто включите заголовок <algorithm>

std::string s{"&|&&|&&&|&"};
// https://en.cppreference.com/w/cpp/algorithm/count
auto const count = std::count(s.begin() + 1  // starting index
                             ,s.begin() + 8  // one pass end index 
                             ,'&');

GyuHyeon Choi · Answer 3 · 13 февраля 2020

int cnt[125];  // ASCII '&' = 46, '|' = 124
cnt['&'] = 0;
for(int i = start; i < end; i++) {
    cnt[S.at(i)]++;
}
cout << cnt['&'] << endl;

if дорого, так как сравнивает и разветвляет. Так было бы лучше.

манипулирование строками - подсчет символов

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Допущения

Подходы

Results

Обсуждение

Код

Пример вывода

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

манипулирование строками - подсчет символов

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

Ответы [ 3 ]

Допущения

Подходы

Results

Обсуждение

Код

Пример вывода

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы