C ++ Самый быстрый способ найти первый пробел в массиве char с фиксированным размером 9

Question

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

Данные выглядят следующим образом:

"1234    "
"ABC     "
"A1235   "
"A1235kgo"

Answer 1

char* found = std::find(arr, arr+9, ' ');

Обратите внимание, что «конечный итератор» сигнализирует «нет совпадения»:

bool match = (arr+9) != found;

Обратите внимание, что двоичный поиск

• не применяется, если вы не символыв известное упорядочение .
• std :: find имеет значение , встроено, шаблонизировано и будет работать максимально, если вы включите оптимизацию (например, -O3 -march=native для g ++)

Edit , так как вы показали больше кода, теперь я понимаю, что вы действительно хотите определить (под) длину строки.Вы можете использовать

• std :: string :: find_first_of
• std :: string :: find_last_of
• std :: string :: find
• std :: string :: rfind и т. д.

Конечно, предполагается, что вы хотите преобразовать char [] в std ::Строка для этой цели.На практике это может быть совершенно верной идеей, поскольку SSO (Small String Optimization) встречается практически во всех реализациях стандартной библиотеки C ++.(см. пункты 13-16 в « More Exceptional C ++ » Херба или обсуждение Скоттом Мейерсом коммерческих реализаций std :: string в Effective STL ).

Answer 2

Вы действительно можете использовать бинарный поиск, чтобы найти первый пробел (в этом случае, используя std::lower_bound(...)):

const char *data= ...;// 8 character string to search

const char *end= std::lower_bound(data, data + 8, ' ', [](char lhs, char rhs)
{
    bool lhs_is_space= lhs==' ';
    bool rhs_is_space= rhs==' ';

    return lhs_is_space < rhs_is_space;
});

Который эффективно использует бинарный поиск, чтобы найти первый пробел. Основная идея состоит в том, чтобы сделать вид, что непробельные символы - false, а пробельные символы - true, и далее предположить, что все непробельные символы предшествуют пробелами. Если это так, то последовательность сортируется в соответствии с этой классификацией, и мы можем просто найти начало (то есть нижнюю границу) серии пробелов.

Answer 3

Поскольку все пробелы находятся в конце, вы можете использовать развернутый двоичный поиск. Тем не менее, обычный линейный поиск чудом близок по скорости и не заставит будущих разработчиков ненавидеть вас.

inline int find_space(char (&data)[9]) {
    if (data[3] == ' ') {
        if (data[1] == ' ') {
            if (data[0] == ' ')
                return 0;
            return 1;
        } else if (data[2] == ' ')
            return 2;
        return 3; 
    }
    if (data[5] == ' ') {
        if (data[4] == ' ')
            return 4;
        return 5;
    } else if (data[7] == ' ') {
        if (data[6] == ' ')
            return 6;
        return 7;
    } else if (data[8] == ' ')
        return 8;
    return -1;
}

Answer 4

Просто мои 2 цента.Я предполагаю, что все строки имеют длину 8. Возможные символы «A» - «Z», «a» - «z», «0» - «9» и пробел.И я попробовал:

//simple
const char *found = std::find(x.data, x.data + 9, ' ');
//binary search
const char *end = std::lower_bound(x.data, x.data + 8, ' ', [](char lhs, char rhs) {

и мою оптимизированную версию (это зависит от компилятора == gcc) (см. Ниже).Я тестировал на Linux 64bit, с -O3 -march = native -std = c ++ 0x.Результаты для случайно сгенерированных 50000000 строк:

простой дубль 0,480000,оптимизированный дубль 0.120000,бинарный поиск займет 0,600000.

union FixedLenStr {
     unsigned char chars[8];
     uint32_t words[2];
     uint64_t  big_word;
};

static int space_finder(const char *str) 
{   
        FixedLenStr tmp;

        memcpy(tmp.chars, str, 8);

        tmp.big_word &= 0xF0F0F0F0F0F0F0F0ull;
        tmp.big_word >>= 4;
        tmp.big_word = (0x0707070707070707ull - tmp.big_word) * 26;
        tmp.big_word &= 0x8080808080808080ull;      

        return (__builtin_ffsll(tmp.big_word) >> 3) - 1;    
}

Answer 5

Разрешить компилятору и оптимизатору выполнять свою работу.

inline
template <typename T_CHAR, int N>
T_CHAR* find_first_of(T_CHAR a[N], T_CHAR t)
{
    for (int ii = 0; ii < N; ++ii)
    {
        if (a[ii] == t) { return a+ii; }
    }
    return NULL;
}

Или позвольте авторам библиотеки стандартных шаблонов сделать всю тяжелую работу за вас.

inline
template <typename T_CHAR, int N>
T_CHAR* find_first_of(T_CHAR a[N], T_CHAR t)
{
    T_CHAR* ii = std::find(a, a+N, t);
    if (ii == a+N) return NULL;
    return ii;
}