მეჩხერი მარტიცის შენახვის ახალი ფორმატი და მისი ეფექტურობა

ავტორი: კობა გელაშვილი
თანაავტორები: ვახტანგ ლალუაშვილი, გიგა ჩალაური
საკვანძო სიტყვები: მეჩხერი მატრიცი, შეუღლებული გრადიენტის მეთოდი, შეკუშული მატრიცა-სტრიქონზე ორიენტირებული
ანოტაცია:

მეჩხერი მატრიცის წარმოდგენისთვის, ჩვენ ვინახავთ მის არანულოვან ელემენტებს დინამიკური მატრციცის სახით. აგრეთვე ვინახავთ ინდექსების მატრიცას, რომელიც ერთმანეთთან აკავშირებს ახალ ფორმატს და ტრადიციულ, მკვრივ მატრიცას. მეჩხერი მატრიცების შენახვის გავრცელებული ეფექტური ფორმატებისგან განსხვავებით, ვიყენებთ მეტ მეხსიერებას, თუმცა არაუმეტეს 2-ჯერ მეტს. თუმცა ახალი ფორმატი მკვრივი მატრიცის ფორმატთან შედარებით მაინც ბევრად ეკონომიურია. ახალი ფორმატის ეფექტურობის გარკვევისთვის, ვადარებთ გავრცელებულ იმისათვის, რომ შევაფასოთ ახალ ფორმატის ეფექტურობა სისწრაფის თვალსაზრისით, მას ვადარებთ boost ბიბლიოთეკის შეკუმშულ მატრიცას (სტრიქონზე ორიენტირებული). განვიხილავთ შეუღლებული გრადიენტის მეთოდს კვადრატული ფუნქციონალისთვის, შესაბამის პროგრამას ვუშვებთ 70 სხვადასხვა ზომის მეჩხერ მატრიცაზე, რომლებიც ამოღებულია ინტერნეტიდან. ვცვლით რა მონაცემთა სტრუქტურას, თითქმის ყველა ტესტზე ჩვენს მიერ შემოთავაზებული ფორმატი საგრძნობლად უკეთეს შედეგს გვაძლევს. შესაბამისი პროექტი შედგენილია C++ ენაზე. შეუღლებული გრადიენტების ალგორითმის კოდი ძალიან მარტივია, რთული და მოცულობითი არის ტესტების კოლექციასთან მუშაობის და პასუხების შენახვის ნაწილები.