C++ функция Split. Оптимизация

384
10 октября 2017, 04:51

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

#include <iostream>
using namespace std;
int length(char *array)
{
    int i = 0;
    while (*array++) i++;
    return i;
}
char **split(char *text, char delim)
{
    int words = 1;
    for(int i=0; i<length(text); i++)
        if(text[i] == delim) words++;
    char **result = new char*[words];
    for(int i=0; i<words; i++)
        result[i] = new char[length(text)];
    int j = 0, t = 0;
    for(int i=0; i<words; i++)
    {
        while(text[j] != delim && text[j] != '\0') result[i][t++] = text[j++];
        j++;
        t = 0;
    }
    return result;
}
int main()
{
    char *text = "audi mersedez reno lambo";
    char **result = split(text, ' ');
    for(int i=0; i<5; i++)
        cout << result[i] << endl;
    for(int i=0; i<5; i++)
        delete result[i];
    delete [] result;
    return 0;
}
Answer 1

Функция определения длины строки.

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

int length(char *array){
    char *start=array;
    while (*array++);
    return array-start-1;
}

Функция split.

При определении количества слов, вы в условии цикла

for(int i=0; i<length(text); i++)
    if(text[i] == delim) words++;

вызываете функцию length ровно столько раз, сколько символов в строке text. И на каждом вызове в функции length происходит выполнение цикла по всей строке, для определения нулевого символа. Стоит, или вынести определение длины строки из цикла, создав отдельную переменную

int len = length(text);
for(int i=0; i<len; i++)

или можно определить переменную длины прямо в цикле, но перенести это определение в блок инициализации цикла

for(int i=0, len = length(text); i<len; i++)

в этом же цикле (как и во всяком подобном, у вас их еще два далее в функции split) эффективней использовать для изменения счетчика не пост, а пред инкремент. Дело в том, что пост инкремент сохраняет начальное значение переменной, увеличивает ее и возвращает начальное значение. На это тратится время.

for(int i=0, len = length(text); i<len; ++i)

тоже самое можно применить и к переменной words

if(text[i] == delim) ++words;

и так же можно делать для всех инкрементов в циклах

Все, что касается функции length справедливо и для цикла

for(int i=0; i<words; i++)
    result[i] = new char[length(text)];

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

int len = length(text);

и использовать это значение, когда необходимо.

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

int j = 0; 
for(int i=0; i<words; ++i){
    result[i] = new char[len];
    int t = 0;
    while(text[j] != delim && text[j] != '\0') result[i][t++] = text[j++];
    j++;
}

Так же примем сразу, что split разбивает именно не константные строки, потому что для константных строк реализация, по идее, должна быть совершенно другой. Ну и использование динамической памяти в таком виде с высокой долей вероятности неудобно и приведет в итоге к ошибкам. Но, если вам важно получить на выходе именно такую структуру, то и пусть. Функцию main рассматривать не будем. Как и передачу функции пустой строки. В итоге получается так

#include <iostream>
using namespace std;
int length(char *array){
    char *start=array;
    while (*array++);
    return array-start-1;
}
char **split(char *text, char delim)
{
    int words = 1;
    int len = length(text);
    for(int i=0; i<len; ++i)
        if(text[i] == delim) ++words;
    char **result = new char*[words];
    int j = 0; 
    for(int i=0; i<words; ++i){
        result[i] = new char[len];
        int t = 0;
        while(text[j] != delim && text[j] != '\0') result[i][t++] = text[j++];
        j++;
    }
    return result;
}
int main()
{
   char *text = "audi mersedez reno lambo";
    char **result = split(text, ' ');
    for(int i=0; i<5; ++i)
        cout << result[i] << endl;
    for(int i=0; i<5; ++i)
        delete result[i];
    delete [] result;

    return 0;
}
READ ALSO
Как скомпилировать программку в notepad++

Как скомпилировать программку в notepad++

Я знаю, как компилировать программку в Sublime Text 3Надо просто нажать клавишу F7

269
Как на C++ записать сложную математическую формулу

Как на C++ записать сложную математическую формулу

Задание, составить программу, которая рассчитывает решение по формуле (прикреплена)Если непонятно, что это за ch1, ch2 и т

556
Пропуск cin.getline

Пропуск cin.getline

Проблема в том, функция addNew() позволяет ввести название книги только первый раз, во всех остальных случаях она просто пропускает ввод названияНе...

242
Разборка одного момента в хеш-таблице

Разборка одного момента в хеш-таблице

Есть код, не могу разобраться как работает put в классе HashMap() Разъясните мне пожалуйста

239