Channel: بنیاد پایتون کاران فارسی
Why must "self" always be passed in as parameter, why wasn't it made a built-in?
چرا self باید همیشه به عنوان یک پارامتر به متدهایمان پاس داده بشه؟!
نمیشه که self رو built-in کنیم؟
https://www.reddit.com/r/Python/comments/y8ofb6/honest_question_why_must_self_always_be_passed_in/
چرا self باید همیشه به عنوان یک پارامتر به متدهایمان پاس داده بشه؟!
نمیشه که self رو built-in کنیم؟
https://www.reddit.com/r/Python/comments/y8ofb6/honest_question_why_must_self_always_be_passed_in/
Reddit
r/Python on Reddit: Honest question: Why must "self" always be passed in as parameter, why wasn't it made a built-in?
Posted by u/lemon_bottle - 461 votes and 145 comments
Kernl
Kernl lets you run Pytorch transformer models several times faster on GPU with a single line of code, and is designed to be easily hackable.
Github: https://github.com/ELS-RD/kernl
🆔 @PsFarsi
Kernl lets you run Pytorch transformer models several times faster on GPU with a single line of code, and is designed to be easily hackable.
Github: https://github.com/ELS-RD/kernl
🆔 @PsFarsi
پایتون 3.12 از ابزار perf در سیستم عامل لینوکس به عنوان یک mini JIT استفاده خواهد کرد و سرعت آن بالاتر خواهد رفت 😁🤟
اول این رشته توییت رو بخونید
https://telegra.ph/a-Twitter-thread-from-pyblogsal-11-01
و برای فهمیدن چگونگیش
https://docs.python.org/pl/dev/howto/perf_profiling.html
این رو بخونید.
@PsFarsi
اول این رشته توییت رو بخونید
https://telegra.ph/a-Twitter-thread-from-pyblogsal-11-01
و برای فهمیدن چگونگیش
https://docs.python.org/pl/dev/howto/perf_profiling.html
این رو بخونید.
@PsFarsi
Telegraph
a Twitter thread from @pyblogsal
1. Python 3.12 will add support for the Linux perf profiler! 🔥🔥 Perf is one of the most powerful and performant profilers for Linux that allows getting a ridiculous amount of information such as CPU counters, cache misses, context switching and much more.…
هر دم از این باغ بری میرسد 😍🤟
یک #رشتو از آقای آنتونی شاو (twitter) @anthonypjshaw در مورد یکی از ایدههای سرعت بخشیدن به پایتون 3.12
ایشون کمی در مورد تغییر نحوهی ذخیرهی instructions از stack به cpu registers صحبت میکنن =)
https://telegra.ph/a-Twitter-thread-from-anthonypjshaw-11-03
@PsFarsi
یک #رشتو از آقای آنتونی شاو (twitter) @anthonypjshaw در مورد یکی از ایدههای سرعت بخشیدن به پایتون 3.12
ایشون کمی در مورد تغییر نحوهی ذخیرهی instructions از stack به cpu registers صحبت میکنن =)
https://telegra.ph/a-Twitter-thread-from-anthonypjshaw-11-03
@PsFarsi
Telegraph
a Twitter thread from @anthonypjshaw
1. Getting up to speed with the Python 3.12 ideas from the Faster CPython team. One that’s been thrown around is a CPU register allocator in the eval loop. Currently, Python opcodes use a “stack” to store and load objects between instructions 1/ 2. The proposal…
سیستم عامل ایرانی پای ابر ۳ منتشر شد
🔻 نگارش ۳ با تغییراتی اساسی:
✔️ برداشتن محدودیت جعبه شنی
✔️ آسان سازی توسعه
✔️ بروزرسانی بسته های لینوکسی
✔️ رفع باگ های بزرگ نگارش های پیشین
✔️ افزایش سازگاری با استاندارد های لینوکس
✔️ افزایش امکانات ابری نظیر اعلان ها، فایل ها، مدیریت برنامه ها و ... (به صورت ابری)
🔻 دریافت پای ابر
🔰 پای ابر ۶۴ بیتی
🔰 پای ابر ۳۲ بیتی
🔰 @PSFarsi
🔰 @PyFarsi
🔻 نگارش ۳ با تغییراتی اساسی:
✔️ برداشتن محدودیت جعبه شنی
✔️ آسان سازی توسعه
✔️ بروزرسانی بسته های لینوکسی
✔️ رفع باگ های بزرگ نگارش های پیشین
✔️ افزایش سازگاری با استاندارد های لینوکس
✔️ افزایش امکانات ابری نظیر اعلان ها، فایل ها، مدیریت برنامه ها و ... (به صورت ابری)
🔻 دریافت پای ابر
🔰 پای ابر ۶۴ بیتی
🔰 پای ابر ۳۲ بیتی
🔰 @PSFarsi
🔰 @PyFarsi
This media is not supported in your browser
VIEW IN TELEGRAM
🔰 ارسال ایمیل تبلیغاتی/ همگانی با پایتون
➕ قبلا به صورت گرافیکی با PyQt5 زده بودم و در چنل قرار دادم.
➕ این کد به صورت کامندی و با چند کد خط ساده نوشته شده.
💠 Language: Python
آدرس گپ :
🔰 hottg.com/PyFarsi
آدرس کانال :
🔰@PSFarsi
➕ قبلا به صورت گرافیکی با PyQt5 زده بودم و در چنل قرار دادم.
➕ این کد به صورت کامندی و با چند کد خط ساده نوشته شده.
💠 Language: Python
آدرس گپ :
🔰 hottg.com/PyFarsi
آدرس کانال :
🔰@PSFarsi
Reloadium: Advanced Hot Reloading & Profiling
• Reloadium adds hot reloading and profiling features to any Python application
📌How to install:
>>>
📌How to use:
>>>
✅ Supports:
° Django
° Flask
° Sqlalchemy
° Pandas
✔️Github: https://github.com/reloadware/reloadium
• Reloadium adds hot reloading and profiling features to any Python application
📌How to install:
>>>
pip install reloadium
📌How to use:
>>>
reloadium run example.py
✅ Supports:
° Django
° Flask
° Sqlalchemy
° Pandas
✔️Github: https://github.com/reloadware/reloadium
بنیاد پایتون کاران فارسی
We are waiting for you dear ☺️ @PyFarsi
What’s New In Python 3.12
This article explains the new features in Python 3.12, compared to 3.11.
https://docs.python.org/dev/whatsnew/3.12.html
@PyFarsi
This article explains the new features in Python 3.12, compared to 3.11.
https://docs.python.org/dev/whatsnew/3.12.html
@PyFarsi
Github Codespaces
Overview :
What is a codespace? A codespace is a development environment that's hosted in the cloud. You can customize your project for GitHub Codespaces by committing configuration files to your repository (often known as Configuration-as-Code), which creates a repeatable codespace configuration for all users of your project.
Link: https://github.com/codespaces
🆔 @PSFarsi
Overview :
What is a codespace? A codespace is a development environment that's hosted in the cloud. You can customize your project for GitHub Codespaces by committing configuration files to your repository (often known as Configuration-as-Code), which creates a repeatable codespace configuration for all users of your project.
Link: https://github.com/codespaces
🆔 @PSFarsi
دوره آموزشی ساخت ربات api و cli با زبان پایتون و کتابخونه Pyrogram | آپدیت شماره یک
دریافت ورودی از کاربر از طریق روش Step Step
نحوه تشخیص اسپم به روش اول
حتما حتما لایک و کامنت فراموش نشه
چنل مارو سابسکرایب کنید 😉
امیدوارم لذت کافی رو از این دوره ببرین 🌹
لینک ویدیو در یوتیوب:
🔰 youtu.be/I8KDdvwHnNA
آدرس گپ :
🔰 hottg.com/PyFarsi
آدرس کانال :
🔰@PSFarsi
دریافت ورودی از کاربر از طریق روش Step Step
نحوه تشخیص اسپم به روش اول
حتما حتما لایک و کامنت فراموش نشه
چنل مارو سابسکرایب کنید 😉
امیدوارم لذت کافی رو از این دوره ببرین 🌹
لینک ویدیو در یوتیوب:
🔰 youtu.be/I8KDdvwHnNA
آدرس گپ :
🔰 hottg.com/PyFarsi
آدرس کانال :
🔰@PSFarsi
بنیاد پایتون کاران فارسی
✔️ سوال خروجی چیست؟ 1) NameError: name 'e' does not exists 2) 10 3) ZeroDivisionError() چرا؟ 😁
جواب:
تو حالت های دیگه مثلا زمانی که از context manager استفاده میکنیم دستور as درواقع همون کار assignment رو انجام میده. مثلا:
ولی اگه این اتفاق توی exception ها هم بیفته مشکل ساز میشه. آبجکت exception داخل خودش یه traceback آبجکتی داره که حاوی اطلاعاتی از exception ما هست. مثلا خود این traceback آبجکت یه رفرنس داره به frame ای که توش exception رخ داده و اون frame هم رفرنس داره به تمام متغیر های لوکال اون scope از جمله؟ e !
e -> traceback -> frame -> e
پس یک circular reference ایجاد میشه:
تو این مثال پایین ما میخوایم از قصد یک رفرنس ایجاد کنیم به e تا زنده بمونه، انگار که همچین مکانیزمی نداشته پایتون. ببینید چه اتفاقی میفته: (فرض کنید obj یک آبجکت خیلی بزرگ هست)
@AmirSoroushh✍️
تو حالت های دیگه مثلا زمانی که از context manager استفاده میکنیم دستور as درواقع همون کار assignment رو انجام میده. مثلا:
e = 10
with open("text.txt") as e:
pass
print(e)
اینجا دیگه e اشاره میکنه به فایل باز شده.ولی اگه این اتفاق توی exception ها هم بیفته مشکل ساز میشه. آبجکت exception داخل خودش یه traceback آبجکتی داره که حاوی اطلاعاتی از exception ما هست. مثلا خود این traceback آبجکت یه رفرنس داره به frame ای که توش exception رخ داده و اون frame هم رفرنس داره به تمام متغیر های لوکال اون scope از جمله؟ e !
e -> traceback -> frame -> e
پس یک circular reference ایجاد میشه:
e = 10
try:
raise ZeroDivisionError("hiiiii")
except ZeroDivisionError as e:
print(e is e.__traceback__.tb_frame.f_locals["e"])
در نتیجه پایتون میاد بعد از اینکه بلاک except تموم شد اون اسمی که اشاره میکرد به آبجکت exception یعنی e رو پاک میکنه از namespace.تو این مثال پایین ما میخوایم از قصد یک رفرنس ایجاد کنیم به e تا زنده بمونه، انگار که همچین مکانیزمی نداشته پایتون. ببینید چه اتفاقی میفته: (فرض کنید obj یک آبجکت خیلی بزرگ هست)
class A:فانکشن تموم شده، obj فقط داخل فانکشن ساخته شده بوده باید رفرنسش صفر میشد و از بین میرفت ولی نرفت...
def __del__(self) -> None:
print("object is deleted")
def fn():
obj = A()
exc = None
try:
raise ZeroDivisionError()
except ZeroDivisionError as e:
exc = e
fn()
print("Object is still alive!")
input()
@AmirSoroushh✍️
✔️ بررسی موشکافانهی منطقهی کدهای C زبان پایتون، اینبار متد
این مقاله چگونگی انجام عمل سادهی append در لیستها رو با بررسی کدهای مفسر CPython بهتون نشون میده و همچنین بررسی میکنه که این عمل از چه الگوریتمی به چه الگوریتمی رفته و چه اتفاقاتی افتاده 😁
📄 https://virgool.io/@liewpl/how-append-works-gp4apwtpr0bt
✒️ @pyeafp
〰〰〰〰〰〰〰
©@PSFarsi
append
از تایپ list
این مقاله چگونگی انجام عمل سادهی append در لیستها رو با بررسی کدهای مفسر CPython بهتون نشون میده و همچنین بررسی میکنه که این عمل از چه الگوریتمی به چه الگوریتمی رفته و چه اتفاقاتی افتاده 😁
📄 https://virgool.io/@liewpl/how-append-works-gp4apwtpr0bt
✒️ @pyeafp
〰〰〰〰〰〰〰
©@PSFarsi
HashMaps به بیان ساده:
قرار هست ببینیم associative array چیه، hashmap چیه، چه ارتباطی به dictionary داره، ویژگی هاشون چیه، hash collision چیه، چطور برطرف میشن، نمونه خیلی سادش رو پیاده سازی کنیم و در انتها یه نمونه کامل هم ببینیم ازش.
خب... زمانی که ما یک سری دیتا داریم که به هم مرتبط هستن میتونیم اون ها رو توی یه collection نگهداری کنیم مثلا array. اطلاعاتی مثل تمام نمرات دانش آموزان یک کلاس:
مشکل کجاست؟
مشکل اینه که برای ما سخته حفظ کنیم کدوم ایندکس برای کدوم شخص بوده و ترجیح میدیم که اگه نمره ی شخصی رو میخوایم به جای اینکه یه عدد بی معنی بدیم، اسمش رو بدیم و نمرش رو بگیریم:
اینکه اسمش رو(که بهش میگیم کلید) متصل یا مربوط یا "associate" بکنیم به نمرش.
چطوری؟ مثلا:
چیزی که ما بالا ساختیم یک پیاده سازی (بد) از associative array بود. چون associate کردیم یک کلید رو به مقدارش. associative array یک abstract هست و میتونه به شکل های مختلف پیاده سازی بشه.
خب... فقط یه مشکلی هست الان:
قبلا که با ایندکس میگرفتیم صاف میرفتیم سراغ خودش، الان مجبوریم که iterate کنیم روشون و دونه دونه بگردیم تا برسیم به اونی که میخوایم. کنده!! (شما مثال های این پست رو با ۱۰۰۰ تا داده مثلا تصور کنید)
راه حل چیه؟
اینکه بیایم "یه جوری" این اسم ها رو map کنیم به ایندکس های عددی تا دوباره بتونیم صاف بریم سراغ اونی که میخوایم و سرعت بهتر بگیریم.
چطور اینکارو بکنیم؟
مثلا بیایم یک فانکشن بنویسیم که از کلیدها عدد تولید کنیم به این صورت که اعداد اسکی متناظر با هر حرف از کلیدمون رو باهم جمع کنیم. یعنی برای sara داریم:
"sara" # -> 115 + 97 + 114 + 97 -> 423
این میشه فانکشنش:
باقی ماندش رو با طول لیستمون حساب کنیم!
اینطوری مطمئن هستیم که داخل اون رنجی که میخوایم هست. پس:
423 % 5 -> 3
کافیه sara و نمرش رو توی ایندکس شماره ۳ ذخیره کنیم:
الان خوب شد. هر کدوم از نمره هارو بخوایم بگیریم اول اون کلید رو hash میکنیم بعد باقی ماندش رو حساب میکنیم میشه ایندکس مورد نظر. دیگه iteration ای در کار نیست و به time complexity عه O(1) رسیدیم. الان get_grade عه ما اینطوری شد:
خب ما الان تونستیم associative array رو با کمک hashmap پیاده سازی کنیم :) بریم ادامش...
حالا اگه اسم یکی دیگه از دانشجو ها aras بود چی؟
(پست بعدی)
پست ۱ از ۳
قرار هست ببینیم associative array چیه، hashmap چیه، چه ارتباطی به dictionary داره، ویژگی هاشون چیه، hash collision چیه، چطور برطرف میشن، نمونه خیلی سادش رو پیاده سازی کنیم و در انتها یه نمونه کامل هم ببینیم ازش.
خب... زمانی که ما یک سری دیتا داریم که به هم مرتبط هستن میتونیم اون ها رو توی یه collection نگهداری کنیم مثلا array. اطلاعاتی مثل تمام نمرات دانش آموزان یک کلاس:
grades = [17, 19, 18, ...]و با ایندکس های عددی بهشون دسترسی پیدا کنیم:
grades[2]خیلی هم سریع هستن array ها تو دسترسی چون مستقیم میریم سراغ همون نمره ای که نیاز داریم.
مشکل کجاست؟
مشکل اینه که برای ما سخته حفظ کنیم کدوم ایندکس برای کدوم شخص بوده و ترجیح میدیم که اگه نمره ی شخصی رو میخوایم به جای اینکه یه عدد بی معنی بدیم، اسمش رو بدیم و نمرش رو بگیریم:
grades["ali"]راه حل چیه؟
اینکه اسمش رو(که بهش میگیم کلید) متصل یا مربوط یا "associate" بکنیم به نمرش.
چطوری؟ مثلا:
grades = [("reza", 17), ("sara", 19), ("ali", 18)]و بعد هم اینجوری میگیریم:
def get_grade(person_name):خیلی بهتر و راحت تر شد الان...
for name, grade in grades:
if name == person_name:
return grade
print(get_grade("ali"))
چیزی که ما بالا ساختیم یک پیاده سازی (بد) از associative array بود. چون associate کردیم یک کلید رو به مقدارش. associative array یک abstract هست و میتونه به شکل های مختلف پیاده سازی بشه.
خب... فقط یه مشکلی هست الان:
قبلا که با ایندکس میگرفتیم صاف میرفتیم سراغ خودش، الان مجبوریم که iterate کنیم روشون و دونه دونه بگردیم تا برسیم به اونی که میخوایم. کنده!! (شما مثال های این پست رو با ۱۰۰۰ تا داده مثلا تصور کنید)
راه حل چیه؟
اینکه بیایم "یه جوری" این اسم ها رو map کنیم به ایندکس های عددی تا دوباره بتونیم صاف بریم سراغ اونی که میخوایم و سرعت بهتر بگیریم.
چطور اینکارو بکنیم؟
مثلا بیایم یک فانکشن بنویسیم که از کلیدها عدد تولید کنیم به این صورت که اعداد اسکی متناظر با هر حرف از کلیدمون رو باهم جمع کنیم. یعنی برای sara داریم:
s: 115در نتیجه:
a: 97
r: 114
a: 97
"sara" # -> 115 + 97 + 114 + 97 -> 423
این میشه فانکشنش:
def hash_func(string):حالا یه لیست بسازیم که ۵ تا جای خالی داره:
return sum(map(ord, string))
grades = [None, None, None, None, None]خب حالا الان عددی که از هش کردن(پس یه هش فانکشن ساده بود اون) کلید sara به دست آوردیم و چطور map کنیم به یکی از ایندکس های لیستمون؟ ما که ۴۲۳ تا slot نداریم...
باقی ماندش رو با طول لیستمون حساب کنیم!
اینطوری مطمئن هستیم که داخل اون رنجی که میخوایم هست. پس:
423 % 5 -> 3
کافیه sara و نمرش رو توی ایندکس شماره ۳ ذخیره کنیم:
grades = [None, None, None, ("sara", 19), None]اگه همین کار رو برای باقی هم بکنیم همچین چیزی میشه:
grades = [(تو پرانتز حواسمون هست که ترتیبش عوض شد...)
("ali", 18),
None,
None,
("sara", 19),
("reza", 17),
]
الان خوب شد. هر کدوم از نمره هارو بخوایم بگیریم اول اون کلید رو hash میکنیم بعد باقی ماندش رو حساب میکنیم میشه ایندکس مورد نظر. دیگه iteration ای در کار نیست و به time complexity عه O(1) رسیدیم. الان get_grade عه ما اینطوری شد:
def hash_func(string):موقع insert کردن هم دقیقا برعکس همین شکل عمل میکنیم یعنی ابتدا هش میکنیم بعد باقیمانده میگیریم بعد که فهمیدیم کدوم slot برای اون کلید میشه میذاریمش اونجا. درواقع هر چیزی که برای get کردن میگیم برعکسش برای set کردن میشه.
return sum(map(ord, string))
def get_grade(person_name):
hash_value = hash_func(person_name)
idx = hash_value % 5
return grades[idx][1]
print(get_grade("reza"))
خب ما الان تونستیم associative array رو با کمک hashmap پیاده سازی کنیم :) بریم ادامش...
حالا اگه اسم یکی دیگه از دانشجو ها aras بود چی؟
(پست بعدی)
پست ۱ از ۳
چجوری aras رو اضافه کنیم به grades ؟ چون aras از همون حروفی که sara داره تشکیل شده با هش فانکشنی که ما نوشتیم دوباره بهمون ۴۲۳ میده و اگه باقی مانده بگیریم میشه ۳ یا درواقع همون ایندکسی که برای سارا اختصاص داده شده.
مشکل بوجود اومد... به این مشکل میگن hash collision یا تداخل هش ها!
هش فانکشنی که انتخاب کردیم شاید زیاد جالب نبود چون درواقع به ازای تمام جای گشت های یک کلمه همون هش رو بهمون میده.
هش فانکشن خوب توی hashmap ها دو تا ویژگی داره:
۱- باید محاسباتش سبک باشه. چون دائما داره برای همه ی کلید ها حساب میشه.
۲- "سعی کنه" مقدار های یونیک تولید کنه تا به hash collision بر نخوریم.
بیایم کمی تغییرش بدیم: علاوه بر اینکه از عدد اسکیشون استفاده میکنیم، بیایم اون عدد رو در جایگاهی که داره(حرف چندمه) ضرب هم بکنیم به این شکل:
چه کنیم؟ بیایم یه هش فانکشن معقول داشته باشیم که سعی کنه با سرعت بالا hash value رو محاسبه کنه (چیزی که الان داریم) ولی اگه collision پیش اومد رفعش کنیم! چطور؟
روش اول، separate chaining :
تو این روش میگه به جای اینکه ما بیایم slot ها رو خالی بذاریم (None) ، بیایم به جاش از لیست خالی استفاده کنیم! هر موقع hash collision داشتیم میایم اضافش میکنیم به لیست.
یعنی اگه ۴ تا دانش آموزش ما باشن: ali, sara, reza, nima
با هش فانکشن جدیدی که نوشتیم slot های ما به این صورت میشن:
اگه دقت کنیم میبینیم هرچی hash collision بیشتر داشته باشیم به رفتار خطی بیشتر نزدیک میشیم.
این روش اول بود که پیاده سازی خیلی ساده ای هم داره. یه مشکلی ریزی داریم اینجا. یه سری فضای خالی الان توی slot های ما بوجود اومده. آیا میتونیم بیایم از این فضاها استفاده کنیم؟
روش دوم، open addressing:
شرایطی و در نظر بگیرید که الان reza و ali و sara ذخیره شدن و ما میخوایم nima رو اضافه کنیم:
0 -> 1 -> 2 -> 3 -> 4
اگه برای ali میخواستیم probing sequence چی میشد؟
3 -> 4 -> 0 -> 1 -> 2
و به همین ترتیب میریم جلو تا به جای خالی برسیم. الان برای نیما ایندکس بعدی میشه ۱. خالی هست؟ بله. پس میذاریمش اونجا و تبدیل میشه به:
1- linear probing
2- quadratic probing
3- double hashing
کاری که بالا کردیم linear probing بود. چون نمیخوام بیشتر از این طولانی بشه دوتای دیگه رو اینجا نمیگم(پیاده سازیش رو در انتها گذاشتم) ولی حدس زدنش سادس. مثلا تو دومی به جای اینکه دونه دونه بره بالا ، با توان های ۲ میره بالا (کمک میکنه که توده ای از کلید ها رو یک جای hash table مون نداشته باشیم پخش بشن) و آخری میگه یه هش دیگه(هش دوم) انجام بدیم برای پیدا کردن ایندکس بعدی!
اینا هر کدوم مزایا و معایبی دارن که میشه کلی دربارشون بحث کرد که کدوم کجا چرا بهتره.
پست تموم شد ولی یه سری نکته های تکمیلی باقی موند:
(پست بعدی و آخر)
پست ۲ از ۳
مشکل بوجود اومد... به این مشکل میگن hash collision یا تداخل هش ها!
هش فانکشنی که انتخاب کردیم شاید زیاد جالب نبود چون درواقع به ازای تمام جای گشت های یک کلمه همون هش رو بهمون میده.
هش فانکشن خوب توی hashmap ها دو تا ویژگی داره:
۱- باید محاسباتش سبک باشه. چون دائما داره برای همه ی کلید ها حساب میشه.
۲- "سعی کنه" مقدار های یونیک تولید کنه تا به hash collision بر نخوریم.
بیایم کمی تغییرش بدیم: علاوه بر اینکه از عدد اسکیشون استفاده میکنیم، بیایم اون عدد رو در جایگاهی که داره(حرف چندمه) ضرب هم بکنیم به این شکل:
def hash_func(string):الان هش collision رو بر طرف کردیم:
hash_value = 0
for i, char in enumerate(string, start=1):
hash_value += ord(char) * i
return hash_value
for name in ("ali", "sara", "reza", "aras"):خروجیش میشه:
hash_value = hash_func(name)
print(f"{name}: {hash_value} : {hash_value % 5}")
ali: 628 : 3ولی همونطور که حدس میزنید باز هم با کلید های مختلف ما به hash collision بر میخوریم... مثلا جای aras بذارید nima ...
sara: 1039 : 4
reza: 1070 : 0
aras: 1076 : 1
چه کنیم؟ بیایم یه هش فانکشن معقول داشته باشیم که سعی کنه با سرعت بالا hash value رو محاسبه کنه (چیزی که الان داریم) ولی اگه collision پیش اومد رفعش کنیم! چطور؟
روش اول، separate chaining :
تو این روش میگه به جای اینکه ما بیایم slot ها رو خالی بذاریم (None) ، بیایم به جاش از لیست خالی استفاده کنیم! هر موقع hash collision داشتیم میایم اضافش میکنیم به لیست.
یعنی اگه ۴ تا دانش آموزش ما باشن: ali, sara, reza, nima
با هش فانکشن جدیدی که نوشتیم slot های ما به این صورت میشن:
grades = [مشکل حل شد. الان با اینکه وقتی نمره ی نیما رو بخوایم باید قبلش یه رضا رو هم چک کنیم ولی خیلی جلو افتادیم نسبت به اینکه بخوایم همه رو چک کنیم! یعنی کلی کلید رو محاسبه نمیکنیم فقط اون چندتایی که collision داشتن سرچ میشن. و خب باقی کلید ها که collision نداشتن مستقیم پیدا میشن.
[("reza", 17), ("nima", 20)],
[],
[],
[("ali", 18)],
[("sara", 19)],
]
اگه دقت کنیم میبینیم هرچی hash collision بیشتر داشته باشیم به رفتار خطی بیشتر نزدیک میشیم.
این روش اول بود که پیاده سازی خیلی ساده ای هم داره. یه مشکلی ریزی داریم اینجا. یه سری فضای خالی الان توی slot های ما بوجود اومده. آیا میتونیم بیایم از این فضاها استفاده کنیم؟
روش دوم، open addressing:
شرایطی و در نظر بگیرید که الان reza و ali و sara ذخیره شدن و ما میخوایم nima رو اضافه کنیم:
grades = [میایم nima رو هش میکنیم ایندکس و پیدا میکنیم میبینیم میشه صفر. و نگاه میکنیم میبینیم پر هست! میایم یه sequence ای تولید میکنیم به اسم probing sequence. به طوری که از همون اون ایندکسی که محاسبه کردیم شروع میشه(اینجا شد صفر برای نیما) و یه دور میزنه:
("reza", 17),
None,
None,
("ali", 18),
("sara", 19),
]
0 -> 1 -> 2 -> 3 -> 4
اگه برای ali میخواستیم probing sequence چی میشد؟
3 -> 4 -> 0 -> 1 -> 2
و به همین ترتیب میریم جلو تا به جای خالی برسیم. الان برای نیما ایندکس بعدی میشه ۱. خالی هست؟ بله. پس میذاریمش اونجا و تبدیل میشه به:
grades = [ما ۳ شکل probe sequence داریم:
("reza", 17),
("nima", 20),
None,
("ali", 18),
("sara", 19),
]
1- linear probing
2- quadratic probing
3- double hashing
کاری که بالا کردیم linear probing بود. چون نمیخوام بیشتر از این طولانی بشه دوتای دیگه رو اینجا نمیگم(پیاده سازیش رو در انتها گذاشتم) ولی حدس زدنش سادس. مثلا تو دومی به جای اینکه دونه دونه بره بالا ، با توان های ۲ میره بالا (کمک میکنه که توده ای از کلید ها رو یک جای hash table مون نداشته باشیم پخش بشن) و آخری میگه یه هش دیگه(هش دوم) انجام بدیم برای پیدا کردن ایندکس بعدی!
اینا هر کدوم مزایا و معایبی دارن که میشه کلی دربارشون بحث کرد که کدوم کجا چرا بهتره.
پست تموم شد ولی یه سری نکته های تکمیلی باقی موند:
(پست بعدی و آخر)
پست ۲ از ۳
HTML Embed Code: