الذهاب هياكل البيانات ورقة الغش

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

لنبدأ مع ما هو واضح.

مجموعة ديناميكية مستمرة

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

 vector := []int{} 

مريح ، يتم تضمين المفاهيم الأساسية في اللغة.

CTEK

التناظرية من std::stack .

مجموعة مرتبة يتم فيها إضافة عناصر جديدة وحذف العناصر الموجودة من طرف واحد. تتم إزالة العنصر الذي تم وضعه الأخير (last-in ، first-out - LIFO) أولاً من المكدس. هذا مرة أخرى شريحة مسورة. يتم نسخ المقتطفات من مشروع إلى آخر:

 // Push stack = append(stack, value) 

 // Pop // ,  len(stack) > 0 stack, value = a[:len(stack)-1], a[len(stack)-1] 

لا تقوم عملية الشريحة بتخصيص ذاكرة جديدة.

تحويل

التناظرية من std::queue و std::deque .

تقوم قوائم الانتظار بتنفيذ عمليات الاسترجاع والإضافة للبدء والنهاية في وقت ثابت. يتم حذف العنصر الذي تم وضعه أولاً (أولاً - أولاً - أولاً - FIFO) أولاً من قائمة الانتظار. القناة المخزنة مؤقتًا هي قائمة انتظار على مخزن مؤقت للحلقات ، يمكنك استخدامها عندما يكون القارئ والكاتب مختلفين. ولكن لا يوجد تطبيق قائمة انتظار منفصل في المكتبة القياسية. قائمة الذهاب رهيبة تنصح مكتبة https://github.com/gammazero/deque .

 import "github.com/gammazero/deque" 

العمليات الجارية:

 func (q *Deque) PushBack(elem interface{}) func (q *Deque) PushFront(elem interface{}) func (q *Deque) PopBack() interface{} func (q *Deque) PopFront() interface{} func (q *Deque) Back() interface{} func (q *Deque) Front() interface{} func (q *Deque) At(i int) interface{} 

قائمة مرتبطة مزدوجة

مماثلة إلى std::list .
يتكون من عناصر تحتوي ، بالإضافة إلى البيانات الخاصة بهم ، على روابط لعنصر القائمة التالي والسابق. في المكتبة القياسية:

 import "container/list" 

كما هو متوقع ، يدعم الإدخال (إلى البداية ، إلى النهاية ، قبل وبعد العنصر الذي يتم تمرير المؤشر إليه) والحذف.

 func (l *List) PushBack(v interface{}) *Element func (l *List) PushFront(v interface{}) *Element func (l *List) InsertAfter(v interface{}, mark *Element) *Element func (l *List) InsertBefore(v interface{}, mark *Element) *Element func (l *List) Remove(e *Element) interface{} 

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

 func (e *Element) Next() *Element func (e *Element) Prev() *Element 

قائمة انتظار الأولوية

التناظرية std::priority_queue
يتيح لك تجميع العناصر في أي ترتيب ، والحصول في أي وقت على أولوية أعلى للباقي. يتم استخدامه ، على سبيل المثال ، في الخوارزمية الخاصة ببناء شجرة الامتداد الدنيا ، عندما تقوم الخوارزمية في الخطوة التالية بتحديد أقصر حافة جميعها بدءًا من القمم المغطاة بالفعل في نهاية واحدة.

تحتوي المكتبة القياسية على محول يقوم بتحويل أي حاوية قابلة للفرز (والتي تنفذ sort.Interface ) إلى قائمة انتظار أولوية.

 import "container/heap" 

هذا هو كومة ثنائية الكلاسيكية. تنفذ الإدراج والحذف في O (سجل ن).

 func Pop(h Interface) interface{} func Push(h Interface, x interface{}) func Remove(h Interface, i int) interface{} 

جدول التجزئة

إنه قاموس ومجموعة نقابية.

التناظرية std::unordered_map .

يتيح لك إضافة قيمة مفتاح ، وحذف القيمة حسب المفتاح والتحقق من وجود عنصر لـ O (1) في المتوسط. من الواضح أن الخريطة مبنية على اللغة:

 unorderedMap := make(map[string]int) 

نتيجة make (map) هي مؤشر ، والطريقة التي تعمل بها تختلف قليلاً عن الحاويات القياسية:

 //  : _, ok := unorderedMap["route"] //  : delete(unorderedMap, "route") //  : n := len(unorderedMap) 

"Runtime / map" ، على عكس std :: unordered_map ، يعتني بالمبرمج - من الآمن حذف القيم أثناء التكرار.

كثير

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

 var m = make(map[string]struct{}) m["!"] = struct{}{} _, ok := m["!"] // true 

لكن هذا التطبيق لا يدعم المشغلين المعقدين. لدمج ، والتقاط ، والاختلاف من المربع ، تحتاج إلى مكتبات تابعة لجهات أخرى. الأكثر استخدامًا ، وفقًا لعدد النجوم: https://github.com/deckarep/golang-set

 import "github.com/deckarep/golang-set" 

الجزء الأكثر حاجة من API :

 Add(i interface{}) bool Remove(i interface{}) Cardinality() int // len() Contains(i ...interface{}) bool IsSubset(other Set) bool Intersect(other Set) Set Union(other Set) Set Difference(other Set) Set SymmetricDifference(other Set) Set 

تعيين كثافة العمليات

في الجزء التجريبي من المكتبة القياسية ، هناك مجموعة محسَّنة int توفر كل قطعة.

 import "golang.org/x/tools/container/intsets" 

كما أنه يدعم الاتحاد ، التقاطع ، اختلاف المجموعات.

أشجار البحث الثنائية

النظير std::set و std::map .
قد يبدو وكأنه نظائر سيئة المبتدئ من الجداول التجزئة:
كما يدعم إضافة ، إزالة والتحقق من الحوادث ، ولكن وراء O (سجل ن).
لكن الأشجار تخزين العقد مرتبة حسب المفتاح.

لا توجد أشجار في مكتبة go القياسية ، حيث يتم استخدام مستودع يحتوي على AVL و Red-Black و B-tree على نطاق واسع.

 import "github.com/emirpasic/gods/trees/avltree" 

طرق API الأكثر استخدامًا:

 func (tree *Tree) Get(key interface{}) (value interface{}, found bool) func (tree *Tree) Put(key interface{}, value interface{}) func (tree *Tree) Remove(key interface{}) func (tree *Tree) Size() int func (tree *Tree) Keys() []interface{} func (tree *Tree) Values() []interface{} func (tree *Tree) Left() *Node func (tree *Tree) Right() *Node 

هناك طريقتان مهمتان للغاية:

 func (tree *Tree) Ceiling(key interface{}) (ceiling *Node, found bool) 

إرجاع أصغر عنصر موجود أكبر من المفتاح.

 func (tree *Tree) Floor(key interface{}) (floor *Node, found bool) 

إرجاع أكبر عنصر موجود أقل من مفتاح.

غالبًا ما توجد مهام هذا في المقابلات. في الحياة الحقيقية يتم استخدامه في فهارس قاعدة البيانات:

 select x from table where x <= $1 limit 1; 

إذا كان هناك فهرس ، فسيعمل من أجل O (log n) ، من أجل البحث عن الحدود في الشجرة B.

مرشح بلوم

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

 import "github.com/willf/bloom" 

لا تستخدم في كثير من الأحيان ، يمكنك إلقاء نظرة خاطفة على API .

HyperLogLog

لا يوجد شيء من هذا القبيل في مكتبة C ++ القياسية.

بنية البيانات الاحتمالية. مع وجود خطأ بسيط (≈ 0.4٪) ، فإنه يأخذ في الاعتبار عدد العناصر الفريدة دون تخزين المفاتيح بأنفسهم. ويوفر وفورات ضخمة في الذاكرة. إذا كانت المهمة هي حساب عدد الزوار أو الطلبات بسرعة - يعد HyperLogLog مثاليًا.

المكتبة الأكثر شعبية لهذا الآن.

https://github.com/axiomhq/hyperloglog

 import "github.com/axiomhq/hyperloglog" 

الفرز

النظير std::sort std::stable_sort .
من وجهة نظر المستهلك ، هناك فقط نوعان مختلفان بشكل أساسي:
ثابت (لا تقم بتغيير ترتيب العناصر المتساوية [[4 ، 0] ، [1 ، 2] ، [1 ، 1] ، [5 ، 6]] -> [[1 ، 2] ، [1 ، 1] ، [4 ، 0] ، [5 ، 6]])
وغير مستقر ، لا يضمن اتساق الحقول المتبقية.
كلاهما في المكتبة القياسية:

 func Sort(data Interface) 

هذا هو تنفيذ فرز سريع هوار ، غير مستقر. ولكن بالنسبة للأقسام ذات الطول <12 ، يتم استخدام فرز كومة الذاكرة المؤقتة كتحسين.

 func Stable(data Interface) 

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

هذه هي الخوارزميات الكلاسيكية التي تعمل من أجل O (n log n).

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