Лекція 2
- Компіляція
- Дебаггінг
- Пам’ять
- Масиви
- Рядки
- Аргументи командного рядка
- Шифрування
- Коди виходу
- Сортування
Компіляція
- Ми почали курс з вивчення Scratch, а потім перейшли на мову програмування С.
- Нагадаємо, що ми пишемо вихідний код мовою програмування C, але ми маємо його спомпілювати на машинний код у двійковій системі, аби запустити на комп'ютері.
clangце компілятор, з яким ми вже познайомилися, аmake– це утіліта, яка допомагає нам запускатиclangавтоматично.- Якщо б ми захотіли використати бібліотеку CS50 за допомогою
#include <cs50.h>, та застосуватиclangзамістьmake, потрібно додати прапорець:clang hello.c -lcs50. Прапорець-lпідключає файлcs50, який було встановлено у CS50 Sandbox.
- Компіляція вихідного коду на машинний відбувається у такі кроки:
- препроцессінг
- компіляція
- збирання
- компонування
- Препроцессінг складається з перегляду рядків, які починаються з
#, як-от#include, перед тим, як виконувати все інше. Наприклад,#include <cs50.h>скажеclangзнайти спочатку цей заголовковий файл, оскільки там міститься контент, який ми хочемо використати у нашій програмі. Потім,clangзамінить вміст цих файлів в нашій програмі:... string get_string(string prompt); int printf(const char *format, ...); ... int main(void) { string name = get_string("Name: "); printf("hello, %s\n", name); } - Компіляція бере наш вихідний код на С та конвертує на код асемблера, який виглядає ось так:
... main: # @main .cfi_startproc # BB#0: pushq %rbp .Ltmp0: .cfi_def_cfa_offset 16 .Ltmp1: .cfi_offset %rbp, -16 movq %rsp, %rbp .Ltmp2: .cfi_def_cfa_register %rbp subq $16, %rsp xorl %eax, %eax movl %eax, %edi movabsq $.L.str, %rsi movb $0, %al callq get_string movabsq $.L.str.1, %rdi movq %rax, -8(%rbp) movq -8(%rbp), %rsi movb $0, %al callq printf ...- Це низькорівневі інструкції, тому краще зрозумілі центральному процессору, і вцілому працюють з байтами, а не з такими абстракціями, як назви змінних.
- Наступний крок – взяти код асемблера та перекласти його на інструкції у двійковій системі – це називається збирання.
- І наостанок потрібно все скомпонувати, коли вміст пов'язаних бібліотек, як
cs50.c, фактично включаються до нашої програми у двійковому вигляді.
Дебаггінг
- Уявімо, ми написали програму
buggy0:int main(void) { printf("hello, world\n") }- Ми бачимо помилку, коли намагаємось скомпілювати цю програму за допомогою
makeпро те, що ми не додали заголовковий файл. - Ми можемо запустити
help50 make buggy0, що врешті-решт повідомить нам про необхідність додати#include <stdio.h>, який міститьprintf. - Ми все зробили, а тепер бачимо ще одну помилку та розуміємо, що ми забули поставити крапку з комою в кінці рядка.
- Ми бачимо помилку, коли намагаємось скомпілювати цю програму за допомогою
- Давайте розглянемо іншу програму:
#include <stdio.h> int main(void) { for (int i = 0; i <= 10; i++) { printf("#\n"); } }- Хм, ми думали, що буде лише 10 символів
#, але їх вийшло 11. Якби ми не знали, в чому полягає проблема (оскільки наша програма працює так, як ми її написали), то могли б додати ще один рядок print на допомогу:#include <stdio.h> int main(void) { for (int i = 0; i <= 10; i++) { printf("i is %i\n", i); printf("#\n"); } } - Тепер, ми бачимо, що
iпочалась з 0 і продовжувалась до 10, але ми повинні його зупинити на 9.
- Хм, ми думали, що буде лише 10 символів
- Якби ми записали нашу програму без пробілів, як подано нижче, то вона все одно була б правильна:
#include <stdio.h> int main(void) { for (int i = 0; i < 10; i++) { printf("i is %i\n", i); printf("#\n"); } }- Однак, читати в такому вигляді складно, це поганий дизайн. Набагато легше буде побачити вкладеність, якщо ми використаємо відступи для циклів.
- Ми можемо запустити
style50 buggy2.c, і побачити рекомендації, що нам слід змінити.
- Отже, нагадаємо, ми маємо три інструменти, які допоможуть нам покращити код:
help50printfstyle50
Пам’ять
- В середині наших комп`ютерів містяться чіпи RAM, тобто оперативна пам'ять, що зберігає дані для короткочасного використання. Можна зберігати файли на жорсткому диску (або SSD) для довготривалого зберігання, але коли ми його відкриємо та будемо вносити зміни, все копіюється до RAM. Попри те, що обсяг RAM значно менший та вона є тимчасовою (поки не буде вимкнене живлення), вона значно швидша.
- Можна розглядати байти, які зберігаються в RAM, у вигляді сітки:
- Насправді там розташовані мільйони або навіть мільярди байтів на кожному чіпі.
- У мові програмування С коли ми створюєму змінну типу
charрозміром в один байт, вона буде фізично збережена в одній із таких комірок у RAM. Ціле число на чотири байти займе чотири таких комірки.
Масиви
- У пам’яті ми можемо зберігати змінні послідовно, одна за одною. І в мові програмування С список збережених змінних, які розташовуються у суміжних комірках пам'яті, називається масивом.
- Виявляється, що з самими тільки масивами можна робити дуже цікаві речі.
- Розглянемо
scores0.c:#include <cs50.h> #include <stdio.h> int main(void) { // Get scores from user int score1 = get_int("Score 1: "); int score2 = get_int("Score 2: "); int score3 = get_int("Score 3: "); // Generate first bar printf("Score 1: "); for (int i = 0; i < score1; i++) { printf("#"); } printf("\n"); // Generate second bar printf("Score 2: "); for (int i = 0; i < score2; i++) { printf("#"); } printf("\n"); // Generate third bar printf("Score 3: "); for (int i = 0; i < score3; i++) { printf("#"); } printf("\n"); }- Ми отримуємо 3 результати (scores) від користувача та виводимо графічне позначення для кожного з них.
- Наші 3 цілих числа,
score1,score2, таscore3будуть збережені десь у пам’яті.
- Ми можемо використати цикл, або почнемо розділяти на частини:
#include <cs50.h> #include <stdio.h> void chart(int score); int main(void) { // Get scores from user int score1 = get_int("Score 1: "); int score2 = get_int("Score 2: "); int score3 = get_int("Score 3: "); // Chart first score printf("Score 1: "); chart(score1); // Chart second score printf("Score 2: "); chart(score2); // Chart third score printf("Score 3: "); chart(score3); } // Generate bar void chart(int score) { // Output one hash per point for (int i = 0; i < score; i++) { printf("#"); } printf("\n"); }- Тепер маємо функцію
chartяка буде виводити кожен результат. - Пам'ятайте, що нам потрібно мати на початку прототип,
void chart(int score);. Ми моглиб мати всю функціюchartвгорі перед її використанням, але врешті наша функціяmainбуде спускатись все нижче і шукати її буде все складніше.
- Тепер маємо функцію
- За допомогою масивів ми можемо зібрати результати в циклі, а потім одержати до них доступ, також в циклі:
// Generates a bar chart of three scores using an array #include <cs50.h> #include <stdio.h> void chart(int score); int main(void) { // Get scores from user int scores[3]; for (int i = 0; i < 3; i++) { scores[i] = get_int("Score %i: ", i + 1); } // Chart scores for (int i = 0; i < 3; i++) { printf("Score %i: ", i + 1); chart(scores[i]); } } // Generate bar void chart(int score) { // Output one hash per point for (int i = 0; i < score; i++) { printf("#"); } printf("\n"); }- Зверніть увагу, що ми застосовуємо
int scores[3]для ініціалізації масиву з трьома цілими числами. Потім ми використовуємоscores[i] = ..., щоб зберегти значення в цьому масиві, використовуючи для цього індексiвід0до2(оскільки в нас три елементи). - Після цього ми використовуємо
scores[i]для доступу до усіх значень в масиві за кожним індексом.
- Зверніть увагу, що ми застосовуємо
- У нас повторюється число
3кілька разів, тому ми можемо виокремити його у константу, тобто число, яке ми можемо один раз задати й використовувати глобально:#include <cs50.h> #include <stdio.h> const int COUNT = 3; void chart(int score); int main(void) { // Get scores from user int scores[COUNT]; for (int i = 0; i < COUNT; i++) { scores[i] = get_int("Score %i: ", i + 1); } // Chart scores for (int i = 0; i < COUNT; i++) { printf("Score %i: ", i + 1); chart(scores[i]); } } // Generate bar void chart(int score) { // Output one hash per point for (int i = 0; i < score; i++) { printf("#"); } printf("\n"); }- На початку ми використовуємо ключове слово
constщоб визначити, що це незмінне значення. Його можна використовувати по всьому коду, і якщо ми захочемо щось змінити, достатньо змінити лише один раз. Врешті, назваCOUNTнаписана великими літерами, щоб показати, що це константа (за домовленістю).
- На початку ми використовуємо ключове слово
- Ми можемо за допомогою функції
chartвивести всі результати, а не по одному стовпчику за раз:#include <cs50.h> #include <math.h> #include <stdio.h> const int COUNT = 3; void chart(int count, int scores[]); int main(void) { // Get scores from user int scores[COUNT]; for (int i = 0; i < COUNT; i++) { scores[i] = get_int("Score %i: ", i + 1); } // Chart scores chart(COUNT, scores); } // Generate bars void chart(int count, int scores[]) { // Output one hash per point for (int i = 0; i < count; i++) { for (int j = 0; j < scores[i]; j++) { printf("#"); } printf("\n"); } }- Передавши весь масив
scoresта кількість результатівcountякі ми хочемо вивести, ми можемо використати функціюchartдля ітерування крізь масивscores. Фактично,chartнаскільки великим є масивscores, тож ми обов'язково маємо передавати йcount.
- Передавши весь масив
Рядки
- Рядки – це насправді просто масиви символів. Це можна побачити у
string0.c:#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { string s = get_string("Input: "); printf("Output: "); for (int i = 0; i < strlen(s); i++) { printf("%c\n", s[i]); } }- Спочатку нам знадобиться нова бібліотека,
string.h, дляstrlen, що показує нам довжину рядка. Далі ми використовуємо той же синтаксис для доступу до елементів масиву,s[i], аби вести окремі символи рядкаs.
- Спочатку нам знадобиться нова бібліотека,
- Ми можемо покращити дизайн нашої програми.
string0була не надто ефективна, оскільки перевіряємо довжину рядка після введення кожного символу, в нашій умові. Проте оскільки довжина рядка не змінюється, то ми можемо перевіряти її лише один раз:#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { string s = get_string("Input: "); printf("Output:\n"); for (int i = 0, n = strlen(s); i < n; i++) { printf("%c\n", s[i]); } }- Зараз, на початку нашого циклу, ми ініціалізуємо дві змінні
iтаnта записуємо довжину рядка уn. Далі ми можемо щоразу перевіряти значення без вираховування довжини рядка. nбуде доступна виключно в межах циклуforхоча ми можемо ініціалізувати її і поза ним, якщо нам потрібно буде її повторне використання.
- Зараз, на початку нашого циклу, ми ініціалізуємо дві змінні
- Коли рядок зберігається у пам’яті, кожен символ розміщується в одному байті в таблиці байтів. Десь, наприклад, слово
Zamylaзбережено у 6 байтах. Але нам потрібен ще один байт, для позначення кінця рядка:
- Байт пам'яті, де збережено перший символ рядка,
Z, позначено якs, оскільки ми назвали наш рядокsу коді вище. Далі, після останнього символу,a, ми маємо один байт з усіма0для позначення кінця рядку. І ьайт з усіма0називається нульовим символом, який можна також позначати як\0.
- Байт пам'яті, де збережено перший символ рядка,
- Якби ми хотіли написати власну версію
strlen, наприклад, то нам треба знати наступне:#include <cs50.h> #include <stdio.h> int main(void) { // Prompt for user's name string s = get_string("Name: "); // Count number of characters up until '\0' (aka NUL) int n = 0; while (s[n] != '\0') { n++; } printf("%i\n", n); }- Тут ми перебираємо кожен символ рядка
s, використовуючи той же синтаксис, що й для доступу до елементів масивів, і ми інкрементуємо лічильник,n, поки символ не дорівнюватиме нульовому символу,\0. Якщо він дорівнює, значить, ми в кінці рядка й можемо вивести значенняn.
- Тут ми перебираємо кожен символ рядка
- Оскільки ми знаємо, що кожен символ має числове, ASCII значення, то можна вивести й таке:
#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { string s = get_string("String: "); for (int i = 0; i < strlen(s); i++) { int c = (int) s[i]; printf("%c %i\n", s[i], c); } }- За допомогою
(int) s[i], wми беремо значенняs[i]та перетворюємо символьний тип на цілочисельний. Після цього ми можемо вивести як символи, так і їхні числові значення. - Технічно ми навіть можемо зробити
printf("%c %i\n", s[i], s[i]);, аprintfрозпізнає значенняs[i]як ціле число.
- За допомогою
- Тепер ми можемо поєднати те, що ми розглянули, аби створити програму, яка замінює маленькі літери на великі:
#include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { string s = get_string("Before: "); printf("After: "); for (int i = 0, n = strlen(s); i < n; i++) { if (s[i] >= 'a' && s[i] <= 'z') { printf("%c", s[i] - ('a' - 'A')); } else { printf("%c", s[i]); } } printf("\n"); }- Спочатку ми отримуємо рядок
s. Тоді, для кожного символу в рядку, якщо він в нижньому регістрі (його значення знаходиться міжaтаz), ми конвертуємо його на велику літеру. В іншому випадку, ми його просто виводимо. - Ми можемо перетворити малі літери у великі шляхом віднімання різниці між малою
aта великоюA. (Ми знаємо, що у малих літер більші значення, тому можна відняти різницю між ними та перетворити малі літери на великі.)
- Спочатку ми отримуємо рядок
- Також є функції з бібліотек, які ми можемо використати для досягнення того ж ефекту:
#include <cs50.h> #include <ctype.h> #include <stdio.h> #include <string.h> int main(void) { string s = get_string("Before: "); printf("After: "); for (int i = 0, n = strlen(s); i < n; i++) { if (islower(s[i])) { printf("%c", toupper(s[i])); } else { printf("%c", s[i]); } } printf("\n"); }- Можна використати функції
islower()таtoupper()з бібліотекиctype. (Про це можна довідатись виключно з документації до бібліотеки, яку інші люди написали задовго до нас.) - Ми можемо використовувати програму командного рядка,
man, щоб прочитати інструкцію з використання інших програм, якщо така існує. Наприклад, ми можемо запуститиman toupperдля перегляду документації для цієї функції. Ми побачимо, щоtoupperповертає символ таким, яким він є, якщо він не написаний маленькими літерами, тож отримаємо:for (int i = 0, n = strlen(s); i < n; i++) { printf("%c", toupper(s[i])); }
- Можна використати функції
Аргументи командного рядка
- Ми використовували такі програми як
makeтаclang, які приймають додаткові слова після своєї назви в командному рядку. Але насправді, наші програми також можуть приймати аргументи командного рядка. - У
argv0.c, ми змінюємо вигляд нашої функціїmain:#include <cs50.h> #include <stdio.h> int main(int argc, string argv[]) { if (argc == 2) { printf("hello, %s\n", argv[1]); } else { printf("hello, world\n"); } }argcтаargv- це дві змінні, які одержить функціяmainколи ми запустимо нашу програму з командного рядка.argcargc – це лічильник аргументів, тобто їх кількість, аargv- масив рядків, що є аргументами. Найперший аргумент,argv[0], буде назвою нашої програми (найперше надруковане слово, наприклад,./hello). У цьому прикладі ми перевіримо, чи маємо ми два аргументи, і, якщо так, виведемо другий.
- Ми можемо вивести кожен аргумент, один за одним:
#include <cs50.h> #include <stdio.h> int main(int argc, string argv[]) { for (int i = 0; i < argc; i++) { printf("%s\n", argv[i]); } } - Ми також можемо вивести кожен символ кожного аргументу:
#include <cs50.h> #include <stdio.h> #include <string.h> int main(int argc, string argv[]) { for (int i = 0; i < argc; i++) { for (int j = 0, n = strlen(argv[i]); j < n; j++) { printf("%c\n", argv[i][j]); } printf("\n"); } }- За допомогою
argv[i], ми отримуємо поточний аргумент із масиву аргументів, а зargv[i][j], символ з цього рядка.
- За допомогою
Шифрування
- Якби ми хотіли надіслати комусь повідомлення, ми б, можливо, захотіли його зашифрувати, тобто певним чином змінити повідомлення, щоб іншим було важко його прочитати. Оригінальний текст тоді ми назвемо звичайний текст, а текст після шифрування - зашифрований текст.
- Таке повідомлення, як
HI!може бути перетворене в ASCII,72 73 33. Проте, кожен може з легкістю виконати цю дію і в зворотному порядку. - Розглянемо приклади шифрів з історії, починаючи ще з Першої світової війни, до поеми про поїздку Пола Рівера.
- Загалом шифрування потребує не тільки самого тексту на вхід, а й додаткової інформації. Потрібен ключ, іноді це просто секретне число. Відкритий текст може бути зашифрований та розшифрований за допомогою ключа за певним алгоритмом.
- Наприклад, якщо ми хочемо надіслати текст
I L O V E Y O U, ми спочатку можемо його перетворити на ASCII:73 76 79 86 69 89 79 85. Тоді, ми можемо зашифрувати його ключем1простим алгоритмом, де ми лише додаємо ключ до значення кожного елемента:74 77 80 87 70 90 80 86. Після цього, якщо хтось перетворить ASCII назад в текст, то отримаєJ M P W F Z P V. Для розшифровки потрібно буде здогадатися значення кожної букви, методом спроб та поразок, але напевне знати без ключа неможливо. Цей алгоритм відомий під назвою шифр Цезаря.
Коди виходу
- Виявляється, що ми можемо вказувати на помилки в нашій програмі, повертаючи значення з функції
main:#include <cs50.h> #include <stdio.h> int main(int argc, string argv[]) { if (argc != 2) { printf("missing command-line argument\n"); return 1; } printf("hello, %s\n", argv[1]); return 0; }- Значення, що повертається
mainв нашій програмі, називається кодом виходу, і ми можемо це побачити в командному рядку. Якщо ми запустимо нашу програму через./exit, можемо потім набратиecho $?, яка виведе повернене останньою програмою значення. - Коли ми почнемо писати складніші прошрами, то такі коди виходу допоможуть нам вчасно зрозуміти, що пішло не так, навіть якщо вони невидимі або незрозумілі для користувача.
- Значення, що повертається
Сортування
- З масивами ми можемо розв’язувати значно цікавіші задачі. Наприклад, ми можемо розглядати масиви як шафки, за дверима кожної з яких знаходиться якесь значення – ціле число чи символ. До того ж, комп’ютер здатний розглядати одну шафку або значення за раз.
- Якби ми мали список чисел та хотіли знайти в ньому певне число, найкраще що можна зробити, це переглянути його значення один за одним або в довільному порядку.
- Проте якби ми знали, що список був відсортований, то спочатку могли б поглянути в його середину і, відповідно, потім рухались би вліво або вправо.
- Разом з добровольцями ми розглянули, як можна відсортувати список.
- Наші добровольці почали у такому довільному порядку:
6 5 1 3 7 8 4 2 - Ми поглянули на перші два числа та переставили їх, щоб вони були у правильному порядку:
5 6 1 3 7 8 4 2 - • Потім ми розглянули наступну пару чисел,
6та1, та переставили їх місцями:5 1 6 3 7 8 4 2 - Ми повторюємо цю дію, поки найбільше число після першого проходу не опиниться з правого боку в кінці рядка:
5 1 6 3 7 4 2 8- (У лекції, цифра 1 була випадково поставлена занадто далеко!)
- Ми повторюємо і щоразу, коли ми робимо один прохід, наступне найбільше число стає справа в кінці:
1 5 3 6 4 2 7 8 - Нарешті наш список повністю відсортований. Спочатку ми порівняли 7 пар чисел, потім – 6 пар.
- Ми повторно перемішали числа:
2 4 8 5 7 1 3 6 - І цього разу ми шукали найменше число в списку та переміщували його в лівий бік:
1 4 8 5 7 2 3 6 1 2 8 5 7 4 3 6 1 2 3 5 7 4 8 6- Щоразу ми обирали найменше число і переставляли його з числом, яке знаходиться зліва у невідсортованій частині списку.
- За допомогою цього алгоритму ми все ще проглядаємо список n - 1 разів, де n кількість людей, та нам потрібно порівняти кожне число, з найменшим.
- Давайте спробуємо розв’язати це формальніше. Перший алгоритм, сортування бульбашкою, складається з порівнювання пар чисел, що знаходяться безпосередньо одна біля одної, поки найбільше число буде знаходитися справа в кінці. Ми можемо це записати в псевдокоді:
повторити поки не залишиться пробілів для i від 0 до n-2 якщо i-ий та i+1-ий елементи не відсортовані поміняти їх місцями - А сортування вибором може виглядати ось так:
для i від 0 до n-1 знайти найменший елемент між i-им та n-1-им поміняти місцями найменший та i-ий елементи - Для першої перестановки нам потрібно зробити
n - 1порівнянь, щоб знайти найменше число. В кожному наступному проході ми зробили меншу кількість порівнянь, оскільки ми вже перемістили деякі цифри ліворуч:(n – 1) + (n – 2) + ... + 1 n(n – 1)/2 (n^2 – n)/2 n^2 / 2 – n/2- Кожен наступний рядок стає простіше, і врешті ми отримуємо
n^2 / 2 – n/2як кількість порівнянь, які треба виконати. В комп'ютерних науках ми використовуємо O, нотація велике O для більшого спрощення, щоб сказати, що наш алгоритм має O(n^2) кроків, “порядку n в квадраті”. Це через те, що з ростом n лише n^2 має значення. - Наприклад, якщо б n був 1,000,000, ми б отримали:
n^2 / 2 – n/2 1,000,000^2 / 2 – 1,000,000/2 500,000,000,000 – 500,000 499,999,500,000- що є того ж порядку, що й n2.
- Кожен наступний рядок стає простіше, і врешті ми отримуємо
- • Виявляється, що є інші поширені порядки величин складності:
- O(n2)
- O(n log n)
- O(n)
- O(log n)
- O(1)
- Пошук в телефонній книзі по одній сторінці за раз має тривалість роботи O(n), оскільки для кожної сторінки потрібна одна дія. Використання бінарного пошуку могло б мати тривалість роботи O(log n), оскільки ми б розділяли задачу навпіл щоразу.
- Давайте візьмемо інший масив чисел, але цього разу використаємо пустий масив такого ж розміру, як наш робочий:
4 2 7 5 6 8 3 1 _ _ _ _ _ _ _ _ - Оскільки у нас 8 чисел, давайте поглянемо на першу половину, тобто на перші 4. Відсортуємо це рекурсивно, подивимося на ліву половину. Маючи 2 числа,
4 2, дивимося на ліву половину (відсортовану), та праву (відсортовану), та об'єднаємо їх, відсортувавши:2 4. Ми перенесемо їх у наш другий масив:_ _ 7 5 6 8 3 1 2 4 _ _ _ _ _ _ - Повторимо це для правої частини першої половини:
_ _ | _ _ 6 8 3 1 2 4 | 5 7 _ _ _ _ - потім об'єднаємо ці половини, щоб отримати відсортовану ліву частину:
_ _ _ _ 6 8 3 1 _ _ _ _ _ _ _ _ 2 4 5 7 _ _ _ _ - Повторимо те саме для правої частини:
_ _ _ _ | _ _ _ _ _ _ _ _ | _ _ _ _ 2 4 5 7 | 1 3 6 8 - Тепер можемо об'єднати обидві половини:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 2 3 4 5 6 7 8 - Кожне число було переставлене тричі, через те що ми поділили 8 на 2 три рази, або log n раз. Тому цей алгоритм займає O(n log n) часу щоб відсортувати список.
- Розгляньте приклад Sorting Algorithms Animations та відео What different sorting algorithms sound like.