این مقاله به بررسی روشهای بهبود عملکرد مرتبسازی تصادفی وزندار میپردازد، بهویژه در سناریوهای مسیریابی ترافیک با حجم بالا که نیاز به لیست "fail-over" دارند. مشکل "گرسنگی" (Starvation) که در مرتبسازی صرف بر اساس نرخ موفقیت رخ میدهد، یعنی هدایت تمام ترافیک به سرویس برتر و محروم کردن سایر سرویسها از ترافیک برای اثبات بازیابی، مورد بحث قرار میگیرد. راهکار پیشنهادی، استفاده از الگوریتم Efraimidis-Spirakis است که یک نوع تخصصی از Reservoir Sampling است و امکان تولید یک جایگشت وزندار را در یک گذر (single pass) فراهم میکند. این روش با محاسبه یک کلید مرتبسازی بر اساس u^(1/weight) (که u یک عدد تصادفی بین 0 و 1 است) و مرتبسازی لیست بر اساس این کلید، پیچیدگی را به O(N log N) کاهش میدهد و برای دادههای جریانی (data streams) مناسب است. نویسنده در وبلاگ خود به مقایسه پیادهسازیهای C# و بررسی عمیقتر ریاضیات این الگوریتم پرداخته است.
مشاهده مطلب اصلی