الفرز ... حسب جدول التجزئة (أيضًا حسب عدد الأشجار وخريطة HashMap)

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

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

فرز عدد الأشجار

نقوم ببناء شجرة Steam (المفتاح ، الكمية) ، حيث يكون المفتاح مسؤولاً عن عنصر الصفيف ، والكمية هي عدد التكرارات لعنصر الصفيف هذا. الشجرة متوازنة بشكل طبيعي ، أسود وأحمر ، على سبيل المثال.

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

نعيد كتابة المصفوفة ونحذف قمة الرأس في كل مرة ونكتب المفتاح عدة مرات مثل رقمه.

من أجل عدم تنفيذ الشجرة نفسها ، بالنسبة للخوارزمية الموصوفة ، استخدمت TreeSet ، والتي تعمل على شجرة سوداء حمراء.

باستخدام HashMap

سنقوم بتخزين عنصر الصفيف كمفتاح ، وعدد التكرار كقيمة المفتاح.

باستخدام جدول التجزئة الخاص بي

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

التصادمات

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

تجزئة التشفير ليست مناسبة لنا ، ولأنها يمكنك نسيان مجموعة من التجزئة المجزأة تقريبًا (بمعنى الترتيب باستخدام المفاتيح).

وقت العمل

فرز العد الشجري: في أسوأ الحالات ، لـ O (n log n) ، في أفضل الأحوال ، للوقت الخطي.
تصنيف جدول التجزئة: وقت التجزئة + تعقيد فرز مصفوفة التجزئة (قد يختلف بناءً على الخوارزمية والتطبيق المختارين ، لذلك لن أشير إلى أي شيء هنا). تقدير التعقيد صعب بسبب استخدام دالة التجزئة والعديد من الأساليب الممكنة لفرز التجزئة. يحتاج هذا السؤال إلى بحث إضافي ، ولكن من الواضح أنه في أسوأ الحالات (عندما تتطابق بيانات الإدخال عن قصد مع وظيفة تجزئة محددة في مرحلة معينة من التنفيذ) ، سيكون وقت التشغيل هو O (n ^ 2).

ماذا من الذاكرة؟

يتطلب فرز عدد الأشجار ذاكرة إضافية O (مميزة (n))
بالنسبة لجدول التجزئة ، نحتاج إلى ذاكرة O (مميزة (n)) + ذاكرة لفرز التجزئة (اعتمادًا على الخوارزمية المحددة).

فيما يلي النتائج بالمللي ثانية التي حصلت عليها على أرقام عشوائية عند فرز مصفوفة من الكائنات إلى 10 مليون elt ، مع مجموعة من القيم [0 ؛ س]:

في الاختبارات ، عامل التحميل في جدول التجزئة الخاص بي = 0.75 ، السعة الأولية = 20 ، يتم مضاعفة الجدول في كل مرة

بالنسبة إلى س = 10:
2044 - متكامل
285 - عدد الأشجار (فرز Usatov)
276 - HashMap (فرز Usatov-Prokurat)
140 - مع جدول التجزئة الخاص بي (فرز Usatov-Prokurat باستخدام MyHashTable)

س = 100:
2406 - مدمج
455 - شجرة العد
283 - هاشماب
134 - جدول التجزئة

س = 1_000:
2171 - متكامل
930 - شجرة العد
380 - هاشماب
209 - جدول التجزئة

س = 10_000
2879 - متكامل
1666 - شجرة العد
634 - هاشماب
326 - جدول التجزئة

س = 100_000
4045 - متكامل
2899 - شجرة العد
866 - هاشماب
762 - جدول التجزئة

س = 1_000_000
4997 - متكامل
5762 - شجرة العد
2505- بندر عبد الحليم
1294 - جدول التجزئة

س = 10_000_000
5083 - متكامل
11480 - شجرة العد
5099 - هاشماب
3240 - جدول التجزئة

كما قلت في البداية ، فإن هذه الفرز هي الأنسب لتلك الحالات عندما تكون قوة العديد من عناصر المصفوفة صغيرة بما يكفي بالنسبة لحجم المصفوفة.

من الجدير بالذكر أيضًا أن الفرز المضمّن يعمل بشكل أسرع بكثير على البيانات المطلوبة (التي تم طلبها تقريبًا) (أو مصفوفة بالترتيب العكسي) ، لكن أسلوبي يعمل بشكل أسرع على الأرقام العشوائية.

فرز عدد الأشجار:

static void usatovSort(Integer[] arr) { TreeSet<MyPair> tree = new TreeSet<>(); MyPair temp; MyPair mp = new MyPair(); for (int i : arr) { temp = mp; temp.first = i; temp = tree.ceiling(temp); if (temp != null && temp.first == i) //   , .    ,      temp.second++; else tree.add(new MyPair(i, 1)); } int ptr = 0; while (!tree.isEmpty()) { temp = tree.pollFirst(); for (int i = 0; i < temp.second; i++) arr[ptr++] = temp.first; } } 

الفرز من خلال HashMap:

  static void usatovProkuratSortUsingHashMap(Integer[] arr) { HashMap<Integer, Integer> hm = new HashMap<>(); Integer temp; for (Integer i : arr) { temp = hm.get(i); if (temp == null) hm.put(i, 1); else hm.put(i, temp + 1); } ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size()); keys.addAll(hm.keySet()); keys.sort(Comparator.naturalOrder()); int ptr = 0; for (Integer i : keys) for (int j = 0; j < hm.get(i); j++) arr[ptr++] = i; } 

فرز من خلال جدول التجزئة الخاص بي:

  static void usatovProkuratSortUsingMyHashTable(Integer[] arr) { MyHashTable mht = new MyHashTable(); for (Integer i : arr) mht.add(i); MyPair[] res = mht.getPairs(); int ptr = 0; Arrays.sort(res, Comparator.comparingInt(o -> o.first)); for (MyPair mp : res) for (int i = 0; i < mp.second; i++) arr[ptr++] = mp.first; } 

تنفيذ جدول التجزئة:

 public class MyHashTable { private MyPair[] hashArr; private double count = 0; private double loadFactor = 0.5; private double expansivity = 2; private static final int DEFAULT_CAPACITY = 20; public MyHashTable() { hashArr = new MyPair[DEFAULT_CAPACITY]; } public MyHashTable(double loadFactor) { hashArr = new MyPair[DEFAULT_CAPACITY]; this.loadFactor = loadFactor; } public MyHashTable(int capacity) { hashArr = new MyPair[capacity]; } public MyHashTable(int capacity, double loadFactor) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; } public MyHashTable(int capacity, double loadFactor, double expansivity) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; this.expansivity = expansivity; } public MyPair[] getPairs() { MyPair[] pairs = new MyPair[(int) count]; int ptr = 0; for (MyPair i : hashArr) if (i != null) pairs[ptr++] = i; return pairs; } public MyPair get(int key) { int add = 0; while (true) if (hashArr[(key + add) % hashArr.length].first == key) { return hashArr[(key + add) % hashArr.length]; } else if (add++ == hashArr.length) return null; } public void add(int key) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(key + add) % hashArr.length] == null) { hashArr[(key + add) % hashArr.length] = new MyPair(key, 1); count++; return; } if (hashArr[(key + add) % hashArr.length].first == key) { hashArr[(key + add) % hashArr.length].second++; return; } add++; } } public void add(MyPair newMP) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(newMP.first + add) % hashArr.length] == null) { hashArr[(newMP.first + add) % hashArr.length] = newMP; count++; return; } if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) { hashArr[(newMP.first + add) % hashArr.length].second += newMP.second; return; } add++; } } private void grow() { MyPair[] oldHash = hashArr; hashArr = new MyPair[(int) (expansivity * hashArr.length)]; for (MyPair i : oldHash) if (i != null) innerAdd(i); } private void innerAdd(MyPair mp) { int add = 0; while (true) { if (hashArr[(mp.first + add) % hashArr.length] == null) { hashArr[(mp.first + add) % hashArr.length] = mp; return; } if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) { hashArr[(mp.first + add) % hashArr.length].second += mp.second; return; } add++; } } } 

فئة Steam:

 public class MyPair implements Comparable<MyPair> { public int first; public int second; public MyPair() { } public MyPair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(MyPair o) { return first - o.first; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MyPair myPair = (MyPair) o; return first == myPair.first; } @Override public int hashCode() { return first; } }