الگوریتم‌های لیست

۱. مجموع و میانگین با دست

# Adding every item of a list, the manual way.
numbers = [200, 350, 40, 1000, 270]

total = 0
for number in numbers:
    total = total + number
    # short form: total += number

print('Total:', total)
print('Average:', total / len(numbers))

مجموع و میانگین: نمونه 01_sum_of_list.py

Total: 1860
Average: 372.0

همان الگوی انباره فصل ششم، این بار روی لیست به جای range. این الگو پایه همه الگوریتم‌های این فصل است.

۲. پیدا کردن بیشینه

منطقش شبیه مسابقه است: عضو اول را «قهرمان فعلی» فرض می‌کنیم و بقیه را یکی‌یکی با او مقایسه می‌کنیم. هر کس بهتر بود، قهرمان تازه می‌شود.

# Finding the biggest item.
# The trick: start with the FIRST item as the current champion,
# then compare it with every other item.
numbers = [30, 20, 45, 18, -7, 22]

largest = numbers[0]

for number in numbers:
    if number > largest:
        largest = number

print('Max:', largest)

# Starting from 0 instead of numbers[0] would be a bug:
# with a list of only negative numbers the answer would wrongly be 0.

بیشینه: نمونه 02_max_of_list.py

۳. پیدا کردن کمینه

# Same algorithm, with the comparison turned around.
numbers = [30, 20, 45, 18, -7, 22]

smallest = numbers[0]

for number in numbers:
    if number < smallest:
        smallest = number

print('Min:', smallest)

کمینه: نمونه 03_min_of_list.py

تنها تفاوت، جهت علامت مقایسه است. اگر بخواهید جایگاه کوچک‌ترین را هم بدانید، باید با اندیس کار کنید و در کنار مقدار، اندیسش را هم نگه دارید.

۴. میانگین با شرط

# Average of the even numbers only: we need a total AND a counter,
# because we do not know in advance how many even numbers there are.
numbers = [30, 20, 45, 18, -7, 22]

total = 0
counter = 0

for number in numbers:
    if number % 2 == 0:
        total += number
        counter += 1

# Guard against a list without any even number.
if counter == 0:
    print('There is no even number in the list.')
else:
    print('Average of the even numbers:', total / counter)

میانگین اعداد زوج: نمونه 04_average_of_evens.py

وقتی شرط دارید، دیگر نمی‌توانید بر len(numbers) تقسیم کنید، چون طول کل لیست با تعداد اعضایی که شرط را دارند فرق می‌کند. پس شمارنده جداگانه لازم است. و باز هم بررسی صفر بودن شمارنده.

۵. توابع آماده پایتون

حالا که الگوریتم‌ها را با دست نوشتید، خبر خوب: پایتون همه‌شان را از قبل دارد.

# Python already knows how to do all of that. Use the built-in functions:
# they are shorter, faster and impossible to get wrong.
numbers = [30, 20, 45, 18, -7, 22]

print('len:', len(numbers))
print('sum:', sum(numbers))
print('max:', max(numbers))
print('min:', min(numbers))
print('avg:', sum(numbers) / len(numbers))

# They work on strings too.
words = ['pear', 'apple', 'banana']
print(max(words))            # the last one in alphabetical order
print(min(words, key=len))   # the shortest word

توابع آماده: نمونه 05_builtin_functions.py

پارامتر key خیلی قدرتمند است: می‌گوید «مقایسه را بر اساس این معیار انجام بده». min(words, key=len) یعنی کوتاه‌ترین کلمه، نه کلمه‌ای که در الفبا اول است. در فصل بیست و ششم به این پارامتر برمی‌گردیم و کاملش می‌کنیم.

۶. جست‌وجوی خطی

# Linear search: walk through the list until the value is found.
numbers = [30, 20, 45, 18, -7, 22]

target = int(input('Which number are you looking for? '))

found_at = -1                     # -1 means "not found yet"

for i in range(len(numbers)):
    if numbers[i] == target:
        found_at = i
        break                     # stop at the first match

if found_at == -1:
    print('Not found.')
else:
    print(f'Found at index {found_at}.')

# Python offers the same thing directly:
if target in numbers:
    print('index() says:', numbers.index(target))

جست‌وجوی خطی: نمونه 06_search.py

شرح مثال

• متغیر found_at با منفی یک شروع می‌شود، یعنی «هنوز پیدا نشده». چون منفی یک نمی‌تواند نتیجه واقعی جست‌وجو باشد، به عنوان علامت مناسب است.
• break بعد از پیدا شدن، از ادامه بی‌فایده جلوگیری می‌کند.
• اینجا از پیمایش با اندیس استفاده شده، چون به جایگاه نیاز داریم نه فقط مقدار.
• راه آماده پایتون همان in و index است که در فصل قبل دیدیم. باز هم اول in، چون index روی مقدار ناموجود خطا ایجاد می‌کند.

۷. مرتب‌سازی

numbers = [30, 20, 45, 18, -7, 22]

# sorted() returns a NEW sorted list and leaves the original alone.
ordered = sorted(numbers)
print('sorted():', ordered)
print('original:', numbers)

# sort() sorts the list IN PLACE and returns None.
numbers.sort()
print('after sort():', numbers)

# Descending order.
numbers.sort(reverse=True)
print('descending:', numbers)

# reverse() just turns the list around, it does not sort.
numbers.reverse()
print('reversed:', numbers)

# Sorting text.
names = ['Reza', 'ali', 'Maryam']
print(sorted(names))                    # capitals come first
print(sorted(names, key=str.lower))     # case-insensitive order

مرتب‌سازی: نمونه 07_sorting.py

درباره مرتب‌سازی متن: حروف بزرگ در جدول کاراکترها پیش از حروف کوچک می‌آیند، پس 'Reza' پیش از 'ali' قرار می‌گیرد. با key=str.lower این مشکل حل می‌شود.

۸. دام سایه‌اندازی نام

در فصل ششم به این اشاره کردیم؛ حالا که واقعاً از sum و max استفاده می‌کنیم، وقتش رسیده که کامل ببینیمش.

# 'sum', 'max', 'min', 'list', 'str', 'input' ... are names of built-in things.
# If you use them as variable names, the built-in version disappears.
numbers = [1, 2, 3]

sum = 0                 # BAD: the built-in function sum() is now hidden
for n in numbers:
    sum += n
print(sum)              # works ...

# ... but now this line would raise:
#   TypeError: 'int' object is not callable
# print(sum(numbers))

# Always prefer a descriptive name instead:
total = 0
for n in numbers:
    total += n
print(total)
print(sum)              # still the integer, the damage is done in this file

سایه‌اندازی: نمونه 08_shadowing_trap.py

نکته مهم: پایتون هیچ خطایی نمی‌دهد و اجازه می‌دهد این کار را بکنید. مشکل بعداً و در جای دیگری از برنامه ظاهر می‌شود، جایی که تازه‌کار به هیچ وجه دنبال علتش نمی‌گردد. ویرایشگرهای خوب مثل VS Code این نام‌ها را رنگ متفاوتی می‌دهند؛ اگر متغیرتان همان رنگ توابع آماده شد، نامش را عوض کنید.

۹. لیست دوبعدی

عضو یک لیست می‌تواند خودش لیست باشد. به این ساختار ماتریس یا لیست دوبعدی می‌گویند و برای جدول، صفحه بازی و تصویر به کار می‌رود.

# A list whose items are themselves lists is a 2-D list (a matrix).
matrix = [
    [4, 17, 81],
    [11, 41, 17],
    [20, 12, 13],
]

# Two indexes: first the row, then the column.
print(matrix[1][1])      # 41
print(matrix[0])         # the whole first row

# A new row can be appended like any other item.
matrix.append([4, 5, 6])

# Printing a matrix needs two loops.
for row in matrix:
    for value in row:
        print(value, end='\t')
    print()

ماتریس: نمونه 09_two_dimensional_list.py

41
[4, 17, 81]
4	17	81	
11	41	17	
20	12	13	
4	5	6	

شرح مثال

• matrix[1][1] را از چپ بخوانید: اول سطر شماره ۱ را بگیر، بعد از آن سطر، عضو شماره ۱ را بردار.
• ترتیب همیشه سطر و بعد ستون است. جابه‌جا کردنشان، خطای رایج ماتریس‌هاست.
• چاپ ماتریس دقیقاً همان حلقه تودرتوی فصل هفتم است. تنها فرق این است که به جای ستاره، مقدار خانه چاپ می‌شود.
• ویرگول بعد از آخرین سطر (آن ویرگول انتهایی) اجباری نیست ولی مجاز است و عادت خوبی است: افزودن سطر بعدی، فقط یک خط تغییر می‌شود.

۱۰. عملیات روی ماتریس

# Classic operations on a square matrix.
matrix = [
    [4, 17, 81],
    [11, 41, 17],
    [20, 12, 13],
]

SIZE = len(matrix)

# Total of every row.
for i in range(SIZE):
    print(f'sum of row {i}:', sum(matrix[i]))

# Total of every column: the column index stays fixed while the row moves.
for column in range(SIZE):
    column_total = 0
    for row in range(SIZE):
        column_total += matrix[row][column]
    print(f'sum of column {column}:', column_total)

# The main diagonal is made of the items where row == column.
diagonal_total = 0
for i in range(SIZE):
    diagonal_total += matrix[i][i]
print('sum of the diagonal:', diagonal_total)

# The biggest value of the whole matrix.
largest = matrix[0][0]
for row in matrix:
    for value in row:
        if value > largest:
            largest = value
print('largest value:', largest)

عملیات ماتریسی: نمونه 10_matrix_operations.py

شرح مثال

• جمع سطر ساده است: هر سطر خودش یک لیست است، پس sum(matrix[i]) کافی است.
• جمع ستون سخت‌تر است، چون ستون یک لیست جدا نیست. باید اندیس ستون را ثابت نگه دارید و اندیس سطر را حرکت دهید: matrix[row][column].
• قطر اصلی خانه‌هایی است که شماره سطر و ستونشان برابر است، پس یک حلقه ساده کافی است.
• برای بیشینه کل ماتریس، حلقه تودرتو لازم است و نقطه شروع matrix[0][0] است، به همان دلیلی که در بخش دوم گفتیم.

۱۱. برنامه کامل گزارش‌گیری

# A complete little program: read numbers until 'exit',
# then report several statistics about them.
numbers = []

while True:
    user_input = input('Enter a number (or "exit"): ')

    if user_input == 'exit':
        break

    numbers.append(float(user_input))

if len(numbers) == 0:
    print('Nothing to report.')
else:
    even_total = 0
    for number in numbers:
        if number % 2 == 0:
            even_total += number

    print('Count:  ', len(numbers))
    print('Sum:    ', sum(numbers))
    print('Average:', sum(numbers) / len(numbers))
    print('Max:    ', max(numbers))
    print('Min:    ', min(numbers))
    print('Sum of the even ones:', even_total)
    print('Sorted: ', sorted(numbers))

گزارش کامل: نمونه 11_sum_of_positive_input.py

این برنامه پایان بخش اول دوره است و همه چیزهایی که تا اینجا خواندید را در خود دارد: ورودی، حلقه، شرط، لیست، توابع آماده و مراقبت از حالت خالی. از فصل بعد یاد می‌گیریم چطور همین کد را به تکه‌های کوچک و قابل استفاده مجدد تقسیم کنیم.

خلاصه فصل