რეზერვუარის შერჩევა

Reservoir Sampling

        მაგალითად გვაქვს ამოცანა. გვსურს n ელემენტიან მიმდევრობაში (x0, x1, ... xn) ერთი ელემენტის შერჩევა შემთხვევითად, თანაბარი განაწილებით. როდესაც n-ის მნიშვნელობა ცნობილია ეს ამოცანა არის უმარტივესი. ჩვენ უბრალოდ შევარჩევთ ინდექსს j-ს 0-დან და n-მდე დიაპაზონში თანაბრად რაც ცალსახად მოგვცემს xj-ს ელემენტს მიმდევრობაში, რომლის შერჩევის ალბათობაც  იქნება 1/n. როგორ შეიძლება ეს ამოცანა ამოვხსნათ თუკი მიმდევრობაში ელემენტების რაოდენობა ცნობილი არ არის, თუკი ელემენტებს ვკითხულობთ როგორც ნაკადს და დროის ერთ მონაკვეთში მხოლოდ ერთ ელემენტზე გვაქვს წვდომა? ასეთ შემთხვევაში ცხადია მარტივი მეთოდი უკვე აღარ მუშაობს და პრობლემა სხვანაირად უნდა გადაიჭრას. 

        რეზერვუარის შერჩევა არის მეთოდი, რომელიც საშუალებას გვაძლებს შევარჩიოთ ელემენტი n ზომის ელემენტების ნაკადში სადაც n-ის მნიშვნელობა ცნობილი არ არის. მაგალითად შესაძლოა, რომ n ელემენტი მეხსიერებაში ერთად არ გვეტევა და ამისათვის ელემენტებს ნელ-ნელა ვტვირთავთ მეხსიერებაში ან უბრალოდ დროის მოცემული მომენტისათვის არაა ცნობილი ყველა ელემენტის მნიშვნელობა და ელემენტებს ვამუშავებთ მიმდევრობით, მას შემდეგ რაც მათი მნიშვნელობა ცნობილი ხდება. მაგალითად ჩვენ ვამუშავებთ ელემენტების მიმდევრობას თანმიმდევრულად და დროის ერთ მომენტში მხოლოდ ერთ ელემენტს ვხედავთ და გვინდა, რომ მას მერე რაც მთელ მიმდევრობას დავამუშავებთ ამოვარჩიოთ ერთი ელემენტი შემთხვევითად, თანაბარი განაწილებით(ამ პისტში სიმარტივისთვის მხოლოდ ერთ ელემენტიან რეზერვუარს განვიხილავთ). რაც იმას ნიშნავს რომ ალბათობა იმისა რომ ჩვენ შევარჩევთ ნებისმიერ ელემენტს xi-ს ნაკადში (x0, x1, ... xi, ...xn)  ყველა ელემენტისათვის უნდა იყოს თანაბარი და უდრიდეს 1/n-ს. ახლა განვიხილოთ მეთოდი დეტალურად:

        როგორც უკვე ვთქვით მეთოდი ამუშავებს ნაკადიდან შემოსუილ ელემენტებს მიმდევრობით, დროის ერთ მომენტში ერთს. ცალკე აქვს გამოყოფილი მეხსიერების ერთი უჯრედი(რომელსაც ვუწოდებთ რეზერვუარს) სადაც მიმდინარე შერჩეულ ელემენტს ინახავს და ყოველი ახალი ელემენტის დამუშავებისას ის ან ხელუხლებელს დატოვებს ამ ელემენტს რაც ჰქონდა შენახული ან ანაცვლებს მას ნაკადიდან შემოსული ახალი ელემენტით. მაგალიტად ჩვენ ვამუშავებთ (x0, x1, ... xi, ...xn) მიმდევრობის xi ელემენტს, ჩვენ 1/i ალბათობით უნდა ჩავანაცვლოთ რეზერვუარში არსებული ელემენტი xi ელემენტით. ეს მოგვცემს იმის გარანტიას, რომ ნაკადის ბოლოს რეზერვუარში არსებული ელემენტის შერჩევის ალბათობა იქნება 1/n. ადვილი წარმოსადგენი არ არის თუ რატომ არის ეს ასე ამიტომ ვცადოთ დავამტკიცოთ.

        xi ელემენტის დამუშავების პროცესში ალბათობა იმისა რომ ეს ელემენტი მოხვდება რეზერვუარში არის 1/i თუმცა თუ გვსურს რომ ის დარჩეს რეზერვურში ხელუხლებელი მაშინ ნაკადში მომავალმა ელემენტებმა ის არ უნდა ჩაანაცვლონ. xi ელემენტის შემგომ ნაკადში მოდის xi+1 ელემენტი და ალბათობა იმისა რომ ის ჩაანაცვლებს xi ელემენტს რეზერვუარში არის 1/(x+1), შესაბამისად ალბათობა იმისა რომ ვერ ჩაანაცვლებს და რეზერვუარში კვლავ xi ელემენტი დარჩება არის 1-1/(x+1). ასე გრძელდება ნაკადის ბოლომდე და გამოდის, რომ ალბათობა იმისა, რომ x ელემენტს შევარჩევთ და ნაკადის ბოლომდე მას ვერავინ ჩაანაცვლებს არის:

        როგორც ხედავთ საბოლოოდ მივიღეთ ისევ 1/n ალბათობა იმისა რომ xi ელემენტი იქნება შერჩეული ნაკადის ბოლოს რეზერვუარში და ეს რა თქმა უნდა სწორია ნებისმიერი i-თვის. მომავალში ასევე ვნახავთ რომ რეზერვუარის შერჩევის მეთოდი გამოსადეგია მაშინაც როცა დაინტერესებული ვართ არათანაბარი შერჩევით, როდესაც ნაკადის ელემენტების შერჩევა გვსურს მათზე მინიჭებული წონების მნიშვნელობების პროპორციულად. რეზერვუარის შერჩევის მეთოდი განსაკუთრებით პოპულარული გახდა კომპიუტერულ გრაფიკაში ბოლო დროს, სადაც რეალურ დროში მომუშავე რენდერერებში განათების დათვლის პროცესში აქტიურად გამოიყენება. ასე რომ რეზერვუარებზე კიდე გველოდება პოსტები.