2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:10 


16/05/19
5
Код:
int mystrcmp(const char* a, const char* b)
{
   char abetka[100] = {'А', 'а', 'Б', 'б', 'В', 'в', 'Г', 'г', 'Ґ', 'ґ', 'Д', 'д', 'Е', 'е', 'Є', 'є', 'Ж', 'ж', 'З', 'з',
                   'И', 'и', 'І', 'і', 'Ї', 'ї', 'Й', 'й', 'К', 'к', 'Л', 'л', 'М', 'м', 'Н', 'н', 'О', 'о', 'П', 'п', 'Р',
                   'р', 'С', 'с', 'Т', 'т', 'У', 'у', 'Ф', 'ф', 'Х', 'х', 'Ц', 'ц', 'Ч', 'ч', 'Ш', 'ш', 'Щ', 'щ', 'ь', 'Ю',
                   'ю', 'Я', 'я' };

}

как сделать цикл сравнения 2 слов по буквенно с даного масива?
если а>b return 1 b>a return -1

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:17 
Заслуженный участник


02/08/11
6874
Вам минимально эффективное решение нужно или лишь бы работало?
(Кстати, в вашем инициализаторе массива меньше ста элементов, поэтому в конце вашего массива много нулей. Зачем они вам?)

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:21 


16/05/19
5
warlock66613 в сообщении #1393283 писал(а):
Вам минимально эффективное решение нужно или лишь бы работало?
(Кстати, в вашем инициализаторе массива меньше ста элементов, поэтому в конце вашего массива много нулей. Зачем они вам?)

эффективное,пожалуйста.Но не откажусь для ознакомления и от варианта лишь бы работало)

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:32 
Заслуженный участник


02/08/11
6874
Тогда давайте начнём с варианта "лишь бы работало". Будем разрабатывать алгоритм сверху вниз - то есть декомпозировать на более мелкие операции, а их потом на ещё более мелкие.

Итак, нам надо сравнить строки. Предположим, что мы уже умеем сравнивать буквы. То есть есть функция int cmpch(char a, char b), которая правильно сравнивает буквы. Сможете написать сравнение строк, пользуясь ею?

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:39 


16/05/19
5
warlock66613 в сообщении #1393287 писал(а):
Тогда давайте начнём с варианта "лишь бы работало". Будем разрабатывать алгоритм сверху вниз - то есть декомпозировать на более мелкие операции, а их потом на ещё более мелкие.

Итак, нам надо сравнить строки. Предположим, что мы уже умеем сравнивать буквы. То есть есть функция int cmpch(char a, char b), которая правильно сравнивает буквы. Сможете написать сравнение строк, пользуясь ею?

Код:
int mystrcmp(const char* a, const char* b)
{
    const char * abetka = "АаБбВвГ㥴ДдЕеЄєЖжЗзИиІіЇїЙйКкЛлМмНнОоПпРрСсТтУуФфХхЦцЧчШшЩщьЮюЯя";
    for(;*a && *b; ++a, ++b)
    {
       const char * apos = strchr(abetka,*a);
        const char * bpos = strchr(abetka,*b);
        if (apos == NULL || bpos == NULL)
        {
            puts("...");
            abort();
        }
        if (apos < bpos) return  1;   // a раньше по алфавиту
        if (apos > bpos) return -1;   // b раньше по алфавиту
    }
    if (*a && !*b) return -1;    // b короче
    if (!*a && *b) return  1;    // a короче
    return 0;
}

посидел только что- написал такое.Вроде работает.Это можно считать эффектиным методом или нет?

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:44 
Заслуженный участник


02/08/11
6874
Svyat.Vasik в сообщении #1393290 писал(а):
Это можно считать эффектиным методом или нет?
Это как раз то, что я назвал "неэффективным". Но не так уж он и плох, конечно. А чтобы сделать "эффективный", надо знать как именно закодированы символы - тогда, используя это знание, можно заменить strchr по массиву на быстрое вычисление индекса.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:47 


16/05/19
5
warlock66613 в сообщении #1393292 писал(а):
Svyat.Vasik в сообщении #1393290 писал(а):
Это можно считать эффектиным методом или нет?
Это как раз то, что я назвал "неэффективным". Но не так уж он и плох, конечно. А чтобы сделать "эффективный", надо знать как именно закодированы символы - тогда, используя это знание, можно заменить strchr по массиву на быстрое вычисление индекса.

что вы имеете ввиду под быстрым вычислением индекса?циклом?

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 09:48 
Заслуженный участник


02/08/11
6874
Хотя, даже без знания кодировки можно заменить strchr на большой switch по буквам.

-- 16.05.2019, 10:50 --

Svyat.Vasik в сообщении #1393293 писал(а):
циклом?
Нет, именно без цикла (который есть внутри strchr). Самое простое - написать большой switch. Компиляторы обычно довольно эффективно компилируют такую конструкцию.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 10:03 


16/05/19
5
warlock66613 в сообщении #1393294 писал(а):
Хотя, даже без знания кодировки можно заменить strchr на большой switch по буквам.

-- 16.05.2019, 10:50 --

Svyat.Vasik в сообщении #1393293 писал(а):
циклом?
Нет, именно без цикла (который есть внутри strchr). Самое простое - написать большой switch. Компиляторы обычно довольно эффективно компилируют такую конструкцию.

значит 66 свичей с внутренними аски кодами вместо стрцхр?

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 10:16 
Заслуженный участник


02/08/11
6874
Svyat.Vasik в сообщении #1393298 писал(а):
значит 66 свичей с внутренними аски кодами вместо стрцхр?
Да, 66 кейсов (только я насчитал 65, 66-м будет default: с выдачей ошибки). Явно коды можно не писать, а писать просто case 'А':, case 'Б': и т. д.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 12:43 


16/04/19
161
Можно выходить из цикла по условию
Код:
*a != *b
вместо apos < bpos и apos > bpos, а искать apos и bpos только в случае выхода по этому условию. Если не сработало
Код:
*a && *b
, то тогда сравнивать длины. Вроде норм будет.
На счёт switch не уверен, что будет быстро работать. Если будет медленно, то можно сделать массив, как выше написали, длинной 256, чтобы он сразу индекс выдавал(и использовать unsigned char для доступа к массиву). Оба варианта универсальны. Ну или считерить - посмотреть таблицу ASCII, чтобы за несколько условий сравнивать символы.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 12:44 
Заслуженный участник


20/08/14
11059
Россия, Москва
Интересно, не быстрее ли будет табличное преобразование кода символа в его номер по алфавиту? Для однобайтных кодировок вполне применимо. Зато всего два обращения в память к одной табличке 256 байтов (быстро попадёт вся в кеш) и три сравнения (третье - проверка одновременно двух нулевых символов, т.е. равенства строк, условие цикла можно не проверять сделав его бесконечным), причём можно сразу сделать чтобы более короткая строка была меньше (закодировав самый меньший номер для символа 0x00 конца строки). К сожалению с Unicode табличка становится довольно большой, хотя всё нужное будет быстро закешировано и на скорость не повлияет. Зато можно бесплатно (без уменьшения скорости) вводить классы эквивалентности символов, типа "Б"="б" или "Ё"="Е" и "ё"="е". По моему именно этот вариант будет оптимальным по скорости.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 13:04 
Аватара пользователя


14/11/12
1338
Россия, Нижний Новгород
Dmitriy40 в сообщении #1393346 писал(а):
Интересно, не быстрее ли будет табличное преобразование кода символа в его номер по алфавиту?
Конечно быстрее.

Код:
order['A'] = 1;
order['a'] = 1;
order['Б'] = 2;
order['б'] = 2;

...

if (order[*a] < order[*b]) return 1;

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 13:34 


16/04/19
161
Dmitriy40 в сообщении #1393346 писал(а):
не быстрее ли будет табличное преобразование кода символа в его номер по алфавиту

Если в стеке хранить то ещё не очень плохо. Если массив где-то далеко в куче, то локальность ухудшается, а это плохо, ну там у кэша вроде всего несколько блоков-окошек в память, которые сплошные.
В идеале, если switch нормально оптимизируется, данные о кодах символов будут в кодовой памяти, но понадобится несколько сравнений, т.к. на этапе компиляции будут известны все коды символов, а они пачками лежат в таблице.

 Профиль  
                  
 
 Re: как сравнивать два слова без стрсмп
Сообщение16.05.2019, 14:57 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Svyat.Vasik в сообщении #1393280 писал(а):
Код:
'Ґ', 'ґ', 'Є', 'є', 'Ї', 'ї'

В какой кодировке у вас исходный файл? Если что, Unicode в char не помещается.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group