دانستنی‌ها

حذف المان‌ها از ArrayList در جاوا ۸

همانطور که می‌دانید پیاده‌سازی ArrayList به این شکل است که المان‌ها را در واقع در یک آرایه نگه می‌دارد.  حذف المان‌ها از ArrayList قدری هزینه‌بر بوده و از مرتبه زمانی n^2 می‌باشد. آیا جاوا ۸ می‌تواند این هزینه را کاهش دهد؟

فرض کنید یک لیست از اعداد صحیح داریم و می‌خواهیم تمام اعداد غیر اول آن را حذف کنیم.

کاری که می‌کنیم استفاده از itarator و یک حلقه while است. نمی‌توانیم همزمان که روی آرایه حرکت می‌کنیم، عناصر آن را حذف کنیم. (با خطای concurrent modification exception روبرو می‌شویم.)

بنابراین…

اما چنین کدی پیچیدگی زمانی n^2 دارد. در این کد دو کار را انجام دادیم،‌ حرکت روی لیست که از مرتبه n است. در ArrayList وقتی المانی را از یک اندیس حذف می‌کنید، هر چیزی در ادامه آرایه لازم است یک واحد شیفت پیدا کند. در واقع کاری که تابع remove انجام می‌دهد این است که داده‌های آرایه را در هر فراخوانی تابع کپی می‌کند. به این معنی است که n بار کپی خواهیم داشت و در کل مرتبه زمانی n^2 داریم.

جاوا ۸ یک تابع removeif در واسط collection دارد. این تابع برای ArrayList یک پیاده‌سازی پیچیده‌ای دارد که در نهایت به مرتبه‌زمانی n ختم می‌شود.

سورس کد تابع removeif از جاوا ۸ نیز به شکل زیر است.

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

[تعداد: 0    میانگین: 0/5]
برچسب ها
نمایش بیشتر

نوشته های مشابه

‫۲ نظرها

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا