تجزیه و تحلیل جریان داده: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
برچسب‌ها: ویرایش همراه ویرایش از وبگاه همراه |
ابرابزار |
||
خط ۳۴:
== همگرایی ==
همان‌طور که پیش تر گفته
* دامنه مقادیر باید [[مجموعه جزئاً مرتب]] و کراندار باشد.
* ترکیب تابع انتقال و پیوند باید یک [[تابع یکنوا]] نسبت به ترتیب مقادیر در دامنه باشد.
خط ۴۵:
ترتیب پیمایش بلوک‌ها در فرایند اجرای الگوریتم روی کارایی الگوریتم و زمان اجرای آن، تأثیر مستقیم دارد. عامل مهم دیگری که در این بحث اهمیت دارد، رو به جلو {{انگلیسی|forward}} یا رو به عقب {{انگلیسی|backward}} بودن تحلیل در گراف روند کنترل می‌باشد. اگر تحلیل ما رو به جلو باشد، بهتر است اجداد هر گره در گراف، قبل از آن شده باشند؛ چرا که حالت هر بلوک وابسته به حالات اجداد آن در گراف خواهد بود و اگر قبل از دیدن هر گره اجداد آن دیده شده باشند، سرعت همگرایی الگوریتم بیشتر خواهد بود. اگر در گراف حلقه نداشته باشیم، می‌توان ترتیبی از بلوک‌ها را پیدا کرد که تنها با یک بار اجرای الگوریتم روی هر بلوک، مقدار نهایی و صحیح هر بلوک به دست آید. برخی از ترتیب‌های ممکن برای پیمایش گراف در اجرای الگوریتم عبارتند از:
* پیمایش تصادفی: در این روش بلوک‌ها به ترتیب تصادفی پیمایش می‌شوند و به رو به جلو یا رو به عقب بودن تحلیل توجهی نمی‌شود به همین دلیل عملکرد این مدل ترتیب پیمایش به نسبت پیمایش‌های دیگر ضعیف است.
* پیمایش پس ترتیب {{انگلیسی| Postorder}}: این ترتیب پیمایش برای تحلیل رو به عقب مناسب است. در این روش هر گره زمانی دیده می‌شود که
* پیمایش عکس پس ترتیب {{انگلیسی|Reverse postorder}}: این ترتیب پیمایش برای تحلیل رو به جلو مناسب است. در این روش هر گره قبل از هر یک از فرزندانش دیده خواهد شد؛ مگر اینکه گره فرزند یک یال رو به عقب داشته باشد. (این روش با پیمایش پیشوندی {{انگلیسی| preorder}} متفاوت است)
خط ۶۱:
== رویکرد لیست کار ==
این روش، مدل بهبود یافته‌ای از الگوریتم راند-رابین است. در این روش، تکرار تنها در بخشی از گراف که در حال تغییر است انجام می‌شود. در این الگوریتم پس از مقداردهی اولیه، یک لیست به نام لیست کار ایجاد می‌شود که در ابتدای الگوریتم
{{چپچین}}
:Worklist ← ∅
| |||