Dynamic array is a data structure with variable length. One can insert, retrieve or delete an element using random access – i.e. it needs a fixed time to reach any element and this does not depend on whole size of the array.
You might come across this structure by different names – dynamic array, growable array, resizable array, dynamic table, mutable array, array list.
To guarantee random access, it is necessary to allocate a continuous memory for the array, i.e. its elements should be stored next to each other.
In case of a static array, this is not a problem, as we define the length in advance. But sometimes we don’t yet know the length. So, how much continuous memory should we allocate?
Clearly, there is no point for allocating huge memory just in case. We should not reserve million bytes in advance just to store 20 elements.
This is where dynamic array comes in. In many programming languages this problem is solved this way:
The dynamic array is backed by a static array, which is created in small size. When this static array is filled and users will try to add more elements, a larger static array will be created behind the scenes. Existing elements will be copied into it and the old one will be deleted. Consequently, insertion of some elements in the dynamic array will take more time than the others.
With this solution in mind, we should answer to an important question: By what factor should we increase the static array length?
It should be noted, that again we are searching for a balance between performance and memory waste. If we increase the array length with only one element, rewriting whole array on each new element will take too much time. But if we increase by a large factor, we might end up with a large empty array.
Optimal number is 2. This number might be slightly altered corresponding to requirements.
You might find its different versions in various programming languages – e.g. Vector in C++ is increased 2 times. Vector from Java standard library also has a factor 2, however you can change it by passing arguments. A static array of ArrayList in Java is increased by 3/2 times. A static array of HashMap – by 2 times. In the C implementation of Python, the number is a bit odd – approximately 9/8. Here is the source.. And here is an explanation.
If the programmer knows approximate size of an array in advance, they can configure the dynamic array correspondingly. E.g. Vector in C++ has a function reserve, which will reserve memory of given size.
ArrayList and HashMap classes in Java have a constructor parameter initialCapacity. In case of HashMap, not only static array is rewritten in the background, but the hashes are also regenerated.
If performance is critical, this parameter can be used. I carried out several experiments and saw the difference, however, in ordinary tasks this difference is not noticeable. Even in case of factor 2 and million elements, the arrays are rewritten only for 20 times.
In the beginning, I mentioned that some element insertion might take time from O(1) to O(n), where n is a total number of elements. Despite of this and based on amortized analysis, insertion time in a dynamic array is defined as O(1).
The idea of amortized analysis is to consider both, slow and fast operations of the algorithm. They might balance each other. While estimating an algorithm performance, we generally reach for the worst case scenario, but sometimes it is possible to calculate the ratio of expensive operations.
Let’s calculate the time for filling a dynamic array of n elements:
If we increase the length of an array by 2 times, we can estimate the number of rewrite like this:
Let’s start from the end. In the end it will need to rewrite all elements. Before that, only half of elements. Before that, quarter of elements, etc.
n + n/2 + n/4 + n/8 + … = n (1 + 1/2 + 1/4 + 1/8 + …) = 2n
Also, let’s add an insertion time of a new element and we get 3n. If we take an average, we will get O(3) = O(1) time for inserting an element.
საინტერესო სტატია, ერთ რაღაცას დავამატებდი,
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 წელია არ მილაპარაკნია ქართულად და მიჭირს აზრის ჩამოყალიბება 🙂