الگوریتم دودشته (Two-Stack) برای تجمیع پنجره لغزان؛ راهکاری کارآمد برای محاسبات استریمینگ

محاسبه خلاصه یا تجمیع روی یک مجموعه داده، مانند مجموع، حداقل یا میانگین، از نیازهای رایج در مهندسی نرم‌افزار است. وقتی این محاسبه روی یک بازه متحرک از داده‌ها انجام شود، اصطلاحاً به آن «پنجره لغزان» (Sliding Window) می‌گوییم. برای مثال، تشخیص ناهنجاری در یک سیستم مانیتورینگ که نیازمند بررسی حداکثر میزان نویز در ۳۰ ثانیه گذشته است، از همین دسته‌بندی است.

پس‌زمینه و مشکل عملگرهای معکوس‌پذیر

اگر عملگر تجمیع ما دارای معکوس باشد (مثل جمع اعداد صحیح)، پیاده‌سازی با استفاده از یک صف دوطرفه یا deque کار ساده‌ای است. در این روش با وارد شدن داده جدید (push) آن را اضافه می‌کنیم و با خارج شدن داده قدیمی (pop) آن را از مجموع کم می‌کنیم.

اما چالش اصلی از جایی شروع می‌شود که عملگر ما معکوس‌پذیر نباشد؛ مانند پیدا کردن حداقل، مقدار میانی (Quantile)، شمارش تقریبی یکتا با استفاده از HyperLogLog، یا حتی جمع اعداد اعتمادی (Floating-point) به دلیل خطای گرد کردن و مقادیر خاصی مثل NaN. در این حالت‌های پیچیده، الگوریتم‌های ساده ناکارآمد می‌شوند یا خطای آن‌ها انباشته می‌شود.

الگوریتم دودشته (Two-Stack Aggregation)

این مقاله به بررسی یک الگوریتم خوش‌نام اما کمتر شناخته‌شده به نام «دودشته» می‌پردازد که ریشه آن به مقالات علمی دهه‌های گذشته و بحث‌های Stack Overflow بازمی‌گردد. این الگوریتم به جای نیاز به عملگر معکوس، تنها به خاصیت شرکت‌پذیری (Associativity) نیاز دارد.

برای استفاده از این الگو، تجمیع را به چند تابع پایه انتزاع می‌کنیم:

• empty(): مقدار اولیه خالی
• unit(x): تبدیل یک مقدار تک به ساختار تجمیع
• combine(x, y): ترکیب دو مقدار تجمیع‌شده
• finalize(x): استخراج خروجی نهایی

ساختار داده این الگوریتم شامل دو پشته (values و cum_aggs) و یک متغیر منفرد برای نگهداری تجمیع فعلی است. با هر بار انجام عملیات، این ساختار با هزینه زمانی میانگین O(1) به‌روزرسانی می‌شود.

ویژگی‌ها و مزایای فنی

• زمان اجرای بهینه: با اینکه ممکن است در هر w عملیات یک‌بار نیاز به تخلیه پشته‌ها باشد، هزینه کل میانگین به ازای هر عنصر O(1) است.
• مدیریت حافظه: میزان حافظه مصرفی متناسب با اندازه پنجره یعنی O(w) است.
• جلوگیری از انباشت خطا و مسمومیت داده: از آنجا که مقادیر خارج از پنجره هیچ‌وقت به صورت معکوس کم نمی‌شوند (بلکه با تخلیه و بازسازی پشته حذف می‌شوند)، ورود مقادیری مثل NaN یا خطاهای انباشته‌شده اعداد اعشاری برای همیشه در سیستم ماندگار نمی‌مانند و با خروج داده از پنجره، اثرشان پاک می‌شود.

دیدگاه جامعه مهندسی (Hacker News)

در بحث‌های هکرنیوز، توسعه‌دهندگان به نکات جالبی اشاره کردند:

• برخی کاربران ریشه‌های این تکنیک را به ادبیات پردازش تصویر در دهه ۱۹۹۰ (الگوریتم‌های van Herk/Gil-Werman) نسبت دادند.
• توسعه‌دهندگانی که روی ابزارهای تشخیص ناهنجاری و تحلیل لاگ کار می‌کنند، اشاره کردند که استفاده از این رویکرد به آن‌ها اجازه می‌دهد پنجره‌های تاریخی بزرگ‌تر و قابل‌تنظیم‌تری داشته باشند بدون اینکه نگران افت پرفورمنس باشند.
• ابزارهایی مانند DuckDB و SQLite نیز از الگوهای مشابهی برای بهینه‌سازی کوئری‌های پنجره‌ای استفاده می‌کنند.