با استفاده از ماژول heapq در پایتون تابعی بنویسید که از یک لیست بزرگ از اعداد اعشاری (مثلاً خروجی شبیه‌سازی عددی) k کوچک‌ترین مقادیر را به صورت مرتب‌شده بازگرداند.

2.0 بازدید آخرین ویرایش در 202 روز قبل ساعت 02:52

0.0

برای حل این مسئله می‌توانید از تابع آماده heapq.nsmallest استفاده کنید که در اغلب موارد برای داده‌های بزرگ کارآمد است (پیچیدگی تقریبی O(n log k)). راه دیگر این است که یک هیپ ماکزیمم با اندازه ثابت k بسازید: عناصر را یکی‌یکی وارد کنید و هرگاه اندازه بیش از k شد بزرگ‌ترین عنصر را حذف کنید تا در نهایت هیپ شامل k کوچک‌ترین مقدار باشد؛ سپس آن‌ها را مرتب کنید. برای پردازش داده‌های بسیار بزرگ می‌توانید از تولیدکننده‌ها (generators) برای خواندن جریانی استفاده کنید و یا اگر داده‌ها آرایهٔ NumPy هستند از numpy.partition برای سرعت بالاتر بهره ببرید؛ اما برای شروع و کاربردهای مبتدی، استفاده از heapq و nsmallest ساده و مناسب است.

توسط پژوهشگر در 202 روز قبل ساعت 02:52
دسته بندی ها: Python Python for beginner
arman در 202 روز قبل ساعت 08:16

یک نکته کوتاه: اگر تنها به k کوچک‌ترین مقادیر و ترتیبِ آن‌ها بصورت مرتب نیاز دارید، استفاده از heapq.nsmallest با داده‌های بزرگ کارآمد است و پیچیدگی تقریبی O(n log k) دارد. اگر می‌خواهید از حافظه کم‌تر استفاده کنید یا داده‌ها به‌صورت پیوسته می‌آیند، می‌توانید از یک هیپ ماکزیمم با اندازه k استفاده کنید و هر بار مقدار جدید را مقایسه کنید تا فقط k مقدار باقی بمانند؛ در نهایت، کارِ مرتب‌سازی را با یک مرتب‌سازی ساده انجام بدهید. برای داده‌های بسیار بزرگ یا جریان‌محور، می‌توانید از تولیدکننده‌ها (generator) یا numpy.partition استفاده کنید تا سرعت بیشتری بگیرید، اما برای مبتدیان همین heapq.nsmallest پاسخ‌گو است.

گزارش

1 پاسخ

جدید ترین قدیمی ترین بالاترین امتیاز پاسخ های من

در حال بارگیری...
ورود به حساب کاربری