Függvény és Változó nevek

Ebben a témában: Alapok, C Programozas, Java Programozas

Sokan lényegtelennek tartják az egyes függvények vagy változók precíz elnevezését a mindennapi munka során, azonban szerintem ez egy nagyon fontos pont. Funkcionalitás tekintetében lehet, hogy nem tűnik olyan lényegesnek mindez, azonban a kód karbantarthatóságát tekintve ez az egyik legfontosabb szempont.

 

 

Azért egy nehéz kérdés ez, mert a fejlesztőnek, aki épp implementálja az adott függvényt, annak triviális, hogy egy változó épp mikor mit jelent. Ezért szinte fel sem tűnik neki, hogy 2 hét vagy 2 év múlva mennyire értelmezhetetlen is lesz majd a kód. Sajnos sokszor láttam már ilyet illetve nekem is kellett már ilyen minőségű kódot megértenem. Nem egy nagy öröm ez, remélem nektek nem kell ezt átélni, azonban sajnos az eddigi tapasztalatom nem ezt mutatja. Nézzük meg az elméletet, hogy mikor ideális szerintem egy függvény vagy egy publikus, globális változó elnevezése:

  1. A programozás nyelve az angol. Angol a függvénynév, a változó, a komment, minden.
  2. A név hierarchia szerint épül fel (azért ezt nem érdemes túlzásban vinni, 1-2, nagyon maximum 3 szint bőven elegendő)
  3. A hierarchiai szintek általában rövidítve szerepelnek
  4. Az utolsó rész legyen a függvény vagy változó célja. Ez általában egy szabadabb rész, tetszőleges, rövid! tartalommal
  5. A függvény vagy változó végén postfix-ként szerepel a típus megnevezés
  6. Egybeírás esetén minden új szó nagybetűvel kezdődik
  7. Elválasztás esetén az elválasztó karakter az alul vonás „_”

 

A fenti szabályrendszert én mindig függvényekre és publikus, globális változókra alkalmazom. A függvény lokális változóknak és a függvény paramétereknek az elnevezésében általában nem használok hierarchia szinteket, ennyiben egyszerűsödik a dolog.

Nézzünk egy jó példát egy C függvényre, ami 3 számot tud összeadni:

int Pti_SumOfThreeNumbers_s16(int NumberOne_s16, int NumberTwo_s16, int NumberThree_s16);

 

Egy függvény ami megjeleníti az eredményt:

void Pti_PrintResult(int Result_s16)

 

Érdemes nagyon odafigyelni az elnevezésekre, mert ha valaki belenéz az implementációnkba, akkor ez az első dolog amit meglát. Fontos, hogy könnyen és gyorsan meg lehessen érteni a forráskódunkat, ellenkező esetben mindenkitől sokkal több időt rabol el ez a feladat mint amennyit feltétlenül szükséges lenne és akaratlanul is ellenszenvet válthatunk ki másokban. A mai komplexitású SW-ekben pedig a mindennapi munka része, hogy a kollégáink által írt kódot kell tudnunk megérteni. A problémákat, összetűzéseket azonban egy kicsi odafigyeléssel el lehet kerülni.

(more…)

Bináris Keresés

Ebben a témában: C Programozas

Sok fajta keresési algoritmus létezik. Ma megnézzük az egyik leggyorsabbat, a bináris keresést és az ahhoz tartozó C nyelvű implementációt.


Mi az a bináris keresés?

A bináris keresés egy rendezett listán belül képes keresni. Az elméleti koncepciója az, hogy ha létezik a rendezett lista, akkor a keresett számról egyértelműen el tudom dönteni, hogy az aktuális számtól kisebb-e vagy nagyobb és ez alapján egyértelműen tudom, hogy a lista melyik maradék részében kell tovább keresnem. Az algoritmus a keresési listát mindig megfelezi, attól függően, hogy a keresett szám kisebb-e vagy nagyobb az aktuális lista elemnél, neve az algoritmus működési elvére utal. A bináris keresés rendkívül optimális, a futási komplexitása O(log N), tehát logaritmikus, ami azt jelenti, hogy nagyon lassan nő csak a futási ideje, vagyis milliós nagyságrendű adatoknál is csak pár lépésre van szüksége általában. Nézzünk egy példát:

  • A lista: [1,2,3,4,5]
  • Keresett szám: {4}


Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
  2. A lista középső eleme: [3]
  3. Aktuális szám: [3] < {4} -> Jobbra kell keresnem a maradék listában
  4. Felezés! Új keresési lista: [4,5]
  5. Aktuális szám: [4] = {4} -> Keresett szám megtalálva, a keresésnek vége


A bináris keresés kihasználja a lista rendezett tulajdonságát, rendezetlen listán nem is használható. Az algoritmus bemenete a lista első és utolsó elemének az indexe, illetve a keresett érték. A trükk az, hogy a bináris keresés mindig a keresési listát felezi, azáltal, hogy az első és utolsó elemének az indexét folyamatosan frissíti. Majd a frissített indexeknek veszi a közepét és azt az elemet hasonlítja össze a keresettel majd ismétli a folyamatot.
Nézzük meg a fenti példát még egyszer, most már feltüntetve az indexeket is (a tömbök indexe mindig 0-ról indul!):

  • A lista: [1,2,3,4,5]
  • Keresett szám: {4}
  • Első elem indexe (EI)
  • Utolsó elem indexe (UI)
  • Aktuális index (AI)


Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
    1. EI = 0
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 0 + ((4-0)/2) = 2
  2. Aktuális szám: [3] < {4} -> Jobbra kell keresnem a maradék listában
  3. Felezés! Új keresési lista: [4,5]
    1. EI = AI+1 = 3
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 3 + ((4-3)/2) = 3
  4. Aktuális szám: [4] = {4} -> Keresett szám megtalálva, a keresésnek vége


Hogyan frissítődnek az indexek?

Az első körben az első elem indexe és az utolsó elem indexe statikus értékeket kapnak. A középső elem indexe mindig az alábbi képlet alapján számolódik: Első elem indexe + ((Utolsó elem indexe – Első elem indexe)/2)
Aztán a további körökben a talált értéktől függően vagy az első elem vagy az utolsó elem indexét frissítjük, a középső elem indexe mellett:

  • Első elem indexe = Középső elem indexe + 1;
  • Utolsó elem index = Középső elem indexe – 1;
  • Középső elem indexe = Első elem indexe + ((Utolsó elem indexe – Első elem indexe)/2)


Meddig fut az algoritmus?

Két opció létezik, vagy megtalálja az algoritmus a keresett számot és akkor leáll vagy nem találja meg a keresett számot. Persze ekkor is leáll, de ilyenkor az lesz a kilépési feltétel, hogy az első elem indexe nagyobb mint az utolsó elem indexe, azaz nincs több ellenőrizendő elem a listában. Nézzük meg, hogy mi történik ha a 6-os a keresett szám a fenti listában:

  • A lista: [1,2,3,4,5]
  • Keresett szám: {6}
  • Első elem indexe (EI)
  • Utolsó elem indexe (UI)
  • Aktuális index (AI)


Az algoritmus futásának lépései:

  1. Keresési lista: [1,2,3,4,5]
    1. EI = 0
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 0 + ((4-0)/2) = 2
  2. Aktuális szám: [3] < {6} -> Jobbra kell keresnem a maradék listában
  3. Felezés! Új keresési lista: [4,5]
    1. EI = AI+1 = 3
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 3 + ((4-3)/2) = 3
  4. Aktuális szám: [4] < {6} -> Jobbra kell keresnem a maradék listában
  5. Felezés! Új keresési lista: [5]
    1. EI = AI+1 = 4
    2. UI = 4
    3. AI = EI + ((UI-EI)/2) = 4 + ((4-4)/2) = 4
  6. Aktuális szám: [5] < {6} -> Jobbra kell keresnem a maradék listában
  7. Felezés!
    1. EI = AI+1 = 5
    2. UI = 4
  8. EI > UI -> Kilépés


Nézzük meg az algoritmushoz tartozó C nyelvű implementációt, amit innen a blogról is le tudtok tölteni. Maga az algoritmus a következő:

uint8_t lowIndex_u8 = 0;
uint8_t highIndex_u8 = (numberOfElements_u8-1);
bool targetFound_b = false;

/**
* Until the target number is not found
* OR
* Out of unchecked elements
*/
while ((targetFound_b == false) && (lowIndex_u8 <= highIndex_u8))
{

(*searchedIndex_pu8) = lowIndex_u8 + ((highIndex_u8-lowIndex_u8)/2);

if (orderedList_pu8[(*searchedIndex_pu8)] == targetNumber_u8)
{

/** Current number is equal to the searched one */
targetFound_b = true;

}
else if (orderedList_pu8[(*searchedIndex_pu8)] < targetNumber_u8)
{

/** Current number is lower than the searched one */
lowIndex_u8 = ((*searchedIndex_pu8)+1);

}
else
{

/** Current number is higher than the searched one */
highIndex_u8 = ((*searchedIndex_pu8)-1);

}

}

return targetFound_b;


Nézzük meg sorról sorra, hogy mi is történik pontosan:

(more…)