K امین آماره ترتیبی با BIT

نکته : در این آموزش فرض می شود شما از قبل با ساختمان داده BIT آشنایی دارید ، اگر از قبل با این ساختمان داده آشنایی ندارید ابتدا آموزش مربوط به ساختمان داده BIT را مطالعه فرمایید.

K امین آماره ترتیبی (order statistic) از یک نمونه آماری برابر است با K امین عضو کوچک مجموعه ، به عبارت دیگر اگر یک مجموعه از اعداد را به ما بدهند ، K امین آماره ترتیبی عبارت است از K امین عضو این مجموعه پس از مرتب سازی غیر نزولی اعداد آن ، به عنوان مثال اگر اعداد 5 و 8 و 1 و 3 و 9 به ما داده شوند ، شکل مرتب شده این اعداد به صورت غیر نزولی برابر است با 1,3,5,8,9 ، سومین آماره ترتیبی این مجموعه عدد 5 است ، چهارمین آماره ترتیبی این مجموعه عدد 8 است و ...

آماره های ترتیبی علاوه بر ریاضیات و آمار در علم کامپیوتر به خصوص در پردازش تصویر نیز نقش مهم را بازی می کنند ، محاسبه سریع K امین آماره ترتیبی می تواند باعث بهبود الگوریتم های بسیاری شود.

مشهور ترین آماره های ترتیبی عبارتند از ماکزیمم (max)  ، مینیمم (min) ، میانه (median) ، که به خوبی با این سه مورد آشنایی دارید.

الگوریتم های بسیاری برای محاسبه K امین آماره های ترتیبی وجود دارند ، برای یک بحث کامل بهتر است به کتاب های الگوریتمی مانند CLRS مراجعه کنید.

مسائل مختلفی وجود دارند که K امین آماره ترتیبی در آن مطرح می شود ، در بعضی از مسائل ممکن است اعداد به صورت ثابت به ما داده شوند و چندین بار آماره های ترتیبی مختلف مورد پرس و جو قرار گیرند ، در چنین شرایطی مرتب سازی اعداد در ابتدای امر می تواند مفید باشد ، در بعضی از مسائل اعدادی از مجموعه حذف می شوند و اعدادی به مجموعه اضافه می شوند ، در چنین شرایطی استفاده از مرتب سازی ممکن است کار ساز نباشد و باید راه حل های دیگری را مد نظر قرار داد.

همچنین در بعضی از مسائل ممکن است اعداد داده شده حقیقی و یا طبیعی و ... باشند.

در این آموزش یک خانواده خاص از این مسئله را در نظر می گیریم مسائلی که در آن :

  • اعداد داده شده اعداد طبیعی بزرگتر از صفر و کوچکتر از n هستند ، به طوری که n چندان بزرگ نباشد (به اندازه ای باشد که بتوانیم آرایه ای به طول n در حافظه تعریف کنیم ، مثلاً n چیزی نزدیک کمتر از 300000 )
  • اعدادی به مجموعه اضافه شوند و اعدادی از مجموعه حذف شوند. (به عبارتی مجموعه به صورت پویا تغییر کند و مرتب سازی در هر بار کارساز نباشد)
  • اعداد منحصر به فرد باشند (در پایان آموزش باید به عنوان تمرین این شرط را حذف کنید)

نکته : در بسیاری از مسائل که داده های ورودی اعداد حقیقی قابل پیش بینی هستند می توان آن ها با استفاده از map به اعداد طبیعی با شرط بالا نگاشت داد.

اما حل مسئله :

در ادامه قصد داریم K امین آماره ترتیبی را برای حالت فوق به شکل بهینه ای محاسبه کنیم ، برای اینکار ابتدا یک آرایه به طول n تعریف می کنیم به طوری که در ابتدا تمام عناصر آن صفر باشند :

هر بار که یک عدد به مجموعه اضافه می شود خانه متناظر با آن عدد را در آرایه مورد نظر 1 می کنیم.

مثال :

5 به مجموعه اضافه می شود :

8 به مجموعه اضافه می شود :

1 و 3 و 9 نیز به مجموعه اضافه می شوند.

برای حذف نیز اندیس متناظر با عدد را 0 می کنیم.

همانطور که در مثال مشاهده کردید اعداد به صورت نامرتب به مجموعه اضافه شدند ، چگونه می توانیم در هر مرحله k امین آماره ترتیبی را به شیوه ای بهینه محاسبه کنیم؟ مطمئناً هر محله مرتب سازی مجموعه اعداد اصلاً بهینه نخواهد بود.

اگر به آرایه فوق دقت کنید متوجه می شوید که شکل تجمعی آن به صورت زیر است (اندیس i ام شامل مجموعه اعداد یک تا i است).

همانطور که می بینید ، با مشاهده آرایه تجمعی به راحتی می توانید سومین آماره ترتیبی را تشخصی دهید.(درست حدس زدید سمت چپ ترین عدد 3 متناظر با سومین آماره ترتیبی است {بیانگر سومین یک در آرایه اصلی است} )

آرایه تجمعی بالا دارای یک خاصیت بسیار جالب است و آن اینکه اعداد آن به صورت غیر نزولی مرتب هستند (چون جمع اعداد غیر منفی هستند).

همانطور که مشاهده کردید پیداد کردن k امین آماره ترتیبی معادل شد با پیدا کردن سمت چپ ترین k در آرایه تجمعی. (سمت چپ ترین یعنی اندیسی که کوچکتر باشد).

اما آرایه تجمعی مرتب شده است پس پیداد کردن سمت چپ ترین عدد k در آن به سادگی و با استفاده از الگوریتم جست و جوی دودویی (binary search) امکان پذیر است.

ولی هنوز یک گره مجهول در راه حل ما وجود دارد

آیا هر بار که k امین آماره ترتیبی از ما خواسته می شود باید آرایه تجمعی را محاسبه کنیم؟ (چون ممکن است اعدادی به مجموعه اضافه شده و یا اعدادی از آن حذف شده باشند)

محاسبه آرایه تجمعی از مرتبه $O(n)$ خواهد بود و جست و جوی دو دویی نیز از مرتبه $O(log(n))$ خواهد بود ولی هر بار اجرای یک الگوریتم از مرتبه$O(n)$ بهینه نخواهد بود .

در اینجا ساختمان داده BIT وارد عمل می شود.

میدانیم که با استفاده از ساختمان داده BIT قادریم فراوانی تجمعی تا اندیس i ام را در زمان $O(log(n))$ محاسبه کنیم .(متد $get(i)$ فراوانی تجمعی تا اندیس i ام را در زمان $O(log(n))$ محاسبه می کند)

الگوریتم جست و جوی دو دویی را با کمک متد get از ساختمان داده BIT به شکل زیر پیاده سازی می کنیم :


int bs(int k){//binary search over bit :D O(log^2(n))
    int a=1;
    int b=n;
    if(get(n)<k)
        return -1;
    int mid;
    int mid_value;
    while(a<b){
        mid=(a+b)/2;
        mid_value=get(mid);
        if(k>mid_value)
            a=mid+1;
        else
            b=mid;
    }
    return a;
}

الگوریتم جست و جوی دو دویی در زمان $O(log(n))$ اجرا می شود ، الگوریتم متد get نیز در زمان $O(log(n))$ اجرا می شود لذا زمان اجرای متد bs از مرتبه $O(log^2(n))$ خواهد بود. دقت کنید که این متد در عمل بسیار سریع اجرا می شود.

تمرین :

برای اینکه در عمل از روش فوق استفاده کرده باشیم سوال ORDERSET از سایت SPOJ را با هم حل می کنیم.

در این سوال چهار عمل انجام می شود :

  • $INSERT(S,x)$ : این عمل x را به مجموعه اضافه می کند.
  • $DELETE(S,x)$ : این عمل x را از مجموعه حذف می کند.
  • $K-TH(S)$ :  این عمل k امین آماره ترتیبی را بر می گرداند.
  • $COUNT(S,x)$ : این عمل تعداد اعداد کوچکتر از x را بر می گرداند.(چند عدد در مجموعه وجود دارند که از x کوچکترند؟ یا به عبارتی x چندمین آماره ترتیبی است؟ جواب به سادگی با استفاده از متد get قابل محاسبه است)

در این سوال یک نکته مهم وجود دارد و آن اینکه اعداد ورودی بسیار بزرگ هستند ($0 ≤ |x| ≤ 10^9$)  ولی در حقیقت حد اکثر 200000 عدد به ما داده می شود لذا می توانیم از تکنیک Coordinate compression استفاده کنیم .

تکنیک Coordinate compression : 

این تکنیک یک تکنیک بسیار ساده است که در بسیاری از مسائل باعث می شود فضای حالت کوچکتر شده و سرعت الگوریتم به شدت افزایش یابد (البته لازمه استفاده از این تکنیک این است که از قبل بتوانیم تمام اعداد را بخوانیم که در مسائل مسابقه ای معمولاً این شرط برقرار است. {در یک کاربرد عملی ممکن است قادر به انجام چنین کاری نباشیم و از ما خواسته شود که برنامه واقعاً به صورت پویا عمل کند (مثلاً یک کاربر اعداد را با دست وارد کند و سریعاً منتظر پاسخ باشد!) }

تکنیک Coordinate compression بدین صورت است که اعداد ورودی به به اعداد کوچکتر نگاشت دهیم ، به عنوان مثال اگر در ورودی اعداد 2 و 20 و 998 و 18 داده شوند می توانیم این اعداد را مرتب کنیم (به صورت 2,18,20,998) و سپس هر عدد را با موقعیت آن در لیست مرتب شده نگاشت دهیم ، به صورت زیر :

2 ----< 1

18----< 2

20----< 3

998----<4

این تکنیک به سادگی و به صورت زیر قابل پیاده سازی است :

  1. ابتدا تمام اعداد را از ورودی میخوانیم (ورودی را باید در جایی ذخیره کنیم تا بعداً دوباره بتوانیم آن را پردازش کنیم)
  2. اعداد را مرتب می کنیم.
  3. تکرار ها را حذف می کنیم.
  4. از map استفاده می کنیم و هر عدد را با موقعیت آن نگاشت می دهیم.

با توجه به توضیحات فوق راه حل مسئله ORDERSET را به صورت زیر می نویسیم :


#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>
using namespace std;
int n;
vector<int> bit(200010);
vector<int> arr(200010);

void add(int i){
    if(arr[i]==1)
        return;
    arr[i]=1;
    while(i<n+1){
        bit[i]++;
        i+=(i&-i);
    }
}
void del(int i){
    if(arr[i]==0)
        return;
    arr[i]=0;
    while(i<n+1){
        bit[i]--;
        i+=(i&-i);
    }
}
int get(int i){
    int sum=0;
    while(i>0){
        sum+=bit[i];
        i-=(i&-i);
    }
    return sum;
}
int bs(int k){//binary search over bit :D O(log^2(n))
    int a=1;
    int b=n;
    if(get(n)<k)
        return -1;
    int mid;
    int mid_value;
    while(a<b){
        mid=(a+b)/2;
        mid_value=get(mid);
        if(k>mid_value)
            a=mid+1;
        else
            b=mid;
    }
    return a;
}
char str[2];
int main() {
	scanf("%d",&n);
	vector<pair<char,int> > q;//list of queries
	vector<int> nums;// save numbers to compress later!
	map<int,int> mp;
	int count;
	char c;
	int v;

	for(int i=0;i<n;i++){
        
        
        scanf("%s%d",&str,&v);
      
		c=str[0];
        if(c!='K'){
            nums.push_back(v);
        }

		//save input!
        q.push_back(pair<char,int>(c,v));
        
	}
	
	//Coordinate compression
	
	//sort numbers 
	sort(nums.begin(),nums.end());
	
	//remove duplicate
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	
	//map numbers to indices
	for(int i=0;i<nums.size();i++){
	    mp.insert(pair<int,int>(nums[i],i+1));
	}

	
	for(int i=0;i<n;i++){
	    pair<char,int> p=q[i];
	    
	    switch(p.first){
	        case 'I':
	            add(mp[p.second]);
	        break;

	        case 'C':
	            count=get(mp[p.second]-1);
	            printf("%d\n",count);
	        break;

	        case 'K':
	         
	            count=bs(p.second);
	            if(count==-1){
	                printf("invalid\n");
	            }else{
	                printf("%d\n",nums[count-1]);
	            }
	        break;

	        case 'D':
	            del(mp[p.second]);
	        break;
	    }
	}
	
	return 0;
}

 

نکته پایانی : روش های دیگری نیز برای حل این مسئله وجود دارد ولی پیاده سازی BIT کوتاه و ساده است و سرعت آن نیز بسیار زیاد است ، به عنوان تمرین در مورد سایر روش های حل این مسئله تحقیق کنید.

تمرین : مسئله CTRICK نیز با ایده مشابهی قابل حل است ، این مسئله را نیز حل کنید.

افزودن دیدگاه جدید

Plain text

  • تگ‌های HTML مجاز نیستند.
  • نشانی صفحه‌ها وب و پست الکترونیک بصورت خودکار به پیوند تبدیل می‌شوند.
  • خطوط و پاراگراف‌ها بطور خودکار اعمال می‌شوند.