LINUX.ORG.RU

[код] Все работает. Помогите оптимизировать


0

0

Учебная задачка, использовать можно только то что есть итак используется + struct(for, while, if, cin, cout)... Если у кто-то подскажет как это можно улучшить, буду благодарен.

#include<iostream>
#include<vector>
using namespace std;

/*Эта программа находит и заменяет в матрице символов все буквы совподающих
слов на заглавные и только если слова написанны сверху вниз и/или слева направо.

При компиляции использовался gcc 4.4 c параметрами -ansi -Wall -O2 -DNDEBUG -Wextra -Werror -Wno-uninitialized -Wno-sign-compare -Wshadow -o

Сначало вводится колчество слов, строк и столбцов:

1 3 4

Потом слова:
gnu

И вконце матрица:

g n u p
n n s t
u t u y

И выдаст:
 
G N U p
N N s t
U t U y

*/

//Эти три рекурсивные функция находят и заменяют строчные буквы на
//заглавные для всех слов из вектора v написанных сверху вниз,
//слева на права и по диагонали соответсвеннож
bool d(const string& s, vector< vector<char> >& v, int x, int y, int n) {
    if (s.size() == n) return true; //если мы прошли до конца и не нашли ни одного раздичия возвращяется True
    char c = v[x + n][y];
    if (c  < 'a') c = char(c - 'A' + 'a'); // Если символ не строчной делаю его таковым
    char cc = char(c + 'A' - 'a'); //Создаю заглавный символ
    if (s[n] == c and d(s, v, x, y, n+1)) { //Если текущий символ слова равен текущиму символу матрицы и тоже самое верно для следующего, то...
        v[x + n][y] = cc; //Заменяю символ в матрице на заглавный
        return true;
    }
    return false;
}

bool r(const string& s, vector< vector<char> >& v, int x, int y, int n) {
    if (s.size() == n) return true;
    char c = v[x][y + n];
    if (c  < 'a') c = char(c - 'A' + 'a');
    char cc = char(c + 'A' - 'a');
    if (s[n] == c and r(s, v, x, y, n+1)) {
        v[x][y + n] = cc;
        return true;
    }
    return false;
}

bool di(const string& s, vector< vector<char> >& v, int x, int y, int n) {
    if (s.size() <= n) return true;
    char c = v[x + n][y + n];
    if (c  < 'a') c = char(c - 'A' + 'a');
    char cc = char(c + 'A' - 'a');
    if (s[n] == c and di(s, v, x, y, n+1)) {
        v[x + n][y + n] = cc;
        return true;
    }
    return false;
}


void search(const vector<string>& w, vector< vector<char> >& v) {
    for (int i = 0; i < w.size(); ++i) { //"Перелистываю" слова
        for (int x = 0; x < v.size(); ++x) { //Перехожу на следующую строчку в матрице
            for (int y = 0; y < v[x].size(); ++y) { //Перехожу на следующую строчку в матрице
                // каждый if проверяет чтобы наш поиск не завел нас за матрицу
                if ((x + w[i].size() - 1) < v.size()) d(w[i], v, x, y, 0);
                if ((y + w[i].size() - 1) < v[0].size()) r(w[i], v, x, y, 0);
                if ((x + w[i].size() - 1) < v.size() and (y + w[i].size() - 1) < v[0].size()) di(w[i], v, x, y, 0);
            }
        }
    }
}

int main() {
    int x, m, n;
    bool first = true;
    while (cin >> x >> m >> n) {
        if (first) first = false;
        else cout << endl;
        vector<string> words(x);
        for (int i = 0; i < x; ++i) cin >> words[i];
        vector< vector<char> > crossword(m, vector<char> (n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) cin >> crossword[i][j];
        }
        search(words, crossword);
        for (int i = 0; i < m; ++i) {
            cout << crossword[i][0];
            for (int j = 1; j < n; ++j) cout << ' ' <<  crossword[i][j];
            cout << endl;
        }
    }
}

Ответ на: комментарий от Andaril

Пытался сходу понять твой алгоритм и как-то не получилось. Почитай про поиск подстроки в строке.
Опишу самый простой случай. Задан масив слов одинаковой длины и строка в которой производим поиск(в твоем случае будет множество строк [столбцы, строки, диагонали]). Считаем для каждого слова хэш (в простейшем случае сума букв) и запоминаем их в дереве (для более быстрого поиска). Потом выделяем окно равное длине слова и начиная с начала строки сдвигаем его попозиционно вправо, пересчитывая хэш (для приведеного примера сума букв, отнимаем левую букву, плюсуем правую) и проверяем есть ли такой хеш в дереве, если хеш совпал, то сравниваем посимвольно.

У Кнута половина 3го тома посвящена поиску.

Kristi ()
Ответ на: комментарий от Kristi

> Пытался сходу понять твой алгоритм и как-то не получилось.

Мой алгоритм заключается в том что бы для каждой буквы проверить есть ли там это слово в каком-нибудь направлении, то есть проверяется и сразу же заполняется... Вроде все просто, но исполнение убогое.)


Я так понимаю:
-создаю матрицуы в которых будут суммы букв столбцов, строк, диагоналей;
-создаю матрицу с суммами букв для каждого слова
-если сумма столбца/строки/диагонали >= сумма слова ищу там слово.

Мне кажется это и есть мой алгоритм плюс суммы... Это было бы выгодней если бы мне нужно было искать... кажется.

Andaril ()
Ответ на: комментарий от Andaril

> если сумма столбца/строки/диагонали >= сумма слова ищу там слово

зачем? при больших размерах матрицы это не поможет, при маленьких не нужно

и еще — у тебя почему-то GNU по диагонали тоже поднято

я бы создал свой класс матрицы, сделал 2 (или 3 если с диагональю) итератора, и юзал бы std::search

www_linux_org_ru ★★★★★ ()

Могу посоветовать давать более осмысленные имена переменным и функциям, 1-2 буквы это не comme il faut. Ещё нужно логические блоки кода разделять пустыми строками, а строки вида

        if (first) first = false; 
        else cout << endl; 
переписывать как
        if (first) 
            first = false; 
        else
            cout << endl; 

Legioner ★★★★★ ()
Ответ на: комментарий от Legioner
if (first)  
    first = false;  
else
    cout << endl;  

По уставу не положенно, будут снимать балы. К тому же мне гоогловский вариант больше нравиться.

Могу посоветовать давать более осмысленные имена переменным и функциям, 1-2 буквы это не comme il faut

Поправлю. Вредная привычка и писать лень.

Andaril ()
Ответ на: комментарий от www_linux_org_ru

зачем? при больших размерах матрицы это не поможет, при маленьких не нужно...

Вот я об этом и подумал!

и еще — у тебя почему-то GNU по диагонали тоже поднято

Так и надо.

std::search...

нельзя... могу использовать только самые примитивные инструкции...

Andaril ()

Упростить код можно вместо трех первых функций сделать одну... Но я пока не смог...

Andaril ()
Ответ на: комментарий от Legioner

Кстати по поводу

if (first) first = false;  
else cout << endl;  

Разве не лучше следующее?

cout << crossword[i][0]; 
for (int j = 1; j < n; ++j) cout << ' ' <<  crossword[i][j];

Andaril ()

Для начала матрицы надо сделать действительно матрицами. То есть это не вектор векторов, а обычный вектор с индексацией [i * n + j]. Соответственно m и n передавать во все функции, size не вызывать.

Reset ★★★★★ ()

Правлю код на пастебине. - Сделал одну функцию вместо трех, и добавил две переменные - заменил корткие и непонятные названия на длинные и неграммотные

Andaril ()
Ответ на: комментарий от Reset

То есть: Вместо таблици m на n я создаю вектор длинной m*n?

Когдато думал об этом, но руки не дошли... А в чем явное приимущество этого метода, и чем плох v.size()?

Andaril ()
Ответ на: комментарий от Andaril
 vector<char> crossword(m*n); 

Вместо?

 vector< vector<char> > crossword(m, vector<char> (n)); 
Andaril ()
Ответ на: комментарий от Andaril

Во первых косвенной адресации не будет, а во вторых кеш будет лучше использоваться.

Reset ★★★★★ ()
Ответ на: комментарий от Andaril

и чем плох v.size()?

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

Reset ★★★★★ ()
Ответ на: комментарий от Andaril

другое дело что к ячей мне придется обращаться спомощью... да ты это уже говорил

 v[i*n + j] 

но разве это не сатратней чем просто?

 v[i][j] 

где не надо каждый раз складывать? Или это уже зарание оптимизированно?

Andaril ()

Что значит оптимизировать? Зачем оптимизировать?

ТС, все предложенные выше «оптимизации» глупость и бред.

anonymous ()
Ответ на: комментарий от Andaril

тогда еще придется

if (j + 1 == n) cout << endl;
else cout << ' ';
но выглядит плохо...

Andaril ()
Ответ на: комментарий от anonymous

Что значит оптимизировать? Зачем оптимизировать?

Ну тогда: читабельносить упростить алгоритм уменьшить нагрузку на железо где это возможно

Andaril ()
Ответ на: комментарий от Andaril

Складывать в разы быстрее чем дважды лезть в память.

Reset ★★★★★ ()
Ответ на: комментарий от Andaril

> Ну тогда: читабельносить упростить алгоритм уменьшить нагрузку на железо где это возможно

Заменить рекурсию на итеративный процесс. Сделать одну функцию, которой передается направление обхода или вынести повторяющийся код из этих функций.

anonymous ()
Ответ на: комментарий от anonymous

Сделать одну функцию, которой передается направление обхода или вынести повторяющийся код из этих функций.

Так точно. pastebin

Заменить рекурсию на итеративный процесс

Не совсем понимаю как тут итерацию привинтить... Прелесть рекурсии в том что достаточно один раз прочитать и если все правельно, то буквы заменятся... в итерации придется читать два раза + плюс три булеана, но в итерации всеравно на много больше... эээх

Анонимус не ошибается...

Andaril ()
Ответ на: комментарий от Andaril

> Да... точно регистр быстрее чем RAM...

Не слушай этого дурака, нихера не понимает, а все туда же, сразу доступ к кешу надо оптимизировать.

anonymous ()
Ответ на: комментарий от Andaril

> Прелесть рекурсии в том что достаточно один раз прочитать и если все правельно, то буквы заменятся...

Если тебе не нужно искать длинных слов, тогда вопрос о скорости выполнения и переполнения стека не стоит.

anonymous ()
Ответ на: комментарий от anonymous

Если тебе не нужно искать длинных слов

Проверку осуществляет машина... но в принципе он проглотила и то что с верху висит. Дургое дело что итерацию всерано надо уметь. Так что буду думать.

Andaril ()
Ответ на: комментарий от anonymous

а все туда же, сразу доступ к кешу надо оптимизировать

Эта раза пока для меня загадка... Вообщем пока vector<char> (n*m) против vector< vector<char> > (m, vector<char> n) для меня не понятно. Короче итерацию допишу... тут уж проще разобраться.

Andaril ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.