მრავალგანზომილებიანი მასივი Java-ში

გუშინ ერთ-ერთ ამოცანაში მეხსიერების ლიმიტს ვაჭარბებდი იმის გამო, რომ არასწორად მქონდა აღწერილი მრავალგანზომილებიანი მასივი. 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 ცალი ზედმეტი ობიექტი იქმნება პირველ შემთხვევაში, მეხსიერებაც შესაბამისად გაცილებით მეტი სჭირდება.

ისე, პროფაილერით ვერ ვხედავ სინამდვილეში მართლაც ამდენი ობიექტია თუ არა და იდეა ხომ არ გაქვთ როგორ შეიძლება შევამოწმო?

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

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

რჩევები საიტის ოპტიმიზაციისთვის (Front end)

დაახლოებით ერთი თვის წინ GeOlymp-ის საიტის გარეგნული მხარე განვაახლეთ თუმცა ბრაუზერის მხარეს სწრაფად ჩატვირთვისთვის საჭირო ოპტიმიზაცია არ გამიკეთებია. ამ პოსტში შევეცდები იმ თემებზე ვისაუბრო, რასაც ამ პროცესზე აქვს გავლენა; ამასთან, რეალურად შევასრულო ისინი საიტზე და ჩატვირთვის დროები შევადარო.

ახლა ქრომი მაჩვენებს, რომ ჯეოლიმპის ერთ-ერთი მთავარი გვერდის გახსნის დროს სერვერზე 42 მოთხოვნა იგზავნება, 307.9 კილობაიტი იტვირთება და 1.2 – 2.3 წამს ანდომებს გვერდის ჩატვირთვას. შევეცდები ამის გაუმჯობესებას..

1. ნაკლები რაოდენობის HTTP მოთხოვნის გაგზავნა სერვერზე
ერთ-ერთი ყველაზე მნიშვნელოვანი წესი, რომელსაც შესამჩნევი შედეგი აქვს, სერვერზე გასაგზავნი HTTP მოთხოვნების შემცირებაა. ეს მოთხოვნები იგზავნება თვითონ html ფაილის და ასევე თითოეული კომპონენტის წამოსაღებად, რასაც საიტი შეიცავს (სურათები, css და javascript ფაილები, ა.შ.).

http მოთხოვნა საკმაოდ მძიმე ოპერაციაა, რადგან მის შესასრულებლად საჭიროა DNS სერვერთან მისვლა, დომენის შესაბამისი ip მისამართის მიღება, მიღებული მისამართის საშუალებით ჰოსტ სერვერის მიგნება და ბოლო ბოლო ვებსერვერიდან რესურსის წამოღება. თუ ეს პუნქტები გეოგრაფიულადაც დაშორებულია (მაგალითად სხვადასხვა ქვეყნებში), მოთხოვნას უფრო მეტი სერვერის და ქსელის გავლა უწევს და დრო შესაბამისად იზრდება (ილუსტრაცია: როგორ მუშაობს ინტერნეტი).

Read more

RAID მასივები

ამ საკითხზე სემინარი მქონდა მოსამზადებელი და ბარემ პოსტსაც მივუძღვნი 🙂

რა არის ეს RAID (Redundant Array of Independent Disks) და რისთვის გამოიყენება? : )

როგორ შევინახოთ ინფორმაცია სისტემის აგების დროს დამოკიდებულია თვითონ ამოცანაზე. რა გვჭირდება: დიდი რაოდენობით ჩაწერა, წაკითხვა, სისწრაფე, საიმედოობა?

მაგალითად, არსებობს ამოცანები, სადაც კრიტიკული მნიშვნელობა აქვს ინფორმაციის საიმედოდ შენახვას და მასზე წვდომის შესაძლებლობას დროის ნებისმიერ მომენტში. ანუ, დისკის დაზიანების დროს უნდა არსებობდეს მისი შემცვლელი იგივე ინფორმაციით და თანაც რაც შეიძლება სწრაფად.

არის ამოცანები, სადაც წარმადობა უფრო პრიორიტეტულია. მაგალითად, როდესაც სერვერიდან დიდი რაოდენობით ვიდეო ნაკადები მოდის.

თავდაპირველად RAID-ის ძირითადი იდეა იყო, რომ რამდენიმე მყარი დისკი გაეერთიანებინა დისკების მასივში და ამით გაეუმჯობესებინა წარმადობა, რომელიც ერთ დიდი ზომის დისკს ჰქონდა.

ახლა RAID-ის არქიტექტურული დიზაინებიდან ყველაზე გავრცელებულია 5 ვარიანტი:  RAID 0, RAID 1, RAID 5, RAID 6, RAID 10.

ისინი ძირითადად ორ მიზანს ემსახურებიან: მონაცემთა შენახვის საიმედოობის გაზრდას, შეტანა/გამოტანის (დისკზე ჩაწერა/წაკითხვის) წარმადობის გაზრდას.

განვიხილოთ თითოეული მათგანი:

RAID 0

ჩაწერის დროს მონაცემები იყოფა ფრაგმენტებად და ეს ფრაგმენტები სათითაოდ ნაწილდება მასივში შემავალ დისკებზე. წაკითხვის დროს კი ყველა დისკიდან ერთდროულად ხდება წაკითხვა.

raid0

up_iconრაც უფრო მეტი დისკია, უფრო მეტად იზრდება სისწრაფე. უხეშად რომ შევადარო, ეს იგივეა, წყლის არხიდან ერთის მაგივრად რამდენიმე მილი გამოვიყვანოთ. იგივე რაოდენობის წყალს უფრო მალე მივიღებთ.

up_iconარ ვკარგავთ ადგილს. მთლიანად ვიყენებთ დისკების მოცულობას ჩვენი ინფორმაციისთვის.

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

Read more

შემთხვევითი ჩანაწერის ამორჩევა მონაცემთა ბაზის ცხრილიდან

ალბათ ბევრგან დაგჭირვებიათ შემთხვევითი ჩანაწერის ამოღება (random წერილის გამოყვანა ბლოგზე, random ფრაზა, random წიგნი – ბიბლიოთეკის საიტზე, random პროდუქტი – მაღაზიის საიტზე, ა.შ.) და შეიძლება რაიმე კარგი მეთოდიც გაქვთ შერჩეული ამისთვის.
მე კვლევები არ მიწარმოებია :))) ამ საკითხზე. უბრალოდ შემხვდა სასარგებლო სტატია, სადაც ამ მეთოდების განხილვაა მოყვანილი და მათი სისწრაფეებია შედარებული.

მეთოდი 1:

ვიყენებთ RAND() ფუნქციას, რომელიც float ტიპის რიცხვს აბრუნებს 0-დან 1-მდე.
sql მოთხოვნას შემდეგი სახე აქვს: SELECT * FROM `table` ORDER BY RAND() LIMIT 0,1;

როგორც სტატიის ავტორი წერს, მეთოდის პრობლემა მისი შესრულების დროა. MySQL-ს ყველა ჩანაწერი დროებით ცხრილში გადააქვს, თითოეულს ანიჭებს რაღაც შემთხვევით ინდექსს სორტირებისთვის. შემდეგ შედეგებს ასორტირებს და აბრუნებს პირველ ჩანაწერს.

უკეთესი მიდგომის აზრი ის არის, რომ ჯერ შეირჩეს შემთხვევითი რიცხვი და ამ შემთხვევითი რიცხვის მიხედვით ამოირჩეს მხოლოდ ერთი ჩანაწერი.

მეთოდი 2:

იმ შემთხვევაში, თუ თითოეულ ჩანაწერს უნიკალური გასაღები (მაგალითად id) გააჩნია, მაშინ შეგვიძლია ავირჩიოთ შემთხვევითი id უმცირეს და უდიდეს id-ებს შორის და შემდეგ დავაბრუნებინოთ იმ არჩეული id-ის ჩანაწერი.

უდიდესი და უმცირესი id-ის გასაგებად MAX() და MIN() ფუნქციები გამოვიყენოთ.

$range_result = mysql_query( " SELECT MAX(`id`) AS max_id , MIN(`id`) AS min_id FROM `table` ");
$range_row = mysql_fetch_object( $range_result );
$random = mt_rand( $range_row->min_id , $range_row->max_id );
$result = mysql_query( " SELECT * FROM `table` WHERE `id` >= $random LIMIT 0,1 ");
მეთოდი საკმაოდ შეზღუდულია, რადგან შეიძლება ცხრილს უნიკალური გასაღები საერთოდ არ ჰქონდეს. ამიტომ მესამე მეთოდში MySQL-ის LIMIT-ს ვეყრდნობით.

მეთოდი 3:

LIMIT ორ არგუმენტს იღებს. მაგალითად LIMIT 5,10  დააბრუნებს ჩანაწერებს 6-დან 15-მდე. ათვლა 0-დან იწყება.  პირველი არგუმენტი offset-ია (არ ვიცი როგორ ითარგმნება), ხოლო მეორე – offset-დან ათვლილი წამოსაღები ჩანაწერების მაქსიმალური რაოდენობა.

რომ გამოვთვალოთ offset პირველ ჩანაწერამდე – დავაგენერიროთ შემთხვევითი რიცხვი MySQL-ის RAND() ფუნქციის საშუალებით. შემდეგ მიღებული რიცხვი გადავამრავლოთ ცხრილში არსებულ ჩანაწერთა რაოდენობას (ამ რაოდენობას COUNT() ფუნქციის მივიღებთ). რადგან LIMIT მხოლოდ მთელ რიცხვებს იღებს არგუმენტებად, ეს ნამრავლი უნდა დავამრგვალოთ – გამოვიყენოთ FLOOR() ფუნქცია.

FLOOR() არითმეტიკული ფუნქციაა, რომელიც გამოთვლის უდიდეს მთელ რიცხვს გადაცემულ პარამეტრამდე. საბოლოოდ, კოდს ასეთი სახე ექნება:

$offset_result = mysql_query( " SELECT FLOOR(RAND() * COUNT(*)) AS `offset` FROM `table` ");

$offset_row = mysql_fetch_object( $offset_result );
$offset = $offset_row->offset;

$result = mysql_query( " SELECT * FROM `table` LIMIT $offset, 1 " );
MySQL 4.1 და უფრო მაღალ ვერსიებში ეს ორი მეთოდი შეგვიძლია ასე გავაერთიანოთ:

მეთოდი 4:

SELECT * FROM `table` WHERE id >= (SELECT CEILING( MAX(id) * RAND()) FROM `table` ) ORDER BY id LIMIT 1;

ამ მეთოდს იგივე ნაკლი აქვს, რაც მეორეს. ის მხოლოდ უნიკალურ გასაღებიან ცხრილებთან მუშაობს.

სტატიის ავტორმა მეთოდების სისწრაფეები შეადარა და სოფტის და ჰარდის სპეციპიკაციებს თუ არ ჩავუღრმავდებით, მიახლოებით ასეთი შედეგი მიიღება:

ყველაზე ნელი პირველი მეთოდია. ვთქვათ, რომ მას დროის 100% დასჭირდა შესრულებისთვის.
მეორე მეთოდს 79%.
მესამეს – 13%.
მეოთხეს – 16%.
გამოდის, რომ ყველაზე სწრაფია მესამე მეთოდი.