ვგონებ შეიძლება ისეთი ზოგადი რჩევების მიცემა როგორიცაა მაგალითად რომ ვექტორების მასივებად გარდაქმნა 99 პროცენტი (თუ არა ყველა) ამოხსნებისა არ შველის დროის მიხედვით.

კიდევ სავარაუდოდ ცპპ-ში ფუნქციების ინლაინად გარდაქმაც არსად არ გიშველით.


უარყავით ჩემი აზრები ადმინობავ თუ ვცდები.

ხოდა დანარჩენი თქვენ თქვით მე რავიცი :დ

ალბათ სჯობდა "ზოგადად პროგრამირების" განყოფილებაში დაგეწერა.

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

ვექტორის ნაცვლად მასივის გამოყენებით დროს ყოველთვის იგებ. აბა ასეთი რაღაც გააკეთე: მასივში ჩაწერე 10 000 000 ცალი რიცხვი და დაითვალე პროგრამის მუშაობის დრო. შემდეგ ვექტორში ჩაწერე 10 000 000 ცალი რიცხვი და ისევ დაითვალე მუშაობის დრო.

შეიძლება ვექტორის დრო 3-ჯერ მეტი გამოგივიდეს მასივის დროზე.

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

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

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

varlevani, სწორედაც აქ უნდა გამეხსნა. ჯიოლიმპზე ვამბობ მაგეებს თორე ისე ინლაინითაც და მასივეში გარდაქმნითაც რო იგებ ვიცი.

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


ხოდა მოდი ერთი ორი სიტყვაც ვთქვათ იდე-ზე :).

რაც შეეხება მასივებს და ვექტორებს, მუშაობის დროში განსხვავება მინიმალური აქვთ, თუ vector-ს სწორად გამოიყენებთ. მაგალითად, თუ ამოცანაში მოცემულია N ცალი რიცხვი და გინდათ ისინი ვექტორში შეინახოთ, ბევრად უკეთესია, თავიდანვე N ზომის ვექტორი შექმნათ და არა ცარიელით დაიწყოთ და push_back მეთოდის მეშვეობით ამატოთ მასში ელემენტები. ამ მეორე შემთხვევაში მასივის შევსებაზე დაახლოებით ორჯერ მეტი დრო გახდება საჭირო და ასევე მას უარეს შემთხვევაში ორჯერ მეტი მეხსიერებაც დასჭირდება.

ვისაც აინტერესებს, ეს რისი ბრალია, უნდა იცოდეთ რისი მეშვეობით ახერხებს vector ამორტიზებულ O(1) დროში (მარტივად რომ ვთქვათ, "სწრაფად") ელემენტის დამატებას. და რომ გესმოდეთ, რატომ არაა ეგ მარტივი, უნდა იცოდეთ როგორ ხდება მეხსიერებაში მასივის შენახვა.

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

მაშინ როგორ მუშაობს vector? იგი ელემენტებს მასივით ინახავს სწრაფი წვდომისთვის, მაგრამ გარკვეულ შემთხვევებში ამ მასივს შლის და ქმნის ახალს, რომლის სიგრძე ორჯერ მეტია წინაზე. მაგალითად, თუ vector-ის მასივის სიგრძე 2-ის ტოლია და მასში მხოლოდ 1 ელემენტია მიმდინარე მომენტში, მაშინ ელემენტის ჩამატებისას იგი თავისუფალ ადგილს დაიკავებს. აი კიდევ ერთი ელემენტის ჩამატებას რომ მოვინდომებთ, vector ავტომატურად შექმნის 4-ელემენტიან მასივს, გადაიტანს მასში თავის ძველ 2 ელემენტს, დაუმატებს ახალს და ძველ 2-ელემენტიან მასივს გაანადგურებს. როდესაც vector-ში ელემენტების რაოდენობა 4-ს მიაღწევს, იგი ანალოგიური გზით 8 სიგრძის მასივს შექმნის და ძველს წაშლის. ერთი შეხედვით, ეს არც ისე სწრაფია, მაგრამ დააკვირდით, რომ თუ vector-ში ჩავამატეთ N ელემენტი, მისი სიგრძე აუცილებლად 2N-ზე ნაკლებია, ხოლო ოპერაციების რაოდენობა, რომელიც ჯამში შესრულდა N ელემენტის დასამატებლად, ასევე 2N-ის პროპორციულია (1+2+4+...+2^i ხომ (2^(i+1)-1)-ის ტოლია).

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

inline-ს რაც შეეხება, არც ერთ შეჯიბრზე არ მქონია შემთხვევა, რომ მის გარეშე ამოხსნა ნელი ყოფილიყო და მას იგი გადაერჩინა. იგივე ეხება register იდენტიფიკატორს, რომელიც ცვლადებს ეწერებათ და მათ რეგისტრებში (ყველაზე სწრაფად წვდომად მეხსიერებაში) უნდა ათავსებდეს.

მეხსიერებაზე წვდომას უკავშირდება ერთი მნიშვნელოვანი მომენტი, რომელიც ბევრმა შეიძლება არ იცოდეს. თქვენი მასივები კი ინახება ოპერატიულ მეხსიერებაში, მაგრამ როდესაც რომელიმე მასივის რომელიმე ელემენტზე წვდომას ახორციელებთ, ოპერაციულ სისტემას ამ მასივის გარკვეული ფრაგმენტი (მეხსიერების ის ფურცელი, სადაც ეს ელემენტი ინახება - ფურცლის ზომა კი მგონი 64 კილობაიტია) მოაქვს უფრო სწრაფად წვდომად მეხსიერებაში - ქეშში (cache). ქეშში შენახული ფრაგმენტის წაკითხვა ბევრად უფრო სწრაფად ხდება და ამიტომ თუ თქვენ შემდეგ მიწვდებით ამ ელემენტის მეზობელ ელემენტს, ეს ოპერაცია უცებ მოხდება (და არა მარტო მეზობელს, 64 კილობაიტში ხომ რამდენიმე ათასი ელემენტი ჩაეტევა). ხოლო თუ მასივის ელემენტებზე წვდომას არეული მიმდევრობით დაიწყებთ და მასივი იმდენად დიდია, რომ რამდენიმე ფურცელს იკავებს, შეიძლება ბევრად მეტი დრო დაიხარჯოს. ქეშის ზომები განსხვავდება, მაგრამ საშუალოდ 1-2 მეგაბაიტია ხოლმე (ისე ანდრო, რამდენია ჩვენს სერვერზე?), ამიტომ იგი ვერ შეინახავს ყველა იმ ფურცელს, რომელზეც წვდომას მოახდენთ და ზოგჯერ მას ძველი ფურცლების "დავიწყება" მოუწევს. და ხშირად თუ მოუწევს ახალ-ახალი ფურცლების ჩატვირთვა, ცუდად იქნება საქმე.

ამოხსნის დაწერისას აუცილებლად უნდა ითვალისწინებდეთ ოპერაციების "სიმძიმეს". მაგალითად, შეკრება და გამოკლება იაფი ოპერაციებია და სერვერზე შეიძლება 500-600 მილიონი შეკრება ერთ წამში ხორციელდებოდეს. შედარებით უფრო მძიმეა გამრავლების ოპერაცია. ყველაზე ცუდადაა საქმე გაყოფასთან და ნაშთის აღებასთან. ეს ოპერაციები 40-50 მილიონი ესწრება 1 წამში. მაგალითად, თუ თქვენს პროგრამას რამდენიმე მილიონჯერ სჭირდება p1/q1 და p2/q2 წილადების შედარება, აზრი აქვს რომ ამის ნაცვლად მოახდინოთ p1*q2 და p2*q1 სიდიდეების შედარება (ამას არა მხოლოდ სწრაფქმედებისთვის აქვს აზრი, მაგრამ ეს უკვე სხვა საკითხია).

ნიკას ნათქვამზეც გავაკეთებ კომენტარს. რა თქმა უნდა, თუ ალგორითმი ოპტიმალურია, კარგია რომ მისი ნებისმიერი რეალიზაცია გამოყოფილ დროში ეტეოდეს. ზოგიერთ ამოცანაში არაოპტიმალური ალგორითმები 1000-ჯერ უფრო ნელია ოპტიმალურზე და ეს მარტივად მიიღწევა. მაგრამ მთელ რიგ შემთხვევებში განსხვავება ასეთი რადიკალური არ გამოდის, ამიტომ მონაწილემ თვითონ უნდა შეაფასოს, რამდენად მძიმე ოპერაციების ჩატარება შეუძლია საკმარისად სწრაფ ამოხსნაში. მაგალითად, წლევანდელი პირველი ეპიზოდის ამოცანა C-ში გრაფის მეზობელთა სიებით შენახვა და sqrt ფუნქციის გამოყენება ერთად დიდი ალბათობით ამოხსნას ჩააგდებდა, მაგრამ თუ შეზღუდვებს დავწევთ ისე, რომ ნებისმიერად დაწერილი კვადრატული ამოხსნა 1 წამში ეტეოდეს, შეიძლება 1 წამში ჩაეტიოს კუბური სირთულის სხვა ამოხსნებიც.

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

გააჩნია შეჯიბრების სტილს. ACM-ზე უფრო ნაკლებად გამოსადეგია ოპტიმიზაციები, ვიდრე მოსწავლეთა შეჯიბრებებზე. ACM-ზე 1 ტესტი მაინც თუ ჩააგდო დროში, მორჩა. მაგრამ მოსწავლეთაზე შეიძლება დაწერო არაოპტიმალური ამოხსნა, მაგრამ ოპტიმიზაციებით ქულები გაზარდო. მაგალითად, წელს რესპუბლიკურზე ერთ-ერთ ამოცანაში შესაძლებელი იყო არაოპტიმალური ამოხსნის დაწერა, რომელიც 90 ქულას იღებდა. 50-დან დავიწყე და პატარ-პატარა ოპტიმიზაციებით 90-მდე ავედი (ციკლების შემცირება, ქეშის გამოყენება, გამრავლება/გაყოფის ცოტაჯერ გამოყენება და ა.შ.) მასივის მაგივრად ვექტორი რომ მქონოდა, არც ისე სწრაფი იქნებოდა :) ასე რომ გააჩნია სიტუაციას. თუმცა იმაში გეთანხმებით, რომ ძირითად შემთხვევებში ნაკლებად გამოსადეგია :)

მაინც რამდენიმე მეთოდი ოდნავ ასასწრაფებლად:

როცა შესატანი გამოსატანი მონაცემები დიდია:
C++ -ში cin/cout ის ნაცვლად scanf/printf ის გამოყენება
Java -ში Scanner ის ნაცვლად BufferedReader

როცა შესაძლებელია ყველაფრის მთელ რიცხვებში გაკეთება, ჯობია double ები არ გამოიყენოთ არსად (მაგალითად, როგორც ელდარმა ახსენა ზოგჯერ გაყოფის გამრავლებად გარდაქმნა შეიძლება)

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

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

მოკლედ მთავარია რამის გასაკეთებლად იმაზე უფრო ძვირიანი/ბევრი ოპერაციები არ შეასრულოთ ვიდრე საჭიროა.

ვინმემ მარტივმამრავლებად დაშლის ყველაზე მარტივი მეთოდი მითხარით უკეთესი იქნება კოდს თუ დამიგდბეთ/

მგონი ეს ყველაზე მარტივია:
Pascal-ზე:

საერთო ჯამში a მასივის პირველ ხაზზე გექნება მარტივმამრავლები ხოლო მეორე ხაზზე მათი ხარისხები.
ამის სირთულე დაახლოებით არი.`

ცუდად დაიპოსტა ჰარები აგარ არი სტრიქონებზე მარა უნდა გაიგო მგონი.

if i*i>n then i:=n; აქ ეს რა საჭიროა პირდაპირ რომ ციკლშIვე დაგეწერა
while i<=sqrt(n) do begin ესეც ხომ შეიძლებოდა რაღათ უნდოდა ციკლშIვე წვალება.

რა საჭიროა და n რიცხვი რომ მარტივი იყოს მაშინ ციკლში საერთოდ აღარ შევა არადა n თვითონ მარტივმამრავლია.

ა გავიგე მადლობა მართლაც მარტივია

ბრაწია თემა სხვა რამეს ეხება.

ხო მაგრამ მჭირდებოდა ბრაწია