گزیر

::گاهنوشتهای حمیدرضا محمدی::



دربارهٔ من:

آخرین نظردهندگان:

مشترک شوید:

ایمیل خود را در جعبهٔ زیر وارد کنید و دکمهٔ اشتراک را بزنید.

جستجو:

Valid XHTML 1.0 Transitional RSS Feed

داستانهایی دربارهٔ اعداد تصادفی

۸۹/۰۶/۲۰

۱) تابع تولید عدد تصادفی

xkcd: Random Number

۲) چرخ چهارگوش

برنامه‌نویس سرشناسی که همچون من و احتمالاً شما، آن روزها که قرار بود موزیلا ویرایش ۳.۵ از مرورگر محبوبش را منتشر کند ذوق دریافت فایرفاکس جدید را داشت در روزهای اول استفاده از این ویرایش مهم فایرفاکس به مشکل آزاردهنده‌ای برخورد کرد:

پس دست به کار شدم و نصاب فایرفاکس را در روز انتشار دریافت کردم و پس از گذر از کثیف‌کاری معمول به‌روزرسانی افزونه‌ها توانستم مرورگر جدید را برای اولین بار اجرا کنم و خدایا من چه می‌بینم: وب -انگارکن- به سال ۱۹۹۴ برگشته: وقتی که هیچ کس جز خوره‌های واقعی سایت نداشت و همه چیز به سرعت برق بود. زندگی شیرین شده بود!

روز بعد با فنجان قهوهٔ تازه در دست، فایرفاکس ۳.۵ عزیزم را روی سیستم تازه بالا آمده‌ام اجرا کردم. انتظار داشتم پنجرهٔ مرورگر را در عرض چند ثانیه ببینم تا باز هم وبگردی با سرعت برق‌آسا را تجربه کنم، اما اتفاقی نیفتاد. البته، یک اتفاق افتاد، هارد دیسک کامپیوترم مثل وقتهایی که آن را ویروسیابی می‌کنم مشغول شده بود تا این که بعد از ۳۵ ثانیه یا چیزی در همین حدود بالاخره توانست تمام بیتها و تکه‌های لازم را پیدا کند و چهرهٔ آشنای فایرفاکس را به من نشان بدهد تا من راهم را به دنیای بیرون شروع کنم!

فایرفاکس روی سیستم فرد معلوم‌‌الحال یاد شده همچنان سریع کار می‌کرد اما همیشه شروع شدنهایش کند و آزاردهنده بود. تا این که بالاخره تصمیم گرفت با جستجو در انجمنهای پشتیبانی فایرفاکس ریشهٔ مشکل را بیابد و این جستجو به کشف این نکته این انجامید که آقا، در این مصیبت تنها نیست و همدردهای زیادی دارد. بگذریم، خلاصه آن که مشخص شد مشکل مربوط به کتابخانهٔ NSS است. کتابخانه‌ای شامل توابع امنیت شبکه که انواع کارکردهای رمزنگاری و امنیتی را پوشش می‌دهد و برای پیاده‌سازی این توابع نیاز به اعداد تصادفی دارد:

ایجاد اعداد تصادفی واقعی مشکل است چرا که در یک سیستم کامپیوتری هیچ چیز واقعاً تصادفی نیست: هر چیزی نتیجهٔ یک عمل قابل پیش‌بینی است. پسران و دختران باهوش تیم NSS باید این مسأله را به گونه‌ای حل می‌کردند: چطور اعداد تصادفی واقعی ایجاد کنیم که تا حد ممکن تصادفی باشند؟ به جای استفاده از توابع ارائه شده توسط سیستم عامل (که این قابلیت را به دلیل نیاز پروتکل TCP در خود دارد) آنها این کار را به همان شیوه‌ای که عموماً شرکت موزیلا کارهایش را انجان می‌دهد انجام دادند: چرخ را از نو اختراع کردند. من مشکلی با اختراع مجدد چیزها ندارم، اشتباه برداشت نکنید، هیچ چرخی مثل چرخ دیگر نیست. اگر چه، مشکل اختراع دیگربارهٔ چرخ آن است که علاوه بر آن که در این فرایند شما حق اشتباه کردن ندارید، باید چرخی بسازید که از چرخهای اختراع شدهٔ قبلی بهتر باشد. برای نمونه هیچ کس از چرخ چهارگوش شما استفاده نخواهد کرد.

برای حل مشکل اعداد تصادفی، تیم NSS به روشی هوشمندانه روی آورده بودند، رویکردی چنان عالی که تا به حال به ذهن هیچ کس نرسیده بود: آنها تصمیم گرفتند که تمام فایلهای موجود در تمام پوشه‌های موقتی ویندوز را با چند ریسمان موازی بخوانند تا از آنها به عنوان نقطه‌های آغاز (seed) تولید اعداد تصادفی استفاده کنند! توجه کنید: این پوشه‌ها در هر چند میلی‌ثانیه تغییر می‌کنند، به سرعت در دسترسند، تأخیری در دسترسی به آنها وجود ندارد و هیچوقت با چیزهای حاشیه‌ای به دردنخور پر نمی‌شوند!

البته، پاراگراف بالا ذهنیت تیم NSS بود. در دنیای واقعی، چیزها یک کوچولو متفاوتند. متوجه هستید که؛ فایرفاکس ویرایش ۳.۵ کش اینترنت اکسپلورر را و پوشهٔ temp ویندوز برای پروفایل کاربر را توسط زیرسیستم NSS خود می‌خواند. این نه تنها به نظر من یک نباید به جهت خواندن داده‌های موقتی برنامهٔ دیگر است، بلکه یک بی‌توجهی شگفت‌آور نسبت به گلوگاه اصلی کامپیوترهای امروزی است: هارد دیسکها. اگر شما ویروس‌کشی داشته باشید که در حالت بددلانه تنظیم شده باشد پیمایش پوشه‌های موقت توسط NSS کندتر هم خواهد بود چرا که دسترسی به هر فایل از سوی فایرفاکس باعث اسکن آن توسط ویروس‌کش می‌شود. و اگر کاربر، با کامپیوترش هیچ کاری غیر از مرور وب با فایرفاکس نکند به گونه‌ای که این پوشه‌های موقت دست‌نخورده یا خالی بمانند، آن وقت چه؟ آیا خواندن فایل بدترین روش ممکن برای تولید نقطه‌های آغاز اعداد تصادفی نیست؟

۳) ماشین تولید اعداد تصادفی

dilbert random generator

– مطمئنید که این تصادفی است؟

– مشکل تصادفی بودن همین است که هیچ وقت نمی‌شود مطمئن بود.

۴) داستان گنجور

برای سیستم بازبینی خروجیهای OCR گنجور، راهکارهای مختلفی می‌شد طراحی کرد: می‌شد با توجه به آن که من عدد اطمینان بازشناسی تکه‌شعرها را هم داخل پایگاه داده‌ها داشتم، اوّل آنهایی را که با دقت پایین‌تری خوانده شده بودند در معرض بازبینی بگذارم. می‌شد به ترتیب عمل کنم، یعنی دوستانی که بازبینی می‌کنند از اوّل شروع کنند و هر کسی که تازه می‌آید آخرین تکه شعری را که هنوز بازبینی نشده یا اگر همه حداقل یک دور بازبینی شده‌اند، هنوز در دور دوم بازبینی نشده بازبینی کند و … .

اما خوب، من آسان‌ترین -و البته از لحاظ پردازشی کم‌هزینه‌ترین- راه را انتخاب کردم. هر بار بر اساس یک عدد تصادفی، یک خط شعر تصادفی در معرض بازبینی قرار می‌گرفت. مزیت این کار، نیاز به کمترین برنامه‌نویسی و همینطور به دلیل عدم نیاز به جستجو برای بازبینی نشده یا کم‌بازبینی‌شده‌ها سرعت و هزینهٔ پردازشی پایین بود.

اما در طولانی مدت چه اتفاقی می‌افتد؟ من حدود پنجاه هزار تکه تصویر بریده شده را در معرض بازبینی قرار داده بودم و اگر روزانه ۱۰۰۰ تکه از اینها بازبینی می‌شد باید در یک سیستم ترتیبی، همه در زمانی حدود دو ماه حداقل یک بار بازبینی شده باشند. اما در یک سیستم مبتنی بر اعداد تصادفی چه؟

نتیجه را احتمالاً می‌توانید حدس بزنید. خیلی از روزها، بیش از ۱۰۰۰ تکه از شعرها بازبینی می‌شد (آمارش هنوز در این صفحه در دسترس است)، اما بعد از دو ماه چیزی حدود ۱۹۰۰۰ تکه بیش از یک بار و حدود ۲۶۰۰۰ تکه تنها یک بار بازبینی شده بودند و ۸۰۰۰ تکه هم اصلاً بازبینی نشده بودند (گزارش تا آن مرحله).

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

خلاصه آن که -با تشکر ویژه از تمامی دوستانی که در این کار مشارکت کردند- مرحلهٔ اول بازبینی خروجیهای OCR گنجور به ثمر نشسته است. برای برداشت محصول نهایی می‌توانید سری به آثار بیدل و قاآنی در گنجور بزنید و اگر گنجور رومیزی دارید مجموعه اشعار متناظر را با شرحی که در این نوشته آمده به برنامه اضافه کنید.

و البته، یادتان باشد که این فقط مرحلهٔ اول بود و نهضت کماکان ادامه دارد.






۷ نظر

علی ستاری:

تاریخ: ۸۹/۰۶/۲۱ ساعت: ۱۸:۲۲

موضوع random جالبه و مشکلاتی که در نوع خاصی از برنامه‌ها در موردش پیش میاد اغلب از یک سوء تفاهم کوچیک ناشی میشه.
random واقعی unpredictable هست، مهم نیست که آیا تکراری باشه یا نه، مهم نیست که همه اون range رو پوشش بده یا نه، فقط غیر قابل پیش بینیه.
چیزی که ما معمولا میخوایم random واقعی نیست، shuffle است! ما وقتی میگیم بین ۱ تا ۵۰ هر بار یک عدد *random* میخوایم، معمولا خوشحال نمیشیم وقتی بعد از ۲۰ بار تست ۵ بار اعداد یکسان میگیرم! در واقع علاقه داریم اگر ۵۰ بار تست کردیم هر بار عدد جدید و غیر ترتیبی (non sequential) بگیریم.

این مطلب به همراه عکس‌ها و لینک‌هاش خوبه: http://seanmonstar.com/post/70.....-generator

حمیدرضا:

تاریخ: ۸۹/۰۶/۲۱ ساعت: ۱۹:۰۳

@علی ستاری:
نظر جالب و به عقیدهٔ من کاملاً درستیه، حداقل در مورد انتظاری که من داشتم کاملاً صادقه. اصلاً فکر می‌کنم در این باره کاریکاتور دیلبرت توی همین نوشته تا حدودی کاربردیه و واقعاً خروجیهای ماشین ارگانیک 😉 تولید اعداد تصادفیش می‌تونه با خروجیهای یه ماشین واقعی تولید اعداد تصادفی تطبیق کنه. و البته یه مسأله هم هست که شاید اگه قرار باشه یه ماشین تولید اعداد تصادفی کمتر اعداد تکراری تولید کنه (شرط) به نوعی میزان تصادفی بودن خروجیهاش محدود شده و کمتر از یه ماشین تولید اعداد تصادفی بدون شرط تصادفیه.
ممنون بابت لینک

مجتبی:

تاریخ: ۸۹/۰۶/۲۴ ساعت: ۱۴:۵۷

فوق العاده لذت بردم از مطلب زیباتون و از مطلب زیبای آقا ستاری. خداقوت

عرفان:

تاریخ: ۸۹/۰۷/۰۲ ساعت: ۲۲:۵۷

الگوریتمی توی بیسیک استفاده می‌شد به نظرم ساده و کارآمد بود.
دستور RANDOMIZE TIMER از تعداد میلی‌ثانیه‌های گذشته از ساعت ۱۲ نیمه‌شب برای نقطه آغاز الگوریتم تولید اعداد تصادفی استفاده می‌کرد. چرا از این استفاده نمی‌شود؟

یک چیزی هم به ذهن خودم رسید. موقعیت مکان‌نمای ماوس هم نقطه آغاز خوبی به نظر می‌رسد!

حمیدرضا:

تاریخ: ۸۹/۰۷/۰۳ ساعت: ۶:۳۴

@عرفان:
اون اشکال فایرفاکس در مدت کمی همون زمان حل شد.

مصطفی رعیتی:

تاریخ: ۹۰/۰۸/۲۹ ساعت: ۱۲:۰۱

با سلام ایا تایمر کامپیوتر مولد خوبی برای اعداد تصادفی هست؟چرا؟

یک نفر:

تاریخ: ۹۰/۰۹/۱۳ ساعت: ۶:۲۵

آقای رعیتی عزیز استادتون سوال میده که نباید بیاید اینجا واسه تقلب 😉

خروجی آر.اس.اس نظرات این نوشته:»

ارسال دنبالک:»

ارسال نظر برای این نوشته امکانپذیر نیست.