أولوية الانتظار الذي يسمح كفاءة أولوية التحديث ؟

Question

التحديث:هنا بلدي تنفيذ تجزئته توقيت عجلات.واسمحوا لي أن أعرف إذا كان لديك فكرة لتحسين الأداء و التزامن.(20-Jan-2009)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

التحديث:أنا حل هذه المشكلة باستخدام الهرمية وتجزئته توقيت عجلات.(19-Jan-2009)

أحاول تنفيذ غرض خاص الموقت في جافا الذي هو الأمثل مهلة التعامل.على سبيل المثال, يمكن للمستخدم تسجيل المهمة مع خط ميت و الموقت يمكن أن يخطر المستخدم طريقة الاستدعاء عند خط الميت انتهى.في معظم الحالات المسجلة المهمة وسيتم ذلك في غضون فترة قصيرة جدا من الوقت ، لذلك معظم المهام سيتم إلغاء (مثلا ، المهمة.إلغاء()) أو إعادة جدولتها إلى المستقبل (على سبيل المثالالمهمة.rescheduleToLater(1 ، TimeUnit.الثاني)).

أريد أن استخدام هذه الموقت للكشف عن الخمول اتصال مأخذ التوصيل (مثلا ، إغلاق الاتصال عندما لا تلقي رسالة في 10 ثواني) و كتابة مهلة (مثلا ، رفع استثناء عند عملية الكتابة لا تنتهي في 30 ثانية.) في معظم الحالات المهلة لن يحدث العميل بإرسال رسالة وسيتم إرسال الرد إلا إذا كان هناك شيء غريب شبكة المسألة..

لا أستطيع استخدام جافا.util.الموقت أو جافا.util.المتزامنة.ScheduledThreadPoolExecutor لأنها تفترض معظم المهام التي من المفترض أن تكون انتهت.إذا كانت مهمة إلغاء إلغاء المهمة المخزنة في داخلي كومة حتى ScheduledThreadPoolExecutor.تطهير() ويسمى وهي مكلفة جدا العملية.(س(NlogN) ربما؟)

في التقليدية أكوام أو الأولوية طوابير تعلمت في بلدي CS دروس تحديث أولوية عنصر كانت عملية مكلفة (O(logN) في كثير من الحالات لأنه لا يمكن أن يتحقق إلا من خلال إزالة عنصر وإعادة إدراجه مع أولوية جديدة قيمة.بعض أكوام مثل فيبوناتشي كومة وقد O(1) وقت decreaseKey() والحد الأدنى() عملية ، ولكن ما أريد على الأقل سريع increaseKey() والحد الأدنى() (أو decreaseKey() وماكس()).

هل تعرف أي بنية البيانات التي هو الأمثل للغاية هذا الخصوص استخدام القضية ؟ استراتيجية واحدة أنا أفكر فقط تخزين جميع المهام في جدول تجزئة و بالتكرار جميع المهام في كل ثانية أو نحو ذلك ، لكنها ليست جميلة.

Answer 1

وماذا عن محاولة لفصل تسليم من الحالة الطبيعية حيث الأشياء كاملة بسرعة من حالات الخطأ؟

استخدم كلا جدول تجزئة وطابور الأولوية. عند بدء مهمة يحصل وضعت في جدول التجزئة، وإذا كان ينتهي بسرعة يحصل إزالته في (1) وقت O.

وكل ثانية واحدة كنت تفحص جدول التجزئة وأي المهام التي كانت لفترة طويلة، ويقول .75 ثانية، والحصول على نقل إلى قائمة انتظار الأولوية. وينبغي أن تكون قائمة الانتظار الأولوية دائما صغيرة وسهلة في التعامل معها. هذا يفترض أن ثانية واحدة هو أقل بكثير من الأوقات مهلة كنت تبحث عنه.

إذا مسح جدول التجزئة بطيئة جدا، هل يمكن استخدام اثنين من الجداول التجزئة، أساسا واحد لبضع ثوان حتى-مرقمة واحد لمدة ثانية الفردية. عندما بدأ يحصل مهمة وضعه في جدول التجزئة الحالي. كل خطوة الثانية جميع المهام من جدول التجزئة غير متداول في قائمة الانتظار ذات الأولوية ومبادلة الجداول التجزئة بحيث جدول التجزئة الحالي هو الآن فارغة ويتضمن جدول غير الحالي بدأت المهام بين واحد واثنين ثوان.

وخيارات هناك الكثير أكثر تعقيدا من مجرد استخدام طابور الأولوية، ولكنها جميلة تنفيذها بسهولة يجب أن تكون مستقرة.

Answer 2

على حد علمي (كتبت ورقة حول أولوية جديدة قائمة الانتظار ، كما استعرض النتائج السابقة) ، أي أولوية انتظار تنفيذ يحصل حدود فيبوناتشي أكوام ، وكذلك المستمر-زيادة الوقت-الرئيسية.

هناك مشكلة صغيرة مع الحصول على هذا حرفيا.إذا كنت يمكن أن تحصل على زيادة الرئيسية في O(1), ثم هل يمكن الحصول على حذف في س(1) - فقط زيادة الرئيسية إلى +ما لا نهاية (يمكنك التعامل مع رتل كامل من الكثير من +infinitys باستخدام بعض الاستهلاك القياسية الحيل).ولكن إذا كان العثور على مين هو أيضا O(1) ، وهذا يعني حذف مين = العثور على مين + حذف يصبح O(1).هذا مستحيل في المقارنة على أساس الأولوية في قائمة الانتظار لأن الفرز بد يعني (إدراج كل شيء ، ثم إزالة واحدا تلو الآخر) أن

n * إدراج + n * حذف مين > n log n.

النقطة هنا هو أنه إذا كنت تريد الأولوية في قائمة الانتظار إلى دعم الزيادة الرئيسية في O(1) ، ثم يجب أن تقبل إحدى العقوبات التالية:

• لا يمكن المقارنة على أساس.في الواقع, هذا هو وسيلة جيدة للحصول على حول أشياء مثل vEB الأشجار.
• تقبل O(log n) من أجل إدراج وأيضا O(n log n) من أجل جعل كومة (نظرا ن ابتداء القيم).هذا مقرف.
• تقبل O(log n) من أجل العثور على مين.هذا مقبول تماما إذا كنت لا في الواقع هل العثور على مين (دون المصاحب حذف).

ولكن, مرة أخرى, على حد علمي لا أحد قد فعلت الخيار الأخير.لطالما رأيت أنها فرصة للحصول على نتائج جديدة في حد الأساسية مجال هياكل البيانات.

Answer 3

حاشد توقيت عجلة - جوجل حاشد الهرمي توقيت عجلات "لمزيد من المعلومات. انها تعميم الإجابات التي أدلى بها الناس هنا. كنت تفضل عجلة المجزأة توقيت مع حجم عجلة كبيرة لالهرمي توقيت عجلات.

Answer 4

وبعض مزيج من التجزئة وO الهياكل (logN) ينبغي أن تفعل ما يطلب منك.

وأنا يميل إلى المماحكة مع الطريقة التي كنت تحليل المشكلة. في تعليقك أعلاه، ويقول لك

<اقتباس فقرة>   

ولأن التحديث سوف يحدث في كثير من الأحيان جدا جدا. دعونا نقول أننا تقوم بإرسال رسائل M لكل اتصال ثم الوقت الكلي يصبح O (MNlogN)، والتي هي كبيرة جدا. - Trustin لي (قبل 6 ساعات)

والذي هو الصحيح تماما بقدر ما يذهب. ولكن معظم الناس وأنا أعلم أن التركيز على التكلفة <م> في رسالة ، على نظرية أنه عند ديه التطبيق المزيد والمزيد من العمل للقيام به، ومن الواضح انها سوف تحتاج إلى مزيد من الموارد.

وحتى إذا كان التطبيق الخاص بك لديه مآخذ مليار المفتوحة <م> في وقت واحد (هو أن من المرجح حقا؟) تكلفة الإدراج ليست سوى حوالي 60 مقارنات لكل رسالة.

وأراهن المال أن هذا هو الأمثل من السابق لأوانه: لديك لا تقاس في الواقع الاختناقات في النظام لكم مع أداة تحليل أداء مثل CodeAnalyst أو VTune

.

وعلى أية حال، هناك ربما عدد لا حصر له من الطرق للقيام ما تسأل، بمجرد أن يقرر فقط أنه لا يوجد هيكل واحد سوف تفعل ما تريد، وتريد بعض مزيج من القوة والضعف في خوارزميات مختلفة.

واحد امكانية هي تقسيم المجال المقبس N إلى بعض عدد من الدلاء من حجم B، ومن ثم تجزئة كل مأخذ في واحدة من تلك (N / B) الدلاء. وفي هذا دلو هو كومة (أو أيا كان) مع O (تسجيل B) وقت التحديث. إذا كان الحد الأعلى على N ليست ثابتة سلفا، ولكن يمكن أن تختلف، ثم يمكنك إنشاء المزيد من الدلاء حيوي، وهو ما يضيف قليلا من المضاعفات، ولكن بالتأكيد قابلة للتنفيذ.

في أسوأ الحالات، وتوقيت الوكالة الدولية للطاقة لديها للبحث (N / B) طوابير لانتهاء الصلاحية، ولكن أفترض <م> غير مطلوب توقيت الوكالة الدولية للطاقة لقتل مآخذ الخمول في أي ترتيب معين!  وهذا هو، إذا ذهبت 10 مآخذ الخمول في وقت مشاركة شريحة، فإنه لا يكون للبحث هذا المجال لأحد أن المهلة الأولى، والتعامل معها، ثم العثور على واحد-مهلة الثانية، وما إلى ذلك فقط وقد لمسح مجموعة (N / B) من الدلاء وتعداد كافة المهلات.

إذا كنت غير راض عن مجموعة خطية من الدلاء، ويمكنك استخدام طابور أولوية الطوابير، ولكن كنت ترغب في تجنب استكمال أن قائمة الانتظار على كل رسالة، وإلا كنت مرة أخرى حيث كنت بدأت. بدلا من ذلك، تحدد بعض الوقت وهذا أقل من الفعلي المهلة. (قل، 3/4 أو 7/8 من ذلك) وكنت وضعت فقط قائمة الانتظار على مستوى منخفض في قائمة الانتظار رفيع المستوى لو كان أطول وقت يتجاوز ذلك.

وفي خطر بديهيا، كنت لا تريد طوابير بك مرتبطا على المنقضي الوقت. يجب أن تكون مفاتيح <م> بدء الوقت. لكل سجل في قوائم الانتظار، فإن الوقت المنقضي يجب أن يتم تحديثه باستمرار، ولكن لا يتغير وقت بدء كل سجل.

Answer 5

هناك طريقة بسيطة جدا للقيام بكل إدراج ويزيل في O(1) ، والاستفادة من حقيقة أن 1) الأولوية على أساس الوقت و 2) ربما يكون صغير, عدد ثابت من مهلة المدد.

1. إنشاء العادية FIFO انتظار عقد جميع المهام التي مهلة في 10 ثوان.لأن كل المهام متطابقة مهلة مدتها ، يمكنك ببساطة إدراج إلى إزالة من البداية للحفاظ على انتظار فرز.
2. خلق آخر FIFO طابور المهام مع 30 ثانية مهلة مدة.خلق المزيد من طوابير أخرى مهلة المدد.
3. إلى إلغاء أو إزالة عنصر من قائمة الانتظار.هذا هو س(1) إذا كانت قائمة الانتظار تنفيذها في قائمة مرتبطة.
4. إعادة جدولة يمكن أن يتم إلغاء إدراج ، كل العمليات O(1).علما بأن المهام التي يمكن إعادة جدولة مختلفة قوائم الانتظار.
5. وأخيرا الجمع بين جميع FIFO طوابير في عام واحد الأولوية في قائمة الانتظار ، وقد رأس كل FIFO طابور المشاركة العادية في كومة الذاكرة المؤقتة.رئيس هذه الكومة ستكون مهمة مع اقرب تنتهي المهلة من جميع المهام.

إذا كان لديك م عدد مختلف مهلة مدتها ، تعقيد لكل عملية من الهيكل العام O(log م).الإدراج O(log م) بسبب الحاجة للبحث الذي انتظار إدراج.إزالة مين هو O(log م) لاستعادة الكومة.إلغاء O(1) ولكن أسوأ الأحوال O(log م) إذا كنت إلغاء رئيس قائمة الانتظار.لأن m هو صغير, عدد ثابت, O(log م) هو أساسا O(1).لا النطاق مع عدد من المهام.

Answer 6

والسيناريو معينة الخاص بك وتقترح منطقة عازلة دائري لي. إذا كان الحد الأقصى. مهلة 30 ثانية، ونحن نريد لجني مآخذ على الأقل كل عشر من الثانية، ثم استخدام منطقة عازلة من 300 القوائم المرتبطة على نحو مضاعف، واحدة لكل عشر ثانية في تلك الفترة. إلى 'increaseTime "على الدخول، وإزالته من القائمة انها في وإضافته إلى واحد (سواء عمليات وقت ثابت) في الفترة الجديدة العاشرة الثانية. عندما تنتهي فترة، تجني أي شيء خلفها في القائمة الحالية (ربما عن طريق تغذية انها لموضوع حصادة) وتقدم مؤشر القائمة الحالية.

Answer 7

وكنت قد حصلت على الحد الثابت على عدد من البنود في قائمة الانتظار - هناك حد لمآخذ TCP

وذلك يحدها المشكلة. وأظن أن أي بنية بيانات ذكية يكون أبطأ من استخدام أنواع المضمنة.

Answer 8

هل هناك سبب وجيه لعدم استخدام java.lang.PriorityQueue؟ لا تقم بإزالة () التعامل الخاص بك إلغاء العمليات في وقت سجل (N)؟ ثم تنفيذ الانتظار الخاصة بك على أساس الوقت حتى هذا البند على الجزء الأمامي من الطابور.

Answer 9

وأعتقد تخزين جميع المهام في قائمة وبالتكرار من خلالها يمكن أن يكون أفضل.

ويجب أن تكون (الذهاب إلى) تشغيل الخدمة على بعض آلة سمين جدا للوصول الى حدود حيث هذه التكلفة ستكون مهمة؟