پیچیدگی زمانی عملیات جاوا روی انواع ساختمان داده — به زبان ساده

۳۱۸ بازدید

آخرین به‌روزرسانی: ۰۶ شهریور ۱۴۰۲

زمان مطالعه: ۷ دقیقه

پیچیدگی زمانی عملیات جاوا روی انواع ساختمان داده — به زبان ساده

در این مقاله در مورد عملکرد کلکسیون‌های مختلف مربوط به API Collection جاوا صحبت می‌کنیم. زمانی که از کلکسیون‌ها سخن می‌گوییم، معمولاً یاد ساختمان‌های داده List ،Map و Set و پیاده‌سازی‌های رایج آن‌ها میافتیم. قبل از هر چیز، به مفهوم پیچیدگی O بزرگ برای عملیات رایج می‌پردازیم و سپس برخی اعداد واقعی از عملیات کلکسیون در زمان اجرا ارائه خواهیم کرد. بنابراین با ما همراه باشید تا پیچیدگی زمانی عملیات جاوا روی انواع ساختمان داده را به زبان ساده توضیح دهیم.

فهرست مطالب این نوشته

پیچیدگی زمانی

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

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

برای یادگیری موارد بیشتر در مورد نمادگذاری O بزرگ پیشنهاد می‌کنیم از مطلب زیر بازدید نمایید:

پیچیدگی زمانی الگوریتم‌های مرتب‌سازی با نماد O بزرگ — به زبان ساده

ساختمان داده List

کار خود را با لیست ساده آغاز می‌کنیم که یک کلکسیون مرتب است. در ابن بخش به بررسی عملکرد پیاده‌سازی‌های ArrayList, LinkedList و CopyOnWriteArrayList می‌پردازیم.

ArrayList

ArrayList در جاوا توسط یک آرایه پشتیبانی می‌شود. بدین ترتیب می‌توانیم منطق درونی پیاده‌سازی آن را درک کنیم. بدین ترتیب ابتدا روی پیچیدگی زمانی عملیات رایج در سطح بالا متمرکز می‌شویم:

add()‎ – مدت زمان O(1)‎ طول می‌کشد.
(add(index, element – به طور میانگین در مدت زمان O(n)‎ اجرا می‌شود.
()‎get – همواره دارای زمان ثابت O(1)‎‎ است.
remove()‎ – با زمان خطی (‎O(n اجرا می‌شود. ما باید روی کل آرایه بچرخیم تا عنصری که شرایط حذف را دارد پیدا کنیم.
indexOf()‎ – این عملیات نیز دارای زمان اجرای خطی است. این عملیات روی کل آرایه می‌چرخد و هر عنصر را یک به یک بررسی می‌کند، بنابراین پیچیدگی زمانی این عملیات همواره O(n)‎ است.
contains()‎ – پیاده‌سازی آن بر مبنای indexOf()‎ است و از این رو زمان مورد نیاز آن نیز O(n)‎ است.

CopyOnWriteArrayList

این پیاده‌سازی از اینترفیس List زمانی که مشغول کار با اپلیکیشن‌های چند نخی هستیم بسیار مفید است، چون دارای ویژگی «ایمنی نخ» (‎(thread-safe است.

در ادامه عملکرد O بزرگ را برای CopyOnWriteArrayList می‌بینید:

()add – به مقداری اضافه کرده‌ایم بستگی دارد و از این رو پیچیدگی آن O(n)‎ است.
()get – عملیات با ثابت زمانی O(1)‎ است.
()remove – مدت زمان O(n)‎ طول می‌کشد.
()contains – به طور مشابه پیچیدگی آن O(n)‎ است.

چنان که می‌بینید استفاده از کلکسیون به دلیل مشخصه‌های عملکردی متد add()‎ بسیار پرهزینه است.

LinkedList

«لیست پیوندی» (LinkedList) یک ساختمان داده خطی است که شامل گره‌هایی برای نگهداری فیلدهای داده و ارجاعی به گره‌های دیگر است. برای کسب اطلاعات بیشتر در مورد لیست‌های پیوندی به لینک زیر مراجعه کنید:

لیست پیوندی یک‌طرفه، دوطرفه و حلقوی — ساختمان داده و الگوریتم‌ها

در ادامه زمان تخمینی میانگین مورد نیاز برای اجرای برخی از عملیات ابتدایی را مشاهده می‌کنید:

()Add – درج در هر موقعیت از پیچیدگی زمانی (O(1 برخوردار است.
()Get – جستجو به دنبال عناصر، زمان (O(n طول می‌کشد.
()remove – حذف یک عنصر نیز به زمان (O(1 نیاز دارد، چون موقعیت عنصر ارائه شده است.
()contains – این عملیات دارای پیچیدگی زمانی خطی (O(n است.

گرم کردن JVM

اینک برای اثبات تئوری، کمی با داده‌های واقعی کار می‌کنیم. به عبارت دقیق‌تر نتایج تست JMH یعنی Java Microbenchmark Harness را برای اغلب عملیات رایج کلکسیون ارائه می‌کنیم.

ابتدا پارامترهای اصلی تست‌های بنچمارک را ارائه می‌کنیم:

1@BenchmarkMode(Mode.AverageTime)
2@OutputTimeUnit(TimeUnit.MICROSECONDS)
3@Warmup(iterations = 10)
4public class ArrayListBenchmark {
5}

سپس تعداد تکرارهای گرم کردن را روی 10 تعیین می‌کنیم. ضمناً می‌خواهیم زمان اجرای میانگین نتایج نمایش یافته را بر حسب میکروثانیه ببینیم.

تست‌های بنچمارک

اینک زمان آن رسیده است که تست‌های بنچمارک را اجرا کنیم. ابتدا با ArrayList آغاز می‌کنیم:

1@State(Scope.Thread)
2public static class MyState {
3 
4    List<Employee> employeeList = new ArrayList<>();
5 
6    long iterations = 100000;
7 
8    Employee employee = new Employee(100L, "Harry");
9 
10    int employeeIndex = -1;
11 
12    @Setup(Level.Trial)
13    public void setUp() {
14        for (long i = 0; i < iterations; i++) {
15            employeeList.add(new Employee(i, "John"));
16        }
17 
18        employeeList.add(employee);
19        employeeIndex = employeeList.indexOf(employee);
20    }
21}

درون ArrayListBenchmark کلاس State را برای نگهداری از داده‌های اولیه اضافه می‌کنیم.

در این بخش یک ArrayList از اشیای Employee می‌سازیم. پس از اقدام به مقداردهی آن با 100،000 آیتم درون متد ()setUp می‌کنیم. State‎@ نشان می‌دهد که تست‌های Benchmark‎@ دسترسی کاملی به متغیرهای اعلان‌شده در همان نخ دارند.

در نهایت نوبت آن می‌رسد که تست‌های بنچمارک را برای متدهای ()add() ،contains() ،indexOf() ،remove و ()get اضافه کنیم:

1@Benchmark
2public void testAdd(ArrayListBenchmark.MyState state) {
3    state.employeeList.add(new Employee(state.iterations + 1, "John"));
4}
5 
6@Benchmark
7public void testAddAt(ArrayListBenchmark.MyState state) {
8    state.employeeList.add((int) (state.iterations), new Employee(state.iterations, "John"));
9}
10 
11@Benchmark
12public boolean testContains(ArrayListBenchmark.MyState state) {
13    return state.employeeList.contains(state.employee);
14}
15 
16@Benchmark
17public int testIndexOf(ArrayListBenchmark.MyState state) {
18    return state.employeeList.indexOf(state.employee);
19}
20 
21@Benchmark
22public Employee testGet(ArrayListBenchmark.MyState state) {
23    return state.employeeList.get(state.employeeIndex);
24}
25 
26@Benchmark
27public boolean testRemove(ArrayListBenchmark.MyState state) {
28    return state.employeeList.remove(state.employee);
29}

نتایج تست

همه نتایج بر حسب میکروثانیه ارائه شده‌اند:

1Benchmark                        Mode  Cnt     Score     Error
2ArrayListBenchmark.testAdd       avgt   20     2.296 ±   0.007
3ArrayListBenchmark.testAddAt     avgt   20   101.092 ±  14.145
4ArrayListBenchmark.testContains  avgt   20   709.404 ±  64.331
5ArrayListBenchmark.testGet       avgt   20     0.007 ±   0.001
6ArrayListBenchmark.testIndexOf   avgt   20   717.158 ±  58.782
7ArrayListBenchmark.testRemove    avgt   20   624.856 ±  51.101

از روی نتایج فوق می‌فهمیم که متدهای ()testContains و ()testIndexOf تقریباً زمان اجرای یکسانی دارند. همچنین به وضوح می‌بینیم که تفاوت عظیمی بین نمرات متد ()testAdd و ()testGet از بقیه نتایج وجود دارد. افزودن یک عنصر باعث می‌شود که 2.296 میکروثانیه طول بکشد و دریافت آن نیز در طی زمان 0.007 میکروثانیه صورت می‌گیرد.

با این که زمان جستجو یا حذف یک عنصر تقریباً 700 میکروثانیه است، این اعداد اثباتی بر بخش نظری قبلی هستند که فهمیدیم پیچیدگی زمانی ()add و ()get به مقدار (O(1 و برای عملیات دیگر به مقدار (O(n است که در این مثال از n=10000 استفاده شده است.

به طور مشابه، می‌توانیم همین تست‌ها را برای کلکسیون CopyOnWriteArrayList بنویسیم. تنها چیزی که نیاز داریم جایگزینی ArrayList در employeeList با وهله CopyOnWriteArrayList است.

در ادامه نتایج بنچمارک را می‌بینید:

1Benchmark                          Mode  Cnt    Score     Error
2CopyOnWriteBenchmark.testAdd       avgt   20  652.189 ±  36.641
3CopyOnWriteBenchmark.testAddAt     avgt   20  897.258 ±  35.363
4CopyOnWriteBenchmark.testContains  avgt   20  537.098 ±  54.235
5CopyOnWriteBenchmark.testGet       avgt   20    0.006 ±   0.001
6CopyOnWriteBenchmark.testIndexOf   avgt   20  547.207 ±  48.904
7CopyOnWriteBenchmark.testRemove    avgt   20  648.162 ± 138.379

در این مورد نیز یک بار دیگر نتایج، تئوری را اثبات می‌کنند. چنان که می‌بینیم ()testGet به صورت میانگین در مدت زمان 0.006 میکروثانیه اجرا می‌شود و می‌توانیم آن را O(1)‎ تصور کنیم. در مقایسه با ArrayList نیز متوجه تفاوت زیادی بین نتایج متد ()testAdd می‌شویم. از آنجا که در اینجا پیچیدگی O(n)‎ را برای متد ()add در برابر مقدار (O(1 برای ArrayList داریم.

به روشنی شاهد یک رشد خطی زمان هستیم، چون عملکرد عدد 878.166 را در مقایسه با 0.051 نمایش می‌دهد.

اینک نوبت به LinkedList می‌رسد:

1Benchmark        Cnt     Score       Error
2testAdd          20     2.580        ± 0.003
3testContains     20     1808.102     ± 68.155
4testGet          20     1561.831     ± 70.876 
5testRemove       20     0.006        ± 0.001

از روی نمرات می‌توان فهمید که افزودن و حذف عناصر در لیست پیوندی کاملاً سریع است. به علاوه یک شکاف عملکردی مهم بین عملیات add/remove و get/contains وجود دارد.

ساختمان داده Map

در جدیدترین نسخه‌های JDK شاهد بهبود عملکرد قابل توجهی برای پیاده‌سازی‌های Map هستیم که شامل جایگزینی با ساختمان گره درخت متعادل متوازن در پیاده‌سازی‌های درونی HashMap و LinkedHashMap می‌شود. این کار موجب کاهش زمان بدترین سناریوهای گشتن به دنبال عنصر از (‎O(n به O(log(n))‎ در زمان تصادم HashMap شده است.

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

با این حال در صورت پیاده‌سازی مناسب احتمال تصادم ()equals و ()hashcode بسیار پایین است.

لازمه به ذکر است که زمان بازیابی و ذخیره‌سازی عناصر در HashMap به صورت (O(1 است.

تست کردن عملیات (O(1

اینک به بررسی مثال‌های واقعی می‌پردازیم. ابتدا HashMap را بررسی می‌کنیم:

1Benchmark                         Mode  Cnt  Score   Error
2HashMapBenchmark.testContainsKey  avgt   20  0.009 ± 0.002
3HashMapBenchmark.testGet          avgt   20  0.011 ± 0.001
4HashMapBenchmark.testPut          avgt   20  0.019 ± 0.002
5HashMapBenchmark.testRemove       avgt   20  0.010 ± 0.001

چنان که می‌بینیم اعداد ثابت می‌کنند که زمان ثابت O(1)‎ برای اجرای متدهای فوق وجود دارد. اینک نمرات تست HashMap را با نمرات وهله دیگری از Map مقایسه می‌کنیم.

در مورد همه متدهای لیست شده برای HashMap ،LinkedHashMap ،IdentityHashMap ،WeakHashMap ،EnumMap و ConcurrentHashMap با زمان ثابت O(1) ‎ مواجه هستیم.

در ادامه نتایج نمرات باقی‌مانده تست را به شکل جدول مشاهده می‌کنید:

1Benchmark      LinkedHashMap  IdentityHashMap  WeakHashMap  ConcurrentHashMap
2testContainsKey    0.008         0.009          0.014          0.011
3testGet            0.011         0.109          0.019          0.012
4testPut            0.020         0.013          0.020          0.031
5testRemove         0.011         0.115          0.021          0.019

از روی اعداد خروجی می‌توان تأیید کرد که ادعای پیچیدگی زمانی O(1)‎ در این مورد صحیح است.

تست کردن عملیات O(log(n))‎

در مورد ساختمان درخت TreeMap و ConcurrentSkipListMap، عملیات ()put() ،get() ،remove و ()containsKey دارای پیچیدگی زمانی O(log(n))‎ است.

در این بخش می‌خواهیم مطمئن شویم که تست‌های عملکردی ما تقریباً در زمان لگاریتمی اجرا می‌شوند. به همین جهت map-ها را به صورت پیوسته با n=1000, 10,000, 100,000, 1,000,000 آیتم مقداردهی می‌کنیم.

در این حالت به زمان کلی اجرا علاقه‌مند هستیم.

1items count (n)         1000      10,000     100,000   1,000,000
2all tests total score   00:03:17  00:03:17   00:03:30  00:05:27

زمانی که n=1000 است، زمان کلی اجرا بر حسب میلی‌ثانیه برابر با 00:03:17 است. در تعداد آیتم n=10,000 زمان تقریباً بدون تغییر و برابر با 00:03:18 میلی‌ثانیه است. در تعداد n=100000، زمان اجرا به 00:03:30 افزایش می‌یابد. در نهایت زمانی که n = 1000000 می‌شود، زمان اجرا برابر با 00:05:27 میلی‌ثانیه خواهد بود.

پس از مقایسه اعداد، زمان اجرای با تابع (log(n برای هر n، می‌توان تأیید کرد که محاسبه هر دو تابع با هم مطابقت دارند.

ساختمان داده Set

به طور کلی Set یک کلکسیون با عناصر یکتا است. در این بخش قصد داریم پیاده‌سازی HashSet ،LinkedHashSet، EnumSet ،TreeSet ،CopyOnWriteArraySet و ConcurrentSkipListSet از اینترفیس Set را بررسی کنیم.

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

اینک مستقیماً به سراغ بررسی اعداد پیچیدگی زمانی می‌رویم. پیچیدگی زمانی برای عملیات ()add() ،remove و ()contains برای HashSet ،LinkedHashSet و EnumSet به صورت ثابت (O(1 است. این واقعیت به لطف پیاده‌سازی داخلی HashMap رخ داده است.

به طور مشابه پیچیدگی زمانی TreeSet برای عملیات لیست شده فوق به صورت ((O(log(n است. دلیل این امر به پیاده‌سازی TreeMap بازمی‌گردد. پیچیدگی زمانی برای ConcurrentSkipListSet نیز برابر با ((O(log(n است چون بر مبنای رد کردن ساختمان داده List طراحی شده است.

متدهای ()add() ،remove و ()contains برای CopyOnWriteArraySet دارای پیچیدگی زمانی میانگین (O(n است.

تست متدها

اینک به سراغ تست‌های بنچمارک خود می‌رویم.

1@Benchmark
2public boolean testAdd(SetBenchMark.MyState state) {
3    return state.employeeSet.add(state.employee);
4}
5 
6@Benchmark
7public Boolean testContains(SetBenchMark.MyState state) {
8    return state.employeeSet.contains(state.employee);
9}
10 
11@Benchmark
12public boolean testRemove(SetBenchMark.MyState state) {
13    return state.employeeSet.remove(state.employee);
14}

به علاوه پیکربندی بنچمارک را نیز همانند قبل و بدون تغییر بوده است.

مقایسه نتایج

در ادامه به مشاهده رفتار نمرات زمان اجرای HashSet و LinkedHashSet در هنگامی که n = 1000; 10,000; 100,000 آیتم است پرداخته‌ایم.

در مورد HashSet نتایج به صورت زیر هستند:

1Benchmark      1000    10,000    100,000
2.add()         0.026   0.023     0.024
3.remove()      0.009   0.009     0.009
4.contains()    0.009   0.009     0.010

به طور مشابه نتایج در مورد LinkedHashSet به صورت زیر هستند:

1Benchmark      1000    10,000    100,000
2.add()         0.022   0.026     0.027
3.remove()      0.008   0.012     0.009
4.contains()    0.008   0.013     0.009

چنان که مشاهده می‌شود، نمرات برای همه عملیات تقریباً یکسان باقی مانده است. حتی هنگامی که آن‌ها را با خروجی‌های تست HashMap مقایسه می‌کنیم، همچنان یکسان به نظر می‌رسند.

در نتیجه تأیید می‌شود که همه متدهای تست شده در زمان ثابت (O(1 اجرا شده‌اند.

سخن پایانی

در این مقاله پیچیدگی زمانی اغلب پیاده‌سازی‌های ساختمان‌های داده جاوا را مورد بررسی قرار دادیم. همچنین عملکرد زمان اجرای واقعی هر نوع از کلکسیون را از طریق تست‌های بنچمارک JVM نشان دادیم. ضمناً عملکرد عملیات یکسان را در کلکسیون‌های مختلف بررسی کردیم. در نتیجه اینک می‌توانیم برای رفع نیازهای خود بهترین کلکسیون مناسب را انتخاب کنیم. همه کدهای مربوط به این مقاله را می‌توانید در این ریپوی گیت‌هاب (+) ملاحظه کنید.

فیلم مجموعه آموزش جاوا Java – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

بر اساس رای ۰ نفر

آیا این مطلب برای شما مفید بود؟

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

ثبت نظر

منابع:

baeldung

میثم لطفی (+)

«میثم لطفی» در رشته‌های ریاضیات کاربردی و مهندسی کامپیوتر به تحصیل پرداخته و شیفته فناوری است. وی در حال حاضر علاوه بر پیگیری علاقه‌مندی‌هایش در رشته‌های برنامه‌نویسی، کپی‌رایتینگ و محتوای چندرسانه‌ای، در زمینه نگارش مقالاتی با محوریت نرم‌افزار با مجله فرادرس همکاری دارد.