გუშინ ერთ-ერთ ამოცანაში მეხსიერების ლიმიტს ვაჭარბებდი იმის გამო, რომ არასწორად მქონდა აღწერილი მრავალგანზომილებიანი მასივი. c-ში და c++-ში ამის პრობლემა არ იქნებოდა, თუმცა, იმის გამო, რომ ჯავაში ყველაფერი ობიექტია (პრიმიტიული ტიპების გარდა), მრავალგანზომილებიანი მასივების შექმნისას მეხსიერება განსხვავებული გზით უნდა დავითვალოთ.
მაგალითად ასეთი მასივის ზომა c++-ში 96 ბაიტია (32 ბიტიან სისტემაში):
int arr[2][3][4];
2 * 3 * 4 = 24. თითოეული კიდევ 4 ბაიტიანია int ტიპის გამო და ჯამში 24 * 4 = 96 ბაიტი გამოდის.
int arr[4][3][2] ასეთი აღწერის დროს შედეგი იგივეა.
შევადაროთ Java-ში ეს ორი აღწერა:
int arr[][][] = new int[40000][200][2];
int arr[][][] = new int[2][200][40000];
აზრობრივად განსხვავება არ არის, თუმცა პირველი გზა გაცილებით მეტ მეხსიერებას მოიხმარს. აი, რატომ:
1. ჯავას მასივი თავისთავად ობიექტია. თითოეულ ობიექტში (არა reference-თან, არამედ heap-ში) დამატებით რამდენიმე ბაიტს იკავებს სპეციალური object header ინფორმაცია. object header-ში ინახება ვირტუალური მანქანისთვის საჭირო მონაცემები, რასაც garbage collector-ისთვის და სხვადასხვა მიზნებისთვის იყენებს. როგორც ვიცი, ჩვეულებრივ ეს 8 ბაიტია ხოლმე 32-ბიტიან მანქანაზე და 16 ბაიტი 64-იანზე. ამის გარდა, მასივის ობიექტში ინახება მასივის ზომაც, ანუ დამატებით 4 ბაიტი. კიდევ შეიძება მეხსიერებაში padding-ს დასჭირდეს რამდენიმე ბაიტი. ამიტომ ზუსტად არ დავთვლი და ვთქვათ, ერთი მასივის ობიექტისთვის (ელემენტების გარდა) საჭიროა X ბაიტი.
2. int[a][b] – ჯავაში ეს არის a ცალი b ელემენტიანი მასივის მასივი, ანუ სინამდვილეში ერთის მაგივრად a+1 ობიექტი გვაქვს.
int[a][b][k]სამგანზომილებიანის შემთხვევაში a * b + a + 1 ცალი ობიექტი და ა.შ.
ახლა გამოვთვალოთ და შევადაროთ ზევით ნახსენები ორი მასივის ზომა:
(40,000 * 200 + 40,000 + 1) * X + (40,000 * 200 * 2 * 4)
(2 * 200 + 2 + 1) * X + (40,000 * 200 * 2 * 4)
მეორე ნაწილი რაც int ტიპის ელემენტების ზომას ითვლის, ცხადია, ორივესთვის ერთი და იგივე იქნება.
პირველი ნაწილის მიხედვით კი 8,039,598 ცალი ზედმეტი ობიექტი იქმნება პირველ შემთხვევაში, მეხსიერებაც შესაბამისად გაცილებით მეტი სჭირდება.
ისე, პროფაილერით ვერ ვხედავ სინამდვილეში მართლაც ამდენი ობიექტია თუ არა და იდეა ხომ არ გაქვთ როგორ შეიძლება შევამოწმო?
მშვენიერი პოსტი, როგორც ყოველთვის. მე ეს ვიცოდი ადრე, მაგრამ დამაინტერესა პროფაილერით მაგის დამტკიცების ამბავი.
ორაკლს აქვს ასეთი კარგი tool-ი – Java VisualVM. მაგით შეგიძლიათ ნებისმიერ ჯავა პროცესს მიუერთდეთ (მგონი სხვა მანქანაზეც კი, თუ გაშვებულია იქ რაღაც სერვერული ნაწილი) და ჩაიხედოთ რა ხდება ვირტუალური მანქანის იმ ინსტანციაში, რომელიც ამუშავებს ამ პროგრამას.
ტესტებისთვის დავწერე მარტივი პროგრამა, რომელიც ითვლის პასკალის სამკუთხედის წესით Cnk-ებს. პირველ ვარიანტში 1000000×100-ზეა მასივი, მეორე შემთხვევაში პირიქით. გავუშვათ პროგრამები და VisualVM-ით დავუკავშირდეთ, გადავიდეთ Monitor გვერდზე და დავაჭიროთ Heap Dump ღილაკს.
მოსალოდნელი სურათები დამხვდა:
პირველი (ცუდი ვარიანტი):
მეორე (კარგი):
როგორც ჩანს პირველ ვარიანტში int[] ტიპიც ობიექტი მილიონზე მეტია და ზედმეტი 16 მეგაბაიტი გამოიყოფა, რაც არც ისე ცოტაა.
ზოგადად მრავალგანზომილებიან მასივების აღწერა ჯერ პატარა და მერე დიდი განზომილებით წარმადობის მხრივაც კარგი იდეაა და ეს არა მარტო ჯავას ეხება. საქმე იმაშია, რომ მეხსიერება უფრო ეფექტურად მუშაობს როდესაც მიყოლებით განლაგებულ ელემენტებს მიმართავთ. პროგრამები საოლიმპიადო პრაქტიკიდან როგორც წესი შიდა ციკლებით დიდ განზომილებას მიმართავენ და თუ ეს იქნება პირველი განზომილება, მაშინ გამოდის რომ სულ აქა იქ მიმართავს პროცესორი და წარმადობა მნიშვნელოვნად ვარდება. დიახ, ამის გამო ჩამიგდია შეჯიბრზე სწორი ამოხსნა 🙂
ისე სგ, კაი ამოცანა ამოგიხსნია 🙂
მადლობა 🙂
ისე მთლად ჩემი დამსახურებაა არაა მაგის ამოხსნა.