Skip to content

Latest commit

 

History

History
279 lines (198 loc) · 9.14 KB

README.md

File metadata and controls

279 lines (198 loc) · 9.14 KB
Raw

Упражнение 1

Въведение в курса

Защо са важни Структурите от данни и алгоритми?

  • Интервюта за работа, "whiteboard interviews"

    • Анализиране на проблем
    • Разработване на решение
    • Извличане на тестови сценарии
    • Тестване на решението
    • Оценка на решението

  • Придобиване на разбиране за това как са имплементирани готовите структури в езика, които използваме ежедневно. Така можем да оценим:

    • каква е тяхната очаквана производителност?
    • как скалират при нарастване на данните?

  • Развиване на способност за оценка на сложността на даден алгоритъм. Възможност за разграничаване на бързи и бавни решения на даден проблем.

Приложения в реалния свят:

  • Google Maps
  • Internet
  • Google, търсачки
  • ДНК

Как ще се провеждат домашните?

  • В платформата HackerRank.
  • Няколко задачи на домашно.
  • Предварително зададени тестови.
  • Автоматично оценяване на решения.
  • Неограничен брой опити за предаване на решение.
  • Получавате точки от най-високия резултат, получен от някое решение.
  • Дори решението да не покрива 100% от тестовете, получавате точките за тестовете, които покривате.
  • Автоматичните тестове не могат да се виждат преди да е приключило домашното.
  • Възможност за собствено тестване преди предаване.

Как се работи с Hackerrank?

Различните грешки при изпълнение на автоматичен тест:

  • Wrong Answer - Логическа грешка в алгоритъма.
  • Runtime error - Синтактична грешка в кода, възникване на изключение.
  • Terminated due to timeout - Бавен, неподходящ алгоритъм.
  • Memory limit - Изчерпване на паметта.
  • Abort called - Грешка от ниско ниво (C++ препълване на стека).

Особености на Python

Mutable и Immutable типове

Immutable обектите не позволяват промяна след създаването си. Python използва нова променлива при възникване на промяна с immutable обект.

n = 1
print(n) # 1
print("Id of the object:", id(n)) # 2076829352176

n += 2
print(n) # 3
print("Id of the object:", id(n)) # 2076829352240

Числата, низовете и кортежите (tuples) са immutable обекти.

t = 1, 2, 3
print(t) # (1, 2, 3)
print("Id of the object:", id(t)) # 2076910038656

t += 4, 5
print(t) # (1, 2, 3, 4, 5)
print("Id of the object:", id(t)) # 2076931006016
s = "abc"
print(s) # abc
print("Id of the object:", id(s)) # 2076834978160

s += "xyz"
print(s) # abcxyz
print("Id of the object:", id(s)) # 2076910065392

Mutable обектите позволяват промяна след създаването си. Python не използва нова променлива при възникване на промяна в mutable обект.

arr = [1, 2, 3]
print(arr) # [1, 2, 3]
print("Id of the object:", id(arr)) # 2076931496320

arr += [4, 5]
print(arr) # [1, 2, 3, 4, 5]
print("Id of the object:", id(arr)) # 2076931496320

Списъци, речници, множества (sets) са mutable обекти.

D = {6: 'Saturday', 7: 'Sunday'}
print(D) # {6: 'Saturday', 7: 'Sunday'}
print("Id of the object:", id(D)) # 2076931815552

D[7] = 'Воскресенье'
print(D) # {6: 'Saturday', 7: 'Воскресенье'}
print("Id of the object:", id(D)) # 2076931815552
A = {1, 1, 2, 3}
print(A) # {1, 2, 3}
print("Id of the object:", id(A)) # 2076910498784

A |= {1, 3, 4}
print(A) # {1, 2, 3, 4}
print("Id of the object:", id(A)) # 2076910498784

Подаване на обекти в Python

Промени по Immutable обекти не могат да бъдат запазени, тъй като се създава нова променлива. Промени извършени по Mutable обекти в функция се запазват, дори след напускане на функцията.

Подаване на число като аргумент на функция:

n = 1
print(n, id(n)) # 1 2076829352176

def f(n):
    n += 1
    print(n, id(n)) # 2 2076829352208

f(n)
print(n, id(n)) # 1 2076829352176

Подаване на масив като аргумент на функция:

arr = [1, 2, 3]
print(arr, id(arr)) # [1, 2, 3] 2076931627264

def func(arr):
    arr.append(4)
    print(arr, id(arr)) # [1, 2, 3, 4] 2076931627264

func(arr)
print(arr, id(arr)) # [1, 2, 3, 4] 2076931627264

Подаване на низ като аргумент на функция:

s = 'abc'
print(s, id(s)) # abc 2076834978160

def func(s):
    s += 'xyz'
    print(s, id(s)) # abcxyz 2076909883568

func(s)
print(s, id(s)) # abc 2076834978160

Bigint

От Python 3.0+ не съществува типът long. Всяко цяло число се представя чрез int класа.

a = 4
print(a) # 4
print(type(a)) # <class 'int'>
b = 2 ** 1024
print(b) # 179769313486231... (309 digits)
print(type(b))

Големината в байтове за обекти от тип int започва от 28 байта. С увеличаване на големината на число, Python заделя все повече памет за да го съхрани.

import sys

a = 4
print(sys.getsizeof(a)) # 28

b = 2 ** 1024
print(sys.getsizeof(b)) # 124

Това се случва автоматично до прехвърляне на лимита за големина на променлива - 9223372036854775807 байта, ~9,223,372 TB (за 64 битова машина). По-вероятно е изчерпването на паметта на машината, на която се изпълнява кода.

print(sys.maxsize) # 9223372036854775807 
from math import log10

c = (2 ** 1024) ** 100

print(log10(c)) # 30825.471555991677 (the digits of c)
print(sys.getsizeof(c)) # 13680 bytes, ~0.01368 MB

List comprehension

Компактен и бърз начин да създадем масив.

arr = [i for i in range(10) if i % 2 == 0]
print(arr) # [0, 2, 4, 6, 8]

Постига се същият ефект като използването на for-цикъл.

arr = []

for i in range(10):
    if i % 2 == 0:
        arr.append(i)

print(arr) # [0, 2, 4, 6, 8]

List comprehension-а се оказва до 30% по-бърз. Това е така, защото се интерпретира до C-код. Интепретаторът го превежда до поредица команди на езика C, които се изпълняват много по-ефективно от чист Python код.

List comprehension-a поддържа else-клауза:

arr = [i ** 2 if i % 2 == 0 else -(i ** 2) for i in range(10)]
print(arr) # [0, -1, 4, -9, 16, -25, 36, -49, 64, -81]

Позволя използването и на вложени цикли.

arr = [(i, j) for i in range(3) for j in 'XY']
print(arr) # [(0, 'X'), (0, 'Y'), (1, 'X'), (1, 'Y'), (2, 'X'), (2, 'Y')]

Global Interpreter Lock

  • механизъм, който не позволява изпълняването на две нишки код паралелно.
  • предотвратява race conditions и гарантира thread safety.
  • паралелизмът може да се постигне чрез multiprocessing.
  • някои външни библиотеки като Numpy могат да използват повече от едно ядро.

Всички снипети са налични в тетрадката.

Задачи за запознаване с платформата HackerRank

Решения на задачите: тук