مسیرها
/
Factor
Factor
/
تمرین‌ها
/
آبدارخانه‌ی مسئول تدارکات
آبدارخانه‌ی مسئول تدارکات

آبدارخانه‌ی مسئول تدارکات

تمرین یادگیری

مقدمه

«جدول هش» در Factor یک آرایه‌ی انجمنی است؛ مجموعه‌ای از جفت‌های key/value با زمان جست‌وجوی O(1). جدول هش بخشی از خانواده‌ی بزرگ‌تر assocs است.

لیترال‌های جدول هش

H{ { "coal" 1 } { "wood" 2 } } .

H{ } یک جدول هش خالی است. جدول‌های هش تغییرپذیرند و با افزودن و حذف کلیدها بزرگ و کوچک می‌شوند؛ اگر می‌خواهید نسخه‌ی اصلی دست‌نخورده بماند، اول clone کنید. چاپ یک جدول هش، درایه‌هایش را نشان می‌دهد، اما ترتیبش به ترتیب درج وابسته نیست: جدول هش ترتیبی ندارد.

خواندن

at (در assocs) یک مقدار را می‌خواند و اگر کلید نبود، f را برمی‌گرداند:

at      ( key assoc -- value/f )
key?    ( key assoc -- ? )
"coal" H{ { "coal" 1 } { "wood" 2 } } at .   ! => 1
"gold" H{ { "coal" 1 } { "wood" 2 } } at .   ! => f

نوشتن

set-at اضافه یا بازنویسی می‌کند؛ delete-at حذف می‌کند؛ change-at یک قطعه‌کد را روی مقدار فعلی اجرا می‌کند. هر سه جدول را در جا تغییر می‌دهند:

set-at     ( value key assoc -- )
delete-at  ( key assoc -- )
change-at  ( key assoc quot: ( old -- new ) -- )
H{ } clone 5 "coal" pick set-at .
! => H{ { "coal" 5 } }

inc-at، میانبر شمارش

inc-at (که در assocs هم هست) به مقدار موجود برای یک کلید ۱ واحد اضافه می‌کند و اگر کلید نبود، آن را با مقدار ۱ درج می‌کند. برای شمارش، عالی است:

inc-at ( key assoc -- )
H{ } clone "coal" over inc-at .
! => H{ { "coal" 1 } }

پیمایش و درج تنبل

assoc-each روی همه‌ی جفت‌های ( key value -- ) حرکت می‌کند؛ cache مقدار یک کلید را برمی‌گرداند و اگر کلید نبود، آن را یک‌بار با قطعه‌کد داده‌شده محاسبه می‌کند.

assoc-each ( assoc quot: ( key value -- ) -- )
cache      ( key assoc quot: ( key -- value ) -- value )

cache الگوی «جست‌وجو یا ساختن» را در یک واژه خلاصه می‌کند؛ وقتی از جریانی از کلیدها جدول هش می‌سازید و نمی‌خواهید در هر نقطه‌ی فراخوانی حالت نبودن درایه را رسیدگی کنید، به کار می‌آید.

اعمال به‌روزرسانی جدول هش روی دنباله‌ای از کلیدها

وقتی ورودی دنباله‌ای از کلیدهاست و می‌خواهید جدول هش را برای هر کلید یک‌بار به‌روزرسانی کنید، روی خود دنباله با each پیمایش کنید و از یک قطعه‌کد سرخ‌شده به شکل '[ _ … ] (از fry) استفاده کنید تا جدول هش را در بدنه‌ی حلقه جای دهید. برای نمونه، حذف فهرستی از کلیدها:

{ "wood" "iron" } H{ { "coal" 5 } { "wood" 3 } { "iron" 2 } } clone
[ '[ _ delete-at ] each ] keep .
! => H{ { "coal" 5 } }

'[ _ delete-at ] جدول هشی را که بالاتر از آن روی پشته است در بر می‌گیرد، تا در هر تکرار each فقط کلید را بدهد. keep قطعه‌کد را اجرا می‌کند و در همان حال جدول هش را برای . نهایی نگه می‌دارد.

ساختن جدول هش از یک دنباله

map>assoc (در assocs) یک قطعه‌کد را روی یک دنباله اعمال می‌کند و نتایج ( elt -- key value ) را در یک assoc از نوع نمونه گرد می‌آورد:

map>assoc ( seq quot: ( elt -- key value ) exemplar -- assoc )
{ "wood" } [ dup length ] H{ } map>assoc .
! => H{ { "wood" 4 } }

کلیدها، مقدارها و جفت‌ها

keys و values (در assocs) فقط کلیدها یا فقط مقدارها را برمی‌گردانند؛ >alist جفت‌های { key value } را برمی‌گرداند.

keys   ( assoc -- keys )
values ( assoc -- values )
>alist ( assoc -- alist )
H{ { "wood" 11 } { "coal" 7 } } keys .     ! the keys (order not guaranteed)
H{ { "wood" 11 } { "coal" 7 } } values .   ! the matching values

keys و values هم‌ترازند: مقدار در یک جایگاه، به کلید در همان جایگاه تعلق دارد.

sort-keys (در sorting) جفت‌های { key value } را به‌ترتیب کلید برمی‌گرداند:

H{ { "wood" 11 } { "coal" 7 } } sort-keys .
! => { { "coal" 7 } { "wood" 11 } }

بازگشت از جفت‌ها به جدول هش

>hashtable (در hashtables) وارون >alist است: هر assoc را، که بیشتر وقت‌ها یک alist از جفت‌های { key value } است، به جدول هشی با جست‌وجوی O(1) تبدیل می‌کند.

>hashtable ( assoc -- hashtable )
{ { "coal" 7 } { "wood" 11 } } >hashtable .
! => H{ { "wood" 11 } { "coal" 7 } }   (entry order not guaranteed)

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

دستورالعمل‌ها

شما مسئول تدارکات کشتی هستید و موجودی انبار آذوقه را مدیریت می‌کنید. موجودی یک «هش‌تیبل» است که در آن هر کلید اسم یک قلم کالا و هر مقدار تعداد آن در انبار است.

1. ساختن موجودی از یک فهرست

create-inventory را طوری تعریف کنید که دنباله‌ای از اسم اقلام را بگیرد و یک هش‌تیبل برگرداند که هر اسم یکتا را با تعدادش جفت می‌کند.

{ "coal" "wood" "wood" "diamond" "diamond" "diamond" } create-inventory .
! => H{ { "coal" 1 } { "wood" 2 } { "diamond" 3 } }

2. افزودن اقلام بیشتر

add-items را طوری تعریف کنید که یک موجودی و دنباله‌ای از اقلام را بگیرد و موجودی تازه‌ای برگرداند که در آن تعداد هر قلمی که در فهرست آمده، افزایش یافته است. موجودی اصلی نباید تغییر کند.

H{ { "coal" 1 } } { "wood" "iron" "coal" "wood" } add-items .
! => H{ { "coal" 2 } { "wood" 2 } { "iron" 1 } }

3. کاهش تعدادها

decrement-items را طوری تعریف کنید که یک موجودی و دنباله‌ای از اقلام را بگیرد و موجودی تازه‌ای برگرداند که در آن تعداد هر قلمی که در فهرست آمده، یک واحد کاهش یافته است. تعدادها هرگز نباید به زیر صفر برسند و اقلامی که از قبل در موجودی نیستند باید نادیده گرفته شوند (هیچ ورودی منفی‌ای درج نمی‌شود).

H{ { "coal" 3 } { "diamond" 1 } { "iron" 5 } }
{ "diamond" "coal" "iron" "iron" } decrement-items .
! => H{ { "coal" 2 } { "diamond" 0 } { "iron" 3 } }

4. حذف کامل یک قلم

remove-item را طوری تعریف کنید که یک موجودی و یک قلم را بگیرد و موجودی تازه‌ای برگرداند که آن قلم از آن حذف شده است. اگر آن قلم در موجودی نباشد، یک نسخه‌ی بدون تغییر برگردانید.

H{ { "coal" 2 } { "wood" 1 } { "diamond" 2 } } "coal" remove-item .
! => H{ { "wood" 1 } { "diamond" 2 } }

5. فهرست کردن اقلام موجود

list-inventory را طوری تعریف کنید که یک موجودی را بگیرد و آرایه‌ای از جفت‌های { name quantity } برگرداند که فقط اقلامی را شامل می‌شود که مقدارشان بیشتر از صفر است و این جفت‌ها بر اساس اسم به ترتیب الفبا مرتب شده‌اند.

H{ { "coal" 7 } { "wood" 11 } { "diamond" 2 } { "iron" 7 } { "silver" 0 } }
list-inventory .
! => { { "coal" 7 } { "diamond" 2 } { "iron" 7 } { "wood" 11 } }
ویرایش از طریق GitHub این لینک در پنجره یا زبانه‌ی جدیدی باز می‌شود
Factor Exercism

آماده‌اید آبدارخانه‌ی مسئول تدارکات را شروع کنید؟

در Exercism ثبت‌نام کنید تا Factor را همراه با 47 مفهوم163 تمرین و مربی‌گری انسانی واقعی یاد بگیرید و در آن استاد شوید، همه‌ی این‌ها رایگان.