Здравейте,
поствам решенията си на домашното от днес за "Управление на изпълнението". Има една "задача-проект", която ми беше изключително интересна, става въпрос за 7-ма разбира се :)
1. Sum Of Squares - Play at PHP Fiddle
Здравейте, колеги,
Ето ги и моите решения на задачите. Както винаги, ще се радвам на коментари и критика 
1. Square Root Sum - задачата е ясна
2. Rich People's Problems - тук има две интересни неща. Първо, array_rand() връща ключ, а не стойност от масива и синтаксисът става малко грозен (ако не обичате да декларирате много локални променливи 
) - $arr[array_rand($arr)];. Второ, preg_match() има опция PREG_SPLIT_NO_EMPTY, която работи като StringSplitOptions.RemoveEmptyEntries в C#.
И още нещо, което ме разочарова - в PHP няма named parameters. Така ако искам да подам на функцията preg_match($pattern, $string, $flags = PREG_SPLIT_NO_EMPTY), т. е. ако пропусна третия параметър и подам четвъртия по име, това не работи 
. Тези named parameters май само в PHP още ги няма...
3. Show Annual Expenses - задачата е сравнително лесна, решава се с два вложени цикъла (за годините и месеците). По-интересната част е да се вземат имената на месеците наготово, а не като hardcode-нат масив
4. Find Primes in Range - в тази задача е интересен алгоритъмът за намиране на просто число. Той може да се напише по много начини, но хубавото е, че позволява да бъде страшно оптимизиран. Не се проверяват числа, по-малки от две, всички четни се изключват, проверява се за делимост само на нечетни числа (във for-цикъла) и последно - цикълът върви не до самото число, което проверяваме, а до квадратния му корен (което може да се докаже - оставям това на по-добри математици от мен 
). Коментарите във функцията обясняват за какво става въпрос, но аз ще илюстрирам с пример - ако проверяваме дали числото 100 се дели на всяко число от 2 до 100 (което е най-наивният и най-бавният вариант), правим около 100 проверки, а с тази функция правим само една - виждаме, че числото е четно и изобщо не се занимаваме с него.
5. Sum of Digits - интересното тук, е че може да използваме директно array_sum() върху split-натия string и да си спестим писането на един for-цикъл
6. Modify String - един много ценен урок, който може да се научи от тази задача е, че входните данни от външния сват винаги трябва да се проверяват много стриктно, особено пък ако един прост string е име на функция, която ще се изпълни. POST заявка може да се направи не само от браузър и е много лесно един хакер да подаде dangerousFunction като string и тя да се изпълни (бих могъл да направя за демонстрация видео или нещо като tutorial). Още по-лесно е, ако функцията не приема параметри (така ще игнорира подадения ѝ string и може да направи още по-големи поразии ).
7. Student Sorting - тук също проверявам дали полето и редът за сортиране са сред разрешените, защото в противен случай сортирането ще гръмне. В StackOverflow има много интересна функция, която може да сортира масив от масиви (jagged array) в зависимост от даден ключ и дадена последователност на сортиране. Още по-интересното на функцията е, че ако ѝ се подадат повече параметри, тя сортира масива последователно по всички (действа както .OrderBy().ThenBy().ThenBy()... в LINQ). С помощта на тази функция задачата става доста по-лесна
Амиии не е лош алгоритъма за prime, но "моя е по-добър" : )) Много си го харесвам и мисля че е доста по-бърз защото проверява и кратни на 3 и минава през 6 елемента на врътка на цикъла.
Със сигурност - но така можем да направим едни if-ове (не може да стане със switch, защото проверяваме изрази), дето проверяват с числата до 100 (до 97 по-точно). Въпросът е, че всяко следващо число "отмахва" все по-малко възможности (а if-овете не са много бързи като цяло, особено голяма серия if /elseif...). Това също не е много оптимизирано за performance - if($num % 2 == 0) return ($num == 2); - трите if-a може да са if / elseif / elseif. Но да не издребняваме - двата if-a във for-цикъла например правят кода по-труден за четене, освен това има т. нар. класове сложност на алгоритмите - броят операции в двата алгоритъма се различават с константа, освен това константата е много малка.
Всъщност, истинската оптимизация в алгоритъма е да не проверяваш всички числа до числото, а до корен квадратен от него - това прави сложността на алгоритъма от линейна (по подаденото число) до sub-linear (не знам как се превежда на български).
Така де, харесвам алгоритъма ти, но е малко overkill
. Има две основни правила при оптимизацията на код за бързодействие: 1) оптимизирай само когато се налага (защото това обикновено води до гаден код), 2) оптимизирай само ако резултатът е по-добър в пъти (примерно кодът върви 5 пъти по-бързо), а не в проценти (особено добре е да смениш алгоритъма, ако минеш в "по-бърз" клас сложност).
Първо, този алгоритъм, който си ползвал е на-стандартния, тоест, ако отвориш един туториал, първо него намираш и не е никак оптимизиран, дори и моя не е - ако ги пуснеш в SPOJ - задачата с прости числа, ще увиснат яко.
Този се води от най-бързите и със сигурност ми е трудно четим на пръв поглед Sieve of Atkins
Не виждам нищо 'бавно' в if защото е една проста математическа операция. докато вляза в цикъла да търся номера вече съм намерил решение за много голям брой случай.
Второ, и в моето решение стигам до корен на числото, не до самото число.
За четимостта е малко субективно, аз не виждам нищо нечетимо в моя код, но виждам ползите - проверката за остатък от делене на 3, което ни улеснява като след това можем да минаваме през 6 числа в цикъла. Не ми се правят тестове сега, но основната ми идея е - if - бързо, loop - бавно.
Sieve of Atkins наистина е съвсем друг тип алгоритъм, използва много неща от теория на числата (и не само) и се справя blazingly fast със задачата :). Колкото до корена от числото, да, вижда се - просто исках да отбележа, че това е най-сериозната оптимизация за нашия алгоритъм. А за четимостта - обичам да се придържам към KISS принципа
.
Сега, не ме разбирай грешно, не искам да се заяждам или нещо такова - просто исках да отбележа някои неща . Да, твоята версия прави по-малко стъпки, но не мисля, че е необходимо да я използвам
.
P. S.: Ама колко изписахме за два-три реда код
В 5 задача е казано, ако числото не е цяло да отпечата "I cannot sum that". Гледам, че и други колеги не са догледали тази малка подробност, която на мен лично много ми усложни работата.
@ZvetanIG, много ти благодаря за препоръката. Оправих го - смених is_numeric на проверка с filter_var и сега работи само за цели числа :)
Чудесно, но аз бих ти препоръчал ctype_digit($number) вместо filter_var, защото тя не хваща варианти като 0005 или 0000 и сега при подобен вход ще получиш "I cannot sum that".
Ех, тая проверкаааа
. Мерси, оправих го отново.
Ето един доста добар алгоритъм за намиране на prime в дадени граници.
$isPrime=true;
for ($i=$startNumber ;$i<=$endNumber; $i++) {
for ($y=2 ;$y<=floor(sqrt($i)); $y++) {
if($i%$y==0){
$isPrime=false;
}
}
if($isPrime){
echo "<b>$i</b>, ";
}
else{
echo "$i, ";
}
$isPrime=true;
}
не мога да разбера защо на 6.а задача тука
function splitString($string)
{
// Works for English and Bulgarian characters only
$result = array();
preg_match_all('/[A-Za-zА-Яа-я]/', $string, $result);
return implode(" ", $result[0]);
}
в implode-то е $result[0], а не $result. Нали уж вкарваме match-овете в масива, т.е. всяка буква A-Za-zА-Яа-я отива в масива поотделно и се получава масив от букви. Така $result[0] ми изглежда, че ще печата само първата буква, а не всички...А защо печата всички?
preg_match_all('/[A-Za-zА-Яа-я]/', $string, $result) връща на мястото на $result масив с два елемента. Първият елемент е масив със съвпаденията, а вторият елемент е са групите. Дебъгни и ще видиш структурта на $result.