انواع سرچ ها روی لیست

خیلی خلاصه چند تا از انواع سرچ ها رو روی لیست باهم ببینیم:

فرض کنید یه لیست نا مرتبی از اعداد داریم به این شکل:
lst = [30, 2, 7, 14, 1, 25, 4, 15, 9]
اگه بخواهیم دنبال عدد ۱۵ بگردیم باید چیکار کنیم؟

1- Linear search(not optimized)
میتونیم از ایندکس شماره صفر شروع کنیم و تک تک تا انتها بریم جلو و اعداد رو نگاه کنیم ببینیم ۱۵ داخلشون هست یا نه. این درواقع کاری هست که پایتون انجام میده زمانی که شما از in استفاده میکنید. چون اعداد ترتیبی ندارن کار دیگه ای نمیشه کرد.
________________________________________
اگه اعداد مرتب بودن چی؟
lst = [1, 2, 4, 7, 9, 14, 15, 25, 30]

2- Linear search(optimized)
فرض کنیم میخواهیم دنبال عدد ۵ بگردیم. دوباره میتونیم شروع کنیم تک تک اعداد رو مقایسه کنیم، ولی بعد از اینکه به عدد ۷ رسیدیم، میتونیم دیگه ادامه ندیم. چون اعداد مرتب هستن، حتما توی اعداد بزرگتر از ۷ هم نخواهد بود. بهتر شد اینجا.

3- Jump search
میتونیم به جای اینکه تک تک به جلو بریم و اعداد رو، چند تا چند تا جلو بریم و بپریم اصطلاحا (jump search).
فرض کنید دنبال عدد ۲۵ میگردیم. میتونیم اعداد رو ۲ تا ۲ تا جلو بریم، یعنی اول ایندکس شماره ۰ (یا عدد ۱) و نگاه میکنیم، بعد میریم ایندکس شماره ۲ (یا عدد ۴)، بعد ایندکس شماره ۴ (یا عدد ۹) و تا آخر، هر جا که دیدیم عدد ایندکس مورد نظر بزرگتر از عدد مقصود ماست، یعنی به اون تیکه از لیست که ممکنه عدد هدف داخلش باشه رسیدیم، فقط کافیه داخل اون رو به صورت linear نگاه کنیم. برای پیدا کردن عدد ۲۵ ، فقط ۶ تا مقایسه لازم بود. (تو حالت خطی ۸ تا). حالا این jump ما چقدر باشه خوبه؟ محاسبات نشون میده که رادیکال n بهترین گام هست. ( n تعداد آیتم های داخل لیست هست)

4- Binary search
کافیه توی هر مرحله لیستمون رو به دو قسمت تقسیم کنیم، و آیتم هدف رو با آیتم وسطی مقایسه کنیم، اگه کوچیکتر بود، دیگه فقط توی اون نیمه ی سمت چپ دنبالش میگردیم، اگه بزرگتر بود توی نیمه ی سمت راست.

5- Interpolation search
خیلی شبیه binary search هست با این تفاوت که اونجا نقطه ای که لیست ما رو تقسیم میکرد و دقیقا وسط لیست میگرفتیم، ولی اینجا با استفاده از این فرمول، اون نقطه رو بدست میاریم:
mid = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low]))

low = کوچکترین ایندکس
high = بزرگترین ایندکس
key = آیتم هدف

این فرمول نقطه ی تقسیم رو مایل به چپ یا راست پیدا میکنه، نزدیک تر به آیتم هدف. ولی برای اینکه interpolation search بتونه خیلی سریع عمل کنه، باید لیست ما به صورت یکنواخت توزیع شده باشه.

6 - Exponential search
توی این روش که برای لیست های خیلی بزرگ کاربرد داره، از ابتدا شروع میکنیم به گشتن، ولی گام های ما به صورت exponential هست (توان های ۲):
0, 1, 4, 9, 16, 25, ...
وقتی که آیتمی پیدا کردیم که از آیتم هدف ما بزرگتر بود، میایم اون تیکه رو دوباره فقط جست و جو میکنیم(مثل jump search) ولی دیگه این جست و جو خطی نیست بلکه روش binary search انجام میدیم.


نکته: این الگوریتم ها بسته به شرایط الگوریتم های خیلی بهتری هستن از کاری که پایتون انجام میده. به پایتون حتی اگه لیست مرتب شده هم بدید باز تک تک سرچ میکنه. ولی خب نکته اینجاست که اون با C پیاده سازی شده و احتمالا توی خیلی از پیاده سازی های pure python از الگوریتم هایی با time complexity بهتر سریعتر باشه.

در آینده سعی میکنم بیشتر درمورد time complexity ی هرکدوم از این انواع سرچ و اینکه کجا کدوم بهتره استفاده بشه صحبت کنیم.

👤 SorousH

💎 Channel: @DevelopixPython

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

💻 کارگاه تجارت بین‌المللی برای برنامه‌نویس‌ها؛
(فریلنسرینگ حرفه‌ای در مقیاس جهانی)

🗓 زمان: 30 شهریور تا 6 مهر 1402
حضوری و آنلاین (2 جلسه حضوری و 5 جلسۀ آنلاین)

📝 اطلاعات بیشتر و ثبت‌نام
🔻و یا برای کسب اطلاعات بیشتر کافیه به آی‌دی ما پیام بدی!

🆔 @MaktabSharif_Admin

🌐 وبسایت |📱کانال تلگرام | 📲 اینستاگرام

.pythonrc

درست مثل
.nanorc
.bashrc
.vimrc
...
و بقیه فایل های مشابه، یه pythonrc هم داریم که به همون منظور ایجاد شده. قرار هست از قبل از startup عه REPL خونده و اجرا بشه.
استفاده های مختلفی میشه کرد: مثلا اگه همیشه وقتی REPL رو باز میکنید یه سری کتابخونه رو import میکنید، میتونید یک بار اینجا import کنید و دیگه هربار اینکار رو نکنید.
یا مثلا اگه یه سری helper فانکشن برای خودتون نوشتید میتونید یکبار اینجا تعریفش کنید و هروقت که REPL رو باز کردید در دسترس شما هست.
یه کار جالب دیگه اینکه میتونیم built-in فانکشن help رو با inspect که توی rich هست عوض کنیم:

from functools import partial
from rich import inspect, pretty

help = partial(inspect, help=True)
pretty.install()

حالا باید environment variable عه PYTHONSTARTUP رو هم ست کنیم که به فایل
.pythonrc
اشاره کنه.
الان وقتی روی آبجکتی بزنید ورژن rich استفاده میشه.

منبع

👤 SorousH

💎 Channel: @DevelopixPython

Conditional breakpoint

فرض کنید همچین کدی داریم:

for i in range(100):
    print(i)

و دوباره فرض کنید زمانی که i میشه ۹۰ یه مشکلی بوجود میاد. میخواهیم برنامه رو دیباگ کنیم. چه کنیم؟ break point بذاریم سمت چپ for loop.
ولی موضوع این هست که دیباگر وقتی ران میشه همون ابتدا کنار for loop متوقف میشه و ما باید دستی جلو ببریم. تو این حالت i مساوی ۰ هست. منطقی نیست که ۹۰ بار روی next بزنیم تا برسیم به اون حالتی که i برابر ۹۰ میشه.

خوشبختانه یه چیزی به اسم conditional breakpoint وجود داره که میتونید بهش یه expression عه boolean بدید و دیباگر فقط زمانی متوقف میشه که اون expression درست باشه.
توی ادیتور دلخواهتون بعد از اینکه break point گذاشتین، راست کلیک کنید روش و edit رو بزنید (یا هر اسم دیگه ای که داره) و توی اون پنجره ای که باز میشه بنویسید:

i == 90

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

👤 SorousH

💎 Channel: @DevelopixPython

📌 دوره آنلاین سئو برای مدیران، آخرین روز ثبت‌نام با تخفیف ویژه

🔘 استراتژی سئو
🔘 مدیریت فرآیندهای سئو
🔘 گزارشات سئو
🔘 ارزیابی و نظارت بر فرآیندهای سئو
🔘 اشتباهات سئو
🔘 قراردادهای سئو


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

پنج جلسه آموزش انلاین فشرده و تخصصی همراه با یک جلسه پرسش و پاسخ.

اطلاعات بیشتر و ثبت‌نام در ایسمینار:
🌐 eseminar.tv/wb116105

کد تخفیف: talebi

فقط امروز و فردا، به جای 5 میلیون تومان فقط با 2 میلیون تومان در این دوره آنلاین شرکت کنید.

هدایای شرکت در دوره:
🔘 حداقل 2 میلیون تومان رپورتاژ در تریبون
🔘 اکانت 6 ماهه جت‌سئو به ارزش 1.200.000 تومان
🔘 اکانت یک سالۀ سازمانی میزیتو به ارزش 2.900.000 تومان
🔘 یک جلد کتاب سئو 2022+2023 امضاء شده.

❌❌ فقط امروز ❌❌

☑️ @kar_kasb

دایناسورها در حال خرید در تهران 🤯

⚡️هیچ‌وقت فکرشو میکردی که همچین تصویری رو ببینی؟

⚡️از آینده به تو سلام 😁

💠این تصویر با استفاده از یک ابزار جدید در تلگرام ساخته شده که هر متنی بهش بدی رو تبدیل به عکس میکنه!

همین‌الان بهش پبام بده تا عکسش رو برات بفرسته😇

فقط کافیه بزنی رو آیدی زیر و شروع کنی 😉👇🏻
@aiolearn_artbot

🌀هوش‌مصنوعی با پیشرفت فوق‌العادش داره همه دنیار رو فرا میگیره 😉🤯

💠 معرفی کتاب 💠
💎 Django Design Patterns and Best Practices

📚 دانستن الگوهای مختلف می‌تواند زمان کد نویسی را تا حد زیادی کاهش دهد و عملکرد کد را افزایش دهد. نویسنده نه‌تنها الگوها را توضیح می‌دهد، بلکه با ارائه مثال‌ها و راه‌حل‌ها، مطمئن می‌شود که می‌دانید کجا و چه زمانی از هر الگوی استفاده کنید. این کتاب همچنین به‌طور کامل تست و امنیت را پوشش می‌دهد که دو جنبه مهم توسعه هر برنامه وب هستند.

📖 سرفصل‌های کتاب عبارتند از:

1️⃣ جنگو و الگو‌ها
2️⃣ طراحی برنامه
3️⃣ مدل‌ها
4️⃣ ویوها و URLها
5️⃣ قالب‌ها
6️⃣ رابط ادمین
7️⃣ فرم‌ها
8️⃣ کار کردن به صورت ناهمزمان
9⃣ ایجاد APIها
🔟 سر و کار داشتن با کد میراثی
1⃣1⃣ تست کردن و دیباگ کردن
2⃣1⃣ امنیت
3⃣1⃣ آمادگی برای محیط پروداکشن

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

#معرفی_کتاب

👤 MHReza

💎 Channel: @DevelopixPython

📥 دانلود کتاب

📚 Django Design Patterns and Best Practices

👤 MHReza

💎 Channel: @DevelopixPython

🔸دیتا استراکچرهای پایتون در یک نگاه

🔗 Source

👤 MHReza

💎 Channel: @DevelopixPython

🔸 تا حالا شده بخواهید مقدار دو متغیر رو با همدیگه جابجا کنید؟
🔹 توی کد بالا با یه روش جالب این کار رو انجام می‌دهیم که دیگه نیاز نباشه برای این کار متغیر جدیدی ایجاد بکنید.

👤 MHReza

💎 Channel: @DevelopixPython

✔️ استیبل بودن یا نبودن یک الگوریتم مرتب سازی

یکی از دسته بندی های موجود برای الگوریتم هایsort کردن، فاکتور stable بودن یا نبودن هست. به طور خلاصه به الگوریتمی میگن stable که:

موقع sort کردن یک لیست، اگه ۲ تا آیتم مساوی هم بودن، دقیقا به همون ترتیبی که توی لیست اولیه بودن، توی لیست مرتب شده هم ظاهر بشن.

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

lst = [
    ("Ashkan",17),
    ("Bahar",18),
    ("Sorena",17)
]

یک راه مرسوم اینه که به این روش sort رو انجام بدیم:

lst.sort(key=lambda x: (x[1], x[0]))

کاملا درسته و هیچ اشکالی نداره. بیشتر میخواستیم درباره موضوع پست صحبت کنیم.

آیا میتونیم فقط بیایم بر اساس آیتم دوم sort ش کنیم؟ این که خود لیست بر اساس حروف الفبا مرتب شده آیا کمکی میکنه؟ یعنی:

lst.sort(key=lambda x: x[1])

اگه بدونیم الگوریتمی که استفاده شده stable هست بله میتونیم و گارانتی هست که آیتم های مساوی به همون ترتیب در خروجی قرار میگیرن، و چون در حال حاضر بر اساس حروف الفبا مرتب شده هستن، اون افرادی که نمره ی برابر دارن اتوماتیک بر اساس حروف الفبا هم مرتب هستن.

خروجی هردو:

[
    ('Ashkan', 17),
    ('Sorena', 17),
    ('Bahar', 18)
]

پایتون از Tim Sort استفاده میکنه و stable هست.


چند تا از الگوریتم های مرتب سازی استیبل:
• Insertion Sort
• Merge Sort
• Bubble Sort
• Tim Sort
و نقطه‌ی مقابلشون:
• Heap Sort
• Selection Sort
• Quick Sort

👤 SorousH

💎 Channel: @DevelopixPython

💠 شده بخواید آیتمی رو که بیشتر از بقیه تکرار شده رو بگیرید؟ با کد بالا می‌تونید این کار رو انجام بدید.

#Tips

💎 Channel: @DevelopixPython

⭕️ کمتر از ۲ هفته تا شروع دوره‌ی محبوب و تخصصی ماشین‌لرنینگ آکادمی آمانج باقی مونده!

⚠️ جای ۷نفر از شما در دوره ما خالیه!

🎁 برای اعضای پیج یه کد تخفیف ۴۰۰ هزار تومانی در نظر گرفتیم: ml4

💰قیمت دوره: ۵‌.۹ میلیون تومان
(امکان پرداخت قسطی هم وجود داره)

🧑‍🏫مدرس دوره: دکتر ریحانی مدیر فنی نوسازان، دیتاساینتیست و دکتری کامپیوتر دانشگاه تهران

⏰ شروع دوره: ۱۵ دی ماه ۱۴۰۲ (جمعه‌ها ۱۵-۱۱)

📊 ۵۵ ساعت آموزش مقدماتی تا پیشرفته

📍ویژگی‌های دوره:

✔️هر هفته وبینار برگزار میشه و شما می‌تونید مستقیما با استاد تعامل داشته‌باشید.

✔️ در پایان دوره، مدرک نمره‌دار آکادمی آمانج بهتون داده میشه.

✔️ در طول دوره، پشتیبان‌های فنی آمانج حواسشون به همه چیز هست تا بهترین تجربه رو در طول یادگیری داشته باشین.

✔️سرفصل‌های دوره ماشین لرنینگ کاملا به‌روز و مطابق با نیاز بازار کاره.

✔️بعد از پایان دوره می‌تونید در کامیونیتی تخصصی برنامه‌نویسی آمانج عضو بشید که حسابی به دردتون می‌خوره.

🌐 👈🏻برای اطلاعات بیشتر و ثبت‌نام کلیک کنید

@AmanjAdmin
09107603363
02191692911

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

قبل از هر چیزی درباره ی خود فانکشن حرف بزنیم؛ ولی نه تو پایتون بلکه تو C:
وقتی یه فانکشنی کال میشه، توی call stack یک frame جدید میاد که برای اون فانکشن هست. این frame شامل تمام متغیر های لوکال و پارامتر های اون فانکشنه. وقتی فانکشن تموم میشه چه اتفاقی میفته؟ اون frame از stack پاپ میشه (یا دقیق ترش stack pointer کم میشه)
و نکته اینجاس که هرچی که توی اون frame هست دیگه قابل دسترس نیست و اگر استفادشون کنیم، undefined behavior هست. چرا؟ چون توی "مموری استک" این frame قرار داده شده بود و اون فضا الان آزاد شده و قابل استفاده هست برای بقیه (توی پرانتز، در C که مدیریت حافظه نداره، باید آبجکت هایی که توی heap میسازیم رو خودمون مدیریت کنیم نه استک):

int *returnArray() {
    int arr[3] = {11, 22, 33};
    printf("%p\n", arr);
    printf("%d\n", arr[1]);
    return &arr;
}
int main(void) {
    int *arr;
    arr = returnArray();
    printf("%p\n", arr);
    printf("%d\n", arr[1]); // ???
}

با اینکه آدرسش رو return کردیم ولی باز هم نمیتونیم به آیتم های لیست دسترسی داشته باشیم.
حالا اینارو گفتم که موضوع مهمی رو بگم. اونم اینه که تو پایتون هم همین call stack و اینا هست ولی اون frame object توی heap ساخته میشه. این یعنی اگر بخوایم میتونیم اون رو ذخیره داشته باشیم و همیشه بمونه! مثلا مانع از نابود شدن خودش و آبجکت های درونش بشیم. تو مثال زیر global f رو اگه از کامنت در بیارید obj از بین نمیره چون frame رو ذخیره کردیم:

from gc import collect
from sys import _getframe

class A:
    def __del__(self):
        print("del called")

def fn():
    # global f
    f = _getframe(0)
    obj = A()

fn()
collect()
input()

خب حالا که اینو گفتیم بریم سراغ خود آبجکت فانکشن تو پایتون. وقتی فانکشن کال میشه یه frame object ساخته میشه. این frame object داخلش آبجکت های زیادی هست (مستقیم یا غیرمستقیم) از جمله رفرنس داره به متغیر های داخل اون namespace و رفرنسی داره به code object که یک unit ئه executable هست. داخل این code object ما bytecode ها رو داریم که همون instruction ها هستن.

درواقع instruction ها هستن که اجرا میشن و این state ذخیره میشه. تو کد زیر lasti یعنی last instruction. (توی cpu هم اتفاق مشابهی میفته. اینجا pvm میخواد بدونه چی رو اجرا کرده و حالا نوبت چیه):

from sys import _getframe
def fn():
    print(_getframe(0).f_lasti)
    a = 10
    print(_getframe(0).f_lasti)

fn()

خب حالا بخش جالب ماجرا اینجاست. ما به عنوان طراحان فرضی زبان پایتون، میدونیم که frame ما میتونه خارج از موقع کال شدن هم زنده بمونه + از طرفی به state هم که دسترسی داریم. ( اینکه الان متغیر های local چیا هستن، اینکه الان تا instruction چندم اجرا شده و غیره)

فقط یه مشکلی هست، فانکشن های ما وقتی کال میشن از اولین instruction تا آخرینش رو اجرا میکنن و تموم میشن و همه ی آبجکت های داخل اون frame از بین میرن (اگر رفرنس دیگه ای نداشته باشن جای دیگه).

الان همه چیز محیا هست برای اینکه یه ساختار یا keyword جدیدی بیاریم تو زبان که هرجایی از execution فانکشن خواستیم بتونیم pause کنیم و اون رو با هر state ای که داره به حال خودش رها کنیم.
بیایم yield رو معرفی کنیم! هروقت yield اومد، کافیه اجرا رو متوقف کنیم و مثل فانکشن ها (که بعد از تموم شدنشون، frame شون از stack frame جدا میشن) frame این generator ها رو هم جدا کنیم.

بعدا اگه خواستیم generator رو ادامه بدیم و روش next بزنیم (مستقیم خودمون یا غیر مستقیم توسط پایتون) تنها کاری که باید بکنیم اینه که frameش رو برداریم و بچسبونیم به stack frame ممون و از اون state ای که بودیم ادامه بدیم.

def gen():
    a = 1
    yield
    b = 1
    yield

g = gen()
next(g)
print(g.gi_frame.f_lasti, g.gi_frame.f_locals)
next(g)
print(g.gi_frame.f_lasti, g.gi_frame.f_locals)

این call stack با linked list پیاده سازی شده و frame ها نود های اون هستن. با f_back به frame قبلی اشاره میکنن به راحتی وصل میشن و جدا میشن.

جنریتور ها با وجود سرعت خوبی که دارن، برای سرعت بیشتر ساخته نشدن بلکه برای استفاده بهینه‌تر از مموری ساخته شدن. داشتن همچین آبجکتی (به اضافه ساختار هایی مثل yield from) میتونه زمینه خیلی چیز ها رو فراهم کنه. از جمله فریموورک هایی مثل asyncio :)

👤 SorousH

💎 Channel: @DevelopixPython