დინამიური მასივი

პროგრამირებაში დინამიური მასივი ისეთი მონაცემთა სტრუქტურაა, რომელსაც ცვლადი სიგრძე აქვს, მასში ელემენტების ჩამატება / წაშლა და 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) დრო.

გამოხმაურება

comments

4 thoughts on “დინამიური მასივი

  • 24 ოქტომბერი, 2012 at 21:34
    Permalink

    საინტერესო სტატია, ერთ რაღაცას დავამატებდი,
    initialCapacity -ის მითითება ასევე საჭიროა, რომ ავირიდოთ ზედმეტი მეხსიერების გამოყოფა. ამ პარამეტრის მითითების გარეშე ძლიან ადვილია გამოიყოს ორჯერ იმაზე მეტი მეხსიერება ვიდრე გვჭირდება.

    “ოპტიმალურ ვარიანტად რიცხვი 2 არის მიღებული.” BTW საინტერესო იქნებოდა ექსპერიმენტები ჩაგეტარებინა კოეფიციენტის სხვა მნიშვნელობებზე და followup პოსტიც გამოგეცხო შედეგების შესახებ 🙂

    Reply
  • 25 ოქტომბერი, 2012 at 11:39
    Permalink

    @რაჭველა
    🙂 ვცადე რაღაც ექსპერიმენტები, მაგრამ ისე არ გამომივიდა როგორც მინდოდა. განსხვავებულ შედეგებს ვიღებდი ხოლმე. როგორც ჩანს ხან garbage collector-ი მიშლის ან კიდევ კომპილატორის ოპტიმიზაციები. ბოლოს netbeans-ის პროფაილერი ვცადე მაგრამ იქ ზედმეტად დეტალური ინფორმაციაა (ბევრი კლასით) და კარგად ვერ გავერკვიე.
    შენ ხომ არ მირჩევ რამე გზას რითიც შემიძლია ჯავას ბენჩმარკები ვაკეთო?

    Reply
  • 27 ოქტომბერი, 2012 at 16:27
    Permalink

    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
    სხვა ენებში როგორ ხდება ეს ამბავი არ ვიცი.

    სასარგებლო პოსტი იყო, მოხარული ვიქნებოდი უფრო ხშირად რომ გეწერა 😉

    Reply
  • 13 ნოემბერი, 2012 at 19:20
    Permalink

    @kashma
    კარგი შენიშვნაა. მე სულ არ მიფიქრია მაგაზე.
    კოდში გადავამოწმე და ვერ ვნახე რომ ჯავას ArrayList ავტომატურად ამცირებდეს ზომას. ისე, მსგავსი ფუნქცია ამასაც აქვს, ზედმეტი ადგილი რომ გაათავისუფლოს – trimToSize();

    Reply

კომენტარის დატოვება

თქვენი ელფოსტის მისამართი გამოქვეყნებული არ იყო. აუცილებელი ველები მონიშნულია *