آیا می‌دانستید حذف المان‌ها در جاوا از یک مجموعه بزرگ در صورتی که به روش درستی انجام نگیرد، می‌تواند بسیار کند و مستعد خطا باشد. در این مطلب یک راه برای انجام صحیح آن بررسی می‌شود.
همانطور که در این مطلب گفته شد، در گذشته حذف به شکل زیر انجام می‌گرفت.
for (Iterator it = items.iterator(); it.hasNext();) {
if (predicate(it.next())) {
it.remove();
}
}اما الان با کمک جاوا ۸ می‌توان نوشت.
items.removeIf(i -> predicate(i));
که نه تنها هوشمندانه تر هست، کاراتر نیز می‌باشد. اما بیایید بیشتر بررسی کنیم.
حذف المان از یک مجموعه در حالیکه روی آن iterate می‌کنیم مثل بریدن شاخه درختی است که روی آن ایستاده ایم. اما با استفاده از شمارنده‌ها این کار بدون خطای ConcurrentModificationException می‌تواند انجام گیرد. مثال ساده و معمولی زیر را در نظر بگیرید.
for (Iterator it = items.iterator(); it.hasNext();) {
if (predicate(it.next())) {
it.remove();
}
}اگر مجموعه یک لیست پیوندی n عضوی باشد که m عضو آن حذف شود، همانطور که در مطلب قبلی هم گفته شد از O(m*n) که همان O(n^2) زمان می‌برد. به این دلیل که هر المانی که حذف می‌شود، تمام المان‌های با اندیس بیشتر جا به جا می‌شوند تا آن فضای خالی آرایه را پر کنند.
اما راه حل جاوا ۸ این چنین نیست.
items.removeIf(i -> predicate(i));
این راه حل واضحا در مقایسه با رویکرد قبلی کاراتر است و از O(n)می‌باشد.
اما بیایید اینجا این تفاوت را روی نمودار ببینیم.
زمان اجرای دو رویکرد را به عنوان تابعی از سایز آرایه مشاهده می‌کنید در حالتی که ۹۹۹ المان از ۱۰۰۰ عضو آرایه حذف می‌شوند. برای هر نقطه داده ۴۰ اجرا گرفته شده که ۵ کندترین و سریع‌ترین اجراها حذف شده و جمع ۳۰ تای دیگر به عنوان زمان اجرا در نظر گرفته می‌شود.
برای آرایه با سایز بیشتر از ۱۵۰۰۰۰ رویکرد removeif() سه هزار برابر سریعتر است. حتی فاصله بین این دو رویکرد با افزایش سایز آرایه بیشتر و بیشتر می‌شود.
برای درک بهتر پیچیدگی زمانی نمودار قبلی را بزرگ می‌کنیم. همانطور که انتظار می‌رفت، رفتار خطی تابع removeIf() جاوا ۸ و رفتار نمایی روش قدیمی قابل مشاهده است.
یک نکته در مورد removeIf این است که پیاده‌سازی آن اتمیک است به این معنی که ابتدا ارزیابی روی همه آیتم‌ها صورت می‌گیرد قبل از اینکه تغییری بخواهد اعمال کند. بنابراین، اگر predicate خطایی برای هر آیتمی پرتاب کند، لیست تغییر نمی‌کند و ثابت می‌ماند.
و یک نکته در مورد رویکرد قدیمی (که در گروه لینکدین انجمن مطرح شد) این است که اگر ترتیب در لیست اهمیت نداشته باشد حذف عنصر iام از لیست با کد زیر در O(1) می‌تواند انجام گیرد.
swap(a,i,a.length-1); a.remove(a.length-1)
منبع:
سلام
با تشکر از مقالات خوبی که روی سایت قرار می دهید
این یکی با توجه به مطلب قبلی که خودتون هم بهش لینک دادین، نکته ی جدیدی نداشت، تقریبا تکراری بود
مثل بریدن شاخه درختی که روی آن ایستاده ایم 🙂