المئينات من يعيش التقاط البيانات

https://stackoverflow.com/questions/1248815

12-09-2019
|

سؤال

أنا أبحث عن خوارزمية التي تحدد النسب المئوية لايف التقاط البيانات.

على سبيل المثال النظر في وضع ملقم التطبيق.

الملقم قد يكون أوقات الاستجابة كما يلي:17 ms 33 ms 52 ms 60 ms 55 ms الخ.

فمن المفيد أن تقرير 90% وقت الاستجابة ، 80 بالمئة في وقت الاستجابة ، إلخ.

ساذجة الخوارزمية إلى إدراج كل وقت الاستجابة إلى قائمة.عندما الإحصاءات طلب فرز القائمة على القيم في المناصب المناسبة.

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

هل هناك خوارزمية التي ينتج "التقريبية" المئين الإحصاءات نظرا ذاكرة محدودة الاستخدام ؟ على سبيل المثال, دعونا نقول كنت ترغب في حل هذه المشكلة في طريقة عملية الملايين من الطلبات ولكن فقط تريد استخدام يقول أحد كيلوبايت من الذاكرة بالنسبة المئوية تتبع (التخلص من تتبع الطلبات القديمة ليس خيارا منذ المئوية من المفترض أن تكون جميع الطلبات).

تتطلب أيضا أنه لا يوجد بداهة معرفة التوزيع.على سبيل المثال, أنا لا أريد أن تحديد أي يتراوح من الدلاء قبل الموعد المحدد.

المحلول

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

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

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

نصائح أخرى

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

لذا السؤال هو في الحقيقة يسأل "ما هي أفضل طريقة حيوي binning بياناتي"?هناك الكثير من النهج, ولكن إذا كنت ترغب في تقليل افتراضات حول مجموعة أو توزيع القيم قد تتلقى, ثم نهج بسيط إلى متوسط على دلاء من حجم ثابت k, مع لها توزيع الاعراض.على سبيل المثال, دعونا نقول كنت ترغب في عقد 1000 القيم في الذاكرة في وقت واحد.اختيار حجم k, ويقول 100.اختيار الخاص بك الحد الأدنى من القرار ، ويقول 1ms.ثم

أول دلو يتعامل مع القيم بين 0-1 مللي ثانية (العرض=1ms)
الثاني دلو:1-3m (w=2ms)
الثالث دلو:3-7ms (w=4ms)
الرابع دلو:7-15ms (w=8ms)
...
العاشرة دلو:511-1023ms (w=512ms)

هذا النوع من تسجيل النطاق نهج مشابه chunking النظم المستخدمة في جدول تجزئة الخوارزميات, يتم استخدامه من قبل بعض أنظمة الملفات وتخصيص الذاكرة الخوارزميات.أنه يعمل بشكل جيد عندما تكون البيانات الخاصة بك لديها مجموعة دينامية كبيرة.

كما قيم جديدة تأتي في ، يمكنك اختيار الطريقة التي ترغب في إعادة تشكيله ، اعتمادا على الاحتياجات الخاصة بك.على سبيل المثال ، يمكن أن تتبع المتوسط المتحرك, استخدام أولا-في-أول-out, أو بعض أخرى أكثر تطورا الأسلوب.ترى Kademlia خوارزمية نهج واحد (تستخدم من قبل تورنت).

في نهاية المطاف ، rebinning يجب أن تخسر بعض المعلومات.الخيارات الخاصة بك فيما يتعلق binning ستحدد تفاصيل ما يتم فقدان المعلومات.طريقة أخرى لقول ذلك هو أن ثابت حجم الذاكرة مخزن يعني المفاضلة بين مجموعة ديناميكية و أخذ العينات الإخلاص;كيف يمكنك أن تجعل المفاضلة متروك لكم ، ولكن مثل أي أخذ العينات المشكلة, هناك لا يمكن الالتفاف حول هذه الحقيقة الأساسية.

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

ما يستحق ، وأظن أن الخادم الخاص بك مرة سوف يكون صغير نسبيا النطاق الديناميكي, حتى أكثر استرخاء زيادة للسماح أخذ العينات أعلى من القيم المشتركة قد توفر نتائج أكثر دقة.

تحرير:للإجابة على تعليقك, هنا مثال بسيط binning الخوارزمية.

يمكنك تخزين 1000 القيم في 10 صناديق.كل بن ولذلك يحمل 100 القيم.نفترض كل بن نفذت مجموعة ديناميكية ("قائمة" في بيرل أو بايثون الشروط).
عندما قيمة جديدة يأتي في:
- تحديد أي بن ينبغي أن تكون مخزنة في ، استنادا إلى بن القيود التي اخترتها.
- إذا كان بن كامل إلحاق القيمة بن القائمة.
- إذا كان بن كامل ، إزالة قيمة في الجزء العلوي من بن القائمة إلحاق قيمة جديدة إلى أسفل بن القائمة.وهذا يعني أن القيم القديمة يتم طرح بعيدا مع مرور الوقت.
للعثور على 90%, نوع بن 10.90% هو القيمة الأولى في قائمة تم فرزها (عنصر 900/1000).

إذا كنت لا ترغب في رمي القيم القديمة ، ثم يمكنك تنفيذ بعض مخطط بديل بدلا من ذلك.على سبيل المثال ، عندما يصبح بن كامل (تصل إلى 100 القيم في بلدي على سبيل المثال) ، هل يمكن أن تأخذ متوسط أقدم 50 العناصر (أيأول 50 في القائمة) ، تجاهل تلك العناصر ، ومن ثم إلحاق جديدة متوسط عنصرا بن ويترك لك مع بن 51 العناصر التي لديها الآن مساحة لعقد 49 قيم جديدة.هذا مثال بسيط من rebinning.

مثال آخر هو rebinning الاختزال;رمي بعيدا كل 5 القيمة في قائمة تم فرزها ، على سبيل المثال.

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

لقد نشرت للتو بلوق نشر على هذا الموضوع. وبعد الفكرة الأساسية هي تقليل الاحتياجات الخاصة بحساب دقيق لصالح "95٪ في المئة من الردود يستغرق 500ms-600ms أو أقل" (لجميع النسبة المئوية الدقيقة من 500ms-600ms)

يمكنك استخدام أي عدد من الدلاء من أي حجم تعسفي (مثل 0MS-50ms، 50ms-100ms، ... فقط أي شيء يناسب USECASE الخاص بك). عادة، لا ينبغي أن تكون مشكلة في أن جميع الطلبات التي تتجاوز وقت استجابة معين (مثل 5 ثوان لتطبيق ويب) في دلو آخر (أي 5000ms).

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

يتطلب هذا النهج فقط 8 بايت لكل دلو، مما يسمح بتتبع 128 دلاء مع 1K من الذاكرة. أكثر من كافية لتحليل أوقات الاستجابة لتطبيق الويب باستخدام حبيبتي 50ms).

كمثال، هنا هو جوجل الرسم البياني لقد قمت بإنشائها من 1 ساعة من البيانات الملتقطة (باستخدام 60 عدادات مع 200ms لكل دلو):

لطيفة، أليس كذلك؟ :) اقرأ المزيد عن بلدي بلوق.

(لقد كان بعض الوقت تماما منذ طرح هذا السؤال، ولكن أود أن أشير إلى بعض الأوراق البحثية ذات الصلة)

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

تقترح جميع هذه الأوراق خوارزميات مع تعقيد الفضاء الخطي الفرعي لحساب النسبة المئوية التقريبية عبر دفق البيانات.

جرب الخوارزمية البسيطة المحددة في الورق "الإجراء المتسلسل لتقدير متزامن للعديد من المترانيات" (raatikainen). إنه سريع، يتطلب علامات 2 * M + 3 (للمورقة M) وتميل إلى تقريب دقيق بسرعة.

استخدام مجموعة ديناميكية T[] من كبيرة أعداد صحيحة أو شيء من حيث T[n] بحساب numer من أوقات الاستجابة الوقت كان ن ميلي ثانية.إذا كنت حقا يفعلون الإحصاءات على تطبيق الملقم ثم ربما 250 ms أوقات الاستجابة هي الحد المطلق على أي حال.حتى 1 كيلو بايت يحمل واحدة 32 بت عدد صحيح لكل ms بين 0 و 250 و لديك بعض غرفة لتجنيب تجاوز بن.إذا كنت تريد شيئا أكثر صناديق تذهب مع 8 بت أرقام 1000 صناديق, وفي اللحظة العداد قد تجاوز (أي256 طلب في وقت الاستجابة) يمكنك تحويل بت في جميع صناديق بنسبة 1.(بشكل فعال في خفض قيمة في جميع صناديق).هذا يعني أنك تتجاهل جميع الصناديق التي تستحوذ على أقل من 1/127 التأخير أن معظم زار بن المصيد.

إذا كنت حقا في حاجة الى مجموعة محددة من صناديق أقترح استخدام أول يوم من يطلب الخروج مع المعقولة الثابتة مجموعة صناديق.أي ديناميكية سوف تكون خطيرة جدا في العيش ، أداء الحساسة التطبيق.إذا اخترت هذا الطريق الأفضل أن تعرف ما تفعل الخاص بك أو في أحد الأيام كنت ذاهب الى الحصول على استدعاء من السرير لشرح لماذا الإحصاءات تعقب فجأة الأكل 90% وحدة المعالجة المركزية و 75% الذاكرة على خادم الإنتاج.

أما بالنسبة إحصاءات إضافية:متوسط و الفرق هناك بعض لطيفة الخوارزميات العودية أن تأخذ القليل جدا من الذاكرة.اثنين من هذه الإحصاءات يمكن أن تكون مفيدة بما فيه الكفاية في أنفسهم الكثير من التوزيعات لأن نظرية الحد المركزي الدول التي التوزيعات التي تنشأ من عدد كبير بما فيه الكفاية من المتغيرات المستقلة نهج التوزيع الطبيعي (وهو يعرف تماما من قبل يعني الفرق) يمكنك استخدام واحدة من اختبارات الطبيعية في آخر N (حيث N كبيرة بما فيه الكفاية ولكن مقيدة الخاص بك متطلبات الذاكرة) لرصد الطقس افتراض الطبيعية لا يزال ساريا.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow