Виж темите без отговор | Виж активните теми
Дата и час: Пет Мар 29, 2024 1:21 pm
Branch mode search string
Автор |
Съобщение |
slav4o.com
Ранг: Форумен бог
Регистриран на: Нед Яну 01, 2012 7:04 pm Мнения: 2582 Местоположение: Велико Търново / София
|
Branch mode search string
Имам една програма приема се някаква команда, по UART: ALABALA\r\n Устройството трябва да разпознае командата, тя може да бъде една от няколко, 10-15-20 команди. Това става с Това нещо разпознава командата и прави нещо според това коя е. Може командата да не е валидна и нищо не се прави. Както се вижда, командата която пристигне може да е 4-тата в списъка. CompareStrings() сравнява символ по символ. Очевидно това коства доста процесорно време. Тук идва моята идея, тя може би съществува реализирана, но не знам как се нарича в програмирането. Идеята ми е всички команди да са нещо като множество, със номера. При прочитане на първия символ received_string[0] ако той е 'C' да се отдели от множеството да останат само команда 0 и 1 След като стигнем до символ received_string[7] който е '0' или '1' да се отдели от множеството точната команда. Т.е. всеки следващ символ да отсява от множеството възможни команди определено подмножество, и така, докато се отсее само една команда. Мисля, че ще работи по-бързо ? Особено с по-голям брой възможни команди, а и времето ще е долу-горе орпеделелимо. Това нещо как се нарича в програмирането ? Искам да прочета по въпроса.
Последна промяна slav4o.com на Съб Окт 05, 2019 9:47 pm, променена общо 1 път
|
Съб Окт 05, 2019 9:43 pm |
|
|
bateAz
Ранг: Форумен бог
Регистриран на: Нед Сеп 26, 2004 3:11 pm Мнения: 3742 Местоположение: София
|
Re: Branch mode search string
Сортирай командите по азбучен ред и после търси с бинарно търсене.
|
Съб Окт 05, 2019 9:46 pm |
|
|
TheWizard
Ранг: Форумен бог
Регистриран на: Сря Апр 27, 2005 11:48 am Мнения: 4671
|
Re: Branch mode search string
при компариране, IF лоопа спира при първото неравенство, така е не губиш много време а и команда_Х, функция_Х ... може да ги сложиш в масив а не да пишеш 20 иф-а
_________________ main[-1u]={1};
|
Съб Окт 05, 2019 9:55 pm |
|
|
slav4o.com
Ранг: Форумен бог
Регистриран на: Нед Яну 01, 2012 7:04 pm Мнения: 2582 Местоположение: Велико Търново / София
|
Re: Branch mode search string
И сега е така - при несъвпадение на символ, веднага връща FALSE. По-скоро за "поетапно пресяване" ми е идеята. Това с масива не го разбрах. Мисля да ги подредя примерно по азбучен ред. Предварително да съставя карта. Ако са 100 команди, ще направя така, ако първият символ е 'A' интервала на множеството ще е 1-8 примерно - първите 8 команди започват с 'A' . После втория символ ако е 'L' задава интервал 3-8. Ако третият е 'A' интервала става 3-3 т.е. команда номер 3. Докрая на търсенето интервала ще си остава 3-3 т.е. командата ще е номер 3. или никаква (return FALSE) ако последва несъвпадение.
|
Съб Окт 05, 2019 10:05 pm |
|
|
palavrov
Ранг: Форумен бог
Регистриран на: Вто Окт 11, 2011 10:53 pm Мнения: 4174 Местоположение: Brussels / Пловдив
|
Re: Branch mode search string
Виж какво значи overengineering. Кода който ще изпишеш и паметта която ще изхабиш за да направиш някакъв супер ефективен алгоритъм ще ти костват много повече отколкото да изхабиш няколко цикъла в повече. Ако все пак решиш да се бориш има толкова много начини да се справиш с този проблем, че едва ли ще мога да ти ги изброя всички. Например можеш да сортираш всички команди по азбучен ред и после да направиш някакво модифицирано двоично търсене. Можеш първоначално да сметнеш дължината на изпратената команда (тя, нали все пак има някакъв символ за край или направо дължина) и да сравняваш само тези команди които са със същата дължина. За да не сравняваш всеки път стрингове можеш да сметнеш някакъв хеш и да сравняваш него с предварително изчислен хеш на всяка конада. Но най добре просто да не ползваш текстови команди ами да си заделиш 2 байта за бинарни и да си ги сравняваш като аритметични числа в един switch/case.
_________________ Мразя да мразя ...
|
Нед Окт 06, 2019 12:09 am |
|
|
palavrov
Ранг: Форумен бог
Регистриран на: Вто Окт 11, 2011 10:53 pm Мнения: 4174 Местоположение: Brussels / Пловдив
|
Re: Branch mode search string
Ако пък по някаква причина трябва да познаеш командата само два такта след последният приет цикъл можеш да правиш инкрементално търсене след всеки приет символ - така ще вършиш нещо полезно докато се чака следващият байт от серийният порт. За да има смисъл това е хубаво да сметнеш предварително мегахерците на процесора върху скоростта на серийния порт за да видиш с колко инструкции разполагаш между всеки два символа - сигурен съм, че числото наистина ще те изненада
_________________ Мразя да мразя ...
|
Нед Окт 06, 2019 12:14 am |
|
|
TheWizard
Ранг: Форумен бог
Регистриран на: Сря Апр 27, 2005 11:48 am Мнения: 4671
|
Re: Branch mode search string
ако са 100,200,300 .... мнооо команди стринга в масива е хаш а масива е сортиран по хаша и лупа търси хаш от масива с последователно приближаване...
_________________ main[-1u]={1};
|
Нед Окт 06, 2019 8:03 am |
|
|
gicho
Ранг: Форумен бог
Регистриран на: Пон Мар 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 |
|
|
Jack
Ранг: Ориентиран
Регистриран на: Вто Май 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 |
|
|
Bai Ui
Ранг: Форумен бог
Регистриран на: Вто Ное 06, 2018 4:18 pm Мнения: 1188
|
Re: Branch mode search string
Славчо, направи го със switch, кодът е бабешки, но е бърз и разбираем: При ПИK микроконтролерите всеки case отнема 2 инструкции т.е. най-дългото време за проверка се определя от най-дългата ти команда, ако е 10 символа това ще отнеме точно 20 инструкции до изпълнение на съответната функция.. Това същото горе може да се опише и със структура от поинтъри, кодът става по-компактен но по-неразбираем.
Последна промяна Bai Ui на Нед Окт 06, 2019 2:51 pm, променена общо 3 пъти
|
Нед Окт 06, 2019 12:57 pm |
|
|
amdatlon
Ранг: Почетен член
Регистриран на: Чет Мар 19, 2009 7:33 pm Мнения: 779
|
Re: Branch mode search string
Не че съм в час с програмирането но , да се изложа Ако може да променяш пращата програма, не може ли от там само да се праща номера на командата: Примерно 10-та команда, приемащото устройство - изпълнява номер 10. и т.н.т
|
Нед Окт 06, 2019 1:02 pm |
|
|
slav4o.com
Ранг: Форумен бог
Регистриран на: Нед Яну 01, 2012 7:04 pm Мнения: 2582 Местоположение: Велико Търново / София
|
Re: Branch mode search string
Пращащата програма е ESP8266 в режим модем с AT команди. Реално не мога да ги сменя, така са го направили. Въпросът ми е по-скоро принципен и сега устройството работи по бабешкия начин. Командите все пак не са много. За други модули в бъдеще, които имат много повече команди обаче, едва ли ще е ефективно. Данните които идват може да са произволни, и само по хеш няма да стане. Все пак си мисля, че хеша със 99% точност може да посочи първоначално командата и след това да я проверя допълнително символ по символ. Това пак би било доста ефективно. Първоначалният начин който си мислех е този на BaiUi само, че бая голямо дърво със switchowe ще стане. Ще разгледам всички идеи и ще попрочета това-онова. Процесора ми е 8 битов PIC на 32 MHz т.е. честота на инструкции 8 MHz . 8 000 000 / 115 200 = 69,4 инструкции време.
|
Нед Окт 06, 2019 1:21 pm |
|
|
Bai Ui
Ранг: Форумен бог
Регистриран на: Вто Ное 06, 2018 4:18 pm Мнения: 1188
|
Re: Branch mode search string
суичове ще имаш докато имаш разклонения, т.е. повече от едно съвпадение. Там , където нямаш раклонение може да провериш само остатъка от командата, пак със суич но за целия остатъчен стринг.
|
Нед Окт 06, 2019 1:27 pm |
|
|
slav4o.com
Ранг: Форумен бог
Регистриран на: Нед Яну 01, 2012 7:04 pm Мнения: 2582 Местоположение: Велико Търново / София
|
Re: Branch mode search string
Проблема е, че данните които идват освен команди могат да бъдат произволни стрингове. Така, че трбява обезателно да има пълна проверка.
|
Нед Окт 06, 2019 1:32 pm |
|
|
Кой е на линия |
Потребители разглеждащи този форум: 0 регистрирани и 1 госта |
|
Вие не можете да пускате нови теми Вие не можете да отговаряте на теми Вие не можете да променяте собственото си мнение Вие не можете да изтривате собствените си мнения Вие не можете да прикачвате файл
|
|