Ծրագրերի սկզբնային տեքստերի գեղեցկության մասին

Կարելի՞ է արդյոք կոմպյուտերային ծրագրի կոդի մասին խոսելիս ասել, որ այն գեղեցիկ է։ Արդյո՞ք ծրագրի տեքստը կարելի է բնութագրել գեղագիտական հատկանիշներով։ Այս հարցին ես առաջին անգամ առնչվեցի, որբ բակալավրիատում սովորելու առաջին կուրսում, ծրագրավորման գործնական պարապմունքի ժամին դասախոսը՝ Արմեն Անդրեասյանը, ցույց տվեց գրատախտակին գրված ծրագիրը ու ասաց. «Գեղեցիկ է, չէ՞»։ Ինչքան հիշում եմ, թեև հնարավոր է, որ սխալվեմ, այդ ծրագիրը Էվկլիդեսի ալգորիթմն էր՝ գրված C++ լեզվով.

int gcd( int a, int b )
{
  while( a != b )
    if( a > b )
      a -= b;
    else
      b -= a;
  return a;
}

Այն ժամանակ մենք նույնիսկ քմծիծաղեցինք, թե ծրագրի գեղեցիկը ո՞րն է, սովորական ծրագիր է։ Հետագայում, սովորելու և աշխատելու տարիներին, երբ գրեցի շատ ու շատ ծրագրեր, երբ նաև կարդացի ուրիշների գրած շատ ու շատ ծրագրեր, համարյա միշտ ինքս ինձ հարցնում էի, թե գեղեցի՞կ է արդյոք իմ գրածն ու կարդացածը։

Էվկլիդեսի ալգորիթմին վերադառնալով ուզում եմ ասել, որ այն իսկապես գեղեցիկե։ Առավել գեղեցիկ է նրա ռեկուրսիվ իրականացումը, որ ահա գրել եմ Oberon լեզվով․

PROCEDURE Gcd( u, v : INTEGER ) : INTEGER;
VAR
  re : INTEGER;
BEGIN
  IF v = 0 THEN
    re := u
  ELSE
    re := Gcd(v, u MOD v)
  END;
RETURN re END Gcd;

Չէ, իսկապես գեղեցիկ է։ Այս ալգորիթմի համար նույնիսկ կարևոր չէ, թե այն ինչ լեզվով է գրված։ Նրա հիմքում գեղեցիկ մաթեմատիկական միտքն է, այն գեղեցիկ է ստացվելու, երևի թե ցանկացած ծրագրավորման լեզվով գրելիս։ Ճիշտ ինչպես Շիլլերի տողերը, որ միատեսակ գեղեցիկ են ինձ ծանոթ բոլոր լեզուներով։ Բնագիրը.

    Ihr Matten lebt wohl,
    Ihr sonnigen Weiden!
    Der Senn muss scheiden,
    Der Sommer ist hin.
Wir fahren zu Berg, wir kommen wieder,
Wenn der Kuckuck ruft, wenn erwachen die Lieder,
Wenn mit Blumen die Erde sich kleidet neu,
Wenn die Brünnlein fliessen im lieblichen Mai
    Ihr Matten lebt wohl,
    Ihr sonnigen Weiden!
    Der Senne muss scheiden,
    Der Sommer ist hin.

Հայերեն՝ Հ. Թումանյանի թարգմանությամբ.

Մնաք բարով, դո՛ւք, արոտնե՛ր սիրուն,
Ամառն անց կացավ, հոտն իջնում է տուն։

Մենք ետ կըգանք ձեզ նորեկ գարունքին,
Երբ զարթնեն ուրախ երգերը կըրկին,
Երբ որ սարերը զուգվեն կանաչով,
Երբ որ ջըրերը վազեն կարկաչով։

Մնաք բարով, դո՛ւք, արոտնե՛ր սիրուն,
Ամառն անց կացավ, հոտն իջնում է տուն։ 

Ռուսերեն՝ Ն. Սլավյատինսկու թարգմանությամբ.

    Прощайте, луга,
    Багряные зори!
    Разлука нам — горе.
    Ах, лето прошло!
Пора нам в долины... Увидимся снова,
Когда все очнется от сна ледяного
И голос кукушки в лесу зазвучит,
Цветы запестреют, родник зажурчит.
    Прощайте, луга,
    Багряные зори!
    Разлука нам — горе.
    Ах, лето прошло!

Անգլերեն՝ Թ. Մարտինի թարգմանությամբ.

    Farewell, ye green meadows,
    Farewell, sunny shore,
    The herdsman must leave you,
    The summer is o'er.
We go to the hills, but you'll see us again,
When the cuckoo is calling, and wood-notes are gay,
When flowerets are blooming in dingle and plain,
And the brooks sparkle up in the sunshine of May.
    Farewell, ye green meadows,
    Farewell, sunny shore,
    The herdsman must leave you,
    The summer is o'er.

Հիմա արդեն, ծրագրային կոդերի հետ աշխատանքի ավելի քան տաս տարիների փորձն ամփոփելով, կարող եմ ինքս ինձ համար պնդել, որ այո՛, կոմպյուտերային ծրագրի տեքստը (սկզբնային տեքստ, source code) նույնպես կարող է գեղեցիկ լինել։ Ավելին, հուսալի ու արդյունավետ կարող են աշխատել միայն այնպիսի ծրագրերը, որոնք գեղեցիկ տեքստ ունեն։ Համարյա ինչպես ավիացիայում. ասում են, որ լավ է թռչում միայն գեղեցիկ ինքնաթիռը։ Օրինակ, МиГ-29 կործանիչը։ Ես կարող եմ ժամերով նայել այս ինքնաթիռի թռիչքին։ Այն թռչում է ինչպես բալետի պարուհին է պարում բեմի վրա, ինչպես գեղասահորդը սահում է սառույցին։ Եվ երբ նայում եմ այդ ինքնաթիռի գծապատկերին, տեսնում եմ նույն պարուհուն կամ գեղասահորդին:

Նույնպիսի համեմատություն կարող եմ անել Դ. Կնուտի (D. Knuth) TeX և METAFONT ծրագրերի համար։ Այդ երկու ծրագրերն էլ գրված են Literate Programming մեթոդով. կարծես գեղարվեստական ստեղծագործություն լինեն։ Դե, իսկ ո՞ւմ չէ հայտնի TeX-ով պատրաստված տեքստերի և METAFONT-ով պատրաստված տպատառերի գեղեցկությունը։

Կան նաև տգեղ ծրագրեր։ Բառացիորեն վերջերս իմ աշխատանքում պետք եղավ C++ լեզվով գրել ծրագրի մի հատված, որտեղ օբյեկտները բնութագրող տողերի զույգերից պետք էր կառուցել օբյեկտների բառարան (map): Տողերի զույգի առաջին տարրը բառարանի բանալին է, իսկ երկրորդ տարրից պետք է կառուցել բանալուն համապատասխանեցված արժեքը։ Ծրագրի բնույթն այնպիսին է, որ տողերի զույգերը ժամանակի ընթացքում ավելանալու են։ Սկզբում, երբ զույգերը դեռ քիչ էին, գրել էի մի այսպիսի տեքստ (պարզեցված տարբերակով, իհարկե).

std::vector keys;
std::map dict;
keys.push_back("k0");
dict["k0"] = new Descriptor("v0");
keys.push_back("k1");
dict["k1"] = new Descriptor("v1");
keys.push_back("k2");
dict["k2"] = new Descriptor("v2");

Չնայած, որ բնութագրող տողերի փոքր քանակի համար սա ընդունելի է, այնուամենայնիվ, ես համարում եմ, որ այս կոդը տգեղ է։ Հենց թեկուզ այն պատճառով, որ տվյալները «կորել» են լեզվի արտահայտությունների մեջ։

Հետո, երբ բնութագրիչների քանակներն ավելանան, ես keys և dict կոնտեյներները լրացնելու համար կոդը ձևափոխեցի հետևյալ տեսքին.

using pair_t = std::pair;
std::list cpairs = {
    { "k0", "v0" },
    { "k1", "v1" },
    { "k2", "v2" },
    // ....
    { "k12", "v12" }
};
auto maker_f = [&]( pair_t e ) { 
                   keys.push_back(e.first);
                   dict[e.first] = new descriptor(e.second);
               };
std::vector keys;
std::map dict;
std::for_each( cpairs.begin(), cpairs.end(), maker_f );

Մի քիչ երկար է, բայց այս դեպքում, եթե նոր տվյալներ ավելացնեմ, ապա դրանք ավելացնելու եմ միայն cpairs ցուցակում, իսկ տվյալների մշակման մասն արդեն անփոփոխ է մնալու։ Պետք է նշել, որ այս գեղեցիկ տեքստը ես ստացել եմ C++11 ստանդարտում ավելացված հնարավորությունների շնորհիվ։ Եթե ես այս կոդը գրեի, C++98 ստանդարտի հնարավորություններով, ապա ստանալու էի մի կոդ, որին ես գեղեցիկ ասել չեմ կարող.

typedef std::pair pair_t;
std::list cpairs;
cpairs.push_back( std::make_pair( "k0", "v0" ) );
cpairs.push_back( std::make_pair( "k1", "v1" ) );
cpairs.push_back( std::make_pair( "k2", "v2" ) );
// ....
cpairs.push_back( std::make_pair( "k12", "v12" ) );

std::vector names;
std::map dict;
for( std::list::iterator it = cpairs.begin(); it != cpairs.end(); ++it ) {
    names.push_back( it->first );
    dict[it->first] = new Descriptor(it->second);
}

Ցանկացած ծրագրում կարելի է գտնել այսպիսի օրինակներ։ Ցանկացած այսպիսի օրինակի գեղեցկության կամ տգեղության մասին կարելի է վիճել։ Բայց ինձ համար մի բան հաստատ է. ծրագրավորումը կարելի է համարել կիրառական արվեստի մի ճյուղ։ Եվ տեղին է այդ արվեստի նմուշների համար օգտագործել գեղեցիկ և տգեղ բնութագրումները։ Իսկ ծրագրավորողներին ու թեսթավորողներին, այն մարդկանց, ովքեր իրենք առօրյա աշխատանքում գրում ու կարդում են հարյուրավոր ու հազարավոր տողերով ծրագրային տեքստ, մնում է այդ գործում գտնել ու գնահատել գեղեցիկը։

Տեքստի հավասարեցում ըստ էջի լայնության

«Этюды для программистов» (Чарльз Уэзерелл, ― «Etudes for Programmers», Charles Wetherell) գրքի չորրորդ էտյուդն առաջարկում է գրել տեքստի ֆորմատավորման ծրագիր, որի պահանջներից մեկը տողի բառերի արանքներում բացատներ ավելացնելով տեքստը ըստ էջի լայնության հավասարացնելն է։ Տեքստի ֆորմատավորման այս մասնակի խնդիրն է նկարագրված նաև, օրինակ, «100 задач по программированию» գրքի (հեղինակներ՝ Дагене В. А., Григас Г. К., Аугутис К. Ф.) 78-րդ առաջադրանքում, որ կոչվում է «Տեքստի տեխնիկական խմբագրում»։

Մի կողմից կարող է այս խնդիրը, գործնական տեսակետից, հնացած թվալ, մյուս կողմից էլ, սակայն, ժամանակակից տեքստային խմբագրիչներում և տեքստային պրոցեսորներում նույնպես կիրառվում են տեքստի հավասարեցման գործողություններ։ Օրինակ, LibreOffice Writer ծրագիրը հավասարեցումը կատարում է ոչ թե բացատների քանակն ավելացնելով, այլ դրանց չափերն ավելացնելով։ Կամ, TeX տեքստային պրոցեսորում ընդհանրապես բացակայում է բացատ նիշը, իսկ հավասարեցման համար բառերի արանքները լցվում են «սոսինձ» կոչվող ազատ տարածությամբ։

Խնդրի լուծման ընթացքը կարող է լինել այսպիսին (որ նույնպես կարդացել եմ ինչ-որ գրքում, արդեն չեմ հիշում, թե՝ որ). ա) տրված տեքստը տրոհել առավելագույնը n երկարությամբ տողերի՝ չթույլատրելով բառի տրոհում, բ) եթե արդյունքում տողի երկարությունն ավելի կարճ է ստացվում, քան n թիվը, ապա պատահական բառերի արանքներում ավելացնել այնքան բացատներ, որ տողի երկարությունը դառնա n-ի հավասար։ Հավասարեցման գործողությունը պետք չէ կիրառել վերջին տողի նկատմամբ։

Այս գրառման մեջ ես պատմում եմ, թե ինչպես եմ C լեզվով ծրագրավորել տեքստն ըստ լայնության հավասարեցման գործողությունը։ Ստորև բերված ծրագրում ես դիտարկում եմ տեքստի հետ կապված մի քանի հասկացություններ. բառ, տող և պարագրաֆ։ Տվյալների կառուցվածքների տեսակետից տեքստը պարագրաֆների հաջորդականություն է։ Պարագրաֆը տողերի կապակցված ցուցակ է։ Տողը բառերի կապակցված ցուցակ է։

#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>

Տեքստի մեկ բառը ներկայացնելու համար նախատեսել եմ word ստրուկտուրան։ Սրա w դաշտը բառի տեքստն է, l դաշտը բառի երկարությունն է, s դաշտը բառին հաջորդող բացատների քանակն է, իսկ n դաշտը հաջորդ բառի ցուցիչն է։

/* տեքստի բառի ներկայացումը */
struct word {
  char* w;        /* պարունակությունը */
  size_t l; /* երկարությունը */
  size_t s; /* հաջորդող բացատների քանակը */
  struct word* n; /* հաջորդ բառի ցուցիչը */
};

Իմ առաջին խնդիրն է const char* text ցուցիչով տրված տողի սկզբից առանձնացնել len երկարությամբ հատված, և կազմել այդ հատվածի բառերի կապակցված ցուցակը։ split_to_words ֆունկցիան ստանում է տողի ցուցիչը, դիտարկվող հատվածի երկարությունը և վերադարձնում է կառուցված ցուցակի առաջին տարրի ցուցիչը։ (Բայց քանի որ տողը բառերի տրոհելու ընթացքում բառերի ցուցակը կառուցվում է գլխիվայր, առաջին բառի ցուցիչը վերադարձնելուց առաջ նախ պետք է շրջել կառուցված ցուցակը։) Բոլոր լրացուցիչ բացատրությունները գրված են ֆունկցիայի մարմնում՝ C լեզվի մեկնաբանությունների տեսքով։

/* Տրոհել տեքստը և կառուցել բառերի կապակցված ցուցակ։ 
   Վերադարձնում է առաջին բառի ցուցիչը։ */
struct word* split_to_words( const char* text, size_t len )
{
  /* բառերի ցուցակը */
  struct word* res = NULL;

  /* տրոհել տողը */
  const char* end = text + len; /* դիտարկվող հատվածի վերջը */
  /* քանի դեռ text ցուցիչը չի հասել հատվածի վերջին */
  while( text != end ) {
    /* անցնել բացատների վրայով */
    while( isspace(*text) ) ++text;
    /* text-ը ցույց է տալիս բառի սկիզբը, 
       p ցուցիչը որոնում է բառի վերջը */
    const char* p = text;
    /* քանի դեռ բացատ չէ և տողն ավարտող 0 նիշը չէ,
       առաջ տանել p-ն */
    while( !isspace(*p) && *p != '\0' ) ++p;
    /* բառի ստրուկտուրայի նմուշի համար վերցնել հիշողություն */
    struct word* wo = malloc(sizeof(struct word));
    /* բառի չափը նրա վերջն ու սկիզբը ցույց տվող ցուցիչների 
       դիրքերի տարբերությունն է */
    wo->l = p - text;
    /* հիշղություն վերցնել բառի պարունակության համար */
    wo->w = malloc(1 + wo->l);
    /* պատճենել գտված բառը ստրուկտուրայի մեջ */
    strncpy(wo->w, text, wo->l);
    /* բառի վերջում ավելացնել 0 նիշը */
    wo->w[wo->l] = '\0';
    /* բառին հաջորդում է 1 բացատ */
    wo->s = 1;
    /* նոր ստեղծվող բառը կցել ցուցակի սկզբից */
    wo->n = res;
    /* ցուցակի սկիզբ համարել նոր ավելացրած բառը */
    res = wo;
    /* անցնել հաջորդ բառի որոնմանը */
    text = p;
  }
  /* վերջին բառին հաջորդող բացատների քանակը նշել զրո */
  res->s = 0;

  /* շրջել բառերի միակապ ցուցակը */
  struct word* pp = NULL;
  struct word* nn = res->n;
  while( nn != NULL ) {
    res->n = pp;
    pp = res;
    res = nn;
    nn = nn->n;
  }
  res->n = pp;

  /* վերադարձնել կառուցված ցուցակը */
  return res;
}

Տեքստի մեկ տողը ներկայացնելու համար սահմանել եմ line ստրուկտուրան։ Սրա w դաշտը կապված է տվյալ տողի բառերի ցուցակի առաջին տարրին, c դաշտում պահվում է տողի բառերի քանակը, l դաշտը ցույց է տալիս տողի երկարությունը, իսկ n դաշտը հաջորդ տողի ցուցիչն է։

/* տեքստի տողի ներկայացումը */
struct line {
  struct word* w; /* բառերի ցուցակ */
  size_t c; /* բառերի քանակ */
  size_t l; /* տողի երկարություն */
  struct line* n; /* հաջորդ տողի ցուցիչ */
};

Տեքստի տողը, ինչպես վերն ասացի՝ բառերի կապակցված ցուցակ է, կառուցվում է create_line ֆունկցիայով։ Սա ստանում է տեքստի ցուցիչը և մեկ տողի առավելագույն երկարությունը։

/* Կառուցել տրված երկորությամբ տող */
struct line* create_line( const char* str, size_t len )
{
  /* կառուցել բառերի ցուցակը */
  struct line* res = malloc(sizeof(struct line));
  res->w = split_to_words( str, len );
  /* բառերի քանակն ու տողի երկարությունը դեռ զրո են */
  res->c = 0; res->l = 0;
  /* սկսել առաջին բառից */
  struct word* i = res->w;
  /* քանի դեռ բառերը չեն վերջացել */
  while( i != NULL ) {
    /* ավելացնել բառերի հաշվիչը */
    ++res->c;
    /* հաշվել տողի ընթացիկ երկարությունը */
    res->l += i->l + i->s;
    /* անցնել հաջորդ բառին */
    i = i->n;
  }
  /* հաջորդ տողի ցուցիչը դեռ դատարկ է */
  res->n = NULL;
  /* վերադարձնել կառուցված օբյեկտը */
  return res;
}

Քանի որ տողերի ցուցակի կառուցման համար էլ է օգտագործվում դինամիկ առանձնացված հիշողություն, պետք է նախատեսել նաև այդ հիշողությունը խնամքով ազատելու և համակարգին վերադարձնելու միջոցը։ Դա արվել է destroy_words ֆունկցիայով։

/* քանդել տողերի ցուցակը */
void destroy_words( struct word* l )
{
  /* եթե ցուցակը դատարկ չէ */
  if( l != NULL ) {
    /* ռեկուրսիվ կանչ ցուցակի պոչի համար */
    destroy_words( l->n );
    /* ազատել բառի տեեքստի տեղը */
    free(l->w);
    /* ազատել բառի ստրուկտուրայի տեղը */
    free(l);
  }
}

Տողերի ցուցակ կազմելու համար պետք է append_line ֆունկցիայով տրված տողի n ցուցիչին կապել ևս մի տող։ Սա մի հասարակ ռեկուրսիվ ֆունկցիա է։

/* տողերի ցուցակի պոչից կցել ևս մի տող */
void append_line( struct line** dest, struct line* src )
{
  if( *dest == NULL )
    *dest = src;
  else
    append_line( &((*dest)->n), src );
}

Պարագրաֆը տողերի ցուցակ է (տողն էլ իր հերթին՝ բառերի ցուցակ է)։ create_paragraph ֆունկցիան ստանում է նախնական տողի ցուցիչը և ֆորմատավորվող տեքստի նպատակային լայնությունը։ Ինչպես վերևում՝ լրացուցիչ բացատրությունները ծրագրի տեքստում են։

/* տրված տեքստից կառուցել տրված երկարությունը չգերազանցող տողերի ցուցակ */
struct line* create_paragraph( const char* text, size_t width )
{
  /* արդյունքի ցուցիչը */
  struct line* res = NULL;
  /* դիտարկվողղ տողի սկիզբն ու վերջը ցույց տվող ինդեքսներ */
  size_t begin = 0, end = strlen(text);
  /* քանի դեռ տեքստի վերջը չէ */
  while( begin < end ) {
    /* հաշվել հերթական հատվածի վերջը */
    size_t pos = begin + width;
    /* ճշտվում է վերջին հատվածի եզրը */
    if( pos > end ) pos = end;
    /* հատվածի աջ եզրից հետ գալ՝ կիսատ բառը չվերցնելու համար */
    while( !isspace(text[pos]) && text[pos] != '\0' ) --pos;
    /* կառուցել նոր տող և կցել տողերի ցուցակի պոչից */
    append_line( &res, create_line( text + begin, pos - begin ) );
    /* անցնել տեքստի հաջորդ հատվածին */
    begin = pos;
  }
  /* վերադարձնել պարագրաֆների ցուցակը */
  return res;
}

Պարագրաֆի համար առանձնացված հիշողության դինամիկ տիրույթը համակարգին է վերադարձվում destroy_lines ֆունկցիայի օգնությամբ։

/* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
void destroy_lines( struct line* p )
{
  /* եթե տողերի ցուցակը դատարկ չէ */
  if( p != NULL ) {
    /* ռեկուրսիվ կանչ պոչի համար */
    destroy_lines(p->n);
    /* քանդել բառերի ցուցակը */
    destroy_words(p->w);
    /* ազատել տողի ստրուկտուրայի տեղը */
    free(p);
  }
}

Պարագրաֆի տողերը արտածման ստանդարտ հոսքին են դուրս բերվում print_lines ֆունկցիայով։ Այն նախ տպում է բառը, իսկ հետո՝ դրան հաջորդող բացատաները՝ հարկավոր քանակով։ Արտածվելիք բացատների քանակը պահվում է word ստրուկտուրայի s դաշտում։ print_lines ֆունկցիայում սահմանված spaces ստատիկ հաստատունը պարունակում է բառից հետո արտածվող բացատների ենթադրվող առավելագույն երկարությամբ տողը, իսկ scount փոփոխականը՝ այդ տողի երկարությունը։ k->w բառն արտածելուց հետո պարզապես պետք է արտածել նաև spaces տողի վերջին k->s հատվածը։

/* արտածել տողերը */
void print_lines( struct line* lines )
{
  /* բացատների տող, և բացատների քանակ */
  static const char* spaces = "                   ";
  static const size_t scount = 20;

  /* քանի դեռ ցուցակի վերջը չէ */
  while( lines != NULL ) {
    /* k-ն ցուցակի աչաջին բառն է */
    struct word* k = lines->w;
    /* քանի դեռ k-ն չի հասել բառերի ցուցակի վերջին */
    while( k != NULL ) {
      /* արտածել բառը դրան հաջորդող բացատները */
      printf( "%s%s", k->w, spaces + scount - k->s );
      /* անցնել հաջորդ բառին */
      k = k->n;
    }
    /* արտածել նոր տողին անցնելու նիշը */
    putchar('\n');
    /* անցնել պարագրաֆի հաջորդ տողին */
    lines = lines->n;
  }
}

Տողի հավասարեցման մարտավարությունը հետևյալն է․ քանի դեռ հացասարեցվող տողի երկարությունը, որը ցույց է տալիս line ստրուկտուրայի l դաշտը, փոքր է պահաջվածից, տողում ընտրել պատահական մի բառ (բացի վերջինից) և դրան հաջորդող բացատների քանակն ավելացնել մեկով։

Տողի n-րդ բառի ցուցիչը վերցնելու համար է նախատեսված nth ֆունկցիան։ Եթե տողում բառերի քանակը ավելի քիչ է, քան տրված n թիվը, ապա, բնականաբար, վերադարձվում է NULL։

/* Վերադարձնում է բառերի ցուցակի n-րդ տարրը։ */
struct word* nth( struct word* list, size_t n )
{
  struct word* res = list;
  while( n-- > 0 ) {
    res = res->n;
    if( res == NULL )
      return NULL;
  }
  return res;
}

Վերջապես ամեն ինչ պատրաստ է՝ պարագրաֆը տրված լայնությամբ հավասարեցնելու համար։ justify_paragraph ֆունկցիան ստանում է տողերի ցուցակն ու տողի հարկավոր width լայնությունը։ Այնուհետև, անցնելով ցուցակի բոլոր տարրերով, բառերի արանքներում բացատներ է ավելացնում այնքան ժամանակ, քանի դեռ տողի երկարությունը չի հասել width թվին։

/* տողերը հավասարեցնել՝ բառերի արանքներում
   ներմուծելով լրացուցիչ բացատներ */
void justify_paragraph( struct line* par, size_t width )
{
  /* քանի դեռ ցուցակի նախավերջին տողը չէ */
  while( par->n != NULL ) {
    /* քանի դեռ տողի երկարությունը փոքր է width-ից */
    while( par->l < width ) {
      /* ընտրել պատահական ինդեքս */
      int po = rand() % (par->c - 1);
      /* վերցնել տողի՝ այդ ինդեքսով բառը */
      struct word* wd = nth( par->w, po );
      /* 1-ով ավելացնել բառի բացատների քանակը */
      ++wd->s;
      /* 1-ով ավելացնել տողի ընդհանուր երկարությունը */
      ++par->l;
    }
    /* անցնել հաջորդ տողին */
    par = par->n;
  }
}

Ահա այսքանը։ Մնում է միայն կազմակերպել ծրագրի մուտքի կետը՝ main ֆունկցիան, որպեսզի հնարավոր լինի ծրագիրն օգտագործել իր նշանակությամբ։ Նախատեսված է, որ ծրագիրը տեքստը կարդում է ներմուծման ստանդարտ հոսքից, իսկ ֆորմատավորված արդյունքը դուրս է բերում արտածման ստանդարտ հոսքին։

int main( int argc, char** argv )
{
  /* ծրագիրը որպես պարամետր սպասում է միայն
     տեքստի լայնությունը */
  if( argc != 1 && argc != 3 )
    return 1;

  /* եթե լայնությունը տրված չէ՝ այն համարել 40 */
  size_t length = 40;
  /* հրամանային տողից կարդալ length-ի նոր արժեքը */
  if( argc == 3 )
    if( argv[1][0] == '-' && argv[1][1] == 'w' )
      sscanf(argv[2], "%d", &length);

  /* արժեքավորել պատահական թվերի գեներատորը */
  srand(time(0));

  /* նախնական տեքստի բուֆերի չափը */
  const size_t bsize = 4096;
  /* դինամիկ բուֆեր՝ տեքստի համար */
  char* text = calloc(bsize, sizeof(char));
  /* քանի դեռ stdin-ի վրա կարդալու բան կա,
     կարդալ այն text բուֆերի մեջ */
  while( fgets(text, bsize, stdin ) != NULL ) {
    /* կարդացած տեքստից կառուցել տողերի ցուցակ */
    struct line* u = create_paragraph( text, length );
    /* հավասարեցնել պարագրաֆը տրված լայնությամբ */
    justify_paragraph( u, length );
    /* արտածել պարագրաֆի տողերը */
    print_lines( u );
    /* ազատել պարագրաֆի զբաղեցրած հիշողությունը */
    destroy_lines( u );
  }
  /* ազատել բուֆերի զբաղեցրած հիշողությունը */
  free(text);

  return 0;
}

Ծրագիրը կոմպիլյացնելու համար կարելի է օտագործել gcc կամ clang կոմպիլյատորները․

$ gcc -std=c11 -o splitext splitext.c

Իսկ test1.txt ֆայլում պարունակվող տեքստը, օրինակ, 30 նիշ լայնությամբ տողերով ֆորմատավորելու համար պետք է գրել։

$ ./splittext -w 30 < text1.txt

Նույն արդյունքը կարելի է ստանալ նաև հետևյալ հրամանով․

$ cat test1.txt | ./splittext -w 30

Հեշավորում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

5 Բանալիների բաշխում (Հեշավորում)

5.1 Ներածություն

Չորրորդ գլխում քննարկվող սկզբունքային հարցը հետևյալն էր․ եթե տրված է բանալիով (key) բնութագրվող տարրերի բազմություն (բանալու վրա սահմանված է նաև կարգի հարաբերություն), ապա ինչպե՞ս կազմակերպել այդ բազմությունը, որպեսզի տրված բանալիով տարրին դիպելու համար պահանջվի նվազագույն ջանք։ Պարզ է, որ կոմպյուտերի հոշողության մեջ գտնվող որևէ տարրին դիմելու համար պետք է ունենալ նրա հասցեն։ Հետևաբար, նշված խնդիրը բերվում է K բանալիները A հասցեներին արտապատկերող H ֆունկցիայի սահմանմանը։

H: K → A

Չորրորդ գլխում այդ արտապատկերումը իրականացվում էր զանազան տվյալների կառուցվածքների վրա հիմնված ցուցակներում և ծառերում որոնման տարբեր ալգորիթմներով։ Այստեղ ներկայացնում ենք ըստ էութան պարզ և շատ դեպքերում արդյունավետ ևս մի եղանակ։ Այնուհետև կքննարկենք նաև այդ եղանակի որոշ թերություններ։

Այս մոտցման մեջ տվյալները կազմակերպվում են զանգվածի տեսքով։ Այս դեպքում H֊ը բանալիները զանգվածի ինդեքսներին բաշխող արտապատկերում է, որտեղից էլ հենց առաջացել է այս մեթոդի համար օգտագործվող բանալիների բաշխում անվանումը։ Պետք է նշել, որ այս դեպքում կարիք չունենք հիշողության դինամիկ առանձնացնող գործողությունների․ զանգվածը մեկն է հիմնարար, ստատիկ կառուցվածքներից։ ?? Բանալիների բաշխման մեթոդը հաճախ օգտագործվում է այն խնդիրներում, որտեղ մոտավորապես նույն հաջողությամբ կարելի է օգտագործել նաև ծառաձև կառուցվածքները։

Բանալիների բաշխման եղանակն օգտագործելիս հիմնական դժվարությունն այն է, որ թույլատրելի բանալիների բազմությունն էապես ավելի մեծ է, քան հիշողության մատչելի հասցեները (զանգվածի ինդեքսները)։ Որպես բանալի վերցնենք, օրինակ, մինչև 16 նիշ պարունակող անունները, որոնք հազարավոր մարդկանց մեջ նույնականացնում են առանձին անհատների։ Այսինքն, գոյություն ունեն 26^16 հնարավոր բանալիներ, որոնք պետք է արտապատկերել 10^3 հնարավոր ինդեքսների։ Ակնհայտ է, որ այս դեպքում H֊ը շատը֊մեկին ֆունկցիա է։ Եթե տրված է k բանալին, ապա որոնման գործողության առաջին քայլը h=H(k) ինդեքսի հաշվարկումն է, իսկ երկրորդ, ակնհայտորեն պարտադիր, քայլը ստուգելն է, թե արդյո՞ք k բանալիով տարրը համապատասխանում է T զանգվածի (աղյուսակի) h ինդեքսով տարրին, այսինքն, ստուգել T[H(k)].key = k հավասարությունը։ Անմիջապես հանդիպում ենք հետևյալ երկու հարցերին․

1. Ինչպիսի՞ն պետք է լինի H ֆունկցիան։
2. Ի՞նչ անել, եթե H ֆունկցիան չի կարողացել հաշվել որոնելի տարրի դիրքը։

Երկրորդ հարցի պատասխանը կայանում է նրանում, որ պետք է ունենալ մի մեթոդ, որը վերադարձնում է այլընտրանաքային դիրք, ասենք h', եթե այդ նոր դիրքն էլ նորից չի պարունակում որոնելի տարրը, ապա վերադարձնում է h'' դիրքը, և այդպես շարունակ։ ?? Եթե հաշվարկված դիրքում գտնվում է որոնելի տարրից տարբերվող մի այլ տարր, ապա այդ իրավիճակը կոչվում է կիլիզիա (collision), իսկ այլընտրանքային դիրքի հաշվարկը՝ կոլիզիայի լուծում։ Ստորև կքննարկենք բանալիների բաշխման ֆունկցիայի ընտրությունը և կոլիզիայի լուծման եղանակները։

5.2 Հեշավորող ֆունկցիայի ընտրությունը

Լավ բաշխման ֆունկցիայի համար կարևոր նախապայմանն է, որ այն կարողանա բանալիների բազմությունը հնարավորինս հավասարաչափ բաշխել ինդեքսների արժեքների ամբողջ միջակայքին։ Այս պայմանից բացի բաշխման համար այլ սահմանափակումներ չկա, սակայն իրականում ցանկալի է, որ այն նման լինի պատահական բաշխման։ Այսպիսի առանձնահատկությունը բանալիների բաշխման մեթոդին տվել է թերևս ոչ֊գիտական մի անվանում՝ հեշավորում (hashing), այսինքն՝ արգումենտի կտրտում, վերածում ինչ֊որ «խյուսի»։ ?? H֊ն էլ կոչվում է հեշավորող ֆունկցիա (հեշ֊ֆունկցիա)։ Պարզ է, որ H֊ը պետք է լինի էֆեկտիվ հաշվարկվող, այսինքն՝ բաղկացած լինի շատ քիչ թվով թվաբանական գործողություններից։

Դիցուք կարող ենք օգտագործել ORD(k) ֆունկցիան, որը վերադարձնում է k բանալու հերթական համարը՝ կարգաթիվը, բոլոր հնարավոր բանալիների բազմության մեջ։ Ենթադրենք նաև, որ զնգվածի i ինդեքսը տարածվում է 0֊ից մինչև N-1, որտեղ N֊ը զանգվածի տարրերի քանակն է։ Այս դեպքում ընտրությունն ակնհայտ է․

H(k) = ORD(k) MOD N

Այս ֆունկցիան ապահովում է բանալիների հավասարաչափ բաշխումն ինդեքսների ամբողջ միջակայքում և հենց դրա համար էլ օգտագործվում է շատ հեշ֊ֆունկցիաներում։ Այն նաև շատ արդյունավետ հաշվարկվում է, եթե N֊ը երկուսի աստիճան է։ Սակայն եթե բանալին տառերի հաջորդականություն է, ապա հենց այսպիսի ֆունկցիայից պետք է խուսափել։ Բանն այն է, որ այս դեպքում բոլոր բանալիների՝ հույն հավանականությամբ հանդիպելու ենթադրությունը սխալ է։ Իրականում բառերը, որոնք տարբերվում են միայն մի քանի տառերով, մեծ հավանականությամբ կարող են արտապատկերվել դույն ինդեքսին, որն էլ կստեղծի խիստ անհավասարաչափ բաշխում։ Այս պատճառով էլ գործնականում խորհուրդ է տրվում N֊ը վերցնել մի որևէ պարզ թիվ [5-2]։ Որպես հետևանք արդեն հարկ է լինում օգտագործել լրիվ բաժանման գործողություն, որը հնարավոր չէ փոխարինել երկուական թվանշանների կրճատումով։ Սակայն ժամանակակից կոմպյուտերներում սա դժվար խնդիր չէ, քանի որ դրանցում առկա է ներդրված բաժանման գործողություն։ ??

Հաճախ օգտագործվում են բանալու որևէ հատվածի երկուական ներկայացման վրա կիրառվող տրամաբանական գործողություններից կառուցված հեշավորող ֆունկցիաներ (այդպիսի գործողություններից է, օրինակ, «բացառող կամ»-ը)։ ?? Որոշ կոմպյուտերների վրա այս գործողությունները կարող են կատարվել ավելի արագ, քան բաժանումը, բայց հաճախ դրանք բերում են ինդեքսերի միջակայքում բանալիների զարմանալի անհավասարաչափ բաշխման։ Այդ պատճառով էլ ձեռնպահ կմնանք այդպիսի մեթոդների հետագա քննարկումից։

5.3 Կոլիզիաների լուծումը

Եթե պարզվում է, որ աղյուսակի՝ տրված բանալուն համապատասխանեցված տարրը որոնելին չէ, ապա տեղի ունի կոլիզիա, այսինքն՝ երկու տարբեր տարրերի բանալիներ արտապատկերվում են նույն ինդեքսին։ Այս դեպքում անհրաժեշտ է երկրորդ փորձը՝ տրված բանալուց խիստ որոշակի եղանակով ստացվող ինդեքսի օգտագործմամբ։ ?? Գոյություն ունեն երկրորդային ինդեքսների հաշվարկման մի քանի մեթոդներ։ Ակնհայտ եղանակ է՝ կապակցված ցուցակում հավաքել նույն H(k) առաջնային ինդեքս ունեցող տարրերը։ Սա կոչվում է ուղիղ կապակցում (direct chaining)։ Այս ցուցակի տարրերը կարող են առաջնային աղյուսակում լինել կամ չլինել, երկրորդ դեպքում դրանց զբաղեցրած հիշողության տիրույթը կոչվում է գերբեռնվածության տիրույթ (overflow area)։ Այս հնարքի թերությունն այն է, որ պետք է կազմակերպել երկրորդային ցուցակների հետ աշխատանքը, ինչպես նաև աղյուսակի ամեն մի տարրը պետք է ցուցիչ (կամ ինդեքս) ունենա խնդրահարույց տարրերի ցուցակի համար։

Կոլիզիաների լուծման այլընտրանքային եղանակ է՝ ընդհանրապես հրաժարվել ցուցակներից և պարզապես դիտարկել նույն աղյուսակի մյուս տարրերը, մինչև կգտնվի տարրը կամ կգտնվի ազատ դիրք։ Վերջին դեպքում համարում ենք, որ որոնվող տարրն աղյուսակում բացակայում է։ Այս եղանակը կոչվում է բաց հասցեավորում (open addressing) [5-3]։ Բնականաբար, տրված բանալու համար երկրորդային փորձերի ինդեքսների հաջորդականությունը միշտ պետք է նույնը լինի։ Ըստ ասվածի, որոնման ալգորիթմը կարող է ունենալ հետևյալ տեսքը․

h := H(k); i := 0;
REPEAT
  IF T[h].key = k THEN տարր գտնված է
  ELSIF T[h].key = free THEN տարրն աղյուսակում չէ
  ELSE (* կոլիզիա *)
    i := i+1; h := H(k) + G(i)
  END
UNTIL գտնված կամ աղյուսակում չէ (կամ աղյուսակը լիքն է)

Կոլիզիաների լուծման տարբեր եղանակներ են առաջարկվլ գրականության մեջ։ Մորիսի (Morris) կողմից 1968-ին թեմայի ուսումնասիրությունը [5-2] բավականին աշխուժություն բերեց ոլորտ։ Ամենապարզ ձևը՝ դիտարկել աղյուսակի հերթական տարրը (համարենք աղյուսակը շրջանաձև), մինչև կգտնվի տրված բանալիով տարրը կամ կգտնվի դատարկ տեղ։ Այսպիսով, G(i) = i, իսկ հաջորդկան փորձերի համար օգտագործվող h_i ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_i-1 + i) MOD N,    i = 1 ... N-1

Սա կոչվում է գծային փորձերի եղանակ (linear probing)։ Նրա թերությունն այն է, որ տարրերը ձգտում են կուտակվել առաջնային բանալիների շուրջը (այսինքն՝ այն բանալիների շուրջը, որոնք ավելացնելիս կոլիզիա չի առաջացել)։ Իհարկե, իդեալական դեպքում G ֆունկցիան էլ պետք է բանալիները հավասարաչափ բաշխի ազատ դիրքերի բազմության վրա։ Սակայն գործնականում բավականին դժվար է ապահովել այդ պահանջը, և այս դեպքում նախընտրում են փոխզիջումային մեթոդներ, որոնք պահանջում են բարդ հաշվարկներ, բայց ավելի լավն են քան գծային ֆունկցիան։ Դրանցից մեկում օգտագործվում է քառակուսային ֆունկցիան այնպես, որ հաջորդական փորձերի ինդեքսները որոշվում են հետևյալ կերպ․

h_0 = H(k)
h_i = (h_0-1 + i^2) MOD N,    i > 0

Նկատենք, որ հերթական ինդեքսը հաշվելիս կարելի է ազատվել քառակուսի բարձրացնելու գործողությունից, եթե h_i = i^2 և d_i = 2i + 1 համար օգտագործենք հետևյալ անդրադարձ առնչությունները․

h_i+1 = h_i + d_i
d_i+1 = d_i + 2,    i >0

որտեղ h_0 = 0 և d_0 = 1։ Սա կոչվում է քառակուսային փորձերի մեթոդ (quadratic probing), և ըհդհանուր դեպքում այն շրջանցում է վերը նշված կուտակումների խնդիրը՝ գործնականում չպահանջելով լրացուցիչ հաշվարկներ։ Մի փոքր թերությունն այն է, որ հաջորդական փորձերի ժամանակ աղյուսակի ոչ բոլոր տարրերն են ստուգվում, այսինքն տարրն ավելացնելիս հնարավոր է չնկատել ազատ դիրքը, թեև աղյուսակում այդպիսիք կան։ Իրականում, եթե N-ը պարզ թիվ է, ապա քառակուսային փորձերի մեթոդով ստուգում է աղյուսակի ամենաքիչը կեսը։ Այս պնդումը կարելի է դուրս բերոլ հետևյալ կերպ։ Այն փաստը, որ i-րդ և j-րդ փորձերը բերում են այսուսակի նույն տարրին, արտահայտվում է հետևյալ հավասարությամբ․

i^2 MOD N = j^2 MOD N
(i^2 - j^2) ≡ 0 (modullo N)

Քառակուսիների տարբերությունն արտահայտելով երկու արտադրիչներով ստանում ենք․

(i + j)(i - j) ≡ 0 (modulo N)

և քանի որ i ≠ j, ապա եզրակացնում ենք, որ i և j թվերից գոնե մեկը պետք է փոքր լինի N/2-ից, որպեսզի ամբողջաթիվ c-ի համար ստանանք i + j = c * N։ Գործականում այս թերությունն էական չէ, քանի որ կոլիզիայի լուծման համար N/2 փորձեր հազվադեպ են կատարվում, այն էլ միայն այն դեպքում, երբ աղյուսակը համարյա լիքն է։

Որպես քննարկված տեխնիկայի կիրառություն բերված է 4.4.3 բաժնի խաչաձև հղումներ գեներացնող ծրագրի ձևափոխությունը։ ?? Հիմնական տարբերությունները search պրոցեդուրայում են և T գլոբալ հեշ աղյուսակի Node ցուցաչային տիպի փոխարինելում։ ?? Հեշ-ֆունկցիա H-ը հաշվարկվում է որպես աղյուսակի չափի վրա բաժանման մնացորդ (modulus)։ Կոլիզիաների լուծման համար օգտագործված է քառակուսային փորձերի մեթոդը։ Նշենք նաև, որ լավ արտադրողականության համար շատ կարևոր է աղյուսակի չափի պարզ թիվ լինելը։

Չնայած որ այս խնդրի համար հեշավորման մեթոդը բավականին արդյունավետ է, նույնիսկ ավելի արդյունավետ, քան ծառաձև կառուցվածքները, այն ունի նաև թերություններ։ Տեքստը կարդալուց և բառերն առանձնացնելուց հետո մենք, հավանաբար, կուզենանք դրանք դասավորել այբբենական կարգով։ Դա դժվար չէ, եթե օգտագործվում են ծառաձև կառուցվածքներ, քանի որ կարգավորվածությունն ընկած է ծառաձև կառուցվածքների հիմքում։ ?? Սակայն գործը դժվարանում է բանալիների բաշխում օգտագործելիս։ ?? Այստեղ է, որ բացահայտվում է «հեշավորում» բառի ամբողջ իմաստը։ Աղյուսակն արտածելու համար պետք է ոչ միայն այն կարգավորել (այդ կտորն այստեղ բաց է թողնված), այլև բացահայտ հետևել աղյուսակում ավելացվող բանալիներին՝ դրանք հավաքելով կապակցված ցուցակում։ Այդ պատճառով էլ հեշավորման ժամանակ որոնման բարձր արագությունը մասնակիորեն փոխհատուցվում է լրացուցիչ գործողություններով, որոնք հարկավոր են խաչաձև հղումների խնդիրն ամբողջությամբ լուծելու համար։

CONST N = 997; (* պարզ թիվ, աղյուսակի չափը *)
  WordLen = 32; (* բանալիների առավելագույն երկարությունը *)
  Noc = 16; (* տարրերի առավ․ քանակը մեկ բառում *)

TYPE
  Word = ARRAY WordLen OF CHAR;
  Table = POINTER TO ARRAY N OF
    RECORD key: Word; n: INTEGER;
      lno: ARRAY Noc OF INTEGER
    END;

VAR line: INTEGER;

PROCEDURE search (T: Table; VAR a: Word);
  VAR i, d: INTEGER; h: LONGINT; found: BOOLEAN;
BEGIN (* հաշվել h հեշ ինդեքսը a-ի համար; օգտագործում է line գլոբալ փոփոխականը*)
  i := 0; h := 0;
  WHILE a[i] > 0X DO h := (256*h + ORD(a[i])) MOD N; INC(i) END;
  d := 1; found := FALSE;
  REPEAT
    IF T[h].key = a THEN (* համընկնում *)
      found := TRUE; T[h].lno[T[h].n] := line;
      IF T[h].n < Noc THEN INC(T[h].n) END
    ELSIF T[h].key[0] = " " THEN (* աղյուսակի նոր տարր *)
      found := TRUE; COPY(a, T[h].key); T[h].lno[0] := line; T[h].n := 1
    ELSE (* կոլիզիա *) h := h+d; d := d+2;
      IF h >= N THEN h := h-N END;
      IF d =N THEN
        Texts.WriteString(W," Աղյուսակը գերբեռնված է"); HALT(88)
      END
    END
  UNTIL found
END search;

PROCEDURE Tabulate (T: Table); (* օգտագործվում է W գլոբալ օբյեկտը *)
  VAR i, k: INTEGER;
BEGIN
  FOR k := 0 TO N-1 DO
    IF T[k].key[0] # " " THEN
      Texts.WriteString(W, T[k].key); Texts.Write(W, TAB);
      FOR i := 0 TO T[k].n -1 DO Texts.WriteInt(W, T[k].lno[i], 4) END;
      Texts.WriteLn(W)
   END
  END
END Tabulate;

PROCEDURE CrossRef (VAR R: Texts.Reader);
  VAR i: INTEGER; ch: CHAR; w: Word;
    H: Table;
BEGIN
  NEW(H); (* ստեղծել հեշ աղյուսակը *)
  FOR i := 0 TO N-1 DO H[i].key[0] := " " END;
  line := 0;
  Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB); Texts.Read(R, ch);
  WHILE ~R.eot DO
    IF ch = 0DX THEN (*line end*) Texts.WriteLn(W);
      INC(line); Texts.WriteInt(W, line, 6); Texts.Write(W, 9X); Texts.Read(R, ch)
    ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN
      i := 0;
      REPEAT
        IF i < WordLen-1 THEN w[i] := ch; INC(i) END;
        Texts.Write(W, ch); Texts.Read(R, ch)
      UNTIL (i = WordLen-1) OR ~(("A" <= ch) & (ch <= "Z")) &
            ~(("a" <= ch) & (ch <= "z")) & ~(("0" <= ch) & (ch <= "9"));
      w[i] := 0X; (*string terminator*)
      search(H, w)
    ELSE Texts.Write(W, ch); Texts.Read(R, ch)
    END;
    Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(H)
  END
END CrossRef

5.4 Բանալիների բաշխման մեթոդի վերլուծությունը

Բանալիների բաշխման մեթոդի վատագույն դեպքում բանալին ավելացնելու և որոնելու արտադրողականությունը սարսափելի է։ Լրիվ հնարավոր է, որ որոնման արգումենտնը փորձերի ժամանակ անցնի բոլոր զբաղված դիրքերով՝ ոչ մի անգամ չընկնելով աղյուսակի անհրաժեշտ (կամ ազատ) դիրքի վրա։ ?? Հեշավորման տեխնիկան օգտագործելու համար պետք է բավականաչափ վստահ լինել հավանականության տեսության օրենքներին։ Մենք պարզապես ուզում ենք համոզված լինել, որ փորձերի միջին թիվը փոքր է։ Ստորև բերված հավանակային փաստարկներն ցույց են տալիս, որ այդ թիվը ոչ թե փոքր է, այլ շատ փոքր է։

Մեկ անգամ էլ ենթադրենք, որ բոլոր բանալիների հանդիպելու հավանականությունը հավասար է, իս H հեշ-ֆունկցիան դրանք հավասարաչափ բաշխում է աղյուսակի ինդեքսների միջակայքի վրա։ Ենթադրենք նաև, թե բանալին պետք է ավելացվի արդեն k հատ տարրեր պարունակող և N չափ ունեցող աղյուսակի մեջ։ Այդ դեպքում առաջին փորձից ազատ դիրքի վրա ընկնելու հավանականությունը (N-k)/N է։ Սա նաև միայն մեկ համեմատում կատարելու p_1 հավանականությունն է։ Հավանականությունը, որ պետք կլինի ճիշտ մեկ երկրորդային փորձ, հավասար է առաձին փորձում կոլիզիայի հավանականությանը՝ բազմապատկած երկրորդ փորձում ազատ դիրքի վրա ընկնելու հավանականությանը։ Այսպիսով, ստանում ենք ճիշտ i փորձեր կատարելու p_i հավանականության հաշվման հետևյալ եղանակը․

p_1 = (N-k)/N
p_2 = (k/N) × (N-k)/(N-1)
p_3 = (k/N) × (k-1)/(N-1) × (N-k)/(N-2)
..........
p_i = (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × (N-k)/(N-(i-1))

Այստեղից էլ աղյուսակում k+1-րդ բանալին ավելացնելու փորձերի E քանակը հավասար է․ ??

E_k+1 = __S__i: 1 ≤ i ≤ k+1 : i × pi = 1 × (N-k)/N + 2 × (k/N) × (N-k)/(N-1) + ... + (k+1) * (k/N) × (k-1)/(N-1) × (k-2)/(N-2) × ... × 1/(N-(k-1)) = (N+1) / (N-(k-1))

Քանի որ տարրն աղյուսակում ավելացնելու փորձերի քանակը հավասար է նրա որոնման փորձերի քանակին, այս արդյունքը կարելի է օգտագործել աղյուսակում պատահական բանալին գտնելու փորձերի E քանակը հաշվելու համար։ Թող նորից N-ը ցույց տա աղյուսակի տարրերի քանակը, և թող m-ը լինի աղյուսակում առկա բանալիների քանակը։ Այդ դեպքում․

E = (Sk: 1 ≤ k ≤ m : Ek) / m = (N+1) × (Sk: 1 ≤ k ≤ m : 1/(N-k+2))/m = (N+1) × (HN+1 - HN-m+1)

որտեղ H-ը հարմոնիկ ֆունկցիան է։ H-ը կարելի է մոտարկել որպես H_N = ln(N) + g, որտեղ g-ն Էյլերի հաստատունն է։ Այնուհետև, եթե m/(N+1)-ը փոխարինենք a-ով, կստանանք․

E = (ln(N+1) - ln(N-m+1))/a = ln((N+1)/(N-m+1))/a = -ln(1-a)/a

a-ն մոտավորապես աղյուսակի զբաղված և ազատ դիրքերի քանակների հարաբերությունն է, որ կոչվում է լրացվածության գործակից (load factor)։ a=0-ն նշանակում է դատարկ աղյուսակ, իսկ a= N/(N+1) ≈ 1-ը՝ լցված աղյուսակ։ Պատահական բանալին աղյուսկում ավելացնելու կամ որոնելու փորձերի E միջին քանակը Աղյուսակ 5.1-ում թվարկված է որպես լրացվածության գործակցի ֆունկցիա։

a      E
0.1    1.05
0.25   1.15
0.5    1.39
0.75   1.85
0.9    2.56
0.95   3.15
0.99   4.66

Աղյուսակ 5.1։ Փորձերի ակնկալվող թիվը որպես լրացվածության գործակցի ֆունկցիա։

Զարմանալի թվեր են ստացվել և դրանք բացատրում են բանալիների բաշխման մեթոդի բացառիկ բարձր արտադրողականությունը։ Նույնիսկ եթե աղյուսակը 90%-ով լիքն է, միջինում 2.56 փորձ է հարկավոր՝ բանալին կամ դատարկ տեղ գտնելու համար։ Հատուկ նշենք, որ այս թիվը կախված է միայն լրացվածության գործակցից և ոչ բանալիների ընդհանուր քանակից։

Բերված վերլուծությունը հիմնված է աղյուսակի ազատ դիրքերի վրա բանալիները հավասարաչափ բաշխող կոլիզիաները լուծող մեթոդի վրա։ ?? Գործնականում օգտագործվող մեթոդները տալիս են քիչ ավելի վատ արդյունք։ Գծային փորձերի մեթոդի մանրամասն վերլուծությունը փորձերի միջին թվի համար տալիս է հետևյալ արդյունքը․

E = (1 - a/2) / (1 - a)

Որոշ թվային արդյունքներ բերված են Աղյուսակ 5.2-ում [5.4].

a     E
0.1   1.06
0.25  1.17
0.5   1.50
0.75  2.50
0.9   5.50
0.95  10.50

Աղյուսակ 5.2. Ակնկալվող փորձերի քանակը գծային փորձերի համար։

Կոլիզիաների լուծման նույնիսկ ամենապարզ մեթոդի արդյունքներն այնքան լավն են, որ գոյթակղություն է առաջանում հեշավորման մեթոդն օգտագործել որպես կյանքի բոլոր դեպքերի փրկարակ միջոց։ Մասնավորապես այն պատճառով, որ նրա արտադրողականությունը գերազանցում է նույնիսկ ամենակատարյալ ծառաձև կառուցվածքներով մեթոդներինը, հենց միայն տարրը որնելու և ավելացնելու համար համեմատությունների տեսակետից։ ?? Եվ հենց այս տեսակետից է կարևոր նշել հեշավորման մի քանի թերությունները, եթե նույնիսկ դրանք ակնհայտ են անշահախնդիր վերլուծության ժամանակ։

Իհարկե, հիշողության դինամիկ կառավարում օգտագործող մեթոդների համեմատությամբ գլխավոր թերությունը աղյուսակի ֆիքսված չափն է, որը չի կարող փոխվել ըստ անհրաժեշտության։ Այդ պատճառով էլ, եթե անընդունելի է հոշողության ոչ-խնայողական օգտագործումը կամ ցածր արտադրողականությունը (կամ աղյուսակի գերբեռնվածությունը), ապա հարկավոր է մշակվող տվյալների տարրերի քանակի բավականաչափ լավ նախնական վերլուծություն։ Նույնիսկ եթե տարրերի քանակը չիշտ հայտնի է, որ հազվադեպ է պատահում, լավ արտադրողականության համար ձգտումը ստիպում է ընտրել քիչ ավելի մեծ (ասենք, 10%) աղյուսակ։

Բաշխման մեթոդների երկրորդ մեծ թերություն ակնհայտ է դառնում, երբ աղյուսակում պետք է ոչ միայն որոնել կամ ավելացնել տարրը, այլև հեռացնել այն։ Հեշ-աղյուսակից տարրերի հեռացնելը չափազանց ծանր է, եթե միայն առանձին գերբեռնվածության տիրույթում ուղիղ կամապցումը չէ օգտագործված։ Այդ պատճառով էլ արդարացի կլինի նշել, որ ծառաձև կառուցվածքների օգտագործումը դեռևս ավելի գայթակղիչ է, հույնիսկ ավելի նախընտրելի է, եթե մշակվող տվյալների ծավալն ակնկանխատեսելի է, խիստ տատանվում է իսկ երբեմն նաև պակասում է։

1.8 Որոնում (թարգմանության փորձ)

Թարգմանված է Նիկլաուս Վիրտի «Ալգորիթմներ
և տվյալների կառուցվածքներ» գրքից։

Որոնումը կոմպյուտերային ծրագրավորման ամենից շատ հանդիպող գործողություններից է։ Այն նաև իդեալական խնդիր է զանազան տվյալների կառուցվածքները փորձարկելու համար։ ?? Գոյություն ունեն որոնման թեմայի մի քանի վարաիցիաներ, և մշակված են բազմաթիվ ալգորիթմներ։ Հետևյալ քննարկումներում ենթադրվում է, որ տվյալների հավաքածուն, որի մեջ որոնվելու է տրված տարրը, ֆիքսված է։ Կհամարենք, որ N տարրերի բազմությունը տրված է, օրինակ, զանգվածի տեսքով․

a : ARRAY N OF Item

Սովորաբար Item տիպը նկարագրված է որպես գրառում (record), որի դաշտերից մեկը բանալին (key) է։ Խնդիրը բերվում է այն տարրի գտնելուն, որի բանալին հավասար է x որոնման արգումենտին։ Արդյունքում ստացված i ինդեքսը, որ բավարարում է a[i].key = x պայմանին, հնարավորություն է տալիս դիմելու գտնված տարրի մյուս դաշտերին։ Քանի որ մեզ հետաքրքրում է միայն որոնման խնդիրը, և առայժմ չենք մտածում այն մյուս տվյալների մասին, որոնց համար որոնվում էր տարրը, կենթադրենք, որ Item տիպը պարունակում է միայն բանալին, այսինքն այն ինքը հենց բանալին է։

1.8.1 Գծային որոնում

Եթե որոնվող տվյալների մասին այլ լրացուցիչ տեղեկություններ տրված չեն, ապա ակնհայտ մոտեցումը զանգվածի տարրերի հաջորդական դիտարկումն է, քայլ առ քայլ մեծացնելուվ նրա այն հատվածի չափը, որտեղ որոնվող տարրը հայտնաբերված չէ։ Այս մոտեցումը կոչվում է գծային որոնում։ Որոնման ավարտի պայմանները երկուսն են․

1. Տարրը գտնված է, այնսինքն՝ a[i] = x։
2. Դիտարկված է ամբողջ զանգվածը և համընկնում չի հայտնաբերված։

Ստացվում է հետևյալ ալգորիթմը․

i := 0;
WHILE (i < N) & (a[i] # x) DO INC(i) END

ՈՒշադրություն դարձրեք, որ բուլյան արտահայտության մեջ ենթաարտահայտությունների կարգը կարևոր է։

Ցիկլի ինվարիանտը, այսինքն այն պայմանը, որը ճշմարիտ է ցիկլի ամեն մի իտերացիայի սկզբում և վերջում, այսպիսինն է․

(0 ≤ i < N) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այն ցույց է տալիս, որ k֊ից փոքր բոլոր i֊երի համար համընկնումներ չեն եղել։ ՈՒշադրություն դարձնենք նաև, որ ցիկլի ամեն մի իտերացիայից առաջ և հետո i֊ի արժեքները տարբեր են։ Այնուամենայնիվ, ինվարիանտը պահպանվում է ցիկլի պայմանում։

Այս ասվածից և այն փաստից, որ որոնումն ավարտվում է միայն այն ժամանակ, երբ ցիկլի պայմանը տեղի չունի (կեղծ է), կարելի է դուրս բերել վերջնական պամանը․

((i = N) OR (a[i] = x)) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Այս պայմանը ոչ միայն մեր ցանկալի արդյունքն է, այլ դրանից նաև հետևում է, որ եթե ալգորիթմը գտել է համընկնում, ապա այն գտել է ամենքփոքր ինդեքսովը, այսինքն՝ առաջինը որոնվող տարրերից։ i = N հավասարությունը ցույց է տալիս, որ համընկնումներ չեն հայտնաբերվել։

Ցիկլի կրկնությունների ավարտը ակնհայտորեն երաշխավորված է, որովհետև ամեն մի քայլում i֊ի արժեքն աճում է, հետևաբար այն, իհարկե, վերջավոր քայլերից հետո կհասնի N֊ին։ Իրականում, եթե համընկնումներ չեն եղել, ապա դա տեղի կունենա N քայլից հետո։

Պարզ է, որ յուրաքանչյուր քայլում պահանջվում է մեծացնել ինդեքսը և հաշվել բուլյան արտահայտությունը։ Կարելի՞ է արդյոք այս խնդիրը պարզեցնել, և դրանով պարզեցնել նաև որոնման գործողությունը։ Միակ հնարավորությունը երկու կտորից բաղկացած բուլյան արտահայտությունը պարզեցնելու մեջ է։ Հետևաբար, միակ տարբերակը այնպիսի ավելի պարզ պայմանի ձևակերպումն է, որը համարժեք է մեր ունեցած բարդ պայմանին։ Դա հնարավոր է, եթե երաշխավորենք, որ համընկնում միշտ տեղի է ունենալու, որին կարելի է հասնել զանգվածի վերջում x արժեքով լրացուցիչ տարր ավելացնելով։ Այս լրացուցիչ տարրը կանվանենք պատնեշ (sentinel), որովհետև այն ինդեքսին արգելում է դուրս ելնել զանգված սահմաններից։ Այժմ a զանգվածը սահմանված է որպես․

a: ARRAY N+1 OF INTEGER

իսկ գծային որոնման ալգորիթմը, պատնեշի օգտագործմամբ, կունենա հետևյալ տեսքը․

a[N] := x; i := 0;
WHILE a[i] # x DO INC(i) END

Նույն ինվարիանտից դուրս բերված վերջնական պայմանը կլինի․

(a[i] = x) & (Ak: 0 ≤ k < i: a[k] ≠ x)

Պարզ է, որ i = N պայմանը ցույց է տալիս համընկնումներ չեն եղել՝ բացառությամբ պատնեշի հետ համընկնելը։

1.8.2 Որոնում կիսման եղանակով (բինար որոնում)

Լրիվ ակնհայտ է, որ այլևս հնարավորություն չկա արագացնելու որոնման գործողությունև, եթե միայն որոնվող տարրերի մասին տրված չեն լրացուցիչ տեղեկություններ։ Հայտնի է, որ որոնումը կարելի է ավելի արդյունավետ դարձնել, եթե տվյալները կարգավորված են։ Պատկերացրեք, օրինակ, մի հեռախոսագիրք, որում անունները այբբենական կարգով դասավորված չեն։ Դա լրիվ անպետք բան է։ Մենք կներկայացնենք ալգորիթմ՝ հիմնված a զանգվածում տարրերի կարգավորված լինելու փաստի վրա, այսինքն՝ հաշվի առնելով հետևյալ պայմանը․

Ak: 1 ≤ k < N: a[k-1] ≤ a[k]

Հիմնական գաղափարն է՝ վերցնել մի պատահական տարր, օրինակ, a[m] և այն համեմատել x որոնման արգումենտի հետ։ Եթե այն հավասար է x֊ին, ապա որոնումն ավարտվում է, եթե այն փոքր է x֊ից, ապա m֊ից փոքր կամ հավասար ինդեքս ունեցող բոլոր տարրերը կարելի է բացառել հետագա որոնումից, և եթե այն մեծ է x֊ից, ապա կարելի է բացառել m֊ից մեծ և հավասար ինդեքս ունեցող տարրերը։ Ասվածից հանգում ենք կիսման եղանակով որոնման ալգորիթմին։ Այն օգտագործում է L և R ինդեքսային փոփոխականները, որոնք ցույց են տալիս զանգվածի այն հատվածի ձախ և աջ սահմանները, որոնցում դեռ կարող է հայտնաբերվել որոնվող տարրը։

L := 0; R := N - 1;
m := L֊ի և R֊ի միջև ընկած որևէ տարր;
WHILE (L <= R) & (a[m] # x) DO
  IF a[m] < x THEN
    L := m + 1
  ELSE
    R := m - 1
  END;
  m := L֊ի և R֊ի միջև ընկած որևէ տարր
END

ՈՒշադրություն դարձրեք այս ալգորիթմի և նախորդ բաժնում նկարագրված գծային որոնման ալգորիթմի հիմնական կառուցվածքային նմանությանը․ այստեղ i ինդեքսի դերկ կատարում է L, m, R եռյակը։ Այդ նմանությունը բացատրելու, և, այնուհետև, ցիկլի կոռեկտության մեջ ավելի լավ համոզվելու համար, մենք ձեռնպահ մնացինք փոքրիկ օպտիմիզացիայից, որը կբացառեր m֊ի երկու նույնական վերագրումները։

Ցիկլի ինվարիանտը, այսինքն՝ ամեմ մի քայլից առաջ ու հետո տեղի ունեցող պայմանը, հետևյալն է․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից դուրս է բերված հետևյալ արդյունքը․

((L > R) OR (a[m] = x)) & (Ak: 0 ≤ k < L: a[k] < x) & (Ak: R < k < N: a[k] > x)

որից էլ հետևում է․

((L > R) & (Ak: 0 ≤ k < N: a[k] ≠ x)) OR (a[m] = x)

m ինդեքսի ընտրությունը բոլորովին կամայական է այն իմաստով, որ ալգորիթմի կոռեկտությունը դրանից կախված չէ։ Բայց m֊ի ընտրությունն ազդում է ալգորիթմի արդյունավետության վրա։ Պարզ է, որ մեր նպատակն է ցիկլի ամեն մի քայլում հետագա որոնումից բացառել որքան հնարավոր է շատ տարրեր՝ անկախ համեմատման արդյունքից։ Լավագույն լուծումը կենտրոնական տարրի ընտրությունն է, որովհետև ամեն մի քայլում այն բացառում է զանգվածի տարրերի կեսը։ Արդյունքում քայլերի առավելագույն քանակը հավասար է log2 N, կլորացված վերև՝ մինչև ամենամոտիկ ամբողջ թիվը։ Այսպիսով, այս ալգորիթմը էականորեն շահեկան է գծային որոնման ալգորիթմից, որում համեմատությունների սպասվող քանակը N/2 է։

Արդյունավետությունը կարելի է մի քիչ լավացնել, տեղերով փոխելով ցիկլի մարմնի IF պայմանները։ Հավասարությունը պետք է ստուգել երկրորդ հերթին, որովհետև այն հանդիպում է միայն մեկ անգամ և բերում է ցիկլի ավարտին։ Բայց ավելի կարևոր է այն հարցը, թե արդյոք, ինչպես գծային որոնման դեպքում, հնարավո՞ր է գտնել ցիլի ավարտը որոշող ավելի պարզ պայման։ Իսկապես մենք գտնում ենք այդպիսի արագ ալգորիթմ, հենց որ հրաժարվում ենք որոնման ցիկլը տարրերի համընկնումով ավարտելու միամիտ ցանկությունից։ Առաջին հայացքից սա տարօրինակ է թվում, բայց ավելի ուշադիր ուսումնասիրությամբ բացահայտվում է, որ ամեն մի քայլում արդյունավետության շահն ավելին է, քան մի քանի լրացուցիչ տարրերի համեմատումից ստացված կորուստները։ Հիշենք, որ քայլերի առավելագույն քանակը log N է։

Արագ լուծումը հիմնված է հետևյալ ինվերիանտի վրա․

(Ak: 0 ≤ k < L: a[k] < x) & (Ak: R ≤ k < N: a[k] ≥ x)

և որոնումը շարունակովում է այնքան ժամանակ, քանի դեռ երկու հատվածները չեն ծածկել ամբողջ զանգվածը։

L := 0; R := 0;
WHILE L < R DO
  m := (L + R) DIV 2;
  IF a[m] < x THEN L := m + 1 ELSE R := m END
END

Ավարտի պայմանն է L ≥ R։ Բայց հասանելի՞ է արդյոք այն։ Այս պնդումն ապացուցելու համար պետք է ցույց տանք, որ բոլոր դեպքերում R - L տարբերությունը նվազում է ամեն մի քայլից հետո։ L < R տեղի ունի յուրաքանչյուր քայլ սկզբում։ m թվաբանական միջինի կամար ճշմարիտ է L ≤ m < R։ Հետևաբար, տարբերությունն իրոք նվազում է L֊ին m+1 վերգրելով (Լ-ը մեծացնելով), կամ R֊ին m վերագրելով (R֊ը նվազեցնելով), և ցիկլի կրկնությունն ավարտվում է L = R պայմանով։

Այնուամենայնիվ, մեր ինվարիանտը և L = R պայմանը դեռևս համընկնում չեն նշանակում։ Իհարկե, եթե R = N, ապա համընկնում չկա։ Այլապես պետք է հաշվի առնենք, որ a[R] տարրը երբեք չի համեմատվել։ Հետևաբար, մի լրացուցիչ a[R] = x հավասարության ստուգումն անհրաժեշտ է։ Ի տարբերություն առաջին լուծման, այս ալգորիթմը, ինչպես և գծային որոնումը, գտնում է ամենափոքր ինդեքսով համընկնող տարրը։

1.8.3 Որոնում աղյուսակում

Զանգվածում որոնումը երբեմն անվանում են նաև որոնում աղյուսակում, հատկապես եթե բանալիները բաղադրյալ օբյեկտներ են, ինչպես օրինակ թվերի կամ նիշերի զանգվածը։ Վերջինս հոնդիպում է ավելի հաճախ․ նիշերի զնգվածներն անվանում են տողեր կամ բառեր։ Սահմանենք String տիպը հետևյալ կերպ․

String = ARRAY M OF CHAR

իսկ x և y տողերի միջև կարգը սահանենք հետևյալ կերպ․

(x = y) ≡ (Aj: 0 ≤ j < M : x[j] = y[j])

(x < y) ≡ Ei: 0 ≤ i < N : ((Aj: 0 ≤ j < i : x[j] = y[j]) & (x[i] < y[i]))

Ակնհայտ է, որ համընկնումը հաստատելու համար, պետք է համոզվենք, որ համեմատվող տողերի բոլոր նիշերը համընկնում են։ Բաղադրյալ օպերանդների այսպիսի համեմատումը բերվում է օպերանդներում չհամընկնող մասերի հայտնաբերմանը, այսինքն՝ անհավասարության որոնման։ Եթե գոյություն չունի չհամընկնող մասեր, ապա հավասարությունը հաստատված է։ Ենթադրենք բառերի երկարությունը բավականաչափ փոքր է, ասենք 30֊ից փոքր, այդ դեպքում կօգտագործենք գծային որոնումը։

Շատ գործնական կիրառություններում ցանկալի է ընդունել, որ տողն ունի փոփոխական երկարություն։ Սա ենթադրում է, որ յուրաքանչյուր տողի հետ պահվում է նաև իր երկարությունը։ Օգտագործելով վերը սահմանված String տիպը, այդ երկարությունը չպետք է գերազանցի M առավելագույն արժեքը։ Այս սխեման բավականաչափ ճկուն է և ընդունելի է շատ դեպքերում, ինչպես նաև ազատում է դինամիկ հիշողության հետ աշխատելու դժվարություններից։ Լայնորեն օգտագործվում են տողի երկարությունը ներկայացնելու երկու ներկայացումներ․

1. Երկարությունը բացահայտ նշվում է տողի վերջում մի հատուկ նիշ կցելով, որը այլ տեղերում չի հանդիպում։ Սովորաբար դա 0X չարտածվող արժեքն է։ (Հետագա կիրառություններում կարևոր է, որ այդ հատուկ նիշը նիշերի բազմության ամենափոքր տարրն է։)
2. Երկարությունը բացահայտ նշվում է զանգվածի առաջին տարրում, այսինքն տողն ունի հետևյալ տեսքը․

s = s[0], s[1], s[2], ..., s[N-1]

որտեղ s[1]...s[N-1] տողի նիշերն ենմ և s[0] = CHR(N)։ Այս եղանակի առավելությունն այն է, որ երկարությունն ուղղակի մատչելի է, իսկ թերությունն այն է, որ տողի երկարությունը սահմանափակված է նիշերի բազմության հզորությամբ, այն է՝ 256 նիշ՝ ASCII կոդավորման դեպքում։

Ստորև բերված որոնման ալգորիթմում նախապատվությունը կտանք առաջին սխեմային։ Այդ դեպքում տողերի համեմատումն ընդունում է հետևյալ տեսքը․

i := 0;
WHILE (x[i] # 0X) & (x[i] = y[i]) DO i := i + 1 END

Այստեղ եզրափակող նիշը կատարում է պատնեշի դերը։ Ցիկլի ինվարիանտն է․

Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X

Իսկ վերջնական պայմանն ունի հետևյալ տեսքը․

((x[i] = 0X) OR (x[i] ≠ y[i])) & (Aj: 0 ≤ j < i : x[j] = y[j] ≠ 0X)

Այս պայմանը հաստատում է x և y տողերի հավասարությունը, երբ x[i] = y[i], և հաստատում է x < y պայմանը, եթե x[i] < y[i]։

Հիմա արդեն պատրաստ ենք վերադառնալու աղյուսակում որոնման խնդրին։ Այն պահանջվում է ներդրված որոնումներ, ավելի ճիշտ՝ որոնում աղյուսակի տարրերով, իսկ ամեն մի տարրի համար՝ կոմպոնենտների համեմատումների հաջորդականություն։ Օրինակ, թող որ T աղյուսակը և x որոնման արգումենտը սահմանված են այսպես․

T: ARRAY N OF String;
x: String

Ենթադրելով որ N֊ը բավականաչափ մեծ է և աղյուսակի տարրերը կարգավորված են այբբենական կարգով, կօգտագործենք որոնման կիսման մեթոդը։ Օգտագործելով բինար որոնման և տողերի համեմատման վերը մշակված ալգորիթմները, ստանում ենք ծրագրի հետևյալ հատվածը։

i := -1;
L := 0; R := N;
WHILE L < R DO
  m := (L + R) DIV 2;
  i := 0;
  WHILE (x[i] # 0X) & (T[m,i] = x[i]) DO i := i + 1 END;
  IF T[m,i] < x[i] THEN L := m + 1 ELSE R := m END
END;
IF R < N THEN
  i := 0;
  WHILE (x[i] # 0X) & (T[R,i] = x[i]) DO i := i + 1 END
END
(* (R < N) & (T[R,i] = x[i]) պայմանը որոշում է համընկնումը *)

March թեսթի իրականացումը Java լեզվով

Այս գրառումը կիսատ է թողնված հավես չունենալու
պատճառով։ Ցանկացողները կարող են շարունակել այն։
Կարծում եմ, որ, զարգացնելու դեպքում, կարող է լավ
կուրսային աշխատանք լինել։

Հիշող սարքերի ներդրված թեսթավորման տարածված եղանակներից մեկը March թեսթերի կիրառումն է։ Այս գրառման մեջ ես ուզում եմ պատմել հիշող սարքի մոդելի, անսարքության մոդելի, ինչպես նաև March թեսթի մոդելի իրականացման մասին։

Ընդհանուր առմամբ գաղափարը հետևյալն է․ a) սահմանել տրված չափերով հիշող սարք, b) նրանում ներմուծել որոշ տիպի անսարքություններ, c) կազմել March թեսթեր, d) գործարկել թեսթերը հիշող սարքի մոդելի վրա և գրանցել արդյունքները։

Նշված տիպի մոդելավորումն օգտագործվում է March թեսթերի մշակման համար։ Մոդելավորման օգնությամբ ստեղծվում են թեսթեր, որոնք պետք է հիշող սարքի վրա հայտնաբերեն թեսթավորողին հայտնի անսարքությունները։

Հիշող սարքը

Սովորական և անսարք բջջի մոդելը

Հիշող սարքը մեկ բիթ ինֆորմացիա պահող հիշող տարրերի՝ բջիջների մատրից է։ Այդ բջջի մոդելը ես իրականացրել եմ Cell դասով։ Այս Cell-ը սարքին բջջի մոդելն է։

package memory;

/**
 * Հիշող բջջի մոդելը
 */
class Cell {
    // տվյալ բջիջը պարունակող մատրիցը
    private Memory parent = null;
    // տողը և սյունը
    private int row = 0, column = 0;
    // բջջի արժեքը
    private char value = 'x';

    // կոնստրուկտորը
    public Cell(Memory p, int r, int c)
    {
        parent = p;
        row = r;
        column = c;
    }

    // վերադարձնում է արժեքը
    public char read()
    {
        return value;
    }

    // փոխում է արժեքը
    public void write(char v)
    {
        value = v;
    }
}

Այս դասի parent անդամը այն հիշող սարքի մոդելի հղում է, որը պարունակում է տվյալ բջիջը։ row և column ինդեքսները ցույց են տալիս, թե հիշող սարքի մատրիցի որ տողում և սյունում է տեղադրված բջիջը։ Այս երեք հատկությունները հնարավորություն են տալիս մոդելավորել այնպիսի անսարքություններ, որտեղ մի բջջի ոչ սարքին լինելը ազդում է մեկ այլ սարքին բջջի պարունակության վրա։

Հիշող բջջի հետ կապված անսարքությունները մոդելավորելու համար պետք է ընդլայնել Cell դասը։ Օրինակ, հաճախ են հանդիպում այնպիսի բջջիջներ, որոնց կարդալու գործողությունը վերադարձնում է հաստատուն 0 կամ 1 արժեքը։ Հաստատուն զրո վերադարձնող բջիջը կարելի է մոդելավորել, օրինակ, ConstZero դասով։

package memory;

/**
 * Մշտական '0' վերադարձնող անսարք բջիջ
 */
public class ConstZero extends Cell {
    public ConstZero(Memory p, int r, int c)
    {
        super(p, r, c);
    }

    @Override
    public char read()
    {
        return '0';
    }
}

Բջիջների մատրիցը

Հիշող սարքը, որը հիշող բջիջների մատրից է մոդելավորված է Memory դասով։ Այն պարունակում է տողերի ու սյուների քանակները ցույց տվող rows և columns անդամները, և Cell օբյեկտների matrix մատրիցը։

package memory;

/**
 * Հիշողղ սարքի մոդելը
 */
public class Memory {
    // տողերի քանակը
    public int rows = 0;
    // սյուների քանակը
    public int columns = 0;
    // բջիջների մատրիցը
    private Cell[][] matrix = null;

    // կոնստրուկտորը
    public Memory(int r, int c)
    {
        rows = r;
        columns = c;
        matrix = new Cell[rows][columns];

        for( int i = 0; i < rows; ++i )
            for( int j = 0; j < columns; ++j )
                matrix[i][j] = new Cell(this, i, j);
    }

    // անսարքություն մոդելավորելու համար
    // տրված դիրքում տեղադրել տրված բջիջը
    public void replaceCell(int r, int c, cell cl)
    {
        matrix[r][c] = cl;
    }

    // կարդալ, տրված է գծային հասցեն
    public char read(int addr)
    {
        return read(addr / rows, addr % rows);
    }
    // կարդալ, տրված է ֆիզիկական հասցեն
    private char read(int r, int c)
    {
        return matrix[r][c].read();
    }

    // գրել, տրված է գծային հասցեն
    public void write(int addr, char d)
    {
        write(addr / rows, addr % rows, d);
    }
    // գրել, տրված է ֆիզիկական հասցեն
    private void write(int r, int c, char d)
    {
        matrix[r][c].write(d);
    }

    // արտածել մատրիցի պարունակությունը
    public void Print()
    {
        for( int r = 0; r < rows; ++r ) {
            System.out.printf("%x: ");
            for( int c = 0; c < columns; ++c )
                System.out.print(read(r,c));
            System.out.println();
        }
        System.out.println();
    }
}

Կոնստրուկտորում matrix մատրիցը արժեքավորվում է «սարքին» բջիջներով։ Իսկ replaceCell մեթոդը հնարավորություն է տալիս մատրիցի տրված դիրքի բջիջը փոխարինել նոր տրվածով։ replaceCell մեթոդին տրվում են բջջի ֆիզիկական հասցեները՝ տողը և սյունը, քանի որ հաճախ հիշող սարքերում կիրառվում է ավելի բարդ հասցեավորում քան գծայինն է, և հարմար է անսարք բջիջը տեղադրել ըստ ֆիզիկական դիրքի։

Հիմա, օրինակ, կարող եմ ստեղծել 8 տողեր և 4 սյուներ ունեցող հիշող սարք և դրա երկրորդ տողի առաջին բջջում տեղադրել մի անսարք բջիջ։

Memory mem = new Memory(8, 4);
mem.replaceCell(1, 0, new ConstZero(mem, 1, 0));

Կամ, քանի որ Java լեզուն հնարավորություն է տալիս օբյեկտի ստեղծման ժամանակ վերասահմանել նրա մեթոդները, կարող եմ ConsOne տիպի անսարքություն մոդելավորել այսպես․

mem.replaceCell(1, 1, new Cell(mem, 1, 1) {
    @Override
    public byte read() { return '1'; }
});

March թեսթը

March թեսթը March ալգորիթմների շարք է, որոնք հաջորդաբար գործարկվում են հիշող սարքի մոդելի վրա և ստեղծում են թեսթավորման արդյունքներ։ Ալգորիթմն իր հերթին March էլեմենտների շարք է, իսկ այս վերջինն էլ March գործողությունների շարք է։

Ես դիտարկում եմ միայն պարզագույն March թեսթերը, որոնցում հանդիպում են միայն գրելու և կարդալու գործողություններ։ Եվ որպեսզի March թեսթը նկարագրելիս ավելի անսխալ լինեմ, բերեմ դրա EBNF քերականությունը։

MarchTest = { Algorithm }.
Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').

March գործողություն

Տվյալ կոնտեքստում կան երկու March գործողություններ․ բջջում տրված արժեքը գրողW (write) գործողությունը, և բջջից տրված սպասվող արժեքը կարդացող R (read) գործողությունը։

Ես ուզում եմ նշված երկու գործողությունները մոդելավարել Operation դասով։ Վերջինիս code անդամը գործողության տեսակն է՝ R կամ W, իսկ data անդամը՝ այն արժեքը, որը պետք է գրել բջջում, կամ պետք է սպասել բջջից կարդալիս։

package march;

import memory.*;

public class Operation {
    // գործողությունը
    private char code = 'X';
    // գրելու կամ կարդալու տվյալը
    private char data = '?';

    public Operation(char c, byte d)
    {
        code = c;
        data = d;
    }

March գործողությունը Memory օբյեկտի վրա գործարկելու համար սահմանեմ runOn մեթոդը, որը ստանում է թեսթավորվող հիշող սարքի հղումը և այն գծային հասցեն, որում գտնվող բջջի նկատմամբ կիրառվում է գործողությունը։

    public boolean runOn(Memory mem, int addr)
    {
        boolean status = true;

        if( opcode == 'W' )
            mem.write(addr, value);
        else if( opcode == 'R' )
            status = value == mem.read(addr);

        if( !status )
            System.out.printf("'%s' գործողությունը ձախողվեց %d հասցեի վրա։",
                              toString(), addr);

        return status;
    }

Եվ վերջապես, ToString մեթոդը, որը վերադարձնում է գործողության տեքստային տեսքը։

    @Override
    public String toString()
    {
        return Character.toString(opcode) + Character.toString(value);
    }
}

March էլեմենտ

March էլեմենտն ունի երկու բաղադրիչ․ a) հասցեների թվարկման ուղղությունը՝ որոշվող => և <= սիմվոլներով, և b) March գործողությունների շղթան։

package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March էլէմենտը
 */
public class Element {
    // հասցեները նվազում են
    public static final int DEC = -1;
    // հասցեներն աճում են
    public static final int INC = 1;

    // հասցեի թվարկման ուղղությունը
    private int direction = 0;
    // գործողությունների շարքը
    private List<Operation> operations = null;

    public Element(int dir, List<Operation> opers)
    {
        direction = dir;
        operations = new ArrayList<Operation>();
        operations.addAll(opers);
    }

March էլեմենտի գործարկումը հիշող սարքի մոդելի վրա կատարվում է runOn մեթոդով։ Քանի որ հասցեների թվարկման ուղղությունը կարող է լինել ինչպես աճող այնպես էլ նվազող, ապա begin և end փոփոխականներում հաշվում եմ առաջին ու վերջին հասցեն։ Հետո while ցիկլի մարմինը կատարվում է այնքան ժամանակ, քանի դեռ begin փոփոխվող հասցեն չի հասել end հասցեին։ Ցիլկի մարմնում մի ուրիշ for ցիկլ է, որը հիշող սարքի մոդելի վրա հերթականորեն աշխատեցնում է March գործողությունները և status բուլյան փոփոխականի մեջ է կուտակում հաջողությունների ու ձախողումների արդյունքը։

    public boolean runOn(Memory mem)
    {
        // ամենամեծ հասցեն
        final int maxaddr = mem.rows * mem.columns - 1;

        // առաջին հասցեն
        int begin = direction == INC ? 0 : maxaddr;
        // վերջին հասցեն
        int end = direction == INC ? maxaddr : 0;

        boolean status = true;
        while( begin != end + direction ) {
            for( Operation op : operations ) {
                boolean opok = op.runOn(mem, begin);
                status = status && opok;
            }
            begin += direction;
        }

        return status;
    }

Էլեմենտի տեքստային ներկայացումը ստանալու համար գրել եմ toString մեթոդը։

@Override
    public String toString()
    {
        String ops = operations.stream()
                               .map(Operation::toString)
                               .collect(Collectors.joining(","));
        String dr = (direction == INC ? "=>" : "<=");
        return String.format("%s(%s)", dr, ops);
    }
}

March ալգորիթմ

March ալգորիթմը March էլեմենտների հավաքածու է՝ խմբավորված ինչ-որ անունի տակ։ Algorithm դասով մոդելավորել եմ March ալգորիթմը։

package march;

import memory.*;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * March ալգորիթմի մոդելը
 */
public class Algorithm {
    // ալգորիթմի անունը
    private String name = "";
    // էլեմենտների ցուցակը
    private List<Element< elements = null;

    /**/
    public Algorithm(String nm, List<Element> elems)
    {
        name = nm;
        elements = new ArrayList<Element>();
        elements.addAll(elems);
    }

Ալգորիթմը հիշող սարքի մոդելի վրա գործարկվում է նորից runOn անունն ունեցող մեթոդի միջոցով։ for ցիկլը անցնում է բոլոր էլեմենտներով և դրանք գործարկում է՝ արգումենտում տալով հիշող սարքի հղումը։ Կատարման կումուլյատիվ արդյունքը ձևավորվում է status փոփոխականում։

    public boolean runOn(Memory mem)
    {
        boolean status = true;

        for( Element el : elements ) {
            boolean elok = el.runOn(mem);
            status = status && elok;
        }

        if( !status )
            System.out.printf("'%s' ալգորիթմի կատարումը ձախողվեց։\n",
                     toString());

        return status;
    }

Վերջապես toString մեթոդը վերադարձնում է ալգորիթմի տեքստային ներկայացումը։

 @Override
    public String toString()
    {
        String estr = elements.stream()
                              .map(Element::toString)
                              .collect(Collectors.joining(";"));
        return String.format("%s { %s }", name, estr);
    }
}

Ալգորիթմների կառուցումը

Ես արդեն պատմեցի Operation, Element և Algorithm դասերի մասին։ Դրանցով կարելի է կազմել թեսթավորման ալգորիթմներ և դրանք գործարկել անսարքությունների մոդելներ պարունակող հիշող սարքի մոդելի վրա։ Բայց միայն նշված դասերի կոնստրուկտորներն օգտագործելով անհարմար է կառուցել մեծ ալգորիթմներ։ Օրինակ, միայն A0 { =>(W0); =>(W1,R1) } ալգորիթմը կառուցելու համար պետք է գրել հետևյալ Java կոդը։

List<Operation> ops0 = new ArrayList<>();
ops0.add( new Operation('W', '0') );

List ops1 = new ArrayList<>();
ops1.add( new Operation('W', '1') );
ops1.add( new Operation('R', '1') );

Element el0 = new Element(Element.INC, ops0);
Element el1 = new Element(Element.INC, ops1);

List els0 = new ArrayList<>();
els0.add(el0);
els0.add(el1);

Algorijthm al0 = new Algorithm("A0", els0);

Շատ ավելի հարմար կլիներ, որ ալգորիթմը կառուցվեր մարդուն հարմար տեքստային ներկայացումից։ Դրա համար march փաթեթում ավելացրել եմ Parser դասը, որի parse մեթոդը ստանում է March ալգորիթմի տեքստային ներկայացումը և վերադարձնում է կառուցված Algorithm օբյեկտի հղումը։

package march;

import java.util.ArrayList;
import java.util.List;

public class Parser {
    private char[] source = null;
    private int position = 0;

    public Algorithm parse(String src) throws Exception
    {
        source = src.replaceAll("\\s+", "").toCharArray();
        position = 0;

        return parseAlgorithm();
    }

Parser դասը մի պարզագույն քերականական վերլուծիչ է, որը «ճանաչում» է March ալգորիթմի վերը բերված քերականությունը․

Algorithm = IDENT '{' Element { ';' Element } '}'.
  Element = ('=>' | '<=') '(' Operation { ',' Operation } ')'.
Operation = ('W' | 'R') ('0' | '1').

Քերականական երեք կանոններից յուրաքանչյուրի համար ստեղծված են համապատասխան մեթոդները՝ parseAlgorithm, parseElement և parseOperation։ Սրանցից ամեն մեկը վերլուծում է քերականությամբ իր համար որոշված հատվածը և վերադարձնում է Algorithm, Element կամ Operation օբյկտի հղում։

    private Algorithm parseAlgorithm() throws Exception
    {
        char[] name = {0, 0};
        if( !Character.isUpperCase(source[position]) )
            throw new Exception("Սպասվում է լատիներեն մեծատառ։");
        name[0] = source[position++];
        if( !Character.isDigit(source[position]) )
            throw new Exception("Սպասվում է թվանշան։");
        name[1] = source[position++];

        if( source[position++] != '{' )
            throw new Exception("Սպասվում է '{'։");

        List<Element> elements = new ArrayList<>();
        elements.add(parseElement());
        while( source[position] == ';' ) {
            ++position;
            elements.add(parseElement());
        }

        if( source[position++] != '}' )
            throw new Exception("Սպասվում է '}'։");

        return new Algorithm(new String(name), elements);
    }

    private Element parseElement() throws Exception
    {
        int direction = 0;
        if( source[position] == '=' && source[position+1] == '>' )
            direction = 1;
        else if( source[position] == '<' && source[position+1] == '=' )
            direction = -1;
        else
            throw new Exception("Սպասվում է '=>' կամ '<=։");

        position += 2;

        if( source[position++] != '(' )
            throw new Exception("Սպասվում է '('։");

        List<Operation> operations = new ArrayList<>();
        operations.add(parseOperation());
        while( source[position] == ',' ) {
            ++position;
            operations.add(parseOperation());
        }

        if( source[position++] != ')' )
            throw new Exception("Սպասվում է ')'։");

        return new Element(direction, operations);
    }

    private Operation parseOperation() throws Exception
    {
        char code = source[position++];
        if( code != 'W' && code != 'R' )
            throw new Exception("Անծանոթ գործողություն");
        char data = source[position++];
        if( data != '0' && data != '1' )
            throw new Exception("Գործողության սխալ արժեք");

        return new Operation(code, data);
    }

Իհարկե, հարմար կլիներ Parser դասին ավելացնել ևս մի parse մեթոդ, որը ստանա ալգորիթմների ցուցակ և վերադարձնի Algorithm օբյեկտների հղումների ցուցակ։

C++11: Իտերացիա ֆայլային հոսքով

Բազմաթիվ ընթերցողների խնդրանքով այս
գրառումը նվիրում եմ Քիմ Քարդաշյանին։

C++11 լեզվում ներմուծված է նոր `for` հրամանը (range-based for loop), որը հնարավորություն է տալիս իտերացիա կատարել օբյեկտի `begin()`֊ից `end()` միջակայքում։ Օգտագործելով այդ `for` հրամանը, ուզում եմ հերթականությամբ թվարկել `ifstream` հոսքի նիշերը։ Ավելի պարզ ասած՝ ուզում եմ գրել այսպիսի մի կոդ․

// ...
std::ifstream inp(name);
// ...
for( char c : obj )
    std::cout << c;
// ...

Որտեղ `obj`-ը պիտի ստացվի `inp`֊ի հետ ինչ֊որ մանիպուլյացիաների արդյունքում։

Նոր `for` հրամանն օգտագործելու համար նրան տրվող օբյեկտը (որով պետք է իտերացիա կատարվի), պետք է ունենա `begin()` և `end()` մեթոդները։ Մի քիչ քչփորելուց հետո պատրաստեցի `IterableFile` դասը, որն ընդլայնում է `ifstream`-ը՝ ավելացնելով ֆայլի սկզբի հետ կապված իտերատորը վերադարձնող `begin()` մեթոդը և դատարկ իտերատոր վերադարձնող `end()` մեթոդը։

class IterableFile : public std::ifstream {
public:
  IterableFile( const char* name )
    : std::ifstream{name}
  {
    // պահպանել բացատանիշերը
    unsetf(std::ios_base::skipws); 
  }
  std::istream_iterator<char> begin()
  {
    // սկսել ֆայլի սկզբից
    clear(); seekg(0, std::ios::beg);
    return std::istream_iterator<char>(*this);
  }
  const std::istream_iterator<char> end()
  {
    return std::istream_iterator<char>();
  }
};

`IterableFile` դասի նմուշն արդեն կարելի է օգտագործել `for` իտերատորի մեջ, օրինակ, այսպես․

  IterableFile fin("ex0.cpp");

  for( char c : fin )
    std::cout << c;

  fin.close();

Շատ հարմար կլիներ, եթե նույն էֆեկտը ստանայի առանց նոր դաս գրելու, միայն STL֊ի հնարավորություններով, բայց կարծես թե դա չի ստացվում։ (Հաստատ չեմ կարող ասել։)

Common Lisp։ Պրոցեդուրային ծրագրավորման մասին

Մի անգամ Կոնֆուցիուսին հարցրեցին.
«Ուսուցիչ, ի՞նչ կարծիքի եք այն մասին, որ Ցզի-Սյուն ծրագրավորում է Lisp լեզվով։»
ՈՒսուցիչը մտածեց և ասաց.
«Ցզին խելացի է։ Նա կարող է գրել Lisp լեզվով։»

Lisp լեզուն մեզ ծանոթ է առավելապես որպես ֆունկցիոնալ ծրագրավորման լեզու։ Բայց ես ուզում եմ այս հոդվածում ներկայացնել Common Lisp լեզվի այն հնարավորությունները, որոնք թույլ են տալիս ծրագրավորել իմպերատիվ ոճով։ Հայտնի է, որ իմպերատիվ եղանակով ցանկացած ալգորիթմ ծրագրավորելու համար պետք են ամենաքիչը չորս ղեկավարող կառուցվածքներ՝ ա) վերագրման հրաման, բ) ճյուղավորման կամ պայմանի հրաման, գ) ցիկլի կամ կրկնման հրաման և դ) հրամանների հաջորդում։ Օրինակ, C++ լեզվում վերագրման հրամանն իրականացվում է «=» սիմվոլով ձևավորվող արտահայտությունների միջոցով, ճյուղավորումները կազմակերպվում են if կամ switch կառուցվածքներով, կրկնությունները կազմակերպվում են for, while և do կառուցվածքներով, իսկ հրամանների հաջորդումը որոշվում է ծրագրի տեքստում նրանց հանդիպելու հերթականությամբ։ Իհարկե, ծրագրերի հարմար կազմակերպման համար պետք է ունենալ ենթածրագրի սահմանման մեխանիզմ, ներածման ու արտածման գործողություններ և այլն։

Սկսենք վերագրման հրամանից։ Common Lisp լեզվում վերագրումները կատարվում են setq հատուկ կառուցվածքով և setf մակրոսով։ Օրինակ, *var-i* դինամիկ փոփոխականին 123 արժեքը կարող ենք վերագրել (setq *var-i* 123) արտահայտությամբ։ Կամ, vec զանգվածի 3-րդ տարրին 3.14 արժեքը կարող ենք վերագրել (setf (aref vec 3) 3.14) արտահայտությամբ։ setq հատուկ կառուցվածքը (ինչպես նաև setf մակրոսը) հնարավորություն ունի կատարել նաև հաջորդական վերագրումներ։ Օրինակ, (setq x 1 y (1+ x) z (* 3 y)) արտահայտությունը համարժեք է (setq x 1), (setq (1+ x)) և (setq z (* 3 y)) արտահայտությունների հաջորդականությանը։ Եթե հարկավոր է կատարել զուգահեռ վերագրումներ, ապա կարող ենք օգտագործել psetq և psetf մակրոսները։ Զուգահեռ վերագրումների դեպքում, բնականաբար, հերթական վերագրման ժամանակ չի կարելի օգտագործել նախորդ վերագրումների արդյունքները։

Ճյուղավորումներ կազմակերպելու համար Common Lisp լեզուն տրմադրում է if հատուկ կառուցվածքը և when, unless, cond մակրոսները։ Ահա նրանց տեսքը.

(if ⟨condition⟩ ⟨then-form⟩ ⟨else-form⟩?)

(when ⟨condition⟩ ⟨form⟩*)

(unless ⟨condition⟩ ⟨form⟩*)

(cond (⟨condition-1⟩ ⟨form-1⟩) (⟨condition-2⟩ ⟨form-2⟩) ...)

Օրինակ, a և b թվերից մեծագույնը c փոփոխականին վերագրելու համար կարող ենք գրել հետևյալ արտահայտություններից որևէ մեկը․

(if (> a b) (setq c a) (setq c b))

կամ

(setq c (if (> a b) a b))

if կառուցվածքը հնարավորություն է տալիս պայմանի ստուգումից հետո կատարել երկու ճյուղերից որևէ մեկը։ Եթե ունենք միայն մեկ ճյուղ, ապա կարող ենք օգտագործել կա՛մ when, կա՛մ unless մակրոսը։ when մակրոսը կատարում է իր մարմինը, երբ պայմանը դրական է, իսկ unless մակրոսը՝ երբ պայմանը բացասական է։ Օրինակ, հետևյալ երկու արտահայտությունների կատարման դեպքում էլ կարտածվի նույն պատասխանը․

(when (> a b) t)
(unless (<= a b) t)

cond մակրոսը կիրառելի է այն ժամանակ, երբ պետք է ընտրություն կատարել երկուսից ավելի ճյուղերի միջև։ Այն իր արգումենտում ստանում է զույգեր, որոնցից առաջին տարրը պայմանն է, իսկ երկրորդը՝ գործողությունը։ Ճյուղավորումն ավարտվում է այն գործողության կատարմամբ, որին համապատասխան պայմանը առաջինն է հաշվարկվում որպես դրական արժեք։ Օրինակ, 0-ից 2 թվերի անուններն արտածելու, իսկ մյուս թվերի համար «more» բառն արտածելու համար կգրենք․

(setq d (parse-integer (read-line)))
(cond ((= d 0) (print "zero"))
      ((= d 1) (print "one"))
      ((= d 2) (print "two"))
      (t (print "more")))

Ցիկլերի կազմակերպման համար Common Lisp լեզուն ունի այնպիսի հնարավորություններ, որ ցանկացած այլ լեզու միայն կարող է նախանձել։ Դիտարկենք dotimes, dolist և loop մակրոսների որոշ հնարավորություններ։ dotimes մակորսը պարզագույն հաշվիչով ցիկլ է։ Օրինակ, 0-ից 100 միջակայքի 20 պատահական թվերի ցուցակ կառուցելու համար կարող ենք գրել․

(setq rnums '())
(dotimes (j 20)
  (push (random 100) rnums))

dolist մակրոսը նման է dotimes մակրոսին, բայց սա իտերացիա է կատարում ցուցակի տարրերով։ Օրինակ, նախորդ օրինակում կառուցված պատահական թվերի ցուցակի տարրերի գումարը կարող ենք հաշվել և արտածել հետևյալ կերպ․

(setq rsum 0)
(dolist (e rnums)
  (incf rsum e))
(print rsum)

loop մակրոսով կարելի է 20 պատահական թվերի ցուցակը կազմել ահա այսպես.

(setq rnums (loop repeat 20 collect (random 100)))

Իսկ rnums ցուցակի տարրերի գումարը կարելի է հաշվել հետևյալ արտահայտությամբ.

(print (loop for e in rnums summing e))

Պրոցեդուրային լեզուների while ցիկլը նույնպես կարելի է գրել loop մակրոսի օգնությամբ։ Օրինակ, 1-ից 20 թվերը հակառակ հաջորդականությամբ տպելու համար կարող ենք գրել.

(setq a 20)
(loop while (> a 0)
      do (print a)
         (incf a -1))

Հրամանների հաջորդման համար Common Lisp լեզվում առկա են progn հատուկ կառուցվածքը և prog1, prog2 մակրոսները։ progn կառուցվածքը հերթականորեն հաշվարկում է իր արգումենտները և վերադարձնում է դրանցից վերջինի արժեքը։ prog1 և prog2 մակրոսները համապատասխանաբար վերադարձնում են առաջին և երկրորդ արգումենտների արժեքները։ Սրանք ինչ-որ իմաստով նման են պրոցեդուրային լեզուներում բլոկների կազմակերպման մեխանիզզմներին (ինչպես օրինակ Pascal լեզվի begin-end բլոկները)։ Լեզվի շատ ֆունկցիաներ ու մակրոսներ ունեն ոչ բացահայտ progn, այսինքն կարելի է պարզապես իրար հետևից գրել արտահայտությունները՝ առանց progn կառուցվածքի օգտագործման։ Օրինակ, while և unless մակրոսների կիրառման դեպքում progn պետք չէ, իսկ if հատուկ կառուցվածքի մարմնում պետք է։

Գլոբալ ֆունկցիաները Common Lisp լեզվում սահմանվում են defun մակրոսով։ Այն ստանում է սահմանվող ֆունկցիայի անունը, պարամետրերի ցուցակը և ֆունկցիայի մարմինը։ Օրինակ, հետևյալ ֆունկցիան իրար է գումարում արգումենտում ստացած երկու թվերը․

(defun add-two-num (a b)
  (+ a b))

Ֆունկցիայի վերադարձրած արժեք է համարվում նրա մարմնում հաշվարկված վերջին արտահայտության արժեքը։ Եվ վերջապես որպես օրինակ դիտարկենք տրված վեկտորի ամենամեծ ու ամենափոքր տարրը որոշող ալգորիթմը։ C++ լեզվով այն կարող ենք գրել հետևյալ կերպ․

template
std::tuple min_and_max( std::vector vec )
{
  T mn(vec.at(0));
  T mx(vec.at(0));
  for( auto e : vec ) {
    if( mn > e ) mn = e;
    if( mx < e ) mx = e;
  }
  return std::make_tuple(mn, mx);
}

Սա մի ֆունկցիա է, որը արգումենտում ստանում է վեկտոր, և վերադարձնում է երկու թիվ՝ վեկտորի տարրերից ամենամեծն ու ամենափոքրը։ Հիմա տեսնենք, թե Common Lisp լեզվով ինչպես կարելի է ծրագրավորել այս նույն ալգորիթմը։ Շաբլոնների կարիքը չունենք, որովհետև Lisp-ը տիպերի դինամիկ ստուգմամբ լեզու է (թեև հայտարարությունների օգնությամբ կարող ենք կոմպիլյատորին հուշել փոփոխականի տիպը)։ min-and-max ֆունկցիան, տիպիկ պրոցեդուրային ոճով, կունենա մոտավորապես հետևյալ տեսքը․

(defun min-and-max (vec)
  (declare (type array vec))
  (let ((mn (aref vec 0))
        (mx (aref vec 1)))
    (loop for e across vec
     do
       (if (> mn e) (setf mn e))
       (if (< mx e) (setf mx e)))
    (values mn mx)))

Բայց․․․ բայց բարեբախտաբար Lisp լեզուն նախատեսված չէ այս ոճի կոպիտ ծրագրեր գրելու համար։ (Ես պատկերացնում եմ, որ եթե Lisp-ինտերպրետատորը կարողանար ծիծանել, ապա այն ինչպիսի քրքջոց կբարձրացներ այս ֆունկցիան կարդալու ժամանակ։)