چالش اعداد باینری در MySQL

فرض کنید پایگاه‌داده‌ای داریم که در آن جدولی برای نگه‌داری اطلاعات مربوط به جلسات یک انجمن نگهداری می‌شود. ساختار جدول جلسات یا meetings بدین شکل است:

alt

ستون days_of_week نشان می‌دهد که یک جلسه در چه روزهایی از هفته برگزار می‌شود؛ برای تشخیص روزهای برگزاری یک جلسه، باید days_of_week را به صورت یک عدد باینری درآوریم و ۷ بیت اول این عدد را معادل ۷ روز هفته در نظر بگیریم. مثلا اگر مقدار days_of_week برای یک جلسه برابر ۲۱ باشد، معادل باینری این عدد 0010101 خواهد بود و این نشان می‌دهد که جلسه در روزهای شنبه، دوشنبه و چهارشنبه هر هفته برگزار می‌شود.

alt

فرض کنید قرار است سایت این انجمن را به گونه‌ای ارتقا دهیم که کاربران بتوانند لیست جلساتی را که در شهرشان برگزار می‌شود، مشاهده کنند. مرتب‌سازی این لیست باید به گونه‌ای باشد که جلساتی که زمان برگزاری آن‌ها نزدیک‌تر است، در ابتدا ظاهر شوند.

برای انجام این کار شرایط و محدودیت‌های زیر را هم داریم:

  • از پایگاه داده MySQL استفاده می‌شود.
  • امکان تغییر ساختار جدول وجود ندارد.
  • برنامه باید لیست جلسات را به شکل مرتب شده از پایگاه داده تحویل بگیرد (پایگاه داده مسئول مرتب‌سازی لیست جلسات است).

سوال این است که MySQL چگونه می‌تواند این کار را برای ما انجام دهد؟

قبل از هر چیز بد نیست سری به داده‌های جدول meetings بزنیم و بخشی از آن‌ها را به عنوان نمونه بررسی کنیم.

alt

اگر امروز سه‌شنبه باشد، معادل باینری آن 0001000 می‌شود. در اولین قدم باید داده‌های ستون days_of_week را به شکل باینری در بیاوریم و ترتیب بیت‌ها را به گونه‌ای تغییر دهیم که سه‌شنبه اولین روز هفته باشد.

به عنوان مثال جلسه Call for Peace را با شناسه ۱۰۹ در نظر بگیرید. این عدد در مبنای دو به صورت 1000001 در می‌آید. برای رسیدن به پاسخ مساله، بیت‌های این عدد را به گونه‌ای می‌چینیم که بیتِ سه‌شنبه در سمت راست قرار گیرد. نتیجه عدد 0011000 خواهد بود:

alt

همان‌طور که در تصویر ملاحظه می‌کنید، عدد 1000001 به دو بخش تقسیم شده و این دو بخش با هم جابه‌جا شده‌اند تا عدد 0011000 را بسازند. با استفاده از روابط ساده زیر می‌توانیم به عدد 0001100 دست پیدا کنیم:

1) A = 1000001 >> 3 = 0001000  
2) B = (1000001 << 4) & 1111111 = 0010000

3) A | B = 0011000  

برای معنادار شدن روابط بالا، نباید فرض اولیه را فراموش کنیم: امروز سه‌شنبه (0001000) است و با توجه به این که چهارمین بیتِ سه‌شنبه 1 می‌باشد (سه بیت اول صفر هستند)، ما در رابطه اول عدد 1000001 را سه بیت به سمت راست شیفت داده‌ایم. به عبارت دیگر:

LOG2(0001000) = 3  

با این اوصاف می‌توان حدس زد عدد 4 در رابطه شماره دو از کجا آمده:

7 - LOG2(0001000) = 4  

در مرحله سوم دو عدد به دست آمده از مراحل قبل را OR می‌کنیم تا به نتیجه مورد نظر برسیم. اکنون می‌توانیم روابط بالا را به زبان SQL بنویسیم:

SELECT *, (days_of_week >> LOG2(@dow)) | ( (days_of_week << (7 - LOG2(@dow))) & 127) AS res FROM meetings  

در Query بالا فرض کرده‌ایم که متغیر @dow مقدار باینری امروز (سه‌شنبه) را در خود نگه داشته است.

با اجرای Query بالا ستونی به نام res را در نتایج ظاهر خواهد شد. این ستون نتیجه اعمال روابط بالا روی ستون days_of_week از جدول meetings‍ می‌باشد. با این جابه‌جایی، بیت‌های ستون res به‌گونه‌ای مرتب می‌شوند که گویا سه‌شنبه اولین روز از هفته است.

حال به مثال قبل برگردیم: برای جلسه Call for Peace، ما اکنون به عدد 0011000 رسیده‌ایم و می‌دانیم اولین بیت این عدد (0) نمایان‌گر این است که این جلسه سه‌شنبه‌ها برگزار نمی‌شود. بنابراین نزدیک‌ترین زمان برگزاری این جلسه، مربوط به اولین بیتی است که مقدار آن 1 باشد (از سمت راست): alt

با توجه به این‌که امروز سه‌شنبه است، ما سه روز تا زمان برگزاری این جلسه فاصله داریم. به نظر می‌رسد که تا همین‌جا هم به راه‌حل نهایی مساله رسیده باشیم: اگر بدانیم اولین بیت 1 در چه مکانی قرار گرفته (یا به عبارتی بدانیم چند بیت صفر در سمت راست عدد داریم)، خواهیم فهمید که چند روز با برگزاری جلسه فاصله داریم و بدین ترتیب می‌توانیم لیست جلسات را مرتب کنیم.

شمارش تعداد 0ها از سمت راست

برای شمارش تعداد بیت‌های صفری که در سمت راست یک عدد قرار گرفته، کافی است سه مرحله زیر را دنبال کنیم:

۱) مکمل‌دوی عدد مورد نظر را به دست آوریم.

۲) نتیجه را با عدد اولیه and کنیم.

۳) لگاریتم عدد به دست آمده را در مبنای دو محاسبه کنیم.

اگر مکمل‌دوی 0011000 را محاسبه کنیم، عدد 1101000 به دست می‌آید. با اجرای مرحله دوم به عدد 0001000 می‌رسیم:

1101000 & 0011000 = 0001000  

در واقع نتیجه مرحله ۲، عددی است که تنها یک بیت 1 دارد. کافی است لگاریتم این عدد را در مبنای دو محاسبه کنیم تا به نتیجه دلخواه برسیم:

LOG2(0001000) = 3  

عدد ۳ یعنی این‌که ما سه روز تا برگزاری جلسه Call for Peace فاصله داریم. اگر برای همه جلسات این محاسبات انجام گیرد، مرتب‌سازی لیست کار ساده‌ای خواهد بود.

با فرض این‌که n = 0011000 باشد، ۳ مرحله بالا را می‌توان بدین شکل خلاصه کرد:

 LOG2(n & -n) = 3

حالا وقت آن است Query نهایی را بنویسیم:

SELECT *, LOG2(res & -res) AS days_distance FROM (SELECT *, (days_of_week >> LOG2(@dow)) | ( (days_of_week << (7 - LOG2(@dow))) & 127) AS res FROM meetings) AS temp ORDER BY days_distance ASC  

تمام!