خوارزمية سريعة للحساب المتكرر للنسبة المئوية؟

Question

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

1. الحصول على قيمة x
2. إدراج x في صفيف تم فرزه بالفعل في الخلف
3. تبديل x لأسفل حتى يتم فرز الصفيف
4. اقرأ العنصر في الموضع array[array.size * 3/4]

النقطة 3 هي o (n) ، والباقي هو o (1) ، ولكن هذا لا يزال بطيئًا للغاية ، خاصة إذا كان الصفيف أكبر. هل هناك أي طريقة لتحسين هذا؟

تحديث

شكرا نيكيتا! بما أنني أستخدم C ++ ، فهذا هو الحل الأسهل للتنفيذ. هنا هو الرمز:

template<class T>
class IterativePercentile {
public:
  /// Percentile has to be in range [0, 1(
  IterativePercentile(double percentile)
    : _percentile(percentile)
  { }

  // Adds a number in O(log(n))
  void add(const T& x) {
    if (_lower.empty() || x <= _lower.front()) {
      _lower.push_back(x);
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
    } else {
      _upper.push_back(x);
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
    }

    unsigned size_lower = (unsigned)((_lower.size() + _upper.size()) * _percentile) + 1;
    if (_lower.size() > size_lower) {
      // lower to upper
      std::pop_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.push_back(_lower.back());
      std::push_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.pop_back();
    } else if (_lower.size() < size_lower) {
      // upper to lower
      std::pop_heap(_upper.begin(), _upper.end(), std::greater<T>());
      _lower.push_back(_upper.back());
      std::push_heap(_lower.begin(), _lower.end(), std::less<T>());
      _upper.pop_back();
    }            
  }

  /// Access the percentile in O(1)
  const T& get() const {
    return _lower.front();
  }

  void clear() {
    _lower.clear();
    _upper.clear();
  }

private:
  double _percentile;
  std::vector<T> _lower;
  std::vector<T> _upper;
};

Answer 1

يمكنك أن تفعل ذلك مع اثنين أكوام. لست متأكدًا مما إذا كان هناك حل أقل "مفتعلة" ، لكن هذا يوفر O(logn) يتم تضمين تعقيد الوقت والمواد في المكتبات القياسية لمعظم لغات البرمجة.

يحتوي الكومة الأولى (الكومة أ) على أصغر 75 ٪ عناصر ، كومة أخرى (كومة ب) - الباقي (أكبر 25 ٪). الأول لديه أكبر عنصر في الأعلى ، والثاني - الأصغر.

1. إضافة عنصر.

معرفة ما إذا كان عنصر جديد x هو <= max(A). إذا كان الأمر كذلك ، أضفه إلى كومة A, ، خلاف ذلك - للكومة B.
الآن ، إذا أضفنا x إلى الكومة A وأصبح كبيرًا جدًا (يحمل أكثر من 75 ٪ من العناصر) ، نحتاج إلى إزالة أكبر عنصر من العناصر A (o (logn)) وأضفه إلى الكومة B (أيضًا O (logn)).
مماثلة إذا أصبحت الكومة B كبيرة جدًا.

2. العثور على "0.75 متوسط"

فقط خذ العنصر الأكبر من A (أو الأصغر من B). يتطلب O (logn) أو o (1) الوقت ، اعتمادًا على تنفيذ الكومة.

تعديل
كما دولفين لاحظ أننا نحتاج إلى تحديد بالضبط حجم كل كومة لكل N (إذا كنا نريد إجابة دقيقة). على سبيل المثال ، إذا size(A) = floor(n * 0.75) و size(B) هو الباقي ، إذن ، لكل n > 0, array[array.size * 3/4] = min(B).

Answer 2

بسيط ترتيب شجرة إحصائيات يكفي لهذا.

يدعم نسخة متوازنة من هذه الشجرة O (logn) وقت إدراج/حذف والوصول حسب الرتبة. لذلك ، لا تحصل على نسبة مئوية بنسبة 75 ٪ فحسب ، بل أيضًا 66 ٪ أو 50 ٪ أو أي شيء تحتاجه دون الحاجة إلى تغيير الكود الخاص بك.

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

معظم التطبيقات القياسية (مثل Java's Treemap) هي أشجار الإحصاء.

Answer 3

يمكنك استخدام البحث الثنائي لإيجاد الموضع الصحيح في O (log n). ومع ذلك ، فإن تحويل الصفيف لا يزال O (n).

Answer 4

هنا حل JavaScript. نسخها في وحدة التحكم في المتصفح وهي تعمل. $scores يحتوي على قائمة الدرجات و ، $percentileيعطي n-th percentile من القائمة. لذا فإن المئوية 75 هي 76.8 و 99 المئوية هي 87.9.

function get_percentile($percentile, $array) {
    $array = $array.sort();
    $index = ($percentile/100) * $array.length;
    if (Math.floor($index) === $index) {
         $result = ($array[$index-1] + $array[$index])/2;
    }
    else {
        $result = $array[Math.floor($index)];
    }
    return $result;
}

$scores = [22.3, 32.4, 12.1, 54.6, 76.8, 87.3, 54.6, 45.5, 87.9];

get_percentile(75, $scores);
get_percentile(90, $scores);

Answer 5

إذا كان لديك مجموعة معروفة من القيم ، فسيكون التالية سريعة جدًا:

قم بإنشاء مجموعة كبيرة من الأعداد الصحيحة (حتى البايتات ستعمل) مع عدد من العناصر التي تساوي أقصى قيمة لبياناتك. على سبيل المثال ، إذا كان الحد الأقصى لقيمة T هو 100000 إنشاء صفيف

int[] index = new int[100000]; // 400kb

الآن تكرار على مجموعة القيم بأكملها

for each (int t : set_of_values) {
  index[t]++;
}

// You can do a try catch on ArrayOutOfBounds just in case :)

الآن احسب النسبة المئوية

int sum = 0, i = 0;
while (sum < 0.9*set_of_values.length) {
  sum += index[i++];
}

return i;

يمكنك أيضًا التفكير في استخدام Treemap بدلاً من الصفيف ، إذا لم تؤكد القيم هذه القيود.