Отговори на тема  [ 28 мнения ]  Отиди на страница 1, 2  Следваща
Branch mode search string 
Автор Съобщение
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Яну 01, 2012 7:04 pm
Мнения: 2581
Местоположение: Велико Търново / София
Мнение Branch mode search string
Имам една програма приема се някаква команда, по UART:

ALABALA\r\n

Устройството трябва да разпознае командата, тя може да бъде една от няколко, 10-15-20 команди. Това става с
Код:
if(CompareStrings(received_string, "COMAND 0"){ // 0
    DoSomethingZero();
    return;
}

if(CompareStrings(received_string, "COMAND 1"){ // 1
    DoSomething();
    return;
}

if(CompareStrings(received_string, "KOMANDA 2"){ // 2
    DoSecondThing();
    return;
}

if(CompareStrings(received_string, "NQKAKVA DRUGA"){ // 3
    DoAnotherThing2();
    return;
}

if(CompareStrings(received_string, "NQKAKVA DRUGA 2"){ // 4
    DoAnotherThing();
    return;
}

if(CompareStrings(received_string, "CHETVARTA KOMANDA"){ // 5
    DoThingNumber4();
    return;
}


Това нещо разпознава командата и прави нещо според това коя е. Може командата да не е валидна и нищо не се прави.
Както се вижда, командата която пристигне може да е 4-тата в списъка. CompareStrings() сравнява символ по символ. Очевидно това коства доста процесорно време.
Тук идва моята идея, тя може би съществува реализирана, но не знам как се нарича в програмирането. Идеята ми е всички команди да са нещо като множество, със номера.
При прочитане на първия символ received_string[0] ако той е 'C' да се отдели от множеството да останат само команда 0 и 1 След като стигнем до символ received_string[7] който е '0' или '1' да се отдели от множеството точната команда. Т.е. всеки следващ символ да отсява от множеството възможни команди определено подмножество, и така, докато се отсее само една команда.
Мисля, че ще работи по-бързо ? Особено с по-голям брой възможни команди, а и времето ще е долу-горе орпеделелимо.
Това нещо как се нарича в програмирането ? Искам да прочета по въпроса.

_________________
https://github.com/slav4ocom/


Последна промяна slav4o.com на Съб Окт 05, 2019 9:47 pm, променена общо 1 път



Съб Окт 05, 2019 9:43 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Нед Сеп 26, 2004 3:11 pm
Мнения: 3742
Местоположение: София
Мнение Re: Branch mode search string
Сортирай командите по азбучен ред и после търси с бинарно търсене.


Съб Окт 05, 2019 9:46 pm
Профил ICQ
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Сря Апр 27, 2005 11:48 am
Мнения: 4671
Мнение Re: Branch mode search string
при компариране, IF лоопа спира при първото неравенство, така е не губиш много време
а и команда_Х, функция_Х ... може да ги сложиш в масив а не да пишеш 20 иф-а

_________________
main[-1u]={1};


Съб Окт 05, 2019 9:55 pm
Профил ICQ
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Яну 01, 2012 7:04 pm
Мнения: 2581
Местоположение: Велико Търново / София
Мнение Re: Branch mode search string
И сега е така - при несъвпадение на символ, веднага връща FALSE.
По-скоро за "поетапно пресяване" ми е идеята.
Това с масива не го разбрах.
Мисля да ги подредя примерно по азбучен ред. Предварително да съставя карта.
Ако са 100 команди, ще направя така, ако първият символ е 'A' интервала на множеството ще е 1-8 примерно - първите 8 команди започват с 'A' . После втория символ ако е 'L' задава интервал 3-8. Ако третият е 'A' интервала става 3-3 т.е. команда номер 3. Докрая на търсенето интервала ще си остава 3-3 т.е. командата ще е номер 3. или никаква (return FALSE) ако последва несъвпадение.

_________________
https://github.com/slav4ocom/


Съб Окт 05, 2019 10:05 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: Branch mode search string
Виж какво значи overengineering. Кода който ще изпишеш и паметта която ще изхабиш за да направиш някакъв супер ефективен алгоритъм ще ти костват много повече отколкото да изхабиш няколко цикъла в повече. Ако все пак решиш да се бориш има толкова много начини да се справиш с този проблем, че едва ли ще мога да ти ги изброя всички. Например можеш да сортираш всички команди по азбучен ред и после да направиш някакво модифицирано двоично търсене. Можеш първоначално да сметнеш дължината на изпратената команда (тя, нали все пак има някакъв символ за край или направо дължина) и да сравняваш само тези команди които са със същата дължина. За да не сравняваш всеки път стрингове можеш да сметнеш някакъв хеш и да сравняваш него с предварително изчислен хеш на всяка конада. Но най добре просто да не ползваш текстови команди ами да си заделиш 2 байта за бинарни и да си ги сравняваш като аритметични числа в един switch/case.

_________________
Мразя да мразя ...


Нед Окт 06, 2019 12:09 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Окт 11, 2011 10:53 pm
Мнения: 4174
Местоположение: Brussels / Пловдив
Мнение Re: Branch mode search string
Ако пък по някаква причина трябва да познаеш командата само два такта след последният приет цикъл можеш да правиш инкрементално търсене след всеки приет символ - така ще вършиш нещо полезно докато се чака следващият байт от серийният порт. За да има смисъл това е хубаво да сметнеш предварително мегахерците на процесора върху скоростта на серийния порт за да видиш с колко инструкции разполагаш между всеки два символа - сигурен съм, че числото наистина ще те изненада ;)

_________________
Мразя да мразя ...


Нед Окт 06, 2019 12:14 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Сря Апр 27, 2005 11:48 am
Мнения: 4671
Мнение Re: Branch mode search string
Код:
int strcmp(s1, s2)    register const char *s1, *s2;
{
   while (*s1 == *s2++) // при първо неравенство на букви лупа излиза - сравнява всички букви само ако са равни
      if (*s1++ == 0)
         return (0);
   return (*(unsigned char *)s1 - *(unsigned char *)--s2);
}



Код:
int (*cmd_handler)(char *);

typedef struct {
    const char * str;
    cmd_handler func;
} cmd_t

int doCmd_00(char * line){ return 0; } // самата команда
...
int doCmd_99(char * line){ return 0; } // самата команда


const cmd_s comands[] = {
    { "cmd-00", doCmd_00 },
    { "cmd-01", doCmd_01 },
    ...
    { "cmd-99", doCmd_99 },
}

for(int i = 0; i<LEN_ARRAY(comands), i++){
    if( compare(line, comands[i].str) )
        if( comands[i].func )
            return comands[i].func( line );
    return -1;
}


ако са 100,200,300 .... мнооо команди
стринга в масива е хаш а масива е сортиран по хаша и лупа търси хаш от масива с последователно приближаване...

_________________
main[-1u]={1};


Нед Окт 06, 2019 8:03 am
Профил ICQ
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Пон Мар 13, 2006 12:59 pm
Мнения: 3855
Местоположение: Габрово
Мнение Re: Branch mode search string
Съгласен съм че е леко безсмислено от практическа гледна точка, но пък то така всичко любителско може да се хвърли на торището по този принцип.
Принципно това дето го правиш му викат parser и така можеш да ровиш за идеи. Има разни "parser generator" продукти които по описание на "езика" ти генерират кода за парсера. При моите ровения не намерих нищо човешки използваемо за C - но за модерно C++ и нагоре има опции. Не че правят идеалния като производителност парсер, но там бонуса е че лесно се поддържат - ако смениш граматиката си на един клик от новия парсер, отделно тия продукти са минали сериозно тестване.
Ако ти се играе в тази посока трябва да помислиш и за някой други неща:
- времето за реакция на първия символ ще е съществено различно от това на последния - в смисъл че олекотяването няма да ти помогне да гарантираш някаква максимална скорост на реакция, но все пак ще ти позволи да спестиш процесорно време по-късно (евентуално)
- ако правиш нещо с хешови таблици виж uthash и utlist - да не почваш от нулата
Това което правиш мяза на някакъв шел може би? Очаква се да се ползва интерактивно от естествен интелект, или ще идват заучени цели команди от друга програма? Ако е за шел с човек и си търсиш играчка можеш да пробваш да направиш разните екстри на unix шеловете - даже мисля че в nuttx и някъде другаде имаше такова нещо. Някой май беше портвал същото от bash може би за freertos или нещо подобно ембедед.


Нед Окт 06, 2019 8:54 am
Профил
Ранг: Ориентиран
Ранг: Ориентиран

Регистриран на: Вто Май 07, 2019 8:16 pm
Мнения: 275
Мнение Re: Branch mode search string
Slav40, то хубаво 'да прочетеш нещо по въпроса' както казваш ( благородно намерение ), но на четивата (поне дето аз попадам напоследък) - всичките се нуждаят от сериозно привеждане в "Чомски нормал форм" , дет се вика - в даден брой прочетени страници да може предвидимо да увеличаваш стринга от знания. Аз имам чувството че докато чета някой от нароилите се в последно време четива , 'стринга' вместо да се увеличава, направо си намалява ( след 500-1000 страници плаямпология - поне знам името на котката на автора, любимия му цвят, имената на родата му и т.н. и на кой автор от книгата от 100 страници от 70-те години са преписали съществената част след първите 900 страници увод.).
Значи като опции остават: Опция 1: ползваш готовите примери от по-горе на колегите Уизард, Палавров и Гичо и се бориш да ги нагласяш за твоя случай докато проработят и докато ги проумееш.
Опция 2: Ако в определен момент командите за разпознаване станат толкова че от многото IF кода заприлича на кадаIF , четеш в насока Парсери , Стейт Машини и пробваш да направиш собствена машина за парсване. Концептуално - декларира се примерно една променлива флаг за текущото състояние в което се намира машината в момента- int state; След това тя и постъпващия символ се ползват в switch - case конструкция където следващото състояние зависи от текущото и постъпващия символ на входа. Ако се получи символ на входа, машината от начално състояние q0 преминава в 'ънхепи състояние' и сменя флага за състоянието. Докато е в начално и в междинно 'ънхепи' състояние, машината не прави нищо освен да предава нишката на следващите процеси след 'машината'. И така докато мине през определен брой постъпили символи и бранчове и попадне в едно от многото финални 'хепи' състояния където чака твоя 'нестнат' код.


Последна промяна Jack на Нед Окт 06, 2019 11:00 am, променена общо 1 път



Нед Окт 06, 2019 10:40 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог
Аватар

Регистриран на: Нед Ное 21, 2004 10:31 pm
Мнения: 9635
Мнение Re: Branch mode search string
https://www.l2f.inesc-id.pt/~david/w3/p ... _Variables
яковете бяха първи, оригинално от Кърниган (~1975). бизоните и гнута донякъде са продължение на стадото говеда (~1990).
ако говорим за по-прости неща, един класически getopt също върши (донякъде) работа.
плен С със stdlib.

но:
(1) стринговите библиотеки са писани с идея максимална преносимост без да отчитат спецификата на конкретния процесор. мого процесори вече имат инструкции за манипулация на стрингове -> може да се получи по-бърза и по-малка библиотечка, но ще работи само на съответната архитектура.
(2) prinf и приятели (примерно atoi) също са разточителни, особено ако са по-пълна реализация.

ако си с малко мускули - хешовия вариант ще е малък и бърз (ама наистина бърз!). неприятното е, че трябва предварително да знаеш всички вариации на думичките и да провериш дали няма повторения на хеша.

ако мускулите са бол вече не си толкова ограничен и критерия, който трябва да те вълнува е разбираемост на кода.
кадаIF определено не е подходящ стил.


Нед Окт 06, 2019 10:59 am
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Ное 06, 2018 4:18 pm
Мнения: 1188
Мнение Re: Branch mode search string
Славчо, направи го със switch, кодът е бабешки, но е бърз и разбираем:
Код:
switch(received_string[0]) {                           // тук проверяваме първият байт от приетия стринг за съвпадения
       case "a":                                                  // процесора отива тук ако първият байт е "a"
             switch(received_string[1]) {               // тук проверяваме вторият байт от приетия стринг ако започва с "а"
              case "a":                                           // процесора отива тук ако първият и вторият байт са "a"
                аа();                                                // ако имаме в списъка команда "аа" тук извикваме съответната функция.
              break;
              ...
              default:                                             // тук отиваме ако няма съвпадения във втория байт
              }
       break;
       case "б":                                                  // процесора отива тук ако първият байт е "б"
       break;
       ...
       default:                                                    // тук отиваме ако няма съвпадения в първия байт
}

При ПИK микроконтролерите всеки case отнема 2 инструкции т.е. най-дългото време за проверка се определя от най-дългата ти команда, ако е 10 символа това ще отнеме точно 20 инструкции до изпълнение на съответната функция.. Това същото горе може да се опише и със структура от поинтъри, кодът става по-компактен но по-неразбираем.


Последна промяна Bai Ui на Нед Окт 06, 2019 2:51 pm, променена общо 3 пъти



Нед Окт 06, 2019 12:57 pm
Профил
Ранг: Почетен член
Ранг: Почетен член

Регистриран на: Чет Мар 19, 2009 7:33 pm
Мнения: 779
Мнение Re: Branch mode search string
slav4o.com написа:
Имам една програма приема се някаква команда, по UART:

Не че съм в час с програмирането но , да се изложа :)
Ако може да променяш пращата програма, не може ли от там само да се праща номера на командата:
Примерно 10-та команда,
приемащото устройство - изпълнява номер 10.
и т.н.т


Нед Окт 06, 2019 1:02 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Яну 01, 2012 7:04 pm
Мнения: 2581
Местоположение: Велико Търново / София
Мнение Re: Branch mode search string
Пращащата програма е ESP8266 в режим модем с AT команди.
Реално не мога да ги сменя, така са го направили. Въпросът ми е по-скоро принципен и сега устройството работи по бабешкия начин. Командите все пак не са много. За други модули в бъдеще, които имат много повече команди обаче, едва ли ще е ефективно.
Данните които идват може да са произволни, и само по хеш няма да стане. Все пак си мисля, че хеша със 99% точност може да посочи първоначално командата и след това да я проверя допълнително символ по символ. Това пак би било доста ефективно.
Първоначалният начин който си мислех е този на BaiUi само, че бая голямо дърво със switchowe ще стане.
Ще разгледам всички идеи и ще попрочета това-онова.
Процесора ми е 8 битов PIC на 32 MHz т.е. честота на инструкции 8 MHz . 8 000 000 / 115 200 = 69,4 инструкции време.

_________________
https://github.com/slav4ocom/


Нед Окт 06, 2019 1:21 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Вто Ное 06, 2018 4:18 pm
Мнения: 1188
Мнение Re: Branch mode search string
slav4o.com написа:
Пращащата програма е ESP8266 в режим модем с AT команди.
Реално не мога да ги сменя, така са го направили. Въпросът ми е по-скоро принципен и сега устройството работи по бабешкия начин. Командите все пак не са много. За други модули в бъдеще, които имат много повече команди едва ли ще е ефективно.
Данните които идват може да са произволни, и само по хеш няма да стане. Все пак си мисля, че хеша със 99% точност може да посочи първоначално командата и след това да я проверя допълнително символ по символ. Това пак би било доста ефективно.
Първоначалният начин който си мислех е този на BaiUi само, че бая голямо дърво със switchowe ще стане.
Ще разгледам всички идеи и ще попрочета това-онова.

суичове ще имаш докато имаш разклонения, т.е. повече от едно съвпадение. Там , където нямаш раклонение може да провериш само остатъка от командата, пак със суич но за целия остатъчен стринг.


Нед Окт 06, 2019 1:27 pm
Профил
Ранг: Форумен бог
Ранг: Форумен бог

Регистриран на: Нед Яну 01, 2012 7:04 pm
Мнения: 2581
Местоположение: Велико Търново / София
Мнение Re: Branch mode search string
Bai Ui написа:
суичове ще имаш докато имаш разклонения, т.е. повече от едно съвпадение. Там , където нямаш раклонение може да провериш само остатъка от командата, пак със суич но за целия остатъчен стринг.

Проблема е, че данните които идват освен команди могат да бъдат произволни стрингове. Така, че трбява обезателно да има пълна проверка.

_________________
https://github.com/slav4ocom/


Нед Окт 06, 2019 1:32 pm
Профил
Покажи мненията от миналия:  Сортирай по  
Отговори на тема   [ 28 мнения ]  Отиди на страница 1, 2  Следваща

Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 3 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения
Вие не можете да прикачвате файл

Търсене:
Иди на:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.
Хостинг и Домейни