Difference between revisions of "LU-LSP-b13:L01"

From DiLab
Jump to: navigation, search
(Papildinformācija)
(Par simbolu virkņu meklēšanu)
 
(One intermediate revision by the same user not shown)
Line 113: Line 113:
* [https://elixir.bootlin.com/glibc/glibc-2.17/source/string/strlen.c GlibC strlen implementācija],
* [https://elixir.bootlin.com/glibc/glibc-2.17/source/string/strlen.c GlibC strlen implementācija],
* un [https://www.eevblog.com/forum/programming/which-strlen-function-is-faster/ dažādu strlen implementāciju veiktspējas salīdzinājums]
* un [https://www.eevblog.com/forum/programming/which-strlen-function-is-faster/ dažādu strlen implementāciju veiktspējas salīdzinājums]

=== Par simbolu virkņu meklēšanu ===

Ir [https://en.wikipedia.org/wiki/String-searching_algorithm vairāki viltīgi algoritmi],
kas atšķiras no naivā meklēšanas algoritma ar labāku veiktspēju.

Piemēram, [https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm Boyer-Moore algoritms], kas meklē no otra gala un lec uz priekšu pa vairākiem burtiem, ja iespējams.

Latest revision as of 14:02, 8 February 2024

Praktiskais darbs #1

Darbs ir paredzēts, lai iepazītos ar Linux kā izstrādes un testēšanas vidi, un atkārtotu C programmēšanas pamatus.

Darbu jāiesniedz Github Classroom laboratorijas darbu repozitorijā. Ielūguma links e-studijās. Faila nosaukums LSP_PD1_vards_uzvards.c

Beigās risinājumi tiek apskatīti kopīgi, pārrunājot risināšanas gaitu.

Uzdevumi

1. Uzrakstīt funkciju int sv_garums(char *virkne), kas atrod simbolu virknes garumu

  • Šeit un turpmāk var pieņemt, ka simbolu virknes korekti beidzas ar nulles simbolu (C kodā pierakstāms kā '\0', vai arī vienkārši 0)

2. Uzrakstīt funkciju void sv_kopet(char *no, char *uz), kas nokopē simbolu virkni

  • Var pieņemt, ka vietas pietiks.
  • Izaicinājums – neizmantot papildus mainīgos!

3. Uzrakstīt funkciju int sv_meklet(char *kur, char *ko)

  • Funkcija sameklē un atgriež simbolu skaitu no virknes "kur" sākuma līdz vietai, kur tajā pirmoreiz atrodama virkne "ko"
  • Ja "ko" nav atrodams virknē "kur", tad atgriež -1
  • sv_meklet("to be or not to be", "be") -> 3
  • sv_meklet("something else", "be") -> -1

4. Uzrakstīt funkciju void sv_apgriezt(char *virkne), kas apgriež simbolu virkni.

  • Piemērs: "abcd" -> "dcba"
  • Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma!

5. (Neobligāts) Uzrakstīt funkciju void sv_vapgriezt(char *virkne), kas apgriež vārdus simbolu virknē

  • Piemērs: "hello world" -> "world hello"
  • Izmantotās papildus atmiņas apjomam jābūt neatkarīgam no simbolu virknes garuma!

Papildinformācija

Risinājums rakstīt vienā vai vairākos C pirmkoda failos.

Risinājumus pārbaudīt, uzbūvējot bināro failu izmantojot GCC kompilatoru, un testējot ar saviem izdomātiem testa piemēriem.

Piemēram, ja risinājums un testa piemēri ir aprakstīti failā pd1.c, var rīkoties šādi:

Pirmkārt, uzbūvējam pd1 izpildāmo failu:

$ gcc pd1.c -o pd1

Otrkārt, palaižam pd1 izpildāmo failu:

$ ./pd1

Faila pd1.c šablons:

#include <stdio.h>

int sv_garums(char *virkne)
{
    // ...
    // TODO: PD1.1 kodu rakstīt te!
    // ...
}
 
void sv_kopet(char *no, char *uz)
{
    // ...
    // TODO: PD1.2 kodu rakstīt te!
    // ...
}

int sv_meklet(char *kur, char *ko)
{
    // ...
    // TODO: PD1.3 kodu rakstīt te!
    // ...
}

void sv_apgriezt(char *virkne)
{
    // ...
    // TODO: PD1.4 kodu rakstīt te!
    // ...
}

void sv_vapgriezt(char *virkne)
{
    // ...
    // TODO: PD1.5 kodu rakstīt te!
    // ...
}

int main(void) {
    char buferis[100];

    printf("Tests uzdevumam PD1.1:\n");
    printf("%d\n", sv_garums("hello world"));
    printf("%d\n", sv_garums("123"));
    printf("%d\n", sv_garums(""));

    printf("Tests uzdevumam PD1.2:\n");

    // ...
    // TODO: PD1 testu kodu rakstīt te!
    // ...

    // Uzdevumus 4. un 5. testēt šādā veidā, lai izvairītos no access violation!
    // sv_kopet("abcd", buferis);
    // sv_apgriezt(buferis);
    // printf("%s\n", buferis);

    return 0;
}


Piezīme. Iepriekš jau atrisinātos uzdevumus drīkst izmantot tālāko uzdevumu risināšanai. Piemēram, uzdevumu 2.-5. risinājumos drīkst izmantot funkcijas sv_garums izsaukumu.

Par strlen veiktspēju

Vai Jūsu garuma funkcija strādā tik pat ātri kā GLibC strlen funkcija?

Interesei te ir:

Par simbolu virkņu meklēšanu

Ir vairāki viltīgi algoritmi, kas atšķiras no naivā meklēšanas algoritma ar labāku veiktspēju.

Piemēram, Boyer-Moore algoritms, kas meklē no otra gala un lec uz priekšu pa vairākiem burtiem, ja iespējams.