دانستنی‌ها

راه و روش لامبدا و removeif در جاوا ۸

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

همانطور که در این مطلب گفته شد، در گذشته حذف به شکل زیر انجام می‌گرفت.

اما الان با کمک جاوا ۸ می‌توان نوشت.

که نه تنها هوشمندانه تر هست،‌ کاراتر نیز می‌باشد. اما بیایید بیشتر بررسی کنیم.

حذف المان از یک مجموعه در حالیکه روی آن iterate می‌کنیم مثل بریدن شاخه درختی است که روی آن ایستاده ایم. اما با استفاده از شمارنده‌ها این کار بدون خطای ConcurrentModificationException می‌تواند انجام گیرد. مثال ساده و معمولی زیر را در نظر بگیرید.

اگر مجموعه یک لیست پیوندی n عضوی باشد که m عضو آن حذف شود، همانطور که در مطلب قبلی هم گفته شد از O(m*n) که همان O(n^2) زمان می‌برد. به این دلیل که هر المانی که حذف می‌شود، تمام المان‌های با اندیس بیشتر جا به جا می‌شوند تا آن فضای خالی آرایه را پر کنند.

اما راه حل جاوا ۸ این چنین نیست.

این راه حل واضحا در مقایسه با رویکرد قبلی کاراتر است و از O(n)می‌باشد.

اما بیایید اینجا این تفاوت را روی نمودار ببینیم.

زمان اجرای دو رویکرد را به عنوان تابعی از سایز آرایه مشاهده می‌کنید در حالتی که ۹۹۹ المان از ۱۰۰۰ عضو آرایه حذف می‌شوند. برای هر نقطه داده ۴۰ اجرا گرفته شده که ۵ کندترین و سریع‌ترین اجراها حذف شده و جمع ۳۰ تای دیگر به عنوان زمان اجرا در نظر گرفته می‌شود.

blog1

برای آرایه با سایز بیشتر از ۱۵۰۰۰۰ رویکرد removeif() سه هزار برابر سریعتر است. حتی فاصله بین این دو رویکرد با افزایش سایز آرایه بیشتر و بیشتر می‌شود.

برای درک بهتر پیچیدگی زمانی نمودار قبلی را بزرگ می‌کنیم. همانطور که انتظار می‌رفت، رفتار خطی تابع removeIf() جاوا ۸ و رفتار نمایی روش قدیمی قابل مشاهده است.

blog2

یک نکته در مورد removeIf این است که پیاده‌سازی آن اتمیک است به این معنی که ابتدا ارزیابی روی همه آیتم‌ها صورت می‌گیرد قبل از اینکه تغییری بخواهد اعمال کند. بنابراین، اگر predicate خطایی برای هر آیتمی پرتاب کند، لیست تغییر نمی‌کند و ثابت می‌ماند.

و یک نکته در مورد رویکرد قدیمی (که در گروه لینکدین انجمن مطرح شد) این است که اگر ترتیب در لیست اهمیت نداشته باشد حذف عنصر iام از لیست با کد زیر در O(1) می‌تواند انجام گیرد.

منبع:

https://dzone.com/

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

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

‫۲ نظرها

  1. سلام
    با تشکر از مقالات خوبی که روی سایت قرار می دهید
    این یکی با توجه به مطلب قبلی که خودتون هم بهش لینک دادین، نکته ی جدیدی نداشت، تقریبا تکراری بود

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

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

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