جلسهی 14: مسیرها و پیشنهادها Paths and Suggestions
گراف جان میدهد برای دو سؤال که در جدول سختاند: «از من تا او چند قدم راه است؟» و «چه کسی یا چه چیزی را پیشنهاد کنم؟». با graph.path کوتاهترین زنجیرهی دوستی را میگیری، درجهی جدایی را میشماری، «کسانی که شاید بشناسی» را با شمردن دوستهای مشترک رتبهبندی میکنی و بازیای پیشنهاد میدهی که دوستهایت بازی میکنند.
در این جلسه یاد میگیری
- با
graph.pathکوتاهترین زنجیرهی دوستی بین دو نفر را میگیری وNoneرا درست جواب میدهی. - درجهی جدایی را با
len(path) - 1حساب میکنی. - دوستهای مشترک را با یک دیکشنری میشماری و «کسانی که شاید بشناسی» را با
sortedو یک کلید دوتایی رتبهبندی میکنی. - بازیای پیشنهاد میدهی که بیشترِ دوستهایت بازی میکنند و خودت نه.
درس
🔐 قانون طلایی این دوره: دادهی آدمها امانت است. پشت هر ردیف جدول یک آدم واقعی است: اسمش، کلاسش، کتابهایی که خوانده. دادهی کسی را بدون اجازه جمع نکن، به کسی نده و برای مسخره کردن یا سرک کشیدن به کار نبر. همهی دادههای این دوره ساختگیاند و هر بار که برنامه را اجرا میکنی از اول ساخته میشوند، پس هر چه میخواهی امتحان کن: چیزی خراب نمیشود.
🔁 یادت هست؟ در جلسهی ۱۳ «دوستِ دوست»ها را با دو حلقه پیدا کردیم: روی دوستهایم، و داخلش روی دوستهای آنها. خودم و دوستهای مستقیمم را کنار گذاشتیم و جوابها را در یک set جمع کردیم تا تکراری نشوند. امروز همین دو حلقه را میشماریم.
from db import graph
me = "Omid"
mine = graph.friends(me)
fof = set()
for f in mine:
for ff in graph.friends(f):
if ff != me and ff not in mine:
fof.add(ff)
print(sorted(fof))مسیر (path): graph.path("Sara", "Omid") کوتاهترین زنجیرهی دوستی از سارا تا امید را به شکل لیست میدهد: هر نفر دوستِ نفر بعدی است. اگر دو زنجیرهی هماندازه باشد، آن که به ترتیب الفبا جلوتر است انتخاب میشود، پس جواب همیشه یکی است. اگر اصلاً راهی نباشد (یا آن اسم در گراف نباشد) جواب None است، یعنی «هیچ». " -> ".join(path) زنجیره را قشنگ چاپ میکند.
from db import graph
path = graph.path("Sara", "Omid")
print(path)
print(" -> ".join(path))
print(graph.path("Sara", "Parisa"))درجهی جدایی یعنی چند قدم دوستی بین دو نفر است. دوست مستقیم ۱ قدم است، دوستِ دوست ۲ قدم. تعداد قدمها یکی کمتر از تعداد آدمهای مسیر است: len(path) - 1. میگویند هر دو نفر روی زمین با حدود شش قدم به هم وصلاند! اول بپرس if path is None: و بعد طول بگیر، چون len(None) خطا میدهد.
from db import graph
path = graph.path("Leila", "Ali")
if path is None:
print("no path")
else:
print(" -> ".join(path))
print("steps:", len(path) - 1)«کسانی که شاید بشناسی» در شبکههای اجتماعی اینطوری کار میکند: هر چه با کسی دوست مشترک بیشتری داشته باشی، احتمال اینکه او را بشناسی بیشتر است. همان دو حلقهی دوستِ دوست را میزنیم، ولی به جای set یک دیکشنری داریم که برای هر نفر میشمارد از چند راه پیدا شد: count[ff] = count.get(ff, 0) + 1. هر راه یعنی یک دوست مشترک.
from db import graph
graph.add_friend("Ali", "Kian")
me = "Sara"
mine = graph.friends(me)
count = {}
for f in mine:
for ff in graph.friends(f):
if ff != me and ff not in mine:
count[ff] = count.get(ff, 0) + 1
for p in sorted(count):
print(p, count[p])حالا رتبهبندی: بیشترین دوست مشترک اول، و اگر مساوی بودند به ترتیب الفبا. sorted(count, key=lambda p: (-count[p], p)) همین کار را میکند. key به sorted میگوید برای هر اسم p چه چیزی را مقایسه کند: اول -count[p] (منفی، تا عدد بزرگتر جلو بیاید) و اگر مساوی بود، خود اسم. ranked[:3] فقط سهتای اول لیست را میدهد (اگر کمتر باشد، همانقدر).
count = {"Yasmin": 2, "Reza": 1, "Kian": 2, "Omid": 1}
ranked = sorted(count, key=lambda p: (-count[p], p))
print(ranked)
print(ranked[:3])همین فکر برای پیشنهاد بازی هم کار میکند: روی دوستهایم و بازیهای هر کدام حلقه میزنم، بازیهایی را که خودم بازی میکنم کنار میگذارم، و میشمارم هر بازی را چند دوست بازی میکنند. پربازیترین (با شکستن تساوی به ترتیب الفبا) پیشنهاد من است. فروشگاهها و سایتهای فیلم هم کموبیش همین کار را میکنند.
from db import graph
me = "Reza"
count = {}
for f in graph.friends(me):
for g in graph.plays(f):
if g not in graph.plays(me):
count[g] = count.get(g, 0) + 1
print(count)اشتباه رایج: len(path) تعداد آدمهای مسیر است، نه تعداد قدمها. مسیر سارا تا علی ['Sara', 'Ali'] است: دو نفر، ولی یک قدم. پس قدمها len(path) - 1 است. اشتباه دوم: رتبهبندی فقط با تعداد (sorted(count, key=count.get, reverse=True)) وقتی دو نفر مساویاند، ترتیب را به این میسپارد که کدام زودتر شمرده شد، نه به الفبا؛ پس جواب ممکن است با چیزی که خواسته شده فرق کند.
from db import graph
path = graph.path("Sara", "Ali")
print(len(path), "people,", len(path) - 1, "step")مثالهای این جلسه
- مثال حلقه for (پایگاه داده با پایتون): for f in mine: — مسیرها و پیشنهادها
- مثال رشته (پایگاه داده با پایتون): print(" -> ".join(path))
- مثال شرط if (پایگاه داده با پایتون): if path is None:
- مثال دیکشنری (پایگاه داده با پایتون): count[ff] = count.get(ff, 0) + 1
- مثال دیکشنری (پایگاه داده با پایتون): count = {"Yasmin": 2, "Reza": 1, "Kian": 2,…
- مثال دیکشنری (پایگاه داده با پایتون): count[g] = count.get(g, 0) + 1
- مثال متغیر (پایگاه داده با پایتون): path = graph.path("Sara", "Ali")
چالشها
- Nima's Friends of Friends (آسان)
- From Sara to Reza (آسان)
- How Many Steps? (متوسط)
- Common Friends (متوسط)
- People You May Know (سخت)
- Suggest a Game (سخت)
بیشتر بخوان
- حلقه for در پایتون: آموزش کامل با range و مثال
- رشته در پایتون: آموزش کامل string با مثال و جدول متدها
- شرط if، elif و else در پایتون: آموزش کامل با مثال
- دیکشنری در پایتون: آموزش کامل کلید و مقدار با مثال
← جلسهی 13: گراف: کی کی را میشناسد؟ جلسهی 15: کدام پایگاه داده برای کدام کار؟ →