منابع ترجمه · Think Python · فصل ۱۰

دیکشنری‌ها (فصل ۱۰ Think Python)

۲۰ دقیقه مطالعه · به‌روزرسانی ۲ آبان ۱۴۰۵

منبع اصلی: Think Python, Chapter 10: Dictionaries — Allen B. Downey

💡 این صفحه مثل یک نوت‌بوک Jupyter است: متغیر و تابعی که در یک سلول تعریف شود، در سلول‌های بعدی همین صفحه در دسترس است. سلول‌ها را به ترتیب اجرا کنید، یا با «⏮ تا اینجا» همهٔ سلول‌های قبلیِ اجرانشده را یک‌جا اجرا کنید.

توضیح: خروجی‌های نمایش‌داده‌شده‌ی زیر کدها را با اجرای همین کدها (روی فایل words.txt کتاب) به دست آورده‌ام. زمان‌های اجرا به رایانه بستگی دارند؛ جمله‌های مربوط به زمان همان‌هایی هستند که نویسنده‌ی کتاب گزارش کرده است.

این فصل نوع داخلی‌ای به نام دیکشنری (dictionary) را معرفی می‌کند. این یکی از بهترین ویژگی‌های پایتون است – و بلوک سازنده‌ی بسیاری از الگوریتم‌های کارآمد و زیبا.

از دیکشنری‌ها برای محاسبه‌ی تعداد کلمه‌های یکتا در یک کتاب و تعداد دفعاتی که هر کدام ظاهر می‌شود استفاده می‌کنیم. و در تمرین‌ها از دیکشنری‌ها برای حل معماهای کلمه‌ای استفاده می‌کنیم.

۱۰.۱. دیکشنری یک نگاشت است

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

lst = ['zero', 'one', 'two']

می‌توانیم از یک عدد صحیح به‌عنوان اندیس برای گرفتن کلمه‌ی متناظر استفاده کنیم.

lst[1]

'one'

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

numbers = {}
numbers

{}

آکولادها، {}، یک دیکشنری تهی را نشان می‌دهند. برای افزودن مورد به دیکشنری، از کروشه استفاده می‌کنیم.

numbers['zero'] = 0

این نسبت‌دهی یک مورد (item) به دیکشنری اضافه می‌کند که ارتباط یک کلید (key) و یک مقدار (value) را نشان می‌دهد. در این مثال، کلید رشته‌ی 'zero' و مقدار عدد صحیح 0 است. اگر دیکشنری را نمایش دهیم، می‌بینیم یک مورد دارد که شامل یک کلید و یک مقدار است که با دو نقطه، :، از هم جدا شده‌اند.

numbers

{'zero': 0}

می‌توانیم موردهای بیشتری را این‌طور اضافه کنیم.

numbers['one'] = 1
numbers['two'] = 2
numbers

{'zero': 0, 'one': 1, 'two': 2}

اکنون دیکشنری سه مورد دارد.

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

numbers['two']

2

اگر کلید در دیکشنری نباشد، KeyError می‌گیریم.

numbers['three']

KeyError: 'three'

تابع len روی دیکشنری‌ها هم کار می‌کند؛ تعداد موردها را برمی‌گرداند.

len(numbers)

3

در زبان ریاضی، دیکشنری یک نگاشت (mapping) از کلیدها به مقدارها را نشان می‌دهد، پس می‌توانید بگویید هر کلید به یک مقدار «نگاشت می‌شود». در این مثال، هر کلمه‌ی عددی به عدد صحیح متناظرش نگاشت می‌شود.

شکل زیر نمودار وضعیت numbers را نشان می‌دهد.

(در کتاب اصلی اینجا نمودار رسم شده است: یک جعبه با کلمه‌ی «dict» بیرونش و سه مورد داخلش – هر کلید رشته‌ای با پیکانی به مقدار صحیح متناظر.)

دیکشنری با جعبه‌ای نشان داده می‌شود که کلمه‌ی «dict» بیرون آن و موردها داخل آن هستند. هر مورد با یک کلید و پیکانی که به یک مقدار اشاره می‌کند نمایش داده می‌شود. علامت‌های نقل‌قول نشان می‌دهند کلیدها در اینجا رشته‌اند، نه نام متغیر.

۱۰.۲. ساختن دیکشنری‌ها

در بخش قبل یک دیکشنری تهی ساختیم و موردها را یکی‌یکی با عملگر کروشه اضافه کردیم. به‌جای آن می‌توانستیم دیکشنری را یک‌جا این‌طور بسازیم.

numbers = {'zero': 0, 'one': 1, 'two': 2}

هر مورد از یک کلید و یک مقدار تشکیل شده که با دو نقطه از هم جدا می‌شوند. موردها با ویرگول از هم جدا و در آکولاد محصور می‌شوند.

راه دیگر برای ساختن دیکشنری استفاده از تابع dict است. می‌توانیم دیکشنری تهی را این‌طور بسازیم.

empty = dict()
empty

{}

و می‌توانیم از یک دیکشنری این‌طور کپی بگیریم.

numbers_copy = dict(numbers)
numbers_copy

{'zero': 0, 'one': 1, 'two': 2}

اغلب مفید است که قبل از انجام عملیاتی که دیکشنری‌ها را تغییر می‌دهند کپی بگیریم.

۱۰.۳. عملگر in

عملگر in روی دیکشنری‌ها هم کار می‌کند؛ به شما می‌گوید آیا چیزی به‌عنوان کلید در دیکشنری هست یا نه.

'one' in numbers

True

عملگر in بررسی نمی‌کند که چیزی به‌عنوان مقدار در دیکشنری هست یا نه.

1 in numbers

False

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

1 in numbers.values()

True

موردهای یک دیکشنری پایتون در یک جدول درهم‌سازی (hash table) ذخیره می‌شوند، که شیوه‌ای برای سازمان‌دهی داده‌هاست و ویژگی قابل‌توجهی دارد: عملگر in تقریباً همان‌قدر زمان می‌برد، مهم نیست چند مورد در دیکشنری باشد. این باعث می‌شود بتوانیم الگوریتم‌هایی فوق‌العاده کارآمد بنویسیم.

download('https://raw.githubusercontent.com/AllenDowney/ThinkPython/v3/words.txt');

برای نمایش، دو الگوریتم را برای پیدا کردن جفت کلمه‌هایی که یکی معکوس دیگری است – مثل stressed و desserts – مقایسه می‌کنیم. با خواندن فهرست کلمه‌ها شروع می‌کنیم.

word_list = open('words.txt').read().split()
len(word_list)

113783

و این reverse_word از فصل قبل است.

def reverse_word(word):
    return ''.join(reversed(word))

تابع زیر کلمه‌های فهرست را پیمایش می‌کند. برای هر کدام، حرف‌ها را معکوس می‌کند و بعد بررسی می‌کند که کلمه‌ی معکوس‌شده در فهرست کلمه‌ها هست یا نه.

def too_slow():
    count = 0
    for word in word_list:
        if reverse_word(word) in word_list:
            count += 1
    return count

اجرای این تابع بیش از یک دقیقه طول می‌کشد. مشکل این است که عملگر in کلمه‌های فهرست را یکی‌یکی، از ابتدا، بررسی می‌کند. اگر چیزی را که دنبالش می‌گردد پیدا نکند – که بیشتر اوقات این‌طور است – باید تا انتها جست‌وجو کند.

برای اندازه‌گیری مدت اجرای یک تابع، می‌توانیم از %time استفاده کنیم که یکی از «دستورهای جادویی داخلی» (built-in magic commands) Jupyter است. این دستورها بخشی از زبان پایتون نیستند، پس ممکن است در محیط‌های توسعه‌ی دیگر کار نکنند.

# %time too_slow()

و عملگر in داخل حلقه است، پس برای هر کلمه یک بار اجرا می‌شود. چون بیش از ۱۰۰٬۰۰۰ کلمه در فهرست هست و برای هر کدام بیش از ۱۰۰٬۰۰۰ کلمه را بررسی می‌کنیم، تعداد کل مقایسه‌ها – تقریباً – مجذور تعداد کلمه‌هاست، که نزدیک به ۱۳ میلیارد است.

len(word_list)**2

12946571089

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

word_dict = {}
for word in word_list:
    word_dict[word] = 1

مقدارهای word_dict همه 1 هستند، اما می‌توانند هر چیزی باشند، چون هیچ‌وقت جست‌وجویشان نمی‌کنیم – فقط از این دیکشنری برای بررسی اینکه یک کلید وجود دارد یا نه استفاده می‌کنیم.

حالا نسخه‌ای از تابع قبلی که word_list را با word_dict جایگزین می‌کند.

def much_faster():
    count = 0
    for word in word_dict:
        if reverse_word(word) in word_dict:
            count += 1
    return count

اجرای این تابع کمتر از یک صدم ثانیه طول می‌کشد، پس تقریباً ۱۰٬۰۰۰ برابر سریع‌تر از نسخه‌ی قبلی است.

به‌طور کلی، زمانی که پیدا کردن یک عنصر در فهرست طول می‌کشد متناسب با طول فهرست است. زمانی که پیدا کردن یک کلید در دیکشنری طول می‌کشد تقریباً ثابت است – صرف‌نظر از تعداد موردها.

%time much_faster()

885

(نتیجه‌ی تابع ۸۸۵ است، یعنی ۸۸۵ کلمه در فهرست هست که معکوسشان هم در فهرست است؛ هر جفت دوبار شمرده می‌شود و کلمه‌های متقارن هم یک بار حساب می‌شوند. خط مربوط به زمان در خروجی %time به رایانه‌ی شما بستگی دارد.)

۱۰.۴. مجموعه‌ای از شمارنده‌ها

فرض کنید رشته‌ای به شما داده می‌شود و می‌خواهید بشمارید هر حرف چند بار ظاهر می‌شود. دیکشنری ابزار خوبی برای این کار است. با یک دیکشنری تهی شروع می‌کنیم.

counter = {}

وقتی حرف‌های رشته را پیمایش می‌کنیم، فرض کنید حرف 'a' را برای اولین بار می‌بینیم. می‌توانیم آن را این‌طور به دیکشنری اضافه کنیم.

counter['a'] = 1

مقدار 1 نشان می‌دهد این حرف را یک بار دیده‌ایم. بعداً، اگر همان حرف را دوباره ببینیم، می‌توانیم شمارنده را این‌طور افزایش دهیم.

counter['a'] += 1

حالا مقدار وابسته به 'a' برابر 2 است، چون این حرف را دو بار دیده‌ایم.

counter

{'a': 2}

تابع زیر از این امکانات برای شمردن تعداد دفعاتی که هر حرف در یک رشته ظاهر می‌شود استفاده می‌کند.

def value_counts(string):
    counter = {}
    for letter in string:
        if letter not in counter:
            counter[letter] = 1
        else:
            counter[letter] += 1
    return counter

هر بار که حلقه تکرار می‌شود، اگر letter در دیکشنری نباشد، یک مورد جدید با کلید letter و مقدار 1 می‌سازیم. اگر letter از قبل در دیکشنری باشد، مقدار وابسته به letter را افزایش می‌دهیم.

این یک مثال است.

counter = value_counts('brontosaurus')
counter

{'b': 1, 'r': 2, 'o': 2, 'n': 1, 't': 1, 's': 2, 'a': 1, 'u': 2}

موردهای counter نشان می‌دهند حرف 'b' یک بار، 'r' دو بار و به همین ترتیب ظاهر می‌شود.

۱۰.۵. حلقه و دیکشنری‌ها

اگر از دیکشنری در یک دستور for استفاده کنید، کلیدهای دیکشنری را پیمایش می‌کند. برای نمایش، دیکشنری‌ای می‌سازیم که حرف‌های 'banana' را می‌شمارد.

counter = value_counts('banana')
counter

{'b': 1, 'a': 3, 'n': 2}

حلقه‌ی زیر کلیدها، یعنی حرف‌ها، را نمایش می‌دهد.

for key in counter:
    print(key)

b
a
n

برای نمایش مقدارها می‌توانیم از متد values استفاده کنیم.

for value in counter.values():
    print(value)

1
3
2

برای نمایش کلیدها و مقدارها، می‌توانیم کلیدها را پیمایش کنیم و مقدارهای متناظر را جست‌وجو کنیم.

for key in counter:
    value = counter[key]
    print(key, value)

b 1
a 3
n 2

در فصل بعد، راه مختصرتری برای انجام همین کار خواهیم دید.

۱۰.۶. فهرست‌ها و دیکشنری‌ها

می‌توانید یک فهرست را به‌عنوان مقدار در دیکشنری بگذارید. برای مثال، این دیکشنری‌ای است که عدد 4 را به فهرستی از چهار حرف نگاشت می‌کند.

d = {4: ['r', 'o', 'u', 's']}
d

{4: ['r', 'o', 'u', 's']}

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

letters = list('abcd')
d[letters] = 4

TypeError: unhashable type: 'list'

قبلاً گفتم که دیکشنری‌ها از جدول درهم‌سازی استفاده می‌کنند، و این یعنی کلیدها باید درهم‌پذیر (hashable) باشند.

درهم‌ساز (hash) تابعی است که مقداری (از هر نوع) را می‌گیرد و یک عدد صحیح برمی‌گرداند. دیکشنری‌ها از این عددهای صحیح، که مقدارهای درهم‌ساز (hash values) نامیده می‌شوند، برای ذخیره و جست‌وجوی کلیدها استفاده می‌کنند.

این سیستم فقط وقتی کار می‌کند که کلید تغییرناپذیر باشد، تا مقدار درهم‌سازش همیشه یکسان بماند. اما اگر کلید تغییرپذیر باشد، مقدار درهم‌سازش ممکن است تغییر کند و دیکشنری درست کار نکند. به همین دلیل کلیدها باید درهم‌پذیر باشند، و به همین دلیل نوع‌های تغییرپذیر مثل فهرست‌ها درهم‌پذیر نیستند.

چون دیکشنری‌ها تغییرپذیرند، به‌عنوان کلید هم نمی‌توانند استفاده شوند. اما می‌توانند به‌عنوان مقدار به کار روند.

۱۰.۷. انباشتن یک فهرست

در بسیاری از وظایف برنامه‌نویسی، مفید است که یک فهرست یا دیکشنری را پیمایش کنیم و همزمان فهرست دیگری بسازیم. به‌عنوان مثال، کلمه‌های word_dict را پیمایش می‌کنیم و فهرستی از کلمه‌های متقارن می‌سازیم – یعنی کلمه‌هایی که از جلو و عقب یک‌جور نوشته می‌شوند، مثل «noon» و «rotator».

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

def is_palindrome(word):
    """Check if a word is a palindrome."""
    return reverse_word(word) == word

اگر کلمه‌های word_dict را پیمایش کنیم، می‌توانیم تعداد کلمه‌های متقارن را این‌طور بشماریم.

count = 0

for word in word_dict:
    if is_palindrome(word):
        count +=1
        
count

91

تا الان این الگو آشناست.

• قبل از حلقه، count با 0 مقداردهی اولیه می‌شود.

• داخل حلقه، اگر word متقارن باشد، count را افزایش می‌دهیم.

• وقتی حلقه تمام می‌شود، count شامل تعداد کل کلمه‌های متقارن است.

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

palindromes = []

for word in word_dict:
    if is_palindrome(word):
        palindromes.append(word)

palindromes[:10]

['aa', 'aba', 'aga', 'aha', 'ala', 'alula', 'ama', 'ana', 'anna', 'ava']

این‌طور کار می‌کند:

• قبل از حلقه، palindromes با یک فهرست تهی مقداردهی اولیه می‌شود.

• داخل حلقه، اگر word متقارن باشد، آن را به انتهای palindromes اضافه می‌کنیم.

• وقتی حلقه تمام می‌شود، palindromes فهرستی از کلمه‌های متقارن است.

در این حلقه، palindromes به‌عنوان انباشتگر (accumulator) استفاده می‌شود، یعنی متغیری که در طول یک محاسبه داده را جمع یا انباشته می‌کند.

حالا فرض کنید می‌خواهیم فقط کلمه‌های متقارن با هفت حرف یا بیشتر را انتخاب کنیم. می‌توانیم palindromes را پیمایش کنیم و فهرست جدیدی بسازیم که فقط کلمه‌های متقارن بلند را دارد.

long_palindromes = []

for word in palindromes:
    if len(word) >= 7:
        long_palindromes.append(word)
        
long_palindromes

['deified', 'halalah', 'reifier', 'repaper', 'reviver', 'rotator', 'sememes']

پیمایش یک فهرست به این شکل، با انتخاب بعضی عنصرها و حذف بقیه، پالایش (filtering) نامیده می‌شود.

۱۰.۸. یادداشت‌ها (Memos)

اگر تابع fibonacci را از فصل ۶ اجرا کرده باشید، شاید متوجه شده باشید که هرچه آرگومان بزرگ‌تری بدهید، تابع زمان بیشتری برای اجرا لازم دارد.

def fibonacci(n):
    if n == 0:
        return 0
    
    if n == 1:
        return 1

    return fibonacci(n-1) + fibonacci(n-2)

علاوه بر این، زمان اجرا به‌سرعت افزایش می‌یابد. برای فهمیدن دلیلش، شکل زیر را در نظر بگیرید که گراف فراخوانی (call graph) تابع fibonacci را با n=4 نشان می‌دهد:

(در کتاب اصلی اینجا نمودار رسم شده است: درختی از قاب‌ها با n=4 در بالا؛ هر قاب n به قاب‌های n-1 و n-2 خط می‌کشد تا به n=1 و n=0 برسد.)

گراف فراخوانی مجموعه‌ای از قاب‌های تابع را نشان می‌دهد، با خط‌هایی که هر قاب را به قاب‌های توابعی که فراخوانی می‌کند وصل می‌کنند. در بالای گراف، fibonacci با n=4 توابع fibonacci با n=3 و n=2 را فراخوانی می‌کند. به نوبه‌ی خود، fibonacci با n=3 توابع fibonacci با n=2 و n=1 را فراخوانی می‌کند. و همین‌طور ادامه می‌یابد.

بشمارید fibonacci(0) و fibonacci(1) چند بار فراخوانی می‌شوند. این راه‌حلی ناکارآمد برای مسئله است و هرچه آرگومان بزرگ‌تر شود بدتر می‌شود.

یک راه‌حل این است که مقدارهایی را که از قبل محاسبه شده‌اند با ذخیره کردنشان در یک دیکشنری پیگیری کنیم. مقداری که قبلاً محاسبه شده و برای استفاده‌ی بعدی ذخیره می‌شود یادداشت (memo) نامیده می‌شود. این یک نسخه‌ی «یادداشت‌دار» (memoized) از fibonacci است:

known = {0:0, 1:1}

def fibonacci_memo(n):
    if n in known:
        return known[n]

    res = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    known[n] = res
    return res

known دیکشنری‌ای است که عددهای فیبوناچی را که از قبل می‌دانیم پیگیری می‌کند. با دو مورد شروع می‌شود: 0 به 0 و 1 به 1 نگاشت می‌شود.

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

با مقایسه‌ی این دو تابع، fibonacci(40) حدود ۳۰ ثانیه طول می‌کشد. fibonacci_memo(40) حدود ۳۰ میکروثانیه طول می‌کشد، پس یک میلیون برابر سریع‌تر است. در نوت‌بوک این فصل می‌بینید این اندازه‌گیری‌ها از کجا می‌آیند.

# %time fibonacci(40)

%time fibonacci_memo(40)

102334155

(مقدار بازگشتی fibonacci_memo(40) برابر 102334155 است؛ خط زمان اجرا در خروجی %time به رایانه‌ی شما بستگی دارد.)

۱۰.۹. اشکال‌زدایی

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

1. ورودی را کوچک کنید: اگر ممکن است، اندازه‌ی مجموعه‌داده را کم کنید. برای مثال اگر برنامه یک فایل متنی را می‌خواند، با فقط ۱۰ خط اول یا کوچک‌ترین نمونه‌ای که می‌توانید پیدا کنید شروع کنید. می‌توانید خود فایل‌ها را ویرایش کنید، یا (بهتر) برنامه را طوری تغییر دهید که فقط n خط اول را بخواند.

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

2. خلاصه‌ها و نوع‌ها را بررسی کنید: به‌جای نمایش و بررسی کل مجموعه‌داده، خلاصه‌های داده را نمایش دهید – برای مثال، تعداد موردهای یک دیکشنری یا مجموع فهرستی از عددها.

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

3. خودآزمون بنویسید: گاهی می‌توانید کدی بنویسید که خطاها را خودکار بررسی کند. برای مثال، اگر میانگین فهرستی از عددها را حساب می‌کنید، می‌توانید بررسی کنید که نتیجه از بزرگ‌ترین عنصر فهرست بزرگ‌تر یا از کوچک‌ترین عنصر کوچک‌تر نیست. این «بررسی سلامت عقل» (sanity check) نامیده می‌شود، چون نتیجه‌های «نامعقول» را تشخیص می‌دهد.

   نوع دیگری از بررسی، نتیجه‌های دو محاسبه‌ی متفاوت را مقایسه می‌کند تا ببیند سازگارند یا نه. این «بررسی سازگاری» (consistency check) نامیده می‌شود.

4. خروجی را قالب‌بندی کنید: قالب‌بندی خروجی اشکال‌زدایی می‌تواند تشخیص خطا را آسان‌تر کند. نمونه‌ای از این را در فصل ۶ دیدیم. ابزار دیگری که ممکن است مفید باشد ماژول pprint است که تابع pprint را فراهم می‌کند و نوع‌های داخلی را با قالبی خواناتر برای انسان نمایش می‌دهد (pprint مخفف «pretty print» به معنی «چاپ زیبا» است).

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

۱۰.۱۰. واژه‌نامه

دیکشنری (dictionary): شیئی که زوج‌های کلید-مقدار را در بر دارد که موردها (items) هم نامیده می‌شوند.

مورد (item): در دیکشنری، نام دیگر یک زوج کلید-مقدار.

کلید (key): شیئی که در دیکشنری به‌عنوان بخش اول یک زوج کلید-مقدار ظاهر می‌شود.

مقدار (value): شیئی که در دیکشنری به‌عنوان بخش دوم یک زوج کلید-مقدار ظاهر می‌شود. این دقیق‌تر از کاربرد قبلی ما از واژه‌ی «مقدار» است.

نگاشت (mapping): رابطه‌ای که در آن هر عنصر یک مجموعه با یک عنصر از مجموعه‌ی دیگر متناظر است.

جدول درهم‌سازی (hash table): مجموعه‌ای از زوج‌های کلید-مقدار که طوری سازمان‌دهی شده تا بتوانیم یک کلید را جست‌وجو کنیم و مقدارش را کارآمد پیدا کنیم.

درهم‌پذیر (hashable): نوع‌های تغییرناپذیر مثل عددهای صحیح، اعشاری و رشته‌ها درهم‌پذیرند. نوع‌های تغییرپذیر مثل فهرست‌ها و دیکشنری‌ها نیستند.

تابع درهم‌ساز (hash function): تابعی که یک شیء را می‌گیرد و عدد صحیحی محاسبه می‌کند که برای پیدا کردن مکان یک کلید در جدول درهم‌سازی به کار می‌رود.

انباشتگر (accumulator): متغیری که در یک حلقه برای جمع زدن یا انباشتن یک نتیجه به کار می‌رود.

پالایش (filtering): پیمایش یک دنباله و انتخاب یا حذف عنصرها.

گراف فراخوانی (call graph): نموداری که هر قابی را که در طول اجرای برنامه ساخته می‌شود نشان می‌دهد، با پیکانی از هر فراخواننده به هر فراخوانده.

یادداشت (memo): مقداری محاسبه‌شده که برای جلوگیری از محاسبه‌ی غیرضروری در آینده ذخیره می‌شود.

۱۰.۱۱. تمرین‌ها

# This cell tells Jupyter to provide detailed debugging information
# when a runtime error occurs. Run it before working on the exercises.

%xmode Verbose

۱۰.۱۱.۱. از یک دستیار مجازی بپرسید

در این فصل گفتم کلیدهای دیکشنری باید درهم‌پذیر باشند و توضیح کوتاهی دادم. اگر جزئیات بیشتری می‌خواهید، از یک دستیار مجازی بپرسید: «Why do keys in Python dictionaries have to be hashable?» (چرا کلیدهای دیکشنری‌های پایتون باید درهم‌پذیر باشند؟)

در بخش قبل فهرستی از کلمه‌ها را به‌عنوان کلید در یک دیکشنری ذخیره کردیم تا بتوانیم از نسخه‌ی کارآمد عملگر in استفاده کنیم. می‌توانستیم همین کار را با set هم بکنیم، که نوع داده‌ی داخلی دیگری است. از یک دستیار مجازی بپرسید: «How do I make a Python set from a list of strings and check whether a string is an element of the set?» (چطور از فهرستی از رشته‌ها یک مجموعه‌ی پایتون بسازم و بررسی کنم که رشته‌ای عضو مجموعه است؟)

۱۰.۱۱.۲. تمرین

دیکشنری‌ها متدی به نام get دارند که یک کلید و یک مقدار پیش‌فرض می‌گیرد. اگر کلید در دیکشنری باشد، get مقدار متناظر را برمی‌گرداند؛ در غیر این صورت مقدار پیش‌فرض را برمی‌گرداند. برای مثال، این دیکشنری‌ای است که حرف‌های یک رشته را به تعداد دفعاتی که ظاهر می‌شوند نگاشت می‌کند.

counter = value_counts('brontosaurus')

اگر حرفی را جست‌وجو کنیم که در کلمه هست، get تعداد دفعاتی را که ظاهر می‌شود برمی‌گرداند.

counter.get('b', 0)

1

اگر حرفی را جست‌وجو کنیم که ظاهر نمی‌شود، مقدار پیش‌فرض، یعنی 0، را می‌گیریم.

counter.get('c', 0)

0

از get برای نوشتن نسخه‌ی مختصرتری از value_counts استفاده کنید. باید بتوانید دستور if را حذف کنید.

۱۰.۱۱.۳. تمرین

طولانی‌ترین کلمه‌ای که می‌توانید فکر کنید و هر حرفش فقط یک بار ظاهر شود چیست؟ ببینیم می‌توانیم کلمه‌ای بلندتر از unpredictably پیدا کنیم.

تابعی به نام has_duplicates بنویسید که یک دنباله – مثل فهرست یا رشته – را به‌عنوان پارامتر بگیرد و اگر عنصری وجود دارد که بیش از یک بار در دنباله ظاهر می‌شود True برگرداند.

برای شروع، این یک طرح کلی از تابع با doctest است.

def has_duplicates(t):
    """Check whether any element in a sequence appears more than once.
    
    >>> has_duplicates('banana')
    True
    >>> has_duplicates('ambidextrously')
    False
    >>> has_duplicates([1, 2, 2])
    True
    >>> has_duplicates([1, 2, 3])
    False
    """
    return None

# Solution goes here

می‌توانید از doctest برای آزمودن تابع‌تان استفاده کنید.

from doctest import run_docstring_examples

def run_doctests(func):
    run_docstring_examples(func, globals(), name=func.__name__)

run_doctests(has_duplicates)

می‌توانید از این حلقه برای پیدا کردن طولانی‌ترین کلمه‌های بدون حرف تکراری استفاده کنید.

no_repeats = []

for word in word_list:
    if len(word) > 12 and not has_duplicates(word):
        no_repeats.append(word)
        
no_repeats

۱۰.۱۱.۴. تمرین

تابعی به نام find_repeats بنویسید که دیکشنری‌ای را بگیرد که هر کلید را به یک شمارنده نگاشت می‌کند، مثل نتیجه‌ی value_counts. باید دیکشنری را پیمایش کند و فهرستی از کلیدهایی که شمارشان بیشتر از 1 است برگرداند. می‌توانید از طرح کلی زیر برای شروع استفاده کنید.

def find_repeats(counter):
    """Makes a list of keys with values greater than 1.
    
    counter: dictionary that maps from keys to counts
    
    returns: list of keys
    """
    return []

# Solution goes here

می‌توانید از مثال‌های زیر برای آزمودن کدتان استفاده کنید. اول، دیکشنری‌ای می‌سازیم که حرف‌ها را به شمارش‌ها نگاشت می‌کند.

counter1 = value_counts('banana')
counter1

{'b': 1, 'a': 3, 'n': 2}

نتیجه‌ی find_repeats باید ['a', 'n'] باشد.

repeats = find_repeats(counter1)
repeats

در اینجا مثال دیگری است که با فهرستی از عددها شروع می‌شود. نتیجه باید [1, 2] باشد.

counter1 = value_counts([1, 2, 3, 2, 1])
repeats = find_repeats(counter1)
repeats

۱۰.۱۱.۵. تمرین

فرض کنید value_counts را با دو کلمه‌ی متفاوت اجرا می‌کنید و نتیجه‌ها را در دو دیکشنری ذخیره می‌کنید.

counter1 = value_counts('brontosaurus')
counter2 = value_counts('apatosaurus')

هر دیکشنری مجموعه‌ای از حرف‌ها را به تعداد دفعاتی که ظاهر می‌شوند نگاشت می‌کند. تابعی به نام add_counters بنویسید که دو دیکشنری از این نوع را بگیرد و دیکشنری جدیدی برگرداند که همه‌ی حرف‌ها و مجموع دفعاتی را که در هر یک از دو کلمه ظاهر می‌شوند دارد.

راه‌های زیادی برای حل این مسئله وجود دارد. وقتی راه‌حل کارآمدی داشتید، از یک دستیار مجازی بخواهید راه‌حل‌های متفاوتی ارائه دهد.

# Solution goes here

# Solution goes here

۱۰.۱۱.۶. تمرین

کلمه‌ای «درهم‌تنیده» (interlocking) است اگر بتوانیم با برداشتن حرف‌های متناوب آن را به دو کلمه تقسیم کنیم. برای مثال، «schooled» کلمه‌ای درهم‌تنیده است چون می‌توان آن را به «shoe» و «cold» تقسیم کرد.

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

در برش زیر، مؤلفه‌ی اول 0 است، پس از حرف اول شروع می‌کنیم. مؤلفه‌ی دوم None است، که یعنی تا انتهای رشته برویم. و مؤلفه‌ی سوم 2 است، پس بین حرف‌هایی که انتخاب می‌کنیم دو گام فاصله هست.

word = 'schooled'
first = word[0:None:2]
first

'shoe'

به‌جای دادن None به‌عنوان مؤلفه‌ی دوم، می‌توانیم با حذف کامل آن همین اثر را بگیریم. برای مثال، برش زیر حرف‌های متناوب را، با شروع از حرف دوم، انتخاب می‌کند.

second = word[1::2]
second

'cold'

تابعی به نام is_interlocking بنویسید که یک کلمه را به‌عنوان آرگومان بگیرد و اگر بتوان آن را به دو کلمه‌ی درهم‌تنیده تقسیم کرد True برگرداند.

# Solution goes here

می‌توانید از حلقه‌ی زیر برای پیدا کردن کلمه‌های درهم‌تنیده‌ی فهرست کلمه‌ها استفاده کنید.

for word in word_list:
    if len(word) >= 8 and is_interlocking(word):
        first = word[0::2]
        second = word[1::2]
        print(word, first, second)