პროგრამირებაში დინამიური მასივი ისეთი მონაცემთა სტრუქტურაა, რომელსაც ცვლადი სიგრძე აქვს, მასში ელემენტების ჩამატება / წაშლა და random access შეიძლება – ანუ მის ნებისმიერ ელემენტზე წვდომას ფიქსირებული დრო სჭირდება და მასივის მთლიან ზომაზე არ არის დამოკიდებული.
ასეთ სტრუქტურას სხვადასხვა დასახელებით შეხვდებით – dynamic array, growable array, resizable array, dynamic table, mutable array, array list.
random access-ის უზრუნველსაყოფად მასივისთვის მეხსიერების უწყვეტი ნაწილი გამოიყოფა, ანუ, მისი ელემენტები მეხსიერებაში ერთმანეთის მიყოლებით ინახება.
სტატიკური მასივის შემთხვევაში ეს პრობლემას არ წარმოადგენს, რადგან ჩვენ თავიდანვე ვეუბნებით სიგრძეს. დინამიურ მასივს კი სწორედ მაშინ ვიყენებთ, როდესაც წინასწარ არ შეგვიძლია ზომის განსაზღვრა. მაშინ რამხელა მეხსიერება უნდა გამოიყოს, რომ ელემენტები კვლავ მიყოლებით არსებულ ბაიტებში იქნას შენახული?
ცხადია, თავის დაზღვევის მიზნით დიდი მეხსიერების გამოყოფას აზრი არ აქვს. 20 ელემენტის შენახვისთვის მილიონი ბაიტი წინასწარ არ უნდა დარეზერვდეს ასეთი მასივისთვის, რომელიც შემდეგ ცარიელი დარჩება.
ბევრ პროგრამირების ენაში ეს პრობლემა შემდეგნაირად არის გადაწყვეტილი:
დინამიური მასივის უკან სტატიკური მასივი დგას, რომელიც დასაწყისში მცირე სიგრძის მითითებით იქმნება. როდესაც მასივი გაივსება და შემდეგ კვლავ შეეცდებიან მასში ელემენტის ჩამატებას, შეიქმნება უფრო დიდი ზომის სტატიკური მასივი, მასში გადაიწერება არსებული მასივის ელემენტები და ძველი წაიშლება. შესაბამისად, დინამიურ მასივში ზოგიერთი ელემენტის ჩამატებას შედარებით მეტი დრო მიაქვს.
ასეთ გადაწყვეტაში მნიშვნელოვანია შეკითხვაზე პასუხი: რამდენჯერ უნდა გაიზარდოს მასივი გადაწერის წინ?
აღვნიშნოთ, რომ ისევ კომპრომისს ვეძებთ დროის და მეხსიერების ხარჯვას შორის. თუ თითო-თითოდ გავზრდით მასივს, ყოველ ახალ ელემენტზე მთელი მასივის გადაწერა დროს წაიღებს, ხოლო თუ რამდენჯერმე დავაგრძელებთ, შეიძლება დიდი ზომის მეხსიერება ცარიელი დაგვრჩეს.
ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული. ამ რიცხვს ზრდიან ამ ამცირებენ იმის მიხედვით მეტი მეხსიერების ხარჯი ურჩევნიათ თუ დროის.
სხვადასხვა პროგრამირების ენაში ან რეალიზაციაში ის ზოგჯერ განსხვავებულია – მაგალითად, ვექტორი c++-ში 2-ჯერ იზრდება, Java-ს ვექტორისთვისაც default მნიშვნელობა ეს რიცხვია, თუმცა პარამეტრის სახით არის და შეცვლა შეიძლება. Java-ს ArrayList-ის სტატიკური მასივი 3/2-ჯერ იზრდება. HashMap-ის მასივი 2-ჯერ. პითონის C-ის იმპლემენტაციაში რაღაც უცნაურად არის, 9/8 გამოდის საშუალოდ. ამ ბმულზეა კოდი. აქ კი მისი გარჩევა
თუ პროგრამისტისთვის წინასწარ არის ცნობილი მინიმუმ რამხელა მასივი დასჭირდება, შეუძლია ეს გაითვალისწინოს და დინამიური მასივი თავიდანვე იმხელა შეიქმნას.
მაგალითად c++-ის vector-ს აქვს ფუნქცია reserve რომლითაც წინასწარ შეიძლება მეხსიერების რეზერვირება.
Java-ში ArrayList და HashMap ობიექტებს კონსტრუქტორში გადაეცემა initialCapacity პარამეტრი. HashMap-ში არა მხოლოდ მასივის გადაწერა, არამედ ჰეშების თავიდან გენერაცია ხდება.
წარმადობისთვის ამ პარამეტრის წინასწარ მითითება უმჯობესია. რამდენიმე ექსპერიმენტი ჩავატარე და მართლაც მივიღე დროში სხვაობა, თუმცა ჩემს ჩვეულებრივ ამოცანებში ასეთი სხვაობა უმნიშვნელოა. ბოლო ბოლო ლოგარითმული რაოდენობით ხდება მასივის გადაწერა და მილიონის შემთხვევაშიც კი ეს სულ რაღაც 20-ია. თუ მილიწამები მნიშვნელოვანია, იქ ღირებული იქნება ასეთი ოპტიმიზაცია.
ზევით ვახსენეთ, რომ დინამიურ მასივში ამ გადაწერის საჭიროების შედეგად ზოგიერთი ელემენტის ჩამატების დროს O(1)-დან იზრდება O(n)-მდე, სადაც n მასივში არსებული ელემენტების რაოდენობაა. ამის მიუხედავად, ამორტიზებული ანალიზის შედეგად, დინამიურ მასივში ელემენტის ჩამატების დრო O(1)-ად არის მიჩნეული.
თვითონ ამორტიზებული ანალიზის არსი იმაში მდგომარეობს, რომ ალგორითმის მუშაობის შეფასებისას გათვალისწინებული იქნას ის სწრაფი ოპერაციებიც, რომელიც ყველაზე ცუდი შემთხვევების მუშაობის დროს აბათილებენ. ალგორითმის შესრულების დროის შეფასებისას worst-case სცენარს ვიღებთ ხოლმე, თუმცა შეიძლება რომ დასამუშავებელ ინფორმაციაში მხოლოდ რაღაც პროპორციით იყოს მძიმე ოპერაციები. შესაბამისად, თუ ჩვენ ყველა ოპერაციას გავითვალისწინებთ შეფასების დროს, შესაძლოა მუშაობის დრო გაცილებით ნაკლები გამოვიდეს, ვიდრე რაოდენობა გამრავლებული ყველაზე დიდ დროზე.
მოდი გამოვთვალოთ n ელემენტიანი დინამიური მასივის შევსების დრო:
თუ ჩავთვლით რომ ყოველ ჯერზე (როდესაც ორის ხარისხს მივაღწევთ) სტატიკური მასივი ორმაგდება, შეგვიძლია ელემენტების გადაწერის რაოდენობა ასე შევაფასოთ:
ბოლოდან მოვყვეთ. ბოლოს ყველას გადაწერა მოუწევს, იმის წინ მხოლოდ ნახევრის, იმის წინ მეოთხედის და ა.შ.
n + n/2 + n/4 + n/8 + … = n (1 + 1/2 + 1/4 + 1/8 + …) = 2n
ამ გადაწერებს მივუმატოთ თვითონ ელემენტების ჩასმაც და გამოვა 3n. შესაბამისად საშუალოს თუ ავიღებთ, თითოეული ელემენტის ჩასმისთვის გამოგვივა O(3) = O(1) დრო.
საინტერესო სტატია, ერთ რაღაცას დავამატებდი,
initialCapacity -ის მითითება ასევე საჭიროა, რომ ავირიდოთ ზედმეტი მეხსიერების გამოყოფა. ამ პარამეტრის მითითების გარეშე ძლიან ადვილია გამოიყოს ორჯერ იმაზე მეტი მეხსიერება ვიდრე გვჭირდება.
“ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული.” BTW საინტერესო იქნებოდა ექსპერიმენტები ჩაგეტარებინა კოეფიციენტის სხვა მნიშვნელობებზე და followup პოსტიც გამოგეცხო შედეგების შესახებ 🙂
@რაჭველა
🙂 ვცადე რაღაც ექსპერიმენტები, მაგრამ ისე არ გამომივიდა როგორც მინდოდა. განსხვავებულ შედეგებს ვიღებდი ხოლმე. როგორც ჩანს ხან garbage collector-ი მიშლის ან კიდევ კომპილატორის ოპტიმიზაციები. ბოლოს netbeans-ის პროფაილერი ვცადე მაგრამ იქ ზედმეტად დეტალური ინფორმაციაა (ბევრი კლასით) და კარგად ვერ გავერკვიე.
შენ ხომ არ მირჩევ რამე გზას რითიც შემიძლია ჯავას ბენჩმარკები ვაკეთო?
C#შიც List ორჯერ იზრდება, კონსტრუქტორს InitialCapacity შეგიძლია მიუთითო.
აქ მეორე მომენტიც არის გამოსაყოფი ალბათ, ეს არის ის შემთხვევა როდესაც შენ გაგეზარდა კოლექცია და შესაბამისი უკან მყოფი მასივიც გაიზარდა, ეს გასაგებია. მაგრამ მოხდა ისე რომ კოლექცია ნელ-ნელა დაიცალა. შეიძლება მიხვიდე იმ მომენტამდე რომ შენ გაქვს მასივი რომელსაც აქვს საკმაოდ დიდი მეხსიერება დაკავებული, და ამ დროს რეალურად ინფორმაცია წერია მის მხოლოდ მცირე ნაწილში. ამ შემთხვევაში კარგი იქნებოდა რომ მასივი ისევ დაპატარევებულიყო.
პირველი რაც მოგდის თავში არის ის რომ, რადგანაც, მასივი ზომაში ორჯერ იზრდება, ლოგიკური იქნებოდა მისი ორჯერ შემცირება მისი ნახევრად დაცარიელების შემთხვევაში
მაგრამ ეს ქმნის ერთ პატარა ხვრელს:
თუ მოხდა ისე რომ კოლექცია არის ნახევრად სავსე და იუზერი აკეთებს ჩამატება-წაშლა-ჩამატება-წაშლა ოპერაციებს, შენი ლოგიკის მიხედვით თითოეული ეს მოქმედება იწევს მასივის გადიდება-შემცირებას.
Count=5 [A] [B] [C] [D] [E] [null] [null] [null] [null] [null] Capacity = 10
Count = 4 [A] [B] [C] [D] [null] Capacity = 5
Count = 5 [A] [B] [C] [D] [E] [null] [null] [null] [null] [null] Capacity = 10
Count = 4 [A] [B] [C] [D] Capacity = 5
ამიტომ მასივის შეკვეცა უფრო ლოგიკური იქნებოდა როდესაც იგი იქნება 25% ან 30% ით სავსე. ამ შემთხვევაში შენ გარანტია გაქვს რომ მასივი აუცილებლად შევსებული იქნება 25%(30%)-100%მდე.
C#ის კოლექციებში ავტომატურად მასივის შეკვეცა მგონი არ ხდება, მაგრამ გაქვს ფუნქცია, რომელიც საშუალებას მართო ასეთი სიტუაციები http://msdn.microsoft.com/en-us/library/ms132207.aspx
სხვა ენებში როგორ ხდება ეს ამბავი არ ვიცი.
სასარგებლო პოსტი იყო, მოხარული ვიქნებოდი უფრო ხშირად რომ გეწერა 😉
@kashma
კარგი შენიშვნაა. მე სულ არ მიფიქრია მაგაზე.
კოდში გადავამოწმე და ვერ ვნახე რომ ჯავას ArrayList ავტომატურად ამცირებდეს ზომას. ისე, მსგავსი ფუნქცია ამასაც აქვს, ზედმეტი ადგილი რომ გაათავისუფლოს – trimToSize();
ArrayList ჯავაში ნახევარჯერ იზრდება, Default სიდიდის ნახევარჯერ ან გადაწოდებული სიდიდის ნახევარჯერ, მეხსიერების კონტროლის მხრივ არც ისე სუსტია თუ გავითვალისწინებთ იმასაც, რომ TrimToSize მეთოდი სიდიდეს აბრუნებს იმ ჩარჩოებში რამდენი ელემენტიც იმყოფება კოლექციაში, Time Complexity-ს თუ გავითვალისწინებთ, შევსებამდე კონსტანტურ დროში მუშაობს გადაწერის მომენტში O(n) ალგორითმში რაც არც ისე დიდი მსხვერპლია ზურგს უკან სტატიკურად დეფინირებულ მასივს თუ გავიხსენებთ. ნუ ახალს არაფერს ვამბობ, ვეკტორსაც იგივე პრობლემები აქვს, თუმცა იდეალური გამოსავალი LoadFactory გახლავთ, რომელიც ზრდის მასივს როდესაც ის გარკვეულ %-მდე იზრდება რაც გარანტირებულ კონსტანტურ დროს გვაძლევს ახალი ელემენტის დამატების დროს. პერფომანსში არაფრით ჩამოუვარდება დაკავშირებულ სიაზე ელემენტის დამატებას :))))
ნახევარჯერ რატო? 🙂 1/2-ჯერ გაზრდა ხო განახევრებას ნიშნავს. 3/2-ჯერ იზრდება და ამორტიზებული შეფასებით მაინც O(1) არის ელემენტის ჩასმის დრო. წინასწარ თუ ცნობილია დატვირთვა, მაშინ კი მისცემ load factor-ს, მარა მე მგონი ძალიან სპეციალურ შემთხვევებში აქვს ხოლმე აზრი.
მეც მაგას ვამბობ, სიდიდე იზრდება არსებული სიდიდის ნახევარით, მაგალითად საწყისი Default Size = 10; როდესაც 10 ადგილი ივსება სიდიდე იზრდება Default_Size + (newSize>>1). 1 right shift გამოდის 5. (არსებული სიდიდის 50 %) 10 ელემენტის შევსებამდე მუშაობს O(1) კონსტანტური ალგორითმით, მაგრამ სიდიდის გაზრდას ყველა შევსებაზე ჭირდება O(n) ალგორითმი, იმიტომ რომ არასდროს არ ვიცით რა რაოდენობის ელემენტებთან გვიწევს მუშაობა და გადაწერის პროცესში სისტემას მთლიანი სტრუკტურის წაკითხვა და კოპირება უწევს, გამომდინარე აქედან დამატების მეთოდი ორივე ალგორითმის მატარებელია როგორც კონსტანტურის ისე წრფივის. ჯავას დეველოპერებს თუ დაუჯერებთ ოპტიმალური ვარიანტია სიდიდე გაიზარდოს 75 % -ით, ოპტიმალური როგორც Space Complexity ის Time Compexity-ის კუთხით. სპეციფიურ შემთხვევას რას ეძახი არ ვიცი მაგრამ ჩემი აზრით ნებისმიერი სიტუაცია სპეციფიურია, კოდმა მოთხოვნას უნდა გაუძლოს ყველაზე ცუდ შემთხვევებში. ყველაზე კარგი შემთხვევები, ან თუნდაც საშუალო შემთხვევები ნაკლებად საინტერესოა როგორც წესი.
🙂 ანუ ვხვდები რისი თქმაც გინდა, მაგრამ ჩემი აზრით გეშლება თარგმანი დოკუმენტაციიდან.
კი, ნახევრით და არა ნახევარჯერ. 🙂
ასევე 75%-ით არა. load factor არის მნიშვნელობა, თუ რამხელაზე უნდა იყოს მასივი შევსებული, რომ გაზრდა დაიწყოს (https://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html). default რაც აყენია – 0.75 ოპტიმალური load factor ნიშნავს, რომ 10 ადგილიან მასივში მერვე ელემენტის ჩაწერისას მასივი 1.5-ჯერ გაიზრდება და გადაკოპირება მოხდება.
სპეციფიური იმიტომ ვთქვი, რომ მაგალითად მე ჯერ არცერთ პროგრამაში არ დამჭირვებია default load factor-ის შეცვლა და არაფერ გავლენას არ ახდენდა წარმადობაზე ჩემს შემთხვევაში.
ხოლო დროის შეფასებას რაც შეეხება, ცალცალკე რომ აიღო კონკრეტული ჩასმები – კი, ერთს შეიძლება O(1) დასჭირდეს და მეორეს O(n), მაგრამ ყველა ჩასმის დრო რომ გაასაშუალო (აი სტატიის ბოლოს რომ წერია, ამორტიზებული შეფასებით), 2-ჯერ გაზრდის შემთხვევაში თითო ჩასმის საშუალო დრო გამოდის O(3) ანუ მაინც O(1).
კარგია რო გაუგეთ ერთმანეთს. მომიტევე ჩემი ქართულისთვის 7 წელია არ მილაპარაკნია ქართულად და მიჭირს აზრის ჩამოყალიბება 🙂