مرحبا مرة اخرى قبل المغادرة إلى عطلة نهاية الأسبوع ، نريد أن نطلعكم على ترجمة للمواد التي تم إعدادها خصيصًا للدورة التدريبية الأساسية "iOS-developer" .
غالبًا ما يكون تحديد بنية البيانات المراد استخدامها لتمثيل مجموعة معينة من القيم أكثر صعوبة مما يبدو. نظرًا لأنه تم تحسين كل نوع من أنواع بنية البيانات لعدد معين من حالات الاستخدام ، فغالبًا ما يكون لاختيار المناسب لكل مجموعة بيانات تأثير كبير على أداء الكود الخاص بنا.
تحتوي مكتبة Swift القياسية على ثلاثة هياكل بيانات رئيسية -
Array و
Dictionary و
Set ، ولكل منها مجموعة خاصة به من التحسينات والإيجابيات والسلبيات. دعونا نلقي نظرة على بعض خصائصها ، وكذلك الحالات التي قد نحتاج فيها إلى تجاوز المكتبة القياسية للعثور على بنية البيانات المناسبة لأغراضنا.
الخطية صفيف
Array المحتمل أن يكون
Array أحد بنيات البيانات الأكثر استخدامًا في Swift ، وهناك أسباب وجيهة لذلك. إنه يخزن عناصره بالتسلسل ، ويتم فرزها بسهولة بطريقة يمكن التنبؤ بها ، ويمكن تخزين أي قيم فيها: من الهياكل إلى مثيلات الفئات والمجموعات الأخرى.
على سبيل المثال ، هنا نستخدم صفيفًا لتخزين مجموعة من الأشكال الموضوعة على
Canvas في تطبيق رسم. ثم ، عندما نحتاج إلى تقديم اللوحة القماشية إلى صورة ، فإننا نذهب إلى الصفيف لرسم كل عنصر باستخدام
DrawingContext - كما يلي:
struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } }
عندما يتعلق الأمر بالعرض المتسلسل لجميع أشكالنا ، كما فعلنا أعلاه ، فإن الصفيف مناسب تمامًا. لا تقوم المصفوفات بتخزين عناصرها بطريقة فعالة للغاية فحسب ، بل لها أيضًا ترتيب فرز مضمون ، والذي يوفر ترتيب تقديم يمكن التنبؤ به دون الاضطرار إلى القيام بأي عمل إضافي.
ومع ذلك ، مثل كل هياكل البيانات الأخرى ، فإن للصفائف عيوبها. في حالتنا ، سنواجه إحدى عيوبه عندما نريد إزالة الأشكال من القماش. نظرًا لأن عناصر المصفوفة يتم تخزينها حسب الفهرس ، نحتاج دائمًا إلى البحث أولاً عن الفهرس المرتبط بالشكل قبل أن نتمكن من حذفه:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } }
في البداية ، قد لا يبدو الرمز أعلاه مشكلة ، ولكنه قد يصبح عنق الزجاجة في أداء أي قماش يحتوي على عدد كبير من الأشكال ، لأن
firstIndex خطي (O (N)) من حيث
تعقيد الوقت .
على الرغم من أننا يمكن أن نتغلب على هذا القيد حيث نستخدم لدينا نوع من قماش. على سبيل المثال ، الإشارة دائمًا إلى الأرقام حسب الفهرس ، وليس حسب القيمة أو المعرف - هذا سيجعل الكود لدينا أكثر تعقيدًا وهشاشة ، حيث سيتعين علينا دائمًا التأكد من أن فهارسنا لا تنتهي صلاحيتها عندما تكون اللوحة التي نعمل معها سوف يتغير.
مجموعات السرعة
بدلاً من ذلك ، دعنا نرى ما إذا كنا نستطيع تحسين
Canvas نفسها عن طريق تغيير هيكل البيانات الأساسي. بالنظر إلى المشكلة المذكورة أعلاه ، قد تكون إحدى أفكارنا الأولية هي استخدام
Set (sets) بدلاً من
Array . كما سبق أن ناقشنا في
قوة المجموعات في Swift ، فإن إحدى الميزات المهمة للمجموعات على المصفوفات هي أنه يمكن دائمًا تنفيذ كل من الحذف والإدخال في وقت ثابت (O (1)) ، منذ يتم تخزين العناصر حسب قيمة التجزئة ، وليس عن طريق الفهرس.
من خلال تحديث
Canvas لاستخدام المجموعات ، نحصل على ما يلي:
struct Canvas { var shapes: Set<Shape> func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func remove(_ shape: Shape) { shapes.remove(shape) } }
مرة أخرى ، قد يبدو الرمز أعلاه صحيحًا ، وحتى يتم تجميعه بدون مشاكل. ومع ذلك ، على الرغم من أننا قمنا بحل مشكلة الحذف ، فقد فقدنا أيضًا نظام التقديم الثابت - لأن المجموعات ، على عكس المصفوفات ، لا تمدنا بترتيب فرز مضمون - وهو حجر عثرة في هذه الحالة ، حيث يبدو أننا سنرسم أشكالًا مخصصة في المراوغة.
فهارس الفهارس
دعنا نواصل التجربة. الآن ، لنرى ما إذا كان يمكننا تحسين لوحة
Canvas خلال تقديم
Dictionary ، والذي يسمح لنا بالبحث عن فهرس أي شكل بناءً على معرفه. سنبدأ بتغيير مستوى الوصول لمجموعة الصفيف
private بنا إلى
private حتى نتمكن من التحكم في إدراج العناصر باستخدام طريقة
add الجديدة. وفي كل مرة يتم إضافة شخصية جديدة ، نضيف أيضًا فهرسها إلى قاموسنا:
struct Canvas { private var shapes = [Shape]() private var indexes = [Shape.ID : Int]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { let index = shapes.count indexes[shape.id] = index shapes.append(shape) } }
بما أننا نعرف الآن في أي مؤشر يتم تخزين رقم معين ، يمكننا تنفيذ الحذف بسرعة في وقت ثابت ، كما هو الحال عند استخدام مجموعة:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } }
ومع ذلك ، هناك خلل خطير جدا في تنفيذ
Canvas الجديد لدينا. في كل مرة نقوم بحذف شكل ما ، فإننا نبطل فعليًا جميع الفهارس الأعلى من الفهرسة التي قمنا بحذفها للتو - لأن كل عنصر من هذه العناصر سينتقل خطوة واحدة إلى بداية الصفيف. يمكننا حل هذه المشكلة عن طريق ضبط هذه المؤشرات بعد كل عملية حذف ، ولكن هذا سيعيدنا مرة أخرى إلى منطقة O (N) ، والتي حاولنا تجنبها من البداية.
تطبيقنا الأخير له مزاياه. بشكل عام ، قد يكون استخدام مزيج من بنيتين للبيانات فكرة رائعة في مثل هذه الحالات ، حيث يمكننا غالبًا استخدام نقاط القوة في بنية بيانات واحدة للتعويض عن أوجه القصور في الآخر ، والعكس بالعكس.
لذلك ، دعونا نحاول مرة أخرى بمزيج مختلف ، لكن هذه المرة لنبدأ بالنظر في متطلباتنا
الحقيقية :
- نحتاج إلى كل من عمليات الإدراج والحذف للحصول على تعقيد زمني ثابت ، ويجب أن يكون من الممكن حذف الشكل دون معرفة فهرسه الأساسي.
- نحتاج إلى ترتيب فرز مضمون حتى نتمكن من الحفاظ على ترتيب تقديم ثابت.
بالنظر إلى المتطلبات المذكورة أعلاه ، اتضح أنه على الرغم من أننا نحتاج إلى ترتيب فرز مستقر ، إلا أننا في الواقع لا نحتاج إلى فهارس. هذا من شأنه أن يجعل القائمة المرتبطة مثالية لحالة الاستخدام لدينا.
تتكون القوائم المرتبطة من العقد ، حيث تحتوي كل عقدة على رابط (أو رابط) إلى العقدة التالية في القائمة ، مما يعني أنه يمكن فرزها بطريقة يمكن التنبؤ بها - دون الحاجة إلى أي تحديثات فهرس عند حذف عنصر. ومع ذلك ، فإن مكتبة Swift القياسية (حتى الآن) لا تحتوي على نوع قائمة مرتبط ، لذا إذا أردنا استخدامها ، يجب علينا أولاً إنشاؤها.
إنشاء قائمة مرتبطة
لنبدأ بإعلان هيكل
List الذي سيتعقب العقدتين الأولى والأخيرة في قائمتنا. سنجعل كل من هذه الخصائص للقراءة فقط خارج نوعنا لضمان اتساق البيانات:
struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? }
بعد ذلك ، لنقم بإنشاء نوع العقدة (العقدة) الخاص بنا ، والذي سنقوم بإنشاء فصل ، لأننا نريد أن نكون قادرين على الرجوع إلى العقد
حسب المرجع وليس القيمة . سيتم ربط قائمتنا على نحو مضاعف ، مما يعني أن كل عقدة ستحتوي على رابط لكل من جارتها التالية والقائمة السابقة. ستخزن كل عقدة قيمة - مثل هذا:
extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } }
السبب في أننا نجعل العقار السابق ضعيفًا هو تجنب حلقات الاحتفاظ التي قد تظهر إذا احتفظنا بروابط قوية في كلا الاتجاهين. لمعرفة المزيد حول تجنب الإبقاء على الدورات ، راجع مقالة "إدارة الذاكرة" .
هذا هو في الواقع كل الشفرة التي نحتاجها حتى يمكن تخزين القيم في قائمتنا المرتبطة. ولكن هذا ليس سوى الجزء الأول من اللغز ، كما هو الحال في أي مجموعة أخرى ، نريد أيضًا أن نكون قادرين على التكرار فوقه وتغيير محتوياته. لنبدأ بالتكرارات ، التي بفضل تصميم Swift شديد البروتوكولات ، يمكن تنفيذها بسهولة من خلال ضمان الامتثال لبروتوكول
Sequence وتنفيذ طريقة
makeIterator :
extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator {
نظرًا لأن التكرار أعلاه بسيط للغاية ، فإننا نستخدم مكتبة AnyIterator القياسية لتجنب الحاجة إلى تطبيق نوع التكرار المخصص. لسيناريوهات أكثر تعقيدًا ، يمكن تنفيذها عن طريق إضافة تطابق إلى IteratorProtocol .
بعد ذلك ، دعونا نضيف واجهة برمجة التطبيقات لتعديل قائمتنا المرتبطة ، بدءًا من عمليات الإدراج. سنقوم بتوسيع
List باستخدام طريقة
append ، التي تضيف عقدة جديدة للقيمة المدرجة ، ثم تُرجع هذه العقدة - كما يلي:
extension List { @discardableResult mutating func append(_ value: Value) -> Node { let node = Node(value: value) node.previous = lastNode lastNode?.next = node lastNode = node if firstNode == nil { firstNode = node } return node } }
أعلاه ، نحن نستخدم السمة @discardableResult ، التي تخبر المترجم بعدم إنشاء أي تحذيرات إذا لم يتم استخدام نتيجة الاتصال @discardableResult ، لأننا لسنا مهتمين دائمًا بالعقدة التي تم إنشاؤها.
نظرًا لأن القوائم المرتبطة لا تستند إلى فهارس ، ولكن إلى الحفاظ على سلسلة من القيم من خلال الارتباطات ، فإن تنفيذ عمليات الحذف هو مجرد تحديث للجيران التاليين والسابقين للعقد البعيدة بحيث تشير إلى بعضها البعض بدلاً من ذلك:
extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous
بناءً على ما تقدم ، يتم إكمال الإصدار الأولي من قائمتنا ، ونحن على استعداد للتحقق من ذلك أثناء العمل. لنقم بتحديث اللوحة القماشية لاستخدام قائمتنا الجديدة ، فضلاً عن القاموس الذي يسمح لنا بالعثور بسرعة على أي عقدة تطابق معرف شكل محدد:
struct Canvas { private var shapes = List<Shape>() private var nodes = [Shape.ID : List<Shape>.Node]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { nodes[shape.id] = shapes.append(shape) } mutating func remove(_ shape: Shape) { guard let node = nodes.removeValue(forKey: shape.id) else { return } shapes.remove(node) } }
الآن لدينا كل من عمليات الإدراج والحذف السريعة ، وترتيب الفرز الذي يمكن التنبؤ به ، دون الحاجة إلى إضافة تعقيد إضافي لعملية المكالمة - إنه أمر رائع! ونظرًا لأن قائمتنا الجديدة نوع عالمي تمامًا ، يمكننا الآن استخدامه كلما احتجنا مرة أخرى إلى تخزين القيم بدون فهرس بطريقة خطية.
استنتاج
على الرغم من أن هياكل البيانات أساسية جدًا بحيث يمكن العثور عليها في جميع أنواع لغات البرمجة ، إلا أن القرار حول أي لغة ستستخدم في كل موقف معين قد لا يزال يتطلب قدراً كبيراً من التفكير والاختبار والتجريب ، خاصة إذا كنا نريد بحيث تظل الشفرة الخاصة بنا فعالة مع نمو مجموعة البيانات.
من المحتمل أيضًا أن تتغير بنية البيانات المناسبة لكل موقف معين بمرور الوقت نظرًا لأن متطلباتنا تتغير ، وأحيانًا قد يكون استخدام مزيج من عدة هياكل بيانات ، وليس واحدة فقط ، وسيلة لتحقيق خصائص الأداء المطلوبة.
سوف نستمر في استكشاف عالم هياكل البيانات في المقالات التالية ، مع التركيز على تلك التي لم يتم تنفيذها بعد في المكتبة القياسية. كما هو الحال مع العديد من الأشياء الأخرى ، في بعض الأحيان نحتاج إلى توسيع تفكيرنا إلى ما وراء سويفت لاختيار هيكل البيانات المناسب لكل موقف.
يمكنك أن تجد لي
على تويتر أو البريد الإلكتروني إذا كان لديك أي أسئلة أو تعليقات أو تعليقات.
شكرا لاهتمامكم!