الگونَوَرد ۹ (حل شد): محاسبه H-index

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

پرسش: آرایه ای از تعداد ارجاع ها (citation) به مقالات یک محقق داده شده است. برنامه ای بنویسید که H-Index محقق را محاسبه نماید.

تعریف H-Index این است: یک محقق دارای ایندکس h هست اگر h مقاله از ‌N مقاله وی حداقل h ارجاع داشته باشند و هیچ یک از N-h مقاله دیگر وی بیش از h ارجاع نداشته باشند.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 1 ژوئن

نکات مهم:

• انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.
• طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد.
• لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.
• بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.

قوانین اهدای جایزه:

• مبلغ جایزه نقدی 50,000 تومان می باشد.
• تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.
• جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.
• جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.

حل مساله

الگونورد برتر: الگونورد برتر الگونورد 9، کاربر با ای دی Fatemeh هست.

ایشون درست و کامل مساله را حل کردن و تشریح راه حل رو نوشتند. شرح مساله را با ویرایش من می خونید.

به Fatemeh تبریک می گم و بهش می گم: عالی هستی! ادامه بده!

و حالا شرح پاسخ:

حل مساله را با یک مثال شروع می کنیم تا مطمین شویم آن را بدرستی درک کرده ایم.  برای مثال، اگر محققی ۵ مقاله A, B, C, D, E با تعداد استنادات ۸، ۳، ۵، ۱۰، ۴ داشته باشد، H-index مقالات وی ۴ می باشد زیرا ۴ مقاله وی حداقل دارای چهار استناد (ارجاع) می باشند و هیچ مقاله دیگری بیش از ۴ ارجاع ندارد. به عنوان مثالی دیگر، اگر تعداد ارجاعات ۳، ۳، ۲۵، ۸، ۵ باشند، آنگاه H-index نویسنده برابر با ۳ است.

روش جستجوی کامل

ارایه الگوریتم را با روش جستجوی کامل شروع می کنیم. در روش جستجوی کامل باید تمام H-index ها را از مقدار حداکثر شروع کنیم. حداکثر H-index یک محقق برابر با تعداد مقالات وی (N) می باشد (یعنی حالتی که تعداد ارجاعات هر مقاله حداقل به تعداد مقالات وی باشد) و حداقل آن صفر می باشد(اگر هیچ مقاله ای ارجاعی نداشته باشد). بنابر این در روش جستجوی کامل هر بار بررسی می کنیم که  آیا نویسنده i مقاله دارد که حداقل i ارجاع داشته باشند. اگر این کار را از N که حداکثر ممکن است شروع کنیم آنگاه اولین مقدار i که شرط گفته شده را برآورد پاسخ می باشد.

برای هر مقدار i باید کل آرایه ارجاعات مقالات  را بررسی کنیم. بنابر این مرتبه اجرایی این الگوریتم N^2 می باشد.

اشکال این روش همان جستجوی بررسی مجدد کل آرایه است.

بهبود با استفاده از مرتب سازی

اگر لیست تعداد ارجاعات را مرتب نماییم آنگاه نیاز نیست که لیست را بصورت کامل بررسی کنیم.و. به عنوان مثال برای نویسنده با مقالات ۸، ۳، ۵، ۱۰، ۴ پس از مرتب سازی به لیست [3, 4, 5, 8, 10] می رسیم. اگر H-index یک نویسنده h باشد آنگاه مقدار اندیس h-1 آن حداقل باید برابر h باشد زیرا در این صورت همه h عنصر اول دارای h یا تعداد بیشتری ارجاع می باشند.

از این رو، در این الگوریتم بهبود یافته ابتدا آرایه را مرتب می کنیم. سپس از مقدار i برابر N شروع می کنیم و هر بار مقدار عنصر i-1 را بررسی می کنیم. در صورتی که مقدار بزرگتر یا مساوی i بود، مقدار i پاسخ می باشد.

توضیح کد: در خط 5 آرایه citations که تعداد استنادات به مقاله‌ها است را به صورت نزولی مرتب کردیم. سپس i را با مقدار اولیه N مقداردهی اولیه کرده ایم و هر بار یک شرط را بررسی می کنیم تا بینیم i مقاله با حداقل i ارجاع وجود دارد.

پیچیدگی زمانی این الگوریتم به دلیل مرتب سازی لیست ((O(n*log(n و پیچیدگی حافظه آن(O(1 است.

کاهش پیچیدگی زمانی با استفاده از یک تکنیک مفید

روش مرتب سازی از مقایسه استفاده می کند تا عناصر را مرتب نماید. بجای مرتب سازی مقایسه ای می توان از یک مرتب سازی لانه ای استفاده کرد. این روش در واقع بیشتر شبیه جستجوی عناصر به ترتیب مرتب شده آنهاست. مثلا لیست 3, 6, 1, 8, 6, 2 را می توان به این صورت مرتب نمود:

• ابتدا یکبار کل لیست را بررسی می کنیم که مقادیر ماکزیمم (یعنی 8) و مقدار مینیمم (یعنی 1) را بیابیم. در ضمن یک دیکشنری می سازیم و هر یک از مقادیر را در آن قرار می دهیم به این صورت که کلید برابر با مقدار عنصر لیست و مقدار عنصر دیکشنری برابر تعداد مشاهده شده عنصر در لیست می باشد (در واقع هر بار یک واحد به شمارنده اضافه می کنیم).
• سپس از یک شمارنده با مقدار اولیه 1(برابر با مینیمم مقادیر لیست)  شروع می کنیم و هر بار بررسی می کنیم که آیا شمارنده به عنوان کلید در دیکشنری وجود دارد و در صورت وجود مقدار آن (تعداد بارهای مشاهده مقدار در لیست اصلی) چند تا است.

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

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

با این توضیحات شروع به نوشتن برنامه می کنیم.  در خط 3 طول آرایه استنادات ورودی، متغیر h با مقدار اولیه صفر جهت نگهداری تعداد استنادات بزرگتر N  و یک مجموعه به صورت دیکشنری با مقدار پیش فرض تعریف کردیم، مجموعه c تکرار تعداد استنادات کوچکتر مساوی N را با کلید نگهداری خواهد کرد.

در خط 5 و 6 هر جا که مقدار تعداد استنادات یک مقاله بزرگتر N باشد به متغیر h یک واحد اضافه کرده ایم (زیرا در هر صورت به تعداد H-index یک واحد اضافه می کنند) وگرنه تعداد مقالات با تعداد ارجاعات x  را یک واحد اضافه می کنیم. در انتها کلیدهای دیکشنری c در بازه 0 تا N می باشند.

پس از خروج از این حلقه حداقل H-index در متغیر h قرار گرفته است. حال باید با بررسی مقالاتی که کمتر از N ارجاع دارند H-index  را بروزرسانی کنیم.

برای این کار در خط 8 تا 10 به صورت نزولی از بزرگترین استناد ممکن یعنی N شروع می کنیم. در صورتی که مقاله i ام کمتر از h ارجاع داشته باشد به مقدار نهایی h دسته یافته ایم.

مزیت استفاده از defaultdict عدم چک کردن کلید و مقدار دهی اولیه مجموعه است.

پیچیدگی زمانی این الگوریتم به جهت استفاده  نکردن از مرتب سازی(O(n و پیچیدگی حافظه به دلیل استفاده از مجموعه(O(n  است.

توضیحات بیشتر

طبق تعریف ویکی پدیا، به طور رسمی اگر f تابع متناظر با تعداد استنادات برای هر مقاله باشد، اچ ایندکس را به شکل زیر محاسبه می‌کنیم:

ابتدا مقادیر f را به ترتیب نزولی مرتب می‌کنیم، سپس به دنبال آخرین مکانی می‌گردیم که در آن f بزرگتر یا مساوی با آن مکان است (این مقدار را h می‌نامیم).

برای مثال، اگر محققی داریم که ۵ مقاله A, B, C, D, E با تعداد استنادات ۳، ۴، ۵، ۸، ۱۰ دارد، اچ ایندکس آن برابر ۴ است زیرا چهارمین مقاله دارای ۴ استناد و پنجمین مقاله دارای ۳ استناد است. در مقابل اگر همین مقالات دارای ۳، ۳، ۵، ۸، ۲۵ استناد باشند، آنگاه اچ ایندکس نویسنده برابر با ۳ است زیرا مقاله چهارم تنها ۳ استناد دارد.

دو مثال از نحوه محاسبه اچ ایندکس

اگر تابع f را به شکل نزولی از بالاترین مقدار تا پایین‌ترین مقدار داشته باشیم، می‌توانیم اچ ایندکس را به شکل زیر محاسبه کنیم:

حل مساله را به دو قسمت می توانیم تقسیم می کنیم.

قسمت اول: می دانیم که i بیشتر N که تعداد عناصر آرایه باشد نخواهد شد (i یک شمارنده از بزرگترین تعداد استناد است)، عملا زمانی که (f(i بزرگتر N هست، تنها مقدار i عمل خواهد نمود، زیرا i کوچکتر خواهد بود و داریم بین (min(f(i),i  را می گیریم و زمانی که max آنها را بگیریم، مثل یک شمارنده عمل خواهد نمود.

قسمت دوم: اگر به عمق یک مثال محاسبه اچ ایندکس توجه کنیم، می بینیم که چند واحد کم داریم، اگر تعداد نتایج تکراری بزرگترین (f(i کوچکتر مساوی N را به نتیجه قسمت اول اضافه کنیم، تا زمانی که قسمت اول بزرگتر مساوی i شود، i جواب مسئله ما خواهد بود.