үш шартты ауыстырудың ең жылдам алгоритмі қандай?

Маған ең төменгі қадамдардағы үш жағдайды бағалаудың ең жылдам әдісі туралы маған ешкім көмектесе ала ма? Менде үш шарт бар және егер екеуінің бірі шын болса, онда толық өрнек true else false болады.

Мен екі әдісті көрдім:

if ((condition1 && condition2) || 
    (condition1 && condition3) || 
    (condition2 && condition3))

Басқа әдіс - айнымалы i және енгізу арқылы

i = 0;
if (condition1) i++;
if (condition2) i++;
if (condition3) i++;
if (i >= 2)
    //do something

Мен жоғарыда айтылғандарға қарағанда кез келген басқа тиімді әдісті қалаймын.

Мен есте сақтау шектеулі ортада жұмыс істеймін (8 кб флеш-жады бар Atmeta8) және C-ге жұмыс істейтін шешім қажет.

7
Шарттары қазірдің өзінде есептелетін логикалық айнымалылар немесе олар әлі бағаланған өрнектер болып табылады және оларды бағалаудан аулақ болғыңыз келе ме?
қосылды автор jxh, көзі
Мен 3-тен 2-нің шын екендігін білуім керек екенін білемін. Сіздің сұрағыңызда condition1 , condition2 және condition3 int айнымалылар болып табылады ма? Сұраймын, себебі олар look сұрағыңыздағы айнымалылар сияқты.
қосылды автор jxh, көзі
@ MichaelKjörling: Ия, ПП PHP жауапына түсініктеме берді.
қосылды автор geoffspear, көзі
Сондықтан біз бұл C екеніне сенімдіміз, мысалы: Java, C ++, C# немесе C сияқты басқа C тілі, шын мәнінде C емес?
қосылды автор Michael Kjörling, көзі
@Wooble Ах, қазір оны көремін. OK, содан кейін жылжытыңыз. :)
қосылды автор Michael Kjörling, көзі
@jxh Оны есептеу керек.
қосылды автор shafeeq, көзі

8 жауаптар

Бұл төмендегілерге дейін қысқартылуы мүмкін:

if((condition1 && (condition2 || condition3)) || (condition2 && condition3))
    //do something

Әрбір жағдайдың ықтималдығына қарай, тезірек қысқа тұйықталуды алу үшін тапсырыс беруді оңтайландыруға болады (бұл, мүмкін, мерзімінен бұрын оңтайландыру болады ...)

9
қосылды
«бұл, мүмкін, мерзімінен бұрын оңтайландыру болар еді». - Жоқ, ол ешқандай күш жұмсамаса немесе қандай да бір маңызды кодын өзгертпесе, ол болмайды.
қосылды автор Christian Rau, көзі
@ChristianRau: жақсы, бұл әр түрлі шарттардың статистикалық ықтималдығын анықтау үшін күш-жігерді қажет етеді, ол тривиальды болуы мүмкін немесе болмауы мүмкін.
қосылды автор geoffspear, көзі
Бұл жай ғана ықтималдықпен тапсырыс беріп қана қоймайды. Егер жағдайдың біреуін бағалау қиын болса, онда ол қысқа тұйықталу ықтималдығы жоғары орынға ауысу керек.
қосылды автор sh1, көзі
yeah @wooble менің екеуімнен жақсы
қосылды автор shafeeq, көзі

Жақсы «жақсы» шешім беру (әрине, кодыңызды, оқылатындығын, орындалу жылдамдығын, машина кодының нұсқауларының байттар саны ... ...) дегенмен, әрине, әрқашан қиын. Бұл жағдайда біз бұл мәселеге назар аудара аламыз.

You can introduce that variable you suggest, and use it to reduce the conditions to a simple less-than condition once the answer is known. Less-than conditions trivially translate to two machine code instructions on most architectures (for example, CMP (compare) followed by JL (jump if less than) or JNL (jump if not less than) on Intel IA-32). With a little luck, the compiler will notice (or you can do it yourself, but I prefer the clarity that comes with having the same pattern everywhere) that trues < 2 will always be true in the first two if() statements, and optimize it out.

int trues = 0;
if (trues < 2 && condition1) trues++;
if (trues < 2 && condition2) trues++;
if (trues < 2 && condition3) trues++;
// ...
if (trues >= 2)
{
   //do something
}

Бұл жауап белгілі болғанда көптеген тілдердің логикалық қысқа тұйықталу әрекеті салдарынан conditionN ықтимал кешенді бағалауды азайтады.

Тіліңіз логикалық жағдайды бүтін санға шығаруға мүмкіндік беретін болса, басқа ықтимал нұсқасы - бұл бастапқы кодының санын азайту үшін артықшылығын пайдалану. Дегенмен, сіз әлі де әр шартты бағалайсыз.

if( (int)(condition1)
  + (int)(condition2)
  + (int)(condition3)
  >= 2)
{
   //do something
}

Бұл логикалық FALSE мәнін бүтін санға ауытқу 0 деп келтіріп, TRUE нәтижесін 1 мәніне шығаратын болжамға негізделіп жұмыс жасайды. Қосымша салынды енгізуді білуіне қарамастан, сіз шартты операторды сол әсер үшін пайдалана аласыз.

if( ((condition1) ? 1 : 0)
  + ((condition2) ? 1 : 0)
  + ((condition3) ? 1 : 0)
  >= 2)
{
   //do something
}

Компилятордың оңтайландырушысының қаншалықты ақылды екеніне қарай, мүмкін кез-келген екі шарт шындыққа бағаланғаннан кейін барлық жағдай шындыққа бағаланады және сол негізінде оңтайландырылатынын анықтай алады.

  • Егер сіз өзіңіздің кодын құрсаңыз және оны кінәлі деп таппасаңыз , бұл, мүмкін, мерзімінен бұрын оңтайландыру жағдайлары. Алдымен at - нақты өнімділік жетіспеушілігі. Профильдің қалай жұмыс істейтінін біліңіз және оны жақсы пайдалануға енгізіңіз. Көптеген жағдайларда бағдарламашы уақыты - CPU уақытынан гөрі қымбатырақ, ал ақылды техникалар бағдарламалаушыға талдау жасайды.
  • Сондай-ақ, компиляторлар шын мәнінде бағдарламалық қамтамасыз етудің ақылды бөліктері болып табылады; кейде олар нақты жазылған кодтың ниетін анықтайды және сол операцияларды тезірек жасауға арналған нақты конструкцияларды пайдалана алады, бірақ ол сіз не жасауға тырысатыныңызды анықтауға негізделеді. Мұның тамаша мысалы, IA-32-дегі аралық айнымалы айнымалыны жою арқылы XCHG арқылы жасалуы мүмкін делдалдық ауыспалы көмегімен екі айнымалыны ауыстыру болып табылады, бірақ компилятор сіз іс жүзінде жасай алатыныңызды анықтауы керек Кейбір жағдайларда басқа нәтиже бере алатын ақылды нәрсе.
  • Жазылмайтын бағдарламалық жасақтаманың басым көпшілігі техникалық қызмет көрсету режимінде оның өмірінің басым бөлігін жұмсайды (және жазылған қашықтан салынған бағдарламалардың көпшілігі тірі және ұзақ мерзімге дейін барынша жақсы уақыт өткен соң) жұмсалғандықтан, егер бұл басқа жағынан қолайсыз шығындар болмаса, оңтайландырады. Әрине, егер сіз бұл жағдайды қатаң цикл ішінде триллион рет бағалай берсеңіз, мақсатты оңтайландыру өте жақсы болуы мүмкін. Бірақ профильдер сізге кодының қандай бөліктерін өнімділік тұрғысынан мұқият қарастыру керек екенін білдіреді, яғни кодты қажетсіз түрде қиындатудан аулақ боласыз.

Және жоғарыда айтылған ескертулерде, жақында кодексте жұмыс істеп келе жатқан өзгерістерді жасаймын, олар бір кездері дереу мерзімінен бұрынғы бөлшекті оңтайландыру болып саналады. Егер жоғары өнімділікке қойылатын талаптарыңыз бар болса және профиляторды кодтың қай бөліктерінде қиындықтар бар екенін анықтау үшін қолдансаңыз, онда оңтайландыру мерзімінен бұрын болмайды. (Дегенмен, олар нақты жағдайға байланысты әлі де қате ескерту болуы мүмкін.)

4
қосылды
екі жылдамдығын және орындау жылдамдығы үшін оңтайландыру өте қиын. Біреуі оңай, бірақ екеуі бірдей қиын. әдетте біреуін немесе екіншісін таңдайды және екіншісінің есебінен оңтайландырады. Сіз қайталау үшін бір жерде екі бит таба алмайсыз ба? (Және айнымалы мәндер шынымен flash жадында сақталады? Мұндай жағдайда: ouch!)
қосылды автор Michael Kjörling, көзі
Құрметті @ Майкл жақсы нәрсені ойладым, тезірек орындағаныңыз үшін екінші тәсілдеме алғысымды білдіремін, сонымен қатар, бұл код адамды адамға оқуға болатындығын айтады, өйткені біз адамға емес, машинаны кодтайтын боламыз, кодты түсіну
қосылды автор shafeeq, көзі

Сіздің тіліңізге байланысты, мен келесідей нәрсеге жүгінуіме болады:

$cond = array(true, true, false);

if (count(array_filter($cond)) >= 2)

немесе

if (array_reduce($cond, function ($i, $k) { return $i + (int)$k; }) >= 2)
3
қосылды
@shafeeq Осындай ақпарат шынымен тікелей сұрақ қоюға тура келеді, бірақ ол, кем дегенде, бір жерде айтылған жақсы.
қосылды автор Michael Kjörling, көзі
Мен үшін код қажет
қосылды автор shafeeq, көзі

Бұл үшін абсолютті жауап жоқ. Бұл негізгі сәулетке байланысты. Мысалы: егер VHDL немесе Verilog бағдарламасында кейбір аппараттық тізбектерді бағдарламаласаңыз, онда бірінші нәтиже сізге ең жылдам нәтиже береді. Менің болжауымша, сіздің мақсатыңыз қандай да бір CPU-ді, бірақ тіпті мұнда өте көп мақсатты CPU-ға, ол қолдайтын нұсқауға және қандай уақытқа созылатынына байланысты болады. Сондай-ақ, сіз сіздің мақсатты тіліңізді көрсетпейсіз (мысалы, сіздің алғашқы тәсіліңіз жылдамдыққа қатты әсер ететін қысқа тұйықталған болуы мүмкін).

Егер ештеңе білмесеңіз, екінші шешімімді ұсынар едім - себебі сіздің ниетіңіз (кем дегенде 2 жағдай шын болуы керек) кодта жақсы көрінеді.

Екі шешімнің жылдамдық айырмашылығы өте жоғары болмайды - егер бұл тек кейбір логика болса, бірнеше рет орындалатын кейбір ішкі бөліктердің бөлігі болмаса, мен тіпті мерзімінен бұрын оңтайландыруды болжап, басқа жерде оңтайландыруға тырысатын болар едім.

1
қосылды
Шын мәнінде бұл Atmega8 коды және бұл ішкі loop.so жылдамдық факторын ескере отырып, бірінші тәсіл жақсы.
қосылды автор shafeeq, көзі

Біз тереңдетілген архитектураға кірмегендіктен, әдетте жұмыс үстелін жасаушылар ұсынған оңтайландыруларға жол бермейтін филиалдардан қашуға ешқандай құндылық болмайды. Қысқартулар - алтын, мұнда.

Егер сіз:

if ((condition1 && (condition2 || condition3)) || (condition2 && condition3))

онда сіз ең жақсы мүмкіндік бар, қосымша ақпаратқа байланысты, компилятордан ең жақсы машина кодын алу. Модульде кодтың өлшемін азайту үшін condition2 condition2 бірінші бағалауына қарай condition2 тармағын екінші бағалауы бар нәрселерді жасауға болады, бірақ экспресс жасаудың сенімді жолы жоқ бұл C.

Егер әдетте сынақтан өтпейтіндігіңізді білсеңіз және сіз қандай екі шартты әдетте туындататындығыңызды білсеңіз, онда сіз:

if ((rare1 || rare2) && (common3 || (rare1 && rare2)))

бірақ компилятор толығымен қайта реттеп, өзінің қысқа мерзімді келісімшартын пайдаланатыны өте жақсы мүмкіндік бар.

__ builtin_expect() немесе _Rarely() немесе қандай да бір компилятор шарттың ықтимал нәтижесін көрсетуге мүмкіндік беретін кез-келген нәрсені түсіндіруге болады.

Дегенмен, өнімділікті айтарлықтай жақсартатын жағдай, жалпы сынақты жеңілдететін шарттармен немесе шарттарды сынақтан өткізудің кез-келген жолымен кез-келген жалпы факторларды таниды.

Мысалы, егер тесттер қарапайым болса, онда жинақтарда жағдайды жылдам жинақтау үшін кейбір негізгі қылықтар жасалуы мүмкін. C-ге кері жүктелген порттар кейде өміршең болады.

1
қосылды

You may consider simpy adding them. If you use masroses from standart stdbool.h, then true is 1 and (condition1 + condition2 + condition3) >= 2 is what you want.

Бірақ бұл әлі де микроптитмизацией, әдетте, сіз осындай өнімділікті жоғарылатасыз.

0
қосылды
менің жауапыма ұсынылған әдістердің бірі дәлме-дәл болып табылады (минус ашық түрде).
қосылды автор Michael Kjörling, көзі

Сіз барлық жағдайларды бағалауға тырысасыз, себебі сіз өзіңізге осындай шешім ұсындыңыз. Егер шарттар өте күрделі формулалар болса, онда көптеген процессорлық циклдар есептеледі (жүздеген миллисекундтар тәртібі сияқты), жылдамдықты жоғарылату үшін барлық үш жағдайды бір мезгілде бағалауға болады. Бір нәрсе:

pthread_create(&t1, detached, eval_condition1, &status);
pthread_create(&t2, detached, eval_condition2, &status);
pthread_create(&t3, detached, eval_condition3, &status);
pthread_mutex_lock(&status.lock);
while (status.trues < 2 && status.falses < 2) {
    pthread_cond_wait(&status.cond, &status.lock);
}
pthread_mutex_unlock(&status.lock);
if (status.trues > 1) {
    /* do something */
}

Бұл сізге жылдамдықты қамтамасыз ететін болсын, шарттарды есептеу қаншалықты қымбат екеніне байланысты. Есептеу уақыты жіп құруды және синхрондау үстемелерін үстем етуі керек.

0
қосылды

Бұл әрекетті байқап көріңіз:

unsigned char i;

i = condition1;
i += condition2;
i += condition3;
if (i & (unsigned char)0x02)
{
    /*
    At least 2 conditions are True
    0b00 - 0 conditions are true
    0b01 - 1 conditions are true
    0b11 - 3 conditions are true 
    0b10 - 2 conditions are true
    So, Checking 2nd LS bit is good enough.
    */
}
0
қосылды
Барлық шарттарды бағалағаннан кейін бағалауды қажет ететін жағдайлар санын азайтуға көмектесетін қосымша операциясын (битальды және ) енгізу әдісі қандай? Бұл әдіс салыстыру қажеттілігін болдырмайды, сондықтан кодты қосады. ОП проблемасы кем дегенде екіеуі шын екендігін анықтау үшін емес, барлық құрылтай шарттарын бағалау қажеттілігіне негізделген. Сондай-ақ, сіздің мысал тек жұмыс істейді, егер бұл белгілі бір бит есепке алынады; айталық, бес шарт бар ма? 5 (база 10) = 101 (2-база); 101 (2-база) және 2 (16-база) == 0. Қате.
қосылды автор Michael Kjörling, көзі