بنى البيانات

9. بنى البيانات

بنى البيانات الفعّالة مكونات أساسية مهمة للبرامج الكبيرة. وسنناقش في هذا الفصل ما يعنيه أن تكون بنية البيانات فعّالة، وكيف ننفّذ بعض بنى البيانات الفعّالة بالبرمجة الأمرية والوظيفية معًا، ونتعلم تقنية التحليل المُستهلَك (amortized analysis).

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

وسنلقي نظرة أيضًا على بعض بنى البيانات الوظيفية الرائعة التي تظهر أقل في اللغات الأمرية: المتتاليات (sequences)، وهي قوائم لا نهائية منفَّذة بدوال تُسمى الثنكات (thunks)؛ والقوائم الكسولة (lazy lists)، المنفَّذة بميزة لغوية (يُسميها بحق «الكسل») تعلّق التقييم؛ والمصفوفات الدائمة (persistent arrays)، التي توفر أداءً كثيرًا ما يكون ثابت الزمن مع كونها دائمة.

9.1. جداول التجزئة

جدول التجزئة (hash table) بنية بيانات واسعة الاستخدام يعتمد أداؤها على القابلية للتغيير. وتنفيذ جدول التجزئة معقد إلى حد ما مقارنة ببنى البيانات الأخرى التي نفّذناها حتى الآن. وسنبنيه خطوة خطوة، حتى نتمكن من تقدير الحاجة إلى كل جزء واستخدامه.

9.1.1. الخرائط

تنفّذ جداول التجزئة تجريد بيانات الخريطة (map). وتربط الخريطة مفاتيح (keys) بـقيم (values). وهذا التجريد مفيد إلى حد أنه يُعرف بأسماء أخرى كثيرة، منها المصفوفة الترابطية (associative array) والقاموس (dictionary) وجدول الرموز (symbol table). وسنكتب الخرائط كتابةً مجرّدة (أي رياضية؛ لا بصياغة OCaml الفعلية) بالشكل { $k_1 : v_1, k_2: v_2, \ldots, k_n : v_n$ }. وكل $k : v$ هو ارتباط (binding) للمفتاح $k$ بالقيمة $v$. وإليك مثالين:

• خريطة تربط رقم مقرر بشيء يتعلق به: {3110 : “Fun”, 2110 : “OO”}.
• خريطة تربط اسم جامعة بسنة إنشائها: {“Harvard” : 1636, “Princeton” : 1746, “Penn”: 1740, “Cornell” : 1865}.

لا يهم ترتيب كتابة الارتباطات كتابةً مجرّدة، لذا يمكن كتابة المثال الأول أيضًا بالشكل {2110 : “OO”, 3110 : “Fun”}. ولهذا نستخدم أقواس المجموعات—فهي توحي بأن الارتباطات مجموعة، دون ترتيب ضمني.

ملاحظة

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

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

وإليك واجهة للخرائط:

module type Map = sig
  (** [('k, 'v) t] is the type of maps that bind keys of type
      ['k] to values of type ['v]. *)
  type ('k, 'v) t
  (** [insert k v m] is the same map as [m], but with an additional
      binding from [k] to [v].  If [k] was already bound in [m],
      that binding is replaced by the binding to [v] in the new map. *)
  val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t
  (** [find k m] is [Some v] if [k] is bound to [v] in [m],
      and [None] if not. *)
  val find : 'k -> ('k, 'v) t -> 'v option
  (** [remove k m] is the same map as [m], but without any binding of [k].
      If [k] was not bound in [m], then the map is unchanged. *)
  val remove : 'k -> ('k, 'v) t -> ('k, 'v) t
  (** [empty] is the empty map. *)
  val empty : ('k, 'v) t
  (** [of_list lst] is a map containing the same bindings as
      association list [lst].
      Requires: [lst] does not contain any duplicate keys. *)
  val of_list : ('k * 'v) list -> ('k, 'v) t
  (** [bindings m] is an association list containing the same
      bindings as [m]. There are no duplicates in the list. *)
  val bindings : ('k, 'v) t -> ('k * 'v) list
end

module type Map =
  sig
    type ('k, 'v) t
    val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t
    val find : 'k -> ('k, 'v) t -> 'v option
    val remove : 'k -> ('k, 'v) t -> ('k, 'v) t
    val empty : ('k, 'v) t
    val of_list : ('k * 'v) list -> ('k, 'v) t
    val bindings : ('k, 'v) t -> ('k * 'v) list
  end

وسنفحص بعد ذلك ثلاثة تنفيذات للخرائط قائمة على

• القوائم الترابطية،
• المصفوفات، و
• مزيج مما سبق يُعرف بـ جدول التجزئة مع السلسلة (hash table with chaining).

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

9.1.2. الخرائط كقوائم ترابطية

أبسط تنفيذ لخريطة في OCaml هو كقائمة ترابطية. وقد رأينا ذلك التمثيل مرتين حتى الآن 1 2. وإليك تنفيذًا للوحدة Map باستخدامه:

module ListMap : Map = struct
  (** AF: [[(k1, v1); (k2, v2); ...; (kn, vn)]] is the map {k1 : v1, k2 : v2,
      ..., kn : vn}. If a key appears more than once in the list, then in the
      map it is bound to the left-most occurrence in the list. For example,
      [[(k, v1); (k, v2)]] represents {k : v1}. The empty list represents
      the empty map.
      RI: none. *)
  type ('k, 'v) t = ('k * 'v) list
  (** Efficiency: O(1). *)
  let insert k v m = (k, v) :: m
  (** Efficiency: O(n). *)
  let find = List.assoc_opt
  (** Efficiency: O(n). *)
  let remove k lst = List.filter (fun (k', _) -> k <> k') lst
  (** Efficiency: O(1). *)
  let empty = []
  (** Efficiency: O(1). *)
  let of_list lst = lst
  (** [keys m] is a list of the keys in [m], without
      any duplicates.
      Efficiency: O(n log n). *)
  let keys m = m |> List.map fst |> List.sort_uniq Stdlib.compare
  (** [binding m k] is [(k, v)], where [v] is the value that [k]
      binds in [m].
      Requires: [k] is a key in [m].
      Efficiency: O(n). *)
  let binding m k = (k, List.assoc k m)
  (** Efficiency: O(n log n) + O(n) * O(n), which is O(n^2). *)
  let bindings m = List.map (binding m) (keys m)
end

module ListMap : Map

9.1.3. الخرائط كمصفوفات

الخرائط القابلة للتغيير (Mutable maps) خرائط يجوز تغيير ارتباطاتها. ولذا تختلف واجهة الخريطة القابلة للتغيير عن الخريطة غير القابلة للتغيير. ولذلك تعيد عمليات الإدراج والإزالة في الخريطة القابلة للتغيير unit، لأنها لا تنتج خريطة جديدة بل تغيّر خريطة قائمة.

ويمكن استخدام مصفوفة لتمثيل خريطة قابلة للتغيير مفاتيحها أعداد صحيحة. ويُخزَّن الارتباط من مفتاح إلى قيمة باستخدام المفتاح كفهرس في المصفوفة، وتخزين الارتباط عند ذلك الفهرس. فمثلًا، يمكننا استخدام مصفوفة لربط أرقام المكاتب بشاغليها:

ويُسمى هذا النوع من الخرائط جدول العنونة المباشرة (direct address table). ولأن المصفوفات ذات حجم ثابت، صار المنفّذ بحاجة إلى معرفة رغبة العميل في سعة (capacity) الجدول (أي عدد الارتباطات التي يمكن تخزينها فيه) كلما أُنشئ جدول فارغ. ويؤدي ذلك إلى الواجهة التالية:

module type DirectAddressMap = sig
  (** [t] is the type of maps that bind keys of type int to values of
      type ['v]. *)
  type 'v t
  (** [insert k v m] mutates map [m] to bind [k] to [v]. If [k] was
      already bound in [m], that binding is replaced by the binding to
      [v] in the new map. Requires: [k] is in bounds for [m]. *)
  val insert : int -> 'v -> 'v t -> unit
  (** [find k m] is [Some v] if [k] is bound to [v] in [m], and [None]
      if not. Requires: [k] is in bounds for [m]. *)
  val find : int -> 'v t -> 'v option
  (** [remove k m] mutates [m] to remove any binding of [k]. If [k] was
      not bound in [m], then the map is unchanged. Requires: [k] is in
      bounds for [m]. *)
  val remove : int -> 'v t -> unit
  (** [create c] creates a map with capacity [c]. Keys [0] through [c-1]
      are _in bounds_ for the map. *)
  val create : int -> 'v t
  (** [of_list c lst] is a map containing the same bindings as
      association list [lst] and with capacity [c]. Requires: [lst] does
      not contain any duplicate keys, and every key in [lst] is in
      bounds for capacity [c]. *)
  val of_list : int -> (int * 'v) list -> 'v t
  (** [bindings m] is an association list containing the same bindings
      as [m]. There are no duplicate keys in the list. *)
  val bindings : 'v t -> (int * 'v) list
end

module type DirectAddressMap =
  sig
    type 'v t
    val insert : int -> 'v -> 'v t -> unit
    val find : int -> 'v t -> 'v option
    val remove : int -> 'v t -> unit
    val create : int -> 'v t
    val of_list : int -> (int * 'v) list -> 'v t
    val bindings : 'v t -> (int * 'v) list
  end

وإليك تنفيذًا لتلك الواجهة:

module ArrayMap : DirectAddressMap = struct
  (** AF: [[|Some v0; Some v1; ... |]] represents {0 : v0, 1 : v1, ...}.
      If element [i] of the array is instead [None], then [i] is not
      bound in the map.
      RI: None. *)
  type 'v t = 'v option array
  (** Efficiency: O(1). *)
  let insert k v a = a.(k) <- Some v
  (** Efficiency: O(1). *)
  let find k a = a.(k)
  (** Efficiency: O(1). *)
  let remove k a = a.(k) <- None
  (** Efficiency: O(c). *)
  let create c = Array.make c None
  (** Efficiency: O(c). *)
  let of_list c lst =
    (* O(c) *)
    let a = create c in
    (* O(c) * O(1) = O(c) *)
    List.iter (fun (k, v) -> insert k v a) lst;
    a
  (** Efficiency: O(c). *)
  let bindings a =
    let bs = ref [] in
    (* O(1) *)
    let add_binding k v =
      match v with None -> () | Some v -> bs := (k, v) :: !bs
    in
    (* O(c) *)
    Array.iteri add_binding a;
    !bs
end

module ArrayMap : DirectAddressMap

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

9.1.4. الخرائط كجداول تجزئة

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

والفكرة الجوهرية أننا نفترض وجود دالة تجزئة (hash function) hash : 'a -> int يمكنها تحويل أي مفتاح إلى عدد صحيح غير سالب. ثم يمكننا استخدام تلك الدالة للفهرسة في مصفوفة، كما فعلنا مع جداول العنونة المباشرة. وبالطبع نريد لدالة التجزئة نفسها أن تعمل في زمن ثابت، وإلا فلن تكون العمليات التي تستخدمها فعّالة.

ويؤدي ذلك إلى الواجهة التالية، التي يجب فيها على عميل جدول التجزئة تمرير دالة تجزئة عند إنشاء الجدول:

module type TableMap = sig
  (** [('k, 'v) t] is the type of mutable table-based maps that bind
      keys of type ['k] to values of type ['v]. *)
  type ('k, 'v) t
  (** [insert k v m] mutates map [m] to bind [k] to [v]. If [k] was
      already bound in [m], that binding is replaced by the binding to
      [v]. *)
  val insert : 'k -> 'v -> ('k, 'v) t -> unit
  (** [find k m] is [Some v] if [m] binds [k] to [v], and [None] if [m]
      does not bind [k]. *)
  val find : 'k -> ('k, 'v) t -> 'v option
  (** [remove k m] mutates [m] to remove any binding of [k]. If [k] was
      not bound in [m], the map is unchanged. *)
  val remove : 'k -> ('k, 'v) t -> unit
  (** [create hash c] creates a new table map with capacity [c] that
      will use [hash] as the function to convert keys to integers.
      Requires: The output of [hash] is always non-negative, and [hash]
      runs in constant time. *)
  val create : ('k -> int) -> int -> ('k, 'v) t
  (** [bindings m] is an association list containing the same bindings
      as [m]. *)
  val bindings : ('k, 'v) t -> ('k * 'v) list
  (** [of_list hash lst] creates a map with the same bindings as [lst],
      using [hash] as the hash function. Requires: [lst] does not
      contain any duplicate keys. *)
  val of_list : ('k -> int) -> ('k * 'v) list -> ('k, 'v) t
end

module type TableMap =
  sig
    type ('k, 'v) t
    val insert : 'k -> 'v -> ('k, 'v) t -> unit
    val find : 'k -> ('k, 'v) t -> 'v option
    val remove : 'k -> ('k, 'v) t -> unit
    val create : ('k -> int) -> int -> ('k, 'v) t
    val bindings : ('k, 'v) t -> ('k * 'v) list
    val of_list : ('k -> int) -> ('k * 'v) list -> ('k, 'v) t
  end

وثمة مشكلة فورية في هذه الفكرة: ما العمل إذا لم يكن مخرج دالة التجزئة ضمن حدود المصفوفة. ومن السهل حل ذلك: فإذا كانت a طول المصفوفة، فإن حساب (hash k) mod a سيعيد فهرسًا ضمن الحدود.

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

وثمة استراتيجيتان مشهورتان للتعامل مع التصادمات. الأولى تخزين ارتباطات متعددة عند كل فهرس من فهارس المصفوفة. وتُسمى عناصر المصفوفة دِلاء (buckets). ويُنفَّذ الدلو عادةً كقائمة مترابطة. وتُعرف هذه الاستراتيجية بأسماء كثيرة، منها السلسلة (chaining) والعنونة المغلقة (closed addressing) والتجزئة المفتوحة (open hashing). وسنستخدم اسم السلسلة. وللتحقق مما إذا كان عنصر في جدول التجزئة، تجزّأ المفتاح أولًا لإيجاد الدلو الصحيح للبحث فيه. ثم تُمسح القائمة المترابطة لمعرفة ما إذا كان العنصر المطلوب موجودًا. وإذا كانت القائمة المترابطة قصيرة، فكان المسح سريعًا جدًا. ويُضاف عنصر أو يُزال بتجزئته لإيجاد الدلو الصحيح. ثم يُفحص الدلو لمعرفة ما إذا كان العنصر فيه، وأخيرًا يُضاف العنصر أو يُزال من الدلو بالطريقة المعتادة للقوائم المترابطة.

أما الاستراتيجية الأخرى فتخزّن الارتباطات في مواضع غير موضعها الصحيح وفق التجزئة. فعندما تؤدي إضافة ارتباط جديد إلى جدول التجزئة إلى تصادم، تبحث عملية الإدراج بدلًا من ذلك عن موضع فارغ في المصفوفة لوضع الارتباط فيه. وتُعرف هذه الاستراتيجية (على نحو مربك) بـ الاستقصاء (probing) والعنونة المفتوحة (open addressing) والتجزئة المغلقة (closed hashing). وسنستخدم اسم الاستقصاء. ومن الطرق البسيطة لإيجاد موضع فارغ البحث إلى الأمام عبر فهارس المصفوفة بخطوة ثابتة (غالبًا 1) عن مدخلة غير مستخدمة؛ وتميل استراتيجية الاستقصاء الخطي (linear probing) هذه إلى إنتاج قدر كبير من التكتل في الجدول، مما يؤدي إلى أداء سيئ. والاستراتيجية الأفضل استخدام دالة تجزئة ثانية لحساب فاصل الاستقصاء؛ وتُسمى هذه الاستراتيجية التجزئة المزدوجة (double hashing). ومهما كانت طريقة تنفيذ الاستقصاء، فالزمن اللازم للبحث عن عنصر أو إضافته ينمو بسرعة مع امتلاء جدول التجزئة.

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

9.1.4.1. تمثيل السلسلة

إليك نوع تمثيل لجدول تجزئة يستخدم السلسلة:

type ('k, 'v) t = {
  hash : 'k -> int;
  mutable size : int;
  mutable buckets : ('k * 'v) list array
}

مصفوفة buckets عناصرها قوائم ترابطية تخزّن الارتباطات. وتُستخدم دالة hash لتحديد الدلو الذي يذهب إليه المفتاح. ويُستخدم size لتتبع عدد الارتباطات الموجودة حاليًا في الجدول، لأن حساب ذلك بالمرور على buckets سيكون مكلفًا.

وإليك دالة التجريد وثابت التمثيل:

  (** AF:  If [buckets] is
        [| [(k11,v11); (k12,v12); ...];
           [(k21,v21); (k22,v22); ...];
           ... |]
      that represents the map
        {k11:v11, k12:v12, ...,
         k21:v21, k22:v22, ...,  ...}.
      RI: No key appears more than once in the array (so, no
        duplicate keys in association lists).  All keys are
        in the right buckets: if [k] is in [buckets] at index
        [b] then [hash(k) = b]. The output of [hash] must always
        be non-negative. [hash] must run in constant time. *)

فماذا ستكون كفاءة insert وfind وremove لنوع التمثيل هذا؟ كلها تتطلب

• تجزئة المفتاح (زمن ثابت)،
• الفهرسة في الدلو المناسب (زمن ثابت)، و
• معرفة ما إذا كان المفتاح موجودًا بالفعل في القائمة الترابطية (زمن خطي في عدد عناصر تلك القائمة).

لذا تعتمد كفاءة جدول التجزئة على عدد العناصر في كل دلو. ويتحدد ذلك بدوره بمدى جودة توزيع دالة التجزئة للمفاتيح على جميع الدلاء.

ودالة تجزئة فظيعة، مثل الدالة الثابتة fun k -> 42، ستضع جميع المفاتيح في الدلو نفسه. وحينئذٍ ستكون كل عملية خطية في العدد $n$ لارتباطات الخريطة—أي $O(n)$. ولا نريد ذلك بالتأكيد.

بل نريد دوال تجزئة توزّع المفاتيح توزيعًا عشوائيًا إلى حد ما على الدلاء. وحينئذٍ سيكون الطول المتوقع لكل دلو متقاربًا. ولو أمكننا ترتيب الأمر بحيث يكون طول الدلو في المتوسط ثابتًا $L$، فسيعمل كل من insert وfind وremove في الزمن $O(L)$ في التوقع.

9.1.4.2. إعادة التحجيم

فكيف يمكننا ترتيب الدلاء لتكون ذات طول ثابت في التوقع؟ للإجابة عن ذلك، لنفكر في عدد الارتباطات والدلاء في الجدول. وعرّف معامل التحميل (load factor) للجدول بأنه

فجدول فيه 20 ارتباطًا و10 دِلاء معامل تحميله 2، وجدول فيه 10 ارتباطات و20 دلوًا معامل تحميله 0.5. فمعامل التحميل إذن هو متوسط عدد الارتباطات في الدلو. ولذا لو أمكننا إبقاء معامل التحميل ثابتًا، لأمكننا إبقاء $L$ ثابتًا، وبذلك يبقى الأداء (متوقعًا) في زمن ثابت.

ولهذا الغرض، لاحظ أن عدد الارتباطات ليس تحت سيطرة منفّذ جدول التجزئة—لكن عدد الدلاء كذلك. فبتغيير عدد الدلاء يستطيع المنفّذ تغيير معامل التحميل. ومن الاستراتيجيات الشائعة إبقاء معامل التحميل بين 1/2 و2 تقريبًا. وحينئذٍ لا يحتوي كل دلو إلا على ارتباط أو اثنين، ويكون الأداء الثابت الزمن المتوقع مضمونًا.

لكن ليس للمنفّذ سبيل إلى معرفة العدد الدقيق للدلاء التي ستلزم مسبقًا. لذا سيتعين عليه إعادة تحجيم (resize) مصفوفة الدلاء كلما صار معامل التحميل مرتفعًا جدًا. وعادةً يكون الدلو المخصص حديثًا بحجم يعيد معامل التحميل إلى نحو 1.

وبجمع الفكرتين معًا، إذا وصل معامل التحميل إلى 2، فهناك ارتباطات ضعف عدد الدلاء في الجدول. لذا بمضاعفة حجم المصفوفة يمكننا إعادة معامل التحميل إلى 1. وبالمثل، إذا وصل معامل التحميل إلى 1/2، فهناك دِلاء ضعف عدد الارتباطات، وتنصيف حجم المصفوفة سيعيد معامل التحميل إلى 1.

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

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

9.1.4.3. التنفيذ

يجمع تنفيذ جدول التجزئة أدناه كل الأجزاء التي ناقشناها أعلاه.

module HashMap : TableMap = struct
  (** AF and RI: above. *)
  type ('k, 'v) t = {
    hash : 'k -> int;
    mutable size : int;
    mutable buckets : ('k * 'v) list array
  }
  (** [capacity tab] is the number of buckets in [tab].
      Efficiency: O(1). *)
  let capacity {buckets} =
    Array.length buckets
  (** [load_factor tab] is the load factor of [tab], i.e., the number of
      bindings divided by the number of buckets. *)
  let load_factor tab =
    float_of_int tab.size /. float_of_int (capacity tab)
  (** Efficiency: O(n). *)
  let create hash n =
    {hash; size = 0; buckets = Array.make n []}
  (** [index k tab] is the index at which key [k] should be stored in the
      buckets of [tab].
      Efficiency: O(1). *)
  let index k tab =
    (tab.hash k) mod (capacity tab)
  (** [insert_no_resize k v tab] inserts a binding from [k] to [v] in [tab]
      and does not resize the table, regardless of what happens to the
      load factor.
      Efficiency: expected O(L). *)
  let insert_no_resize k v tab =
    let b = index k tab in (* O(1) *)
    let old_bucket = tab.buckets.(b) in
    tab.buckets.(b) <- (k,v) :: List.remove_assoc k old_bucket; (* O(L) *)
    if not (List.mem_assoc k old_bucket) then
      tab.size <- tab.size + 1;
    ()
  (** [rehash tab new_capacity] replaces the buckets array of [tab] with a new
      array of size [new_capacity], and re-inserts all the bindings of [tab]
      into the new array.  The keys are re-hashed, so the bindings will
      likely land in different buckets.
      Efficiency: O(n), where n is the number of bindings. *)
  let rehash tab new_capacity =
    (* insert [(k, v)] into [tab] *)
    let rehash_binding (k, v) =
      insert_no_resize k v tab
    in
    (* insert all bindings of bucket into [tab] *)
    let rehash_bucket bucket =
      List.iter rehash_binding bucket
    in
    let old_buckets = tab.buckets in
    tab.buckets <- Array.make new_capacity []; (* O(n) *)
    tab.size <- 0;
    (* [rehash_binding] is called by [rehash_bucket] once for every binding *)
    Array.iter rehash_bucket old_buckets (* expected O(n) *)
  (* [resize_if_needed tab] resizes and rehashes [tab] if the load factor
     is too big or too small.  Load factors are allowed to range from
     1/2 to 2. *)
  let resize_if_needed tab =
    let lf = load_factor tab in
    if lf > 2.0 then
      rehash tab (capacity tab * 2)
    else if lf < 0.5 then
      rehash tab (capacity tab / 2)
    else ()
  (** Efficiency: O(n). *)
  let insert k v tab =
    insert_no_resize k v tab; (* O(L) *)
    resize_if_needed tab (* O(n) *)
  (** Efficiency: expected O(L). *)
  let find k tab =
    List.assoc_opt k tab.buckets.(index k tab)
  (** [remove_no_resize k tab] removes [k] from [tab] and does not trigger
      a resize, regardless of what happens to the load factor.
      Efficiency: expected O(L). *)
  let remove_no_resize k tab =
    let b = index k tab in
    let old_bucket = tab.buckets.(b) in
    tab.buckets.(b) <- List.remove_assoc k tab.buckets.(b);
    if List.mem_assoc k old_bucket then
      tab.size <- tab.size - 1;
    ()
  (** Efficiency: O(n). *)
  let remove k tab =
    remove_no_resize k tab; (* O(L) *)
    resize_if_needed tab (* O(n) *)
  (** Efficiency: O(n). *)
  let bindings tab =
    Array.fold_left
      (fun acc bucket ->
         List.fold_left
           (* 1 cons for every binding, which is O(n) *)
           (fun acc (k,v) -> (k,v) :: acc)
           acc bucket)
      [] tab.buckets
  (** Efficiency: O(n^2). *)
  let of_list hash lst =
    let m = create hash (List.length lst) in  (* O(n) *)
    List.iter (fun (k, v) -> insert k v m) lst; (* n * O(n) is O(n^2) *)
    m
end

module HashMap : TableMap

وثمة تحسين ممكن لـ rehash. فعندما تستدعي insert_no_resize لإعادة إدراج ارتباط، يُؤدى عمل إضافي: فلا حاجة لتلك العملية إلى استدعاء remove_assoc أو mem_assoc، لأننا نضمن أن الارتباط لا يحتوي مفتاحًا مكررًا. ويمكننا إغفال ذلك العمل. وإذا كانت دالة التجزئة جيدة، فما نوفره قدر ثابت من العمل فحسب. لكن إذا كانت سيئة ولا توزع المفاتيح بانتظام، فقد يكون ذلك تحسينًا مهمًا.

9.1.5. دوال التجزئة

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

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

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

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

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

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

1. التسلسل (Serialization): حوّل المفتاح إلى تيار من البايتات يحتوي كل المعلومات في المفتاح الأصلي. ويجب أن ينتج مفتاحان متساويان تيار البايتات نفسه. وينبغي ألا يكون تيارا بايتات متساويين إلا إذا كان المفتاحان متساويين فعلًا. وكيفية ذلك تعتمد على شكل المفتاح. فإذا كان المفتاح سلسلة نصية، فسيكون تيار البايتات ببساطة محارف السلسلة.
2. الانتشار (Diffusion): اربط تيار البايتات بعدد صحيح كبير x على نحو يجعل كل تغيير في التيار يؤثر في بِتات x عشوائيًا كما يبدو. وثمة مقايضة هنا بين الأداء والعشوائية (والأمن).
3. الضغط (Compression): اختزل ذلك العدد الكبير ليكون ضمن مدى الدلاء. فمثلًا، احسب فهرس دلو التجزئة كـ x mod m. وهذا رخيص بشكل خاص إذا كانت m قوة من قوى اثنين.

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

9.1.6. وحدة Hashtbl في المكتبة القياسية

رغم أن معرفة كيفية تنفيذ جدول تجزئة، ورؤية كيفية استخدام القابلية للتغيير في ذلك، أمر رائع، فمن الرائع أيضًا ألا تضطر إلى تنفيذ بنية بيانات بنفسك في مشاريعك. ولحسن الحظ توفر المكتبة القياسية لـ OCaml وحدة Hashtbl [كذا] تنفّذ جداول التجزئة. ويمكنك التفكير في هذه الوحدة كمكافئ أمري لوحدة Map الوظيفية.

دالة التجزئة. تتولى الدالة Hashtbl.hash : 'a -> int مسؤولية التسلسل والانتشار. وهي قادرة على تجزئة أي نوع من القيم. ويشمل ذلك لا الأعداد الصحيحة فحسب بل السلاسل النصية والقوائم والأشجار وما إلى ذلك. فكيف تعمل في زمن ثابت، إذا كان طول شجرة أو حجم شجرة قد يكون اعتباطيًا كبيرًا؟ إنها تنظر فقط إلى عدد محدد مسبقًا من العقد ذات المعنى (meaningful nodes) في البنية التي تجزّئها. وهذا العدد هو 10 افتراضيًا. والعقدة ذات المعنى هي عدد صحيح أو عدد عشري أو سلسلة نصية أو محرف أو قيمة منطقية أو منشئ ثابت. ويمكنك رؤية ذلك ونحن نجزّئ هذه القوائم:

Hashtbl.hash [1; 2; 3; 4; 5; 6; 7; 8; 9];;
Hashtbl.hash [1; 2; 3; 4; 5; 6; 7; 8; 9; 10];;
Hashtbl.hash [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11];;
Hashtbl.hash [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12];;

- : int = 635296333

- : int = 822221246

- : int = 822221246

- : int = 822221246

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

جدول التجزئة. إليك ملخصًا لواجهة جدول التجزئة:

module type Hashtbl = sig
  type ('a, 'b) t
  val create : int -> ('a, 'b) t
  val add : ('a, 'b) t -> 'a -> 'b -> unit
  val find : ('a, 'b) t -> 'a -> 'b
  val remove : ('a, 'b) t -> 'a -> unit
  ...
end

يربط نوع التمثيل ('a, 'b) Hashtbl.t مفاتيح من النوع 'a بقيم من النوع 'b. وتهيئ الدالة create جدول تجزئة بسعة معينة، كما فعل تنفيذنا أعلاه. لكن بدلًا من إلزام العميل بتقديم دالة تجزئة، تستخدم الوحدة Hashtbl.hash.

تحدث إعادة التحجيم عندما يتجاوز معامل التحميل 2. ولنرَ ذلك يحدث. أولًا، سننشئ جدولًا ونملؤه:

open Hashtbl;;
let t = create 16;;
for i = 1 to 16 do
  add t i (string_of_int i)
done;;

val t : ('_weak1, '_weak2) Hashtbl.t = <abstr>

- : unit = ()

ويمكننا الاستعلام من جدول التجزئة لمعرفة كيفية توزيع الارتباطات على الدلاء بـ Hashtbl.stats:

stats t

- : Hashtbl.statistics =
{num_bindings = 16; num_buckets = 16; max_bucket_length = 3;
 bucket_histogram = [|6; 5; 4; 1|]}

عدد الارتباطات وعدد الدلاء متساويان، لذا فمعامل التحميل 1. والمدرّج التكراري للدلاء مصفوفة a يكون فيها a.(i) عدد الدلاء التي حجمها i.

ولنرفع معامل التحميل إلى 2:

for i = 17 to 32 do
  add t i (string_of_int i)
done;;
stats t;;

- : unit = ()

- : Hashtbl.statistics =
{num_bindings = 32; num_buckets = 16; max_bucket_length = 4;
 bucket_histogram = [|3; 3; 3; 5; 2|]}

الآن ستؤدي إضافة ارتباط واحد آخر إلى إثارة إعادة تحجيم، تضاعف عدد الدلاء:

add t 33 "33";;
stats t;;

- : unit = ()

- : Hashtbl.statistics =
{num_bindings = 33; num_buckets = 32; max_bucket_length = 3;
 bucket_histogram = [|11; 11; 8; 2|]}

لكن Hashtbl لا تنفّذ إعادة تحجيم عند الإزالة:

for i = 1 to 33 do
  remove t i
done;;
stats t;;

- : unit = ()

- : Hashtbl.statistics =
{num_bindings = 0; num_buckets = 32; max_bucket_length = 0;
 bucket_histogram = [|32|]}

عدد الدلاء ما زال 32، رغم إزالة جميع الارتباطات.

ملاحظة

لمنشئ Java الافتراضي HashMap() جدول تجزئة فارغ بسعة 16 يُعاد تحجيمه عندما يتجاوز معامل التحميل 0.75 لا 2. لذا تميل جداول تجزئة Java إلى أن يكون طول دلوها أقصر من جداول تجزئة OCaml، لكنها تميل أيضًا إلى شغل مساحة أكبر بسبب الدلاء الفارغة.

دوال التجزئة التي يقدمها العميل. ماذا لو وجد عميل لـ Hashtbl أن دالة التجزئة الافتراضية تؤدي إلى تصادمات، ومن ثمّ إلى أداء سيئ؟ حينئذٍ سيكون من المنطقي التحول إلى دالة تجزئة مختلفة. ولدعم ذلك، توفر Hashtbl واجهة قائمة على الدوال التصنيفية (functorial) مشابهة لـ Map. والدالة التصنيفية هي Hashtbl.Make، وتتطلب مدخلًا من نوع الوحدة التالي:

module type HashedType = sig
  type t
  val equal : t -> t -> bool
  val hash : t -> int
end

النوع t هو نوع مفتاح الجدول، وتوضح الدالتان equal وhash كيفية مقارنة المفاتيح للتساوي وكيفية تجزئتها. وإذا كان مفتاحان متساويين وفق equal، فيجب أن تكون لهما قيمة تجزئة واحدة وفق hash. ولو خُرق ذلك الشرط، لما بقي جدول التجزئة يعمل بصورة صحيحة. فمثلًا، لنفترض أن equal k1 k2 تصح لكن hash k1 <> hash k2. حينئذٍ سيُخزَّن k1 وk2 في دلوين مختلفين. فإذا أضاف عميل ارتباطًا لـ k1 بالقيمة v، ثم بحث عن k2، فلن يحصل على v.

ملاحظة

قد يبدو ذلك الشرط الأخير مألوفًا من Java. فهناك، إذا أعدت تعريف Object.equals() وObject.hashCode()، وجب ضمان التقابل نفسه.

9.2. التحليل المُستهلَك

خلص تحليلنا لكفاءة عمليات جدول التجزئة إلى أن find تعمل في زمن ثابت في التوقع، حيث يلزم المعدّل «في التوقع» للتعبير عن أن الأداء متوسط ويعتمد على استيفاء دالة التجزئة خواص معينة.

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

يتبين أن ثمة طريقة أخرى للنظر إلى هذا التحليل تتيح لنا أن نستنتج أن insert تتمتع فعلًا بأداء ثابت الزمن في التوقع مُستهلَك—أي لتبرير الأداء الخطي العرضي في أسوأ الحالات. وعينا أن نعترف فورًا بأن هذه التقنية مجرد تغيير في المنظور. فنحن لن نغيّر الخوارزميات الأساسية. فستبقى خوارزمية insert ذات أداء خطي في أسوأ الحالات. وهذه حقيقة.

لكن تغيير المنظور الذي نشرع فيه الآن هو الاعتراف بأنه إذا كان من النادر جدًا أن تتطلب insert زمنًا خطيًا، فربما يمكننا «توزيع» تلك الكلفة على سائر استدعاءات insert. إنها حيلة محاسبية إبداعية!

السوشي مقابل الرامن. لنُسلِ أنفسنا بمثال من العالم الواقعي للحظة. لنفترض أن لديك 20 دولارًا لتنفقها على الغداء خلال الأسبوع. وأنت تحب أكل السوشي، لكنك لا تستطيع تحمّل تناوله كل يوم. لذا تأكل بدلًا من ذلك كما يلي:

• الاثنين: رامن بدولار
• الثلاثاء: رامن بدولار
• الأربعاء: رامن بدولار
• الخميس: رامن بدولار
• الجمعة: سوشي بـ 16 دولارًا

في معظم الأوقات كان غداؤك رخيصًا. وفي مناسبة نادرة كان مكلفًا. لذا يمكنك النظر إلى الأمر بإحدى طريقتين:

• كانت كلفة غدائي في أسوأ الحالات 16 دولارًا.
• كانت كلفة غدائي في المتوسط 4 دولارات.

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

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

9.2.1. التحليل المُستهلَك لجداول التجزئة

«الاستهلاك» مصطلح مالي. ومن معانيه سداد دين على مر الزمن. وفي التحليل الخوارزمي نستخدمه للإشارة إلى سداد كلفة عملية مكلفة بتضخيم كلفة العمليات غير المكلفة. وفي الواقع، نحن ندفع مسبقًا كلفة عملية مكلفة لاحقة بإضافة بعض الكلفة الإضافية إلى عمليات رخيصة سابقة.

والتعقيد المُستهلَك (amortized complexity) أو زمن التشغيل المُستهلَك لمتتالية من العمليات كلفة كل منها $T_1, T_2, \ldots, T_n$، ليس إلا متوسط كلفة كل عملية:

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

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

لنفترض أن الجدول فيه 8 ارتباطات و8 دلاء. ثم تُجرى 8 عمليات إدراج أخرى. السبع الأولى ثابتة الزمن (في التوقع)، لكن الإدراج الثامن خطي الزمن: فهو يرفع معامل التحميل إلى 2، فيسبب إعادة تحجيم، ومن ثمّ إعادة تجزئة جميع الارتباطات الستة عشر في جدول جديد. لذا فالكلفة الإجمالية على تلك المتتالية من العمليات هي: كلفة 8 عمليات إدراج في الجدول القديم، زائد كلفة تخصيص جدول جديد من 16 عنصرًا، زائد كلفة 16 عملية إدراج في الجدول الجديد. أي كلفة إجمالية قدرها 40. إذن متوسط كلفة كل عملية في المتتالية هو 40/8 = 5 عمليات إدراج.

وبعبارة أخرى، لو تخيلنا أن كلفة كل إدراج خمسة أمثال سعره المعتاد، لكانت العملية الأخيرة في المتتالية قد «دُفعت مسبقًا» بالسعر الإضافي الذي دفعناه عن عمليات الإدراج السابقة. وستكون كلها ثابتة الزمن، لأن خمسة أمثال الثابت تبقى ثابتًا.

وبتعميم المثال أعلاه، لنفترض أن عدد الدلاء في جدول تجزئة هو حاليًا $2^n$، وأن معامل التحميل حاليًا 1. إذن توجد حاليًا $2^n$ ارتباطًا في الجدول. بعد ذلك:

• تحدث سلسلة من $2^n - 1$ عملية إدراج. فيصبح في الجدول $2^n + 2^n - 1$ ارتباطًا.
• تحدث عملية إدراج واحدة أخرى. فيرتفع عدد الارتباطات إلى $2^n + 2^n$، أي $2^{n+1}$. لكن عدد الدلاء $2^n$، فمعامل التحميل وصل للتو إلى 2. وتلزم إعادة تحجيم.
• تحدث إعادة التحجيم. وتكلفتها $2^{n+1}$ لتخصيص ذاكرة للجدول الجديد. ويضاعف ذلك عدد الدلاء. ويجب إعادة إدراج جميع الارتباطات $2^{n+1}$ في الجدول الجديد الذي حجمه $2^{n+1}$. ويعود معامل التحميل إلى 1.

إذن نفّذنا في المجموع $2^n + 2^{n+1}$ عملية إدراج، تضمنت $2^n$ إدراجًا للارتباطات و$2^{n+1}$ إعادة إدراج بعد إعادة التحجيم. وتحمّلنا أيضًا كلفة تخصيص جدول جديد حجمه $2^{n+1}$ في الذاكرة، وتلك الكلفة $2^{n+1}$.

وعلى سلسلة من $2^n$ عملية إدراج، يكون ذلك متوسط كلفة قدره $\frac{2^n + 2^{n+1} + 2^{n+1}}{2^n}$، ويساوي 5. فإذا تخيلنا إذن أن كلفة كل إدراج خمسة أمثال سعره المعتاد، كانت كل عملية في المتتالية ثابتة الزمن مُستهلَكًا (وفي التوقع).

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

• ابدأ بـ 100 دلو و100 ارتباط. معامل التحميل هو 1.
• الجولة 1. أدرج 100 ارتباط. فيصبح لديك 200 ارتباط و100 دلو. معامل التحميل 2.
• زد عدد الدلاء بمقدار 100 وأعد التجزئة. فتلك 200 عملية إدراج أخرى. ويعود معامل التحميل إلى 1.
• متوسط كلفة كل إدراج حتى الآن ثلاثة أمثال كلفة الإدراج الفعلي فقط (100+200 عملية إدراج / 100 ارتباط مُدرج). فكل شيء جيد حتى الآن.
• الجولة 2. أدرج 200 ارتباط آخر. فيصبح لديك 400 ارتباط و200 دلو. معامل التحميل 2.
• زد عدد الدلاء بمقدار 100 وأعد التجزئة. فتلك 400 عملية إدراج أخرى. فيصبح لديك 400 ارتباط و300 دلو. ومعامل التحميل 400/300 = 4/3، لا 1.
• متوسط كلفة كل إدراج الآن (100+200+200+400) / 300 = 3. ولا يزال ذلك مقبولًا.
• الجولة 3. أدرج 200 ارتباط آخر. فيصبح لديك 600 ارتباط و300 دلو. معامل التحميل 2.
• زد عدد الدلاء بمقدار 100 وأعد التجزئة. فتلك 600 عملية إدراج أخرى. فيصبح لديك 600 ارتباط و400 دلو. ومعامل التحميل 3/2، لا 1.
• متوسط كلفة كل إدراج الآن (100+200+200+400+200+600) / 500 = 3.4. إنه يرتفع.
• الجولة 4. أدرج 200 ارتباط آخر. فيصبح لديك 800 ارتباط و400 دلو. معامل التحميل 2.
• زد عدد الدلاء بمقدار 100 وأعد التجزئة. فتلك 800 عملية إدراج أخرى. فيصبح لديك 800 ارتباط و500 دلو. ومعامل التحميل 8/5، لا 1.
• متوسط كلفة كل إدراج الآن (100+200+200+400+200+600+200+800) / 700 = 3.9. إنه يواصل الارتفاع، لا يبقى ثابتًا.

بعد $k$ جولة يكون لدينا $200k$ ارتباطًا و$100(k+1)$ دلوًا. وقد استدعينا insert لإدراج $100+200(k-1)$ ارتباطًا، لكن كل إعادة التجزئة جعلتنا نُجري $100+200(k-1)+\sum_{i=1}^{k} 200i$ عملية إدراج فعلية. والحد الأخير هو المشكلة الحقيقية. فهو تربيعي:

فعلى سلسلة من $n$ استدعاء لـ insert، نُجري $O(n^2)$ عملية إدراج فعلية. ويجعل ذلك الكلفة المُستهلَكة لـ insert هي $O(n)$، وهي خطية! لا ثابتة.

ولهذا من المهم جدًا مضاعفة حجم المصفوفة عند كل إعادة تجزئة. فهو ما يمنحنا الأداء الثابت الزمن المُستهلَك.

9.2.2. التحليل المُستهلَك للطوابير المُدفوعة على دفعات

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

وكما لاحظنا آنذاك، فالعكس نادر نسبيًا. فهو لا يحدث إلا عندما يُستنفد صندوق الإخراج. ويمنحنا التحليل المُستهلَك طريقة لتبرير ذلك. بل يمكننا أن نبيّن أن عملية dequeue ثابتة الزمن مُستهلَكًا.

ولإبقاء التحليل بسيطًا في البداية، لنفترض أن الطابور يبدأ بعنصر واحد بالضبط 1 مُدرج بالفعل، وأننا نُجري ثلاث عمليات enqueue للعناصر 2 ثم 3 ثم 4، يتبعها dequeue واحدة. وسينتهي العنصر الأولي الواحد في صندوق الإخراج. وستضيف عمليات enqueue الثلاث عنصرًا إلى صندوق الإدخال. لذا، قبل dequeue مباشرةً، يبدو الطابور هكذا:

{o = [1]; i = [4; 3; 2]}

وبعد dequeue:

{o = [2; 3; 4]; i = []}

وتطلب الأمر

• 3 عمليات cons لإجراء عمليات الإدراج الثلاث، و
• 3 عمليات cons أخرى لإتمام dequeue بعكس القائمة.

وذلك مجموع 6 عمليات cons لإجراء العمليات الأربع من enqueue وdequeue. فمتوسط الكلفة إذن 1.5 عملية cons لكل عملية طابور. وكانت هناك عمليات مطابقة أنماط أخرى وإنشاءات سجلات، لكنها كلها استغرقت زمنًا ثابتًا فقط، لذا سنغفلها.

وماذا عن حالة أعقد، تتخلل فيها عمليات enqueue وdequeue بعضها بعضًا؟ سيصعب تحليل محاولة حساب المتوسطات على السلسلة. لكن، مستلهمين من تحليلنا لجداول التجزئة، لنفترض أننا تخيلنا أن كلفة كل enqueue ضعف كلفتها الفعلية، مقيسة بعمليات cons؟ حينئذٍ يمكننا، عند إدراج عنصر، أن «ندفع مسبقًا» الكلفة اللاحقة التي ستقع عندما يُضاف ذلك العنصر بـ cons إلى القائمة المعكوسة.

ولا تزال عملية enqueue ثابتة الزمن، لأنه حتى مع تخيّل أن كلفتها 2 بدلًا من 1، فما زال 2 ثابتًا. وعملية dequeue ثابتة الزمن مُستهلَكًا:

• إذا لم تكن dequeue بحاجة إلى عكس صندوق الإدخال، فهي تؤدي عملًا ثابتًا فحسب، و
• إذا احتاجت dequeue إلى عكس صندوق إدخال فيه $n$ عنصرًا، فلدينا بالفعل $n$ وحدة عمل «مدخرة» من كل عملية إدراج من عمليات إدراج تلك العناصر $n$.

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

9.2.3. المصرفيون والفيزيائيون

من حيث المفهوم، يمكن فهم التحليل المُستهلَك بثلاث طرق:

1. أخذ متوسط الكلفة على سلسلة من العمليات. وهذا ما فعلناه حتى الآن.
2. الاحتفاظ بـ«حساب مصرفي» عند كل عنصر فردي من عناصر بنية البيانات. فبعض العمليات تودع أرصدة، وبعضها يسحبها. والهدف ألا تكون مجاميع الحسابات سالبة أبدًا. والكلفة المُستهلَكة لأي عملية هي الكلفة الفعلية، زائد أي أرصدة مودعة، ناقص أي أرصدة مصروفة. فإذا كانت كلفة عملية ما $n$ فعلًا لكنها تصرف $n-1$ رصيدًا، فكلفتها المُستهلَكة 1 فحسب. وتُسمى هذه طريقة المصرفي (banker’s method) في التحليل المُستهلَك.
3. اعتبار بنية البيانات كلها ذات كمية من «الطاقة الكامنة (potential energy)» المدخرة. فبعض العمليات تزيد الطاقة وبعضها ينقصها. وينبغي ألا تكون الطاقة سالبة أبدًا. والكلفة المُستهلَكة لأي عملية هي كلفتها الفعلية، زائد التغير في الطاقة الكامنة. فإذا كانت كلفة عملية ما $n$ فعلًا، وكانت الطاقة الكامنة قبلها $n$، وكانت بعدها $0$، فالكلفة المُستهلَكة $n + (0 - n)$، أي 0 فحسب. وتُسمى هذه طريقة الفيزيائي (physicist’s method) في التحليل المُستهلَك.

وقد تكون طريقة المصرفي وطريقة الفيزيائي أسهل استخدامًا في حالات كثيرة من تحليل معقد لسلسلة من العمليات. ولنعد إلى أمثلتنا حتى الآن لتوضيح استخدامهما:

• طريقة المصرفي، جداول التجزئة: يبدأ الجدول فارغًا. وعند إضافة ارتباط إلى الجدول، ادخر رصيدًا واحدًا في حسابه. وعندما تلزم إعادة تجزئة، يكون من المضمون أن كل ارتباط لديه رصيد واحد. واستخدم ذلك الرصيد لدفع كلفة إعادة التجزئة. الآن جميع الارتباطات لديها 0 أرصدة. ومن الآن فصاعدًا، عند إضافة ارتباط إلى الجدول، ادخر رصيدًا واحدًا في حسابه ورصيدًا واحدًا في حساب أي ارتباط من الارتباطات ذات 0 أرصدة. وعندما تلزم إعادة التجزئة التالية، يكون عدد الارتباطات قد تضاعف. لكن بما أننا ادخرنا رصيدين عند كل إدراج، فصار لكل ارتباط رصيد واحد في حسابه مرة أخرى. فيمكننا دفع كلفة إعادة التجزئة. ولا تصير الحسابات سالبة أبدًا، لأن أرصدتها دائمًا إما 0 وإما 1.
• طريقة المصرفي، الطوابير المُدفوعة على دفعات: عند إضافة عنصر إلى الطابور، ادخر رصيدًا واحدًا في حسابه. وعندما يجب عكس صندوق الإدخال، استخدم الرصيد في كل عنصر لدفع كلفة إضافة cons إلى صندوق الإخراج. وبما أن العناصر تدخل عند صندوق الإدخال وتنتقل إلى صندوق الإخراج مرة واحدة على الأكثر، فسيكون لكل عنصر 0 أو 1 رصيد. فلا تصير الحسابات سالبة أبدًا.
• طريقة الفيزيائي، جداول التجزئة: في البداية، عرّف الطاقة الكامنة للجدول بأنها عدد الارتباطات المُدرجة. فلن تكون تلك الطاقة سالبة أبدًا. وكل إدراج يزيد الطاقة وحدة واحدة. وعندما تلزم إعادة التجزئة الأولى بعد إدراج $n$ ارتباطًا، تكون الطاقة الكامنة $n$. وتهبط الطاقة إلى $0$ عند إعادة التجزئة. فالكلفة الفعلية إذن $n$، لكن التغير في الطاقة $n$، وهو ما يجعل الكلفة المُستهلَكة 0، أي ثابتة. ومن الآن فصاعدًا، عرّف الطاقة الكامنة بأنها ضعف عدد الارتباطات المُدرجة منذ آخر إعادة تجزئة. ومرة أخرى لن تكون الطاقة سالبة أبدًا. وكل إدراج يزيد الطاقة وحدتين. وعندما تلزم إعادة التجزئة التالية بعد إدراج $n$ ارتباطًا، سيكون هناك $2n$ ارتباطًا تحتاج إلى إعادة تجزئة. ومرة أخرى ستكون الكلفة المُستهلَكة ثابتة، لأن الكلفة الفعلية لإعادة $2n$ إدراجًا يقابلها تغير في الطاقة قدره $2n$.
• طريقة الفيزيائي، الطوابير المُدفوعة على دفعات: عرّف الطاقة الكامنة للطابور بأنها طول صندوق الإدخال. فلن تكون سالبة أبدًا. وعندما تضطر dequeue إلى عكس صندوق إدخال طوله $n$، فثمة كلفة فعلية $n$ لكن مع تغير في الطاقة $n$ أيضًا، وهو ما يقابل الكلفة ويجعلها ثابتة.

والطريقتان متكافئتان في قدرتهما التحليلية:

• لتحويل تحليل مصرفي إلى تحليل فيزيائي، اجعل الطاقة مساوية لمجموع كل الأرصدة في الحسابات الفردية.
• ولتحويل تحليل فيزيائي إلى تحليل مصرفي، خصّص عنصرًا واحدًا مميزًا في بنية البيانات ليكون الوحيد الذي يحمل أي أرصدة، واجعل كل عملية تودع أو تسحب التغير في الطاقة في حساب ذلك العنصر.

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

9.2.4. التحليل المُستهلَك والاستمرارية

ينهار التحليل المُستهلَك كتقنية عندما تُستخدم بنى البيانات استخدامًا مستمرًا (persistent). فمثلًا، لنفترض أن لدينا طابورًا مُدفوعًا على دفعات q أدرجنا فيه $n+1$ عنصرًا. فسيكون عنصر في صندوق الإخراج والآخر $n$ في صندوق الإدخال. والآن نفعل ما يلي:

# let q1 = dequeue q
# let q2 = dequeue q
...
# let qn = dequeue q

تتطلب كل واحدة من عمليات dequeue الـ $n$ كلفة فعلية $O(n)$ لعكس صندوق الإدخال. فالسلسلة كلها لها كلفة فعلية $O(n^2)$. لكن تقنيات التحليل المُستهلَك لا تنطبق إلا على dequeue الأولى. وبعدها تصير جميع الحسابات فارغة (طريقة المصرفي)، أو تصير الطاقة صفرًا (طريقة الفيزيائي)، وهو ما يعني أن العمليات المتبقية لا يمكنها استخدامها لدفع كلفة عكس القائمة المكلف. فالكلفة الإجمالية للسلسلة إذن $O(n^2 - n)$، وهي $O(n^2)$.

والمشكلة في الاستمرارية أنها تخالف الافتراض المضمّن في التحليل المُستهلَك بأن الأرصدة (أو وحدات الطاقة) تُصرف مرة واحدة فقط. فكل نسخة مستمرة من بنية البيانات تحاول بدلًا من ذلك صرفها بنفسها، غير مدركة لسائر النسخ.

وثمة تقنيات أكثر تقدمًا للتحليل المُستهلَك يمكنها مراعاة الاستمرارية. وتقوم تلك التقنيات على فكرة تكديس دين (debt) يُسدد لاحقًا، بدلًا من تكديس مدخرات تُصرف لاحقًا. ويمكن تلخيص سبب نجاح الدين كتقنية تحليلية في أن بنوكنا، بالمعنى المالي، لن تسمح لنا أبدًا بصرف المال مرتين، لكنها لا تمانع في سداد ديننا مرات متعددة. راجع كتاب Okasaki، Purely Functional Data Structures، لمعرفة المزيد.

9.3. أشجار الأحمر والأسود

كما رأينا الآن، جداول التجزئة بنية بيانات فعّالة لتنفيذ تجريد الخريطة. فهي توفر أداءً ثابت الزمن مُستهلَكًا وفي التوقع—وهو ضمان دقيق بسبب معدّلي «مُستهلَك» و«في التوقع» اللذين نضطر إلى إضافتهما. كما أن جداول التجزئة تتطلب القابلية للتغيير في تنفيذها. ونحن كمبرمجين وظيفيين نفضّل تجنب القابلية للتغيير حيث أمكن.

فلنتقصَّ إذن كيفية تنفيذ خرائط وظيفية. ومن أفضل بنى البيانات لذلك شجرة الأحمر والأسود (red-black tree)، وهي نوع من أشجار البحث الثنائية المتوازنة يوفر أداءً لوغاريتميًا في أسوأ الحالات. فالأداء من جهة أسوأ قليلًا من جداول التجزئة (لوغاريتمي مقابل ثابت)، لكننا من جهة أخرى لا نضطر إلى تقييد الأداء بكلمات مثل «مُستهلَك» و«في التوقع». واللوغاريتمي لا يزال فعالًا بما يكفي حتى لأحمال العمل الكبيرة جدًا. وننجو أيضًا من القابلية للتغيير!

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

شجرة البحث الثنائية (binary search tree, BST) شجرة ثنائية بثابت التمثيل التالي:

لأي عقدة n، كل عقدة في الشجرة الفرعية اليسرى لـ n لها قيمة أصغر من قيمة n، وكل عقدة في الشجرة الفرعية اليمنى لـ n لها قيمة أكبر من قيمة n.

ونسمي ذلك ثابت شجرة البحث الثنائية.

وإليك شيفرة تنفّذ عمليتين على شجرة بحث ثنائية:

type 'a tree = Node of 'a * 'a tree * 'a tree | Leaf
(** [mem x t] is [true] iff [x] is a member of [t]. *)
let rec mem x = function
  | Leaf -> false
  | Node (y, l, r) ->
    if x < y then mem x l
    else if x > y then mem x r
    else true
(** [insert x t] is [t] with [x] inserted as a member. *)
let rec insert x = function
  | Leaf -> Node (x, Leaf, Leaf)
  | Node (y, l, r) as t ->
    if x < y then Node (y, insert x l, r)
    else if x > y then Node (y, l, insert x r)
    else t

type 'a tree = Node of 'a * 'a tree * 'a tree | Leaf

val mem : 'a -> 'a tree -> bool = <fun>

val insert : 'a -> 'a tree -> 'a tree = <fun>

فما زمن تشغيل هاتين العمليتين؟ بما أن insert ليست إلا mem مع إنشاء عقدة إضافي ثابت الزمن، فسنركز على العملية mem.

زمن تشغيل mem هو $O(h)$، حيث $h$ ارتفاع الشجرة، لأن كل استدعاء تعاودي ينزل مستوى واحدًا في الشجرة. وما أسوأ ارتفاع ممكن لشجرة؟ يحدث ذلك في شجرة من $n$ عقدة كلها في فرع طويل واحد—تخيل إضافة الأعداد 1,2,3,4,5,6,7 بالترتيب إلى الشجرة. إذن أسوأ زمن تشغيل لـ mem ما زال $O(n)$، حيث $n$ عدد العقد في الشجرة.

وما الشكل الجيد لشجرة يسمح ببحث سريع؟ الشجرة الثنائية الكاملة (perfect binary tree)، التي تقع فيها كل ورقة في المستوى السفلي، لها أصغر ارتفاع ممكن بالنسبة إلى عدد عقدها. تأمل هذه الشجرة الكاملة:

Node (2, Node (1, Leaf, Leaf), Node (3, Leaf, Leaf))

يمكننا رسمها هكذا، حيث تشير . إلى Leaf، وحيث نمثل ارتفاع كل مستوى من مستويات الشجرة:

                     Height
        2              2
       / \
     1     3           1
    / \   / \
   .   . .   .         0

عدد العقد $n$ في شجرة ثنائية كاملة أسي في ارتفاع الشجرة $h$. (لاحظ أننا نعني بـ«العقدة» هنا منشئ Node تحديدًا لا Leaf.) وبوجه خاص، $n = 2^h - 1$ (وهي حقيقة يمكننا إثباتها بالاستقراء). لذا $h = \log_2(n+1)$، وهو $O(\log n)$. وعليه ستعمل عمليات البحث في شجرة بحث ثنائية كاملة في زمن لوغاريتمي.

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

• أشجار 2-3 (Hopcroft، 1970): جميع المسارات لها الطول نفسه.
• أشجار AVL (Adelson-Velsky و Landis، 1962): يختلف طول أقصر مسار وأطوله بواحد على الأكثر.
• أشجار الأحمر والأسود (Guibas و Sedgewick، 1978): يختلف طول أقصر مسار وأطوله بمعامل اثنين على الأكثر.

وتضمن كل من تلك البنى زمن تشغيل $O(\log n)$. وسندرس بعد ذلك أشجار الأحمر والأسود، التي لها تنفيذ جميل بوجه خاص قائم على الأنواع الجبرية ومطابقة الأنماط.

9.3.2. أشجار الأحمر والأسود

أشجار الأحمر والأسود بنية بيانات شجرة ثنائية متوازنة بسيطة نسبيًا. ونلوّن كل عقدة في الشجرة إما بالأحمر وإما بالأسود.

type color = Red | Black
type 'a rbtree = Leaf | Node of color * 'a * 'a rbtree * 'a rbtree

type color = Red | Black

type 'a rbtree = Leaf | Node of color * 'a * 'a rbtree * 'a rbtree

لاحظ أننا حين نكتب «عقدة» في هذا النقاش نعني المنشئ Node؛ وLeaf ليست عقدة. ونشترط أن تكون العقدة الجذرية لأي شجرة غير فارغة ملونة بالأسود.

إضافة إلى ثابت تمثيل شجرة البحث الثنائية، يجب أن تحقق أشجار الأحمر والأسود الثابتين التاليين أيضًا:

1. الثابت المحلي (Local Invariant): لا توجد عقدتان حمراوان متجاورتان على أي مسار.
2. الثابت الكلي (Global Invariant): لكل مسار كامل (مسار من الجذر إلى ورقة) العدد نفسه من العقد السوداء. ويُسمى هذا العدد الارتفاع الأسود (black height) للشجرة.

وإذا حققت شجرة هذين الشرطين، فمن اللازم أيضًا أن تحققهما كل شجرة فرعية منها. فلو خالفت شجرة فرعية أيًا من الشرطين، لخالفته الشجرة كلها أيضًا.

9.3.2.1. التوازن

تضمن ثوابت أشجار الأحمر والأسود بقاء الشجرة متوازنة. وليس التوازن كاملًا بالضرورة — فقد تكون بعض المسارات الكاملة أطول من غيرها — لكن الاختلال لا يمكن أن يكون سيئًا جدًا، كما تقول المبرهنة التالية.

مبرهنة. طول أطول مسار كامل في شجرة الأحمر والأسود لا يتجاوز ضعف طول أقصر مسار كامل.

البرهان. بالثابت الكلي، يجب أن يكون لأطول مسار كامل وأقصره العدد نفسه من العقد السوداء، وهو $b$، أي الارتفاع الأسود للشجرة. (وإن تساوت مسارات في كونها الأطول أو الأقصر فلا يهم. تأمل أي مسار من المسارات المتساوية.) فإن لم يكن في الأقصر عقد حمراء، فطوله $b$ فحسب. وبالثابت المحلي، لا يمكن للأطول أن يتجاوز ضعف ذلك الطول بإضافة $b$ عقدة حمراء. فمثلًا، لنفترض أن أقصر مسار كامل هو B-B-B-B-Leaf، حيث يشير “B” إلى عقدة سوداء. فطوله أربعة. وما أطول مسار كامل يمكن أن يكون للشجرة بالنظر إلى ارتفاعها الأسود؟ سيكون مسارًا يضيف عقدة حمراء بعد كل عقدة سوداء—أي B-R-B-R-B-R-B-R-Leaf، حيث يشير “R” إلى عقدة حمراء. وطوله ثمانية، أي ضعف طول الأقصر. □

9.3.2.2. العضوية

نتحقق من العضوية في أشجار الأحمر والأسود بالطريقة نفسها تمامًا المتبعة في أشجار البحث الثنائية:

let rec mem x = function
  | Leaf -> false
  | Node (_, y, l, r) ->
    if x < y then mem x l
    else if x > y then mem x r
    else true

val mem : 'a -> 'a rbtree -> bool = <fun>

فما كفاءة mem؟ في أسوأ الحالات تُجري تعاودًا نزولًا إلى أدنى ورقة في الشجرة ولا تجد العنصر x—أي أن زمن التشغيل يتحدد بارتفاع الشجرة. وارتفاع شجرة الأحمر والأسود لوغاريتمي في عدد العقد، كما تثبت المبرهنة التالية.

مبرهنة. شجرة الأحمر والأسود ذات $n$ عقدة ارتفاعها $h$ لا يتجاوز $O(\log n)$.

البرهان. لنكن $b$ الارتفاع الأسود للشجرة—أي عدد العقد السوداء على كل مسار كامل. وسنستخدم $b$ لإقامة علاقة بين $h$ و$n$ في المُبرهنتين المساعدتين التاليتين.

المُبرهنة المساعدة 1: $h \leq 2b$. تأمل أي مسار كامل من العقد طوله $h$. يجب أن يكون على المسار $b$ عقدة سوداء. وإن وُجدت عقد حمراء، فقد يكون منها $b$ على الأكثر، كما استدللنا أعلاه في البرهان الخاص بالتوازن. لذا فطول المسار $2b$ على الأكثر. وبذلك $h \leq 2b$.

المُبرهنة المساعدة 2: $n \geq 2^b - 1$. تأمل العقد السوداء في الشجرة. بما أن كل مسار كامل يجب أن يحتوي $b$ عقدة سوداء، أمكننا تكوين شجرة كاملة ارتفاعها $b$ من تلك العقد. (ابدأ من الجذر، وهو أسود. أبقِه. ثم انتقل تعاوديًا إلى كل ابن. فإن كان الابن أسود فأبقِه. وإن كان أحمر وليس له أبناء فاطرحه. وإن كان أحمر وله أبناء، فأولئك الأبناء يجب أن يكونوا سودًا؛ اختر أحدهم اعتباطًا ليحل محل العقدة الحمراء واطرح الابن الأسود الآخر.) وستكون لتلك الشجرة الكاملة $2^b - 1$ عقدة على الأقل، كما نوقش أعلاه. وبذلك $n \geq 2^b - 1$.

وأخيرًا: يمكننا إعادة كتابة المُبرهنة المساعدة 2 كما يلي:

ثم يمكننا، بالمُبرهنة المساعدة 1، إرخاء الحد الأدنى $2b$ في الطرف الأيسر من تلك المتباينة إلى $h$، فنحصل على $h \leq 2 \log_2(n + 1)$. لذا فـ $h$ لا يتجاوز $O(\log n)$. □

9.3.2.3. الإدراج: خوارزمية Okasaki

والأكثر إثارة للاهتمام عملية insert. وكما في الأشجار الثنائية المعتادة، نضيف عقدة باستبدال الورقة التي وجدها إجراء البحث. لكن بأي لون نلوّن تلك العقدة؟

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

فلا خيار آمن إذن عمومًا. وقدّم Chris Okasaki (Purely Functional Data Structures، 1999) خوارزمية أنيقة تحل المشكلة باختيار خرق الثابت المحلي، ثم الصعود في الشجرة لإصلاح الخرق. وإليك كيف تعمل.

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

أما إذا كان أب العقدة الجديدة أحمر، فقد خُرق الثابت المحلي. وفي هذه الحالة لا يمكن أن يكون أب العقدة الجديدة جذر الشجرة (وهو أسود)، لذا فللعقدة الجديدة جدّ. ويجب أن يكون ذلك الجد أسود، لأن الثابت المحلي كان محققًا قبل إدراج العقدة الجديدة. والآن صار لدينا عمل لإعادة الثابت المحلي.

ويوضح الشكل التالي الخروق الأربعة الممكنة. وفيه a-d أشجار فرعية قد تكون فارغة، وx-z قيم مخزنة عند عقدة. وتُشار إلى ألوان العقد بـ R وB. وقد وسّمنا الأدنى من العقدتين الحمراوين المخالفتين بأقواس مربعة. وعندما نبدأ في إصلاح الشجرة، تكون تلك العقدة الموسَّمة هي العقدة الجديدة التي أدرجناها للتو. لذا لن يكون لها أبناء—فمثلًا في الحالة 1 سيكون a وb ورقتين. (لكن لاحقًا، ونحن نصعد في الشجرة لمواصلة الإصلاح، قد نصادف حالات تكون فيها العقدة الموسَّمة ذات أشجار فرعية غير فارغة.)

           1             2             3             4

           Bz            Bz            Bx            Bx
          / \           / \           / \           / \
         Ry  d         Rx  d         a   Rz        a   Ry
        /  \          / \               /  \          /  \
     [Rx]  c         a  [Ry]          [Ry]  d        b   [Rz]
     /  \               /  \          / \                /  \
    a    b             b    c        b   c              c    d

لاحظ أننا في كل من هذه الأشجار وسمنا القيم والعقد بعناية بحيث يضمن ثابت شجرة البحث الثنائية الترتيب التالي:

all nodes in a
 <
  x
   <
    all nodes in b
     <
      y
       <
        all nodes in c
         <
          z
           <
            all nodes in d

لذا يمكننا تحويل الشجرة لإعادة الثابت المحلي باستبدال أي من الحالات الأربع أعلاه بـ:

         Ry
        /  \
      Bx    Bz
     / \   / \
    a   b c   d

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

let balance = function
  | Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
    Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d -> Node (a, b, c, d)

val balance : color * 'a * 'a rbtree * 'a rbtree -> 'a rbtree = <fun>

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

لماذا يحافظ الدوران على الثابت الكلي؟ قبل الدوران تحقق الشجرة الثابت الكلي. ويعني ذلك أن الأشجار الفرعية a-d تحت الجد لها الارتفاع الأسود نفسه، ويضيف الجد واحدًا إليه. وفي الشجرة المدوّرة، تقع الأشجار الفرعية كلها في المستوى نفسه، لكن x وz يضيفان الآن واحدًا إلى ذلك الارتفاع. ولم يتغير الارتفاع الأسود الكلي للشجرة، ويستمر كل مسار في امتلاك الارتفاع الأسود نفسه.

لماذا يرسي الدوران الثابت المحلي؟ كان خرق الثابت المحلي الوحيد في الشجرة قبل الدوران متعلقًا بالعقدة الموسَّمة. وبعد الدوران أُزيل ذلك الخرق. وعلاوة على ذلك، بما أن x وz ملونتان بالأسود بعد الدوران، فلا يمكن أن تُحدثا خرقًا جديدًا للثابت المحلي مع جذر الأشجار الفرعية a-d (إن وُجد). غير أن جذر الشجرة المدوّرة صار الآن هو y وهو ملون بالأحمر. وإذا كان لتلك العقدة أب—أي إذا لم يكن الجد في الحالات 1-4 جذر الشجرة كلها—فمن الممكن أن نكون قد أنشأنا للتو خرقًا جديدًا للثابت المحلي بين y وأبيه!

ولمعالجة ذلك الخرق الجديد المحتمل، علينا مواصلة الصعود في الشجرة من y إلى الجذر، وإصلاح أي خروق أخرى للثابت المحلي في الطريق. وفي أسوأ الحالات تتسلسل العملية صعودًا حتى قمة الشجرة وتُنتج عقدتين حمراوين متجاورتين، صارت إحداهما جذرًا للتو. لكن إذا حدث ذلك، فيمكننا ببساطة إعادة تلوين هذا الجذر الجديد من الأحمر إلى الأسود. وبذلك يكتمل إرساء الثابت المحلي. كما يحافظ ذلك على الثابت الكلي مع زيادة الارتفاع الأسود الكلي للشجرة كلها بواحد—وهذه هي الطريقة الوحيدة التي يزداد بها الارتفاع الأسود من إدراج. وشيفرة insert باستخدام balance كما يلي:

let insert x s =
  let rec ins = function
    | Leaf -> Node (Red, x, Leaf, Leaf)
    | Node (color, y, a, b) as s ->
      if x < y then balance (color, y, ins a, b)
      else if x > y then balance (color, y, a, ins b)
      else s
  in
  match ins s with
  | Node (_, y, a, b) -> Node (Black, y, a, b)
  | Leaf -> (* guaranteed to be non-empty *)
    failwith "RBT insert failed with ins returning leaf"

val insert : 'a -> 'a rbtree -> 'a rbtree = <fun>

مقدار العمل الذي تؤديه insert هو $O(\log n)$. فهي تُجري تعاودًا بـ ins نزولًا في الشجرة إلى ورقة، حيث يقع الإدراج، ثم تستدعي balance عند كل خطوة في طريق العودة صعودًا. وطول المسار إلى الورقة $O(\log n)$، لأن الشجرة كانت متوازنة بالفعل. وكل استدعاء لـ balance هو عمل $O(1)$.

9.3.2.4. الإزالة

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

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

وقد اخترع Germane و Might خوارزمية أنيقة للتعامل مع إعادة التوازن تلك. وحلهما إنشاء عقد «سوداء مزدوجة» تُحسب مرتين في تحديد الارتفاع الأسود. ولمعرفة المزيد، اقرأ ورقتهما: Deletion: The Curse of the Red-Black Tree Journal of Functional Programming، المجلد 24، العدد 4، يوليو 2014.

9.3.3. الخرائط والمجموعات من أشجار البحث الثنائية

من السهل استخدام شجرة بحث ثنائية لتنفيذ تجريد خريطة أو تجريد مجموعة:

• للخريطة، ما عليك إلا تخزين ارتباط عند كل عقدة. وتُرتَّب العقد بالمفاتيح. أما القيم فلا علاقة لها بالترتيب.
• وللمجموعة، ما عليك إلا تخزين عنصر عند كل عقدة. وتُرتَّب العقد بالعناصر.

وتفعل المكتبة القياسية لـ OCaml ذلك في وحدتي Map وSet. وهي تستخدم شجرة بحث ثنائية متوازنة هي نسخة من شجرة AVL. وأشجار AVL أشجار بحث ثنائية متوازنة يُسمح فيها لارتفاع المسارات بالاختلاف بواحد على الأكثر. وقد عدّلت المكتبة القياسية لـ OCaml ذلك لتسمح للارتفاع بالاختلاف باثنين على الأكثر. وهي، مثل أشجار الأحمر والأسود، تحقق أداءً لوغاريتميًا في أسوأ الحالات.

والآن بعد أن صارت لدينا بنية بيانات خريطة وظيفية، كيف تقارن بنسختنا الأمرية، أي جدول التجزئة؟

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

ولا فائز واضح هنا. وبما أن مكتبة OCaml توفر Map وHashtbl معًا، فلك الاختيار.

9.4. المتتاليات

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

نعلم بالفعل أن OCaml تتيح لنا إنشاء دوال تعاودية—أي دوال معرّفة بدلالة نفسها. ويتبين أنه يمكننا تعريف قيم أخرى بدلالة نفسها أيضًا.

let rec ones = 1 :: ones

val ones : int list = [1; <cycle>]

let rec a = 0 :: b and b = 1 :: a

val a : int list = [0; 1; <cycle>]
val b : int list = [1; 0; <cycle>]

تنشئ التعبيرات أعلاه قيمًا تعاودية (recursive values). فالقائمة ones تحتوي متتالية لا نهائية من 1، والقائمتان a وb تتناوبان إلى ما لا نهاية بين 0 و1. ولأن القوائم لا نهائية، لا يستطيع المستوى الأعلى طباعتها بكاملها. بل يشير بدلًا من ذلك إلى دورة (cycle): أي أن القائمة تعود إلى بدايتها دوريًا. ورغم أن هذه القوائم تمثل متتالية لا نهائية من القيم، فتمثيلها في الذاكرة منتهٍ: فهي قوائم مترابطة بمؤشرات خلفية تُنشئ تلك الدورات.

وعلاوة على متتاليات الأعداد، ثمة أنواع أخرى من الكائنات الرياضية اللانهائية قد نريد تمثيلها ببنى بيانات منتهية:

• تيار من المدخلات يُقرأ من ملف أو مقبس شبكة أو مستخدم. وكلها غير محدودة الطول، ومن ثمّ يمكننا التفكير فيها كأنها لا نهائية الطول. بل إن كثيرًا من مكتبات الإدخال/الإخراج تعتبر الوصول إلى نهاية تيار الإدخال/الإخراج حالة غير متوقعة وترفع استثناءً.
• شجرة اللعبة (game tree) شجرة تكون فيها أوضاع اللعبة (مثل الشطرنج أو إكس-أو) عقدًا، ويكون الانتقالات الممكنة أضلاعًا. وفي بعض الألعاب تكون هذه الشجرة لا نهائية فعلًا (تخيل مثلًا أن قطع الرقعة تستطيع مطاردة بعضها بعضًا إلى ما لا نهاية)، وفي ألعاب أخرى تكون عميقة إلى حد أننا لا نريد أبدًا إظهار الشجرة كلها، فهي لا نهائية من حيث الأثر.

9.4.1. كيف لا نعرّف متتالية

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

(** [from n] is the infinite list [[n; n + 1; n + 2; ...]]. *)
let rec from n = n :: from (n + 1)

val from : int -> int list = <fun>

(** [nats] is the infinite list of natural numbers [[0; 1; ...]]. *)
let nats = from 0

Stack overflow during evaluation (looping recursion?).

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

وإليك محاولة أخرى تستخدم ما اكتشفناه أعلاه عن القيم التعاودية:

let rec nats = 0 :: List.map (fun x -> x + 1) nats

File "[4]", line 1, characters 15-50:
1 | let rec nats = 0 :: List.map (fun x -> x + 1) nats
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This kind of expression is not allowed as right-hand side of let rec

لا تنجح تلك المحاولة لسبب أدق. ففي تعريف قيمة تعاودية لا يُسمح لنا باستخدام قيمة قبل أن ينتهي تعريفها. والمشكلة أن List.map مطبَّقة على nats، ومن ثمّ فهي تطابق أنماطًا لاستخراج رأس nats وذيلها. لكننا في منتصف تعريف nats، فلا يُسمح بذلك الاستخدام لـ nats.

9.4.2. كيف نعرّف متتالية تعريفًا صحيحًا

يمكننا محاولة تعريف متتالية بالقياس على كيفية تعريف القوائم (المنتهية). تذكّر ذلك التعريف:

type 'a mylist = Nil | Cons of 'a * 'a mylist

type 'a mylist = Nil | Cons of 'a * 'a mylist

ويمكننا محاولة تحويل ذلك إلى تعريف للمتتاليات:

type 'a sequence = Cons of 'a * 'a sequence

type 'a sequence = Cons of 'a * 'a sequence

لاحظ أننا تخلصنا من المنشئ Nil، لأن القائمة الفارغة منتهية، ونحن نريد قوائم لا نهائية فقط.

والمشكلة في ذلك التعريف أنه ليس أفضل حقًا من القائمة المدمجة في OCaml، حيث ما زلنا لا نستطيع تعريف nats:

let rec from n = Cons (n, from (n + 1))

val from : int -> int sequence = <fun>

let nats = from 0

Stack overflow during evaluation (looping recursion?).

وكما سبق، تحاول تلك التعريفات الانطلاق لحساب المتتالية اللانهائية كلها للأعداد الطبيعية.

وما نحتاجه هو طريقة لإيقاف التقييم مؤقتًا، بحيث لا يكون قد حُسب في أي لحظة إلا تقريب منتهٍ للمتتالية اللانهائية. ولحسن الحظ، نعرف بالفعل كيف نفعل ذلك!

تأمل التعريفين التاليين:

let f1 = failwith "oops"

Exception: Failure "oops".

Raised at Stdlib.failwith in file "stdlib.ml", line 29, characters 17-33
Called from f1 in file "[8]", line 1, characters 9-24
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

let f2 = fun x -> failwith "oops"

val f2 : 'a -> 'b = <fun>

f2 ();;

Exception: Failure "oops".

Raised at Stdlib.failwith in file "stdlib.ml", line 29, characters 17-33
Called from <unknown> in file "[10]", line 1, characters 0-5
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

تعريف f1 يرفع استثناءً فورًا، أما تعريف f2 فلا. لماذا؟ لأن f2 تلفّ failwith داخل دالة مجهولة. تذكّر أنه، وفق الدلالات الديناميكية لـ OCaml، الدوال قيم أصلًا. فلا يُؤدى أي حساب داخل جسم الدالة حتى تُطبَّق. ولهذا ترفع f2 () استثناءً.

ويمكننا استخدام هذه الخاصية في التقييم—وهي أن الدوال تؤخر التقييم—لصالحنا في تعريف المتتاليات: لنلفّ ذيل المتتالية داخل دالة. وبما أنه لا يهم حقًا أي وسيط تأخذه تلك الدالة، فيمكننا جعله unit. والدالة التي تُستخدم لمجرد تأخير الحساب، وبوجه خاص التي تأخذ unit كمدخل، تُسمى ثنكة (thunk).

(** An ['a sequence] is an infinite list of values of type ['a].
    AF: [Cons (x, f)] is the sequence whose head is [x] and tail is [f ()].
    RI: none. *)
type 'a sequence = Cons of 'a * (unit -> 'a sequence)

type 'a sequence = Cons of 'a * (unit -> 'a sequence)

يتبين أن هذا التعريف ينجح نجاحًا جيدًا. ويمكننا أخيرًا تعريف nats:

let rec from n = Cons (n, fun () -> from (n + 1))
let nats = from 0

val from : int -> int sequence = <fun>

val nats : int sequence = Cons (0, <fun>)

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

(** [hd s] is the head of [s]. *)
let hd (Cons (h, _)) = h

val hd : 'a sequence -> 'a = <fun>

(** [tl s] is the tail of [s]. *)
let tl (Cons (_, t)) = t ()

val tl : 'a sequence -> 'a sequence = <fun>

لاحظ كيف يجب، في تعريف tl، تطبيق الدالة t على () للحصول على ذيل المتتالية. أي أنه علينا إجبار (force) الثنكة على التقييم عند تلك النقطة، بدلًا من مواصلة تأخير حسابها.

وللملاءمة، يمكننا كتابة دوال تطبق hd أو tl مرات متعددة لأخذ بادئة منتهية من متتالية أو إسقاطها:

(** [take n s] is the list of the first [n] elements of [s]. *)
let rec take n s =
  if n = 0 then [] else hd s :: take (n - 1) (tl s)
(** [drop n s] is all but the first [n] elements of [s]. *)
let rec drop n s =
  if n = 0 then s else drop (n - 1) (tl s)

val take : int -> 'a sequence -> 'a list = <fun>

val drop : int -> 'a sequence -> 'a sequence = <fun>

For example:

take 10 nats

- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

9.4.3. البرمجة بالمتتاليات

لنكتب بعض الدوال التي تتعامل مع المتتاليات. وسيساعدنا أن يكون لدينا ترميز للمتتاليات نستخدمه كجزء من التوثيق. لنستخدم `` للدلالة على المتتالية التي تحتوي العناصر a وb وc في رأسها، يتبعها عدد لا نهائي من العناصر الأخرى.

وإليك دالتين لتربيع متتالية وجمع متتاليتين:

(** [square <a; b; c; ...>] is [<a * a; b * b; c * c; ...]. *)
let rec square (Cons (h, t)) =
  Cons (h * h, fun () -> square (t ()))
(** [sum <a1; a2; a3; ...> <b1; b2; b3; ...>] is
    [<a1 + b1; a2 + b2; a3 + b3; ...>]. *)
let rec sum (Cons (h1, t1)) (Cons (h2, t2)) =
  Cons (h1 + h2, fun () -> sum (t1 ()) (t2 ()))

val square : int sequence -> int sequence = <fun>

val sum : int sequence -> int sequence -> int sequence = <fun>

لاحظ كيف أن القالب الأساسي لتعريف الدالتين هو نفسه:

• طابق الأنماط على متتالية (أو متتاليات) المدخل، ويجب أن تكون Cons من رأس ودالة ذيل (ثنكة).
• أنشئ متتالية كمخرج، ويجب أن تكون Cons من رأس جديد ودالة ذيل جديدة (ثنكة).
• في بناء دالة الذيل الجديدة، أخّر تقييم الذيل بالبدء فورًا بـ fun () -> ....
• داخل جسم تلك الثنكة، طبّق الدالة المعرَّفة (square أو sum) تعاوديًا على نتيجة إجبار ثنكة (أو ثنكات) على التقييم.

وبالطبع، التربيع والجمع مجرد طريقتين ممكنتين لربط دالة عبر متتالية أو متتاليات. ويوحي ذلك بأننا نستطيع كتابة دالة ربط عالية الرتبة، مثل ما نفعل مع القوائم:

(** [map f <a; b; c; ...>] is [<f a; f b; f c; ...>]. *)
let rec map f (Cons (h, t)) =
  Cons (f h, fun () -> map f (t ()))
(** [map2 f <a1; b1; c1;...> <a2; b2; c2; ...>] is
    [<f a1 b1; f a2 b2; f a3 b3; ...>]. *)
let rec map2 f (Cons (h1, t1)) (Cons (h2, t2)) =
  Cons (f h1 h2, fun () -> map2 f (t1 ()) (t2 ()))
let square' = map (fun n -> n * n)
let sum' = map2 ( + )

val map : ('a -> 'b) -> 'a sequence -> 'b sequence = <fun>

val map2 : ('a -> 'b -> 'c) -> 'a sequence -> 'b sequence -> 'c sequence =
  <fun>

val square' : int sequence -> int sequence = <fun>

val sum' : int sequence -> int sequence -> int sequence = <fun>

والآن بعد أن صارت لدينا دالة ربط للمتتاليات، يمكننا تعريف nats بنجاح بإحدى الطرق البارعة التي حاولناها في الأصل:

let rec nats = Cons (0, fun () -> map (fun x -> x + 1) nats)

val nats : int sequence = Cons (0, <fun>)

take 10 nats

- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

لماذا ينجح هذا؟ بديهيًا، nats هي ، لذا فإن ربط دالة الزيادة عبر `nats` يعطي . وإذا أضفنا 0 بـ cons إلى بداية ، حصلنا على كما هو مطلوب. ويُسمح بتعريف القيمة التعاودية، لأننا لا نحاول استخدام nats أبدًا قبل انتهاء تعريفها. وبوجه خاص، تؤخر الثنكة تقييم nats في الطرف الأيمن من التعريف.

وإليك تعريفًا بارعًا آخر. تأمل متتالية فيبوناتشي . إذا أخذنا ذيلها، حصلنا على . وإذا جمعنا هاتين المتتاليتين، حصلنا على ``. وذلك ليس إلا ذيل ذيل متتالية فيبوناتشي. لذا لو أضفنا [1; 1] في بدايتها، لكانت لدينا متتالية فيبوناتشي الفعلية. وهذا هو الحدس وراء هذا التعريف:

let rec fibs =
  Cons (1, fun () ->
    Cons (1, fun () ->
      sum fibs (tl fibs)))

val fibs : int sequence = Cons (1, <fun>)

وهو ينجح!

take 10 fibs

- : int list = [1; 1; 2; 3; 5; 8; 13; 21; 34; 55]

لكنه للأسف غير فعّال أبدًا. ففي كل مرة نُجبر حساب العنصر التالي، كان يتطلب إعادة حساب جميع العناصر السابقة، مرتين: مرة لـ fibs ومرة لـ tl fibs في السطر الأخير من التعريف. جرّب تشغيل الشيفرة بنفسك. وبحلول العدد الثلاثين يصير الحساب بطيئًا ملحوظًا؛ وبحلول المئة يبدو وكأنه يستمر إلى الأبد.

فهل نستطيع أن نفعل أفضل؟ نعم، بعون قليل من ميزة لغوية جديدة: الكسل. وسنناقشها بعد ذلك.

9.4.4. الكسل

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

module Lazy :
  sig
    type 'a t = 'a lazy_t
    val force : 'a t -> 'a
    ...
  end

قيمة من النوع 'a Lazy.t قيمة من النوع 'a تأخر حسابها. وبديهيًا، تكون اللغة كسولة (lazy) عن تقييمها: فلن تُحسب حتى يُطلب ذلك تحديدًا. ويُعبَّر عن ذلك الطلب بـإجبار التقييم بواسطة Lazy.force، التي تأخذ 'a Lazy.t وتؤدي إلى إنتاج 'a داخلها أخيرًا. وفي المرة الأولى التي تُجبر فيها قيمة كسولة، قد يستغرق الحساب وقتًا طويلًا. لكن النتيجة تُخزَّن مؤقتًا (cached) أو تُمَوَّه (memoized)، وفي أي مرة لاحقة تُجبر فيها تلك القيمة الكسولة، تُعاد النتيجة المخزنة مؤقتًا فورًا دون إعادة حسابها.

ملاحظة

«Memoized» هي فعلًا التهجئة الصحيحة لهذا المصطلح. ولم نخطئ في كتابة «memorized»، وإن كان قد يبدو كذلك.

لا تحتوي وحدة Lazy على دالة تنتج 'a Lazy.t. بل توجد كلمة مفتاحية مدمجة في صياغة OCaml تفعل ذلك: lazy e.

• الصياغة: lazy e
• الدلالات الساكنة: إذا كان e : u، فإن lazy e : u Lazy.t.
• الدلالات الديناميكية: لا يقيّم lazy e التعبير e إلى قيمة. بل ينتج تعليقًا (suspension)، متى أُجبر لاحقًا، يقيّم e إلى قيمة v ويعيد v. وعلاوة على ذلك، يتذكر ذلك التعليق أن v هي قيمته عند الإجبار. وإذا أُجبر التعليق مرة أخرى يومًا، أعاد v فورًا بدلًا من إعادة حسابها.

ملاحظة

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

ولتوضيح استخدام القيم الكسولة، لنجرب حساب عدد فيبوناتشي الثلاثين باستخدام هذا التعريف لـ fibs:

let rec fibs =
  Cons (1, fun () ->
    Cons (1, fun () ->
      sum fibs (tl fibs)))

val fibs : int sequence = Cons (1, <fun>)

تلميح

ستكون الأمثلة القليلة التالية أوضح بكثير إذا شغّلتها تفاعليًا بدلًا من قراءة هذه الصفحة فحسب.

إذا حاولنا الحصول على عدد فيبوناتشي الثلاثين، فسيستغرق حسابه وقتًا طويلًا:

let fib30long = take 30 fibs |> List.rev |> List.hd

val fib30long : int = 832040

لكن إذا لففنا تقييم ذلك بـ lazy، فسيعود فورًا، لأن تقييم ذلك العدد قد عُلِّق:

let fib30lazy = lazy (take 30 fibs |> List.rev |> List.hd)

val fib30lazy : int lazy_t = <lazy>

وبعد ذلك يمكننا إجبار تقييم تلك القيمة الكسولة، وسيستغرق حسابها وقتًا طويلًا، كما فعل fib30long:

let fib30 = Lazy.force fib30lazy

val fib30 : int = 832040

لكن إذا حاولنا يومًا إعادة حساب القيمة الكسولة نفسها، فستعود فورًا، لأن النتيجة قد خُزّنت مؤقتًا:

let fib30fast = Lazy.force fib30lazy

val fib30fast : int = 832040

ومع ذلك، لم ننجح نجاحًا كاملًا بعد. فقد خُزّن ذلك الحساب المعين لعدد فيبوناتشي الثلاثين مؤقتًا، لكن إذا عرّفنا لاحقًا حسابًا آخر لعدد آخر، فلن تُسرَّع المرة الأولى التي يُحسب فيها:

let fib29 = take 29 fibs |> List.rev |> List.hd

val fib29 : int = 514229

وما نريده حقًا تغيير تمثيل المتتاليات نفسه ليستفيد من القيم الكسولة.

9.4.4.1. المتتاليات الكسولة

إليك تمثيلًا للقوائم اللانهائية باستخدام القيم الكسولة:

type 'a lazysequence = Cons of 'a * 'a lazysequence Lazy.t

type 'a lazysequence = Cons of 'a * 'a lazysequence Lazy.t

لقد تخلصنا من الثنكة، وصارت القيمة الكسولة تُستخدم بدلًا منها كذيل للمتتالية الكسولة. وإذا أردنا يومًا حساب ذلك الذيل، أجبرناه.

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

module SequenceFibs = struct
  type 'a sequence = Cons of 'a * (unit -> 'a sequence)
  let hd : 'a sequence -> 'a =
    fun (Cons (h, _)) -> h
  let tl : 'a sequence -> 'a sequence =
    fun (Cons (_, t)) -> t ()
  let rec take_aux n (Cons (h, t)) lst =
    if n = 0 then lst
    else take_aux (n - 1) (t ()) (h :: lst)
  let take : int -> 'a sequence -> 'a list =
    fun n s -> List.rev (take_aux n s [])
  let nth : int -> 'a sequence -> 'a =
    fun n s -> List.hd (take_aux (n + 1) s [])
  let rec sum : int sequence -> int sequence -> int sequence =
    fun (Cons (h_a, t_a)) (Cons (h_b, t_b)) ->
      Cons (h_a + h_b, fun () -> sum (t_a ()) (t_b ()))
  let rec fibs =
    Cons(1, fun () ->
      Cons(1, fun () ->
        sum (tl fibs) fibs))
  let nth_fib n =
    nth n fibs
end
module LazyFibs = struct
  type 'a lazysequence = Cons of 'a * 'a lazysequence Lazy.t
  let hd : 'a lazysequence -> 'a =
    fun (Cons (h, _)) -> h
  let tl : 'a lazysequence -> 'a lazysequence =
    fun (Cons (_, t)) -> Lazy.force t
  let rec take_aux n (Cons (h, t)) lst =
    if n = 0 then lst else
      take_aux (n - 1) (Lazy.force t) (h :: lst)
  let take : int -> 'a lazysequence -> 'a list =
    fun n s -> List.rev (take_aux n s [])
  let nth : int -> 'a lazysequence -> 'a =
    fun n s -> List.hd (take_aux (n + 1) s [])
  let rec sum : int lazysequence -> int lazysequence -> int lazysequence =
    fun (Cons (h_a, t_a)) (Cons (h_b, t_b)) ->
      Cons (h_a + h_b, lazy (sum (Lazy.force t_a) (Lazy.force t_b)))
  let rec fibs =
    Cons(1, lazy (
      Cons(1, lazy (
        sum (tl fibs) fibs))))
  let nth_fib n =
    nth n fibs
end

module SequenceFibs :
  sig
    type 'a sequence = Cons of 'a * (unit -> 'a sequence)
    val hd : 'a sequence -> 'a
    val tl : 'a sequence -> 'a sequence
    val take_aux : int -> 'a sequence -> 'a list -> 'a list
    val take : int -> 'a sequence -> 'a list
    val nth : int -> 'a sequence -> 'a
    val sum : int sequence -> int sequence -> int sequence
    val fibs : int sequence
    val nth_fib : int -> int
  end

module LazyFibs :
  sig
    type 'a lazysequence = Cons of 'a * 'a lazysequence Lazy.t
    val hd : 'a lazysequence -> 'a
    val tl : 'a lazysequence -> 'a lazysequence
    val take_aux : int -> 'a lazysequence -> 'a list -> 'a list
    val take : int -> 'a lazysequence -> 'a list
    val nth : int -> 'a lazysequence -> 'a
    val sum : int lazysequence -> int lazysequence -> int lazysequence
    val fibs : int lazysequence
    val nth_fib : int -> int
  end

9.5. التخزين المؤقت

رأينا في القسم السابق أن وحدة Lazy تخزّن نتائج الحسابات مؤقتًا، بحيث لا يُهدر وقت في إعادة حسابها. والتخزين المؤقت تقنية قوية لتسريع الخوارزميات التعاودية البسيطة تسريعًا مقاربًا، دون الحاجة إلى تغيير طريقة عمل الخوارزمية.

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

9.5.1. فيبوناتشي

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

let rec fib n = if n < 2 then 1 else fib (n - 1) + fib (n - 2)

val fib : int -> int = <fun>

ملاحظة

وللدقة، يتبين أن زمن تشغيله هو $O(\phi^n)$، حيث $\phi$ النسبة الذهبية $\frac{1 + \sqrt{5}}{2}$.

وإذا سجّلنا أعداد فيبوناتشي أثناء حسابها، أمكننا تفادي هذا العمل المكرر. والفكرة أننا عند حساب f n نخزّنه في جدول مفهرس بـ n. وفي هذه الحالة مفاتيح الفهرسة أعداد صحيحة، لذا يمكننا تنفيذ هذا الجدول بمصفوفة:

let fibm n =
  let memo : int option array = Array.make (n + 1) None in
  let rec f_mem n =
    match memo.(n) with
    | Some result -> (* computed already *) result
    | None ->
        let result =
          if n < 2 then 1 else f_mem (n - 1) + f_mem (n - 2)
        in
        (* record in table *)
        memo.(n) <- Some result;
        result
  in
  f_mem n

val fibm : int -> int = <fun>

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

فكيف نحلل زمن تشغيل هذه الدالة؟ الزمن المستغرق في استدعاء واحد لـ f_mem هو $O(1)$ إذا استثنينا الزمن المستغرق في أي استدعاءات تعاودية تجريها. والآن نبحث عن طريقة لتقييد العدد الإجمالي للاستدعاءات التعاودية بإيجاد مقياس ما للتقدم الحاصل.

ومن الخيارات الجيدة لمقياس التقدم، ليس هنا فحسب بل في استخدامات كثيرة للتخزين المؤقت، عدد المدخلات غير الفارغة في الجدول (أي المدخلات التي تحتوي Some n لا None). ففي كل مرة تُجري f_mem الاستدعاءين التعاوديين تزيد أيضًا عدد المدخلات غير الفارغة بمقدار واحد (بملء مدخلة كانت فارغة في الجدول بقيمة جديدة). وبما أن الجدول لا يحتوي إلا n مدخلة، فلا يمكن أن يكون هناك في المجموع إلا $O(n)$ استدعاء لـ f_mem، بزمن تشغيل إجمالي $O(n)$ (لأننا أثبتنا أعلاه أن كل استدعاء يستغرق $O(1)$). وهذا التسريع من التخزين المؤقت يقلل زمن التشغيل من أسي إلى خطي، وهو تغيير هائل—فمثلًا، عند $n=4$ يكون التسريع من التخزين المؤقت أكثر من مليون ضعف!

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

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

9.5.2. التخزين المؤقت باستخدام الدوال عالية الرتبة

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

let memo f =
  let h = Hashtbl.create 16 in
  fun x ->
    try Hashtbl.find h x
    with Not_found ->
      let y = f x in
      Hashtbl.add h x y;
      y

val memo : ('a -> 'b) -> 'a -> 'b = <fun>

أما الدوال التعاودية، فيجب تعديل بنية الاستدعاء التعاودي فيها. ويمكن تجريد ذلك بصورة مستقلة عن الدالة التي تُخزَّن مؤقتًا:

let memo_rec f =
  let h = Hashtbl.create 16 in
  let rec g x =
    try Hashtbl.find h x
    with Not_found ->
      let y = f g x in
      Hashtbl.add h x y;
      y
  in
  g

val memo_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

والآن يمكننا إعادة كتابة دالة fib الأصلية أعلاه مع تعديل طفيف باستخدام تقنية التخزين المؤقت العامة هذه:

let fib_memo =
  let fib self n =
    if n < 2 then 1 else self (n - 1) + self (n - 2)
  in
  memo_rec fib

val fib_memo : int -> int = <fun>

9.5.3. للمتعة فحسب: تحسين الحفلة

لنفترض أننا نريد إقامة حفلة لشركة مخططها التنظيمي شجرة ثنائية. ولكل موظف «قيمة متعة» مرتبطة به، ونريد أن يكون لمجموعة الموظفين المدعوين أقصى مجموع لقيم المتعة. لكن لا متعة لأي موظف إذا دُعي رئيسه، لذا لا ندعو أبدًا موظفين متصلين في المخطط التنظيمي. (والاسم الأقل متعة لهذه المسألة هو المجموعة المستقلة ذات الوزن الأقصى في شجرة.) وبالنسبة إلى مخطط تنظيمي فيه $n$ موظفًا، توجد $2^{n}$ قائمة دعوة ممكنة، لذا فالخوارزمية الساذجة التي تقارن متعة كل قائمة دعوة صالحة تستغرق زمنًا أسيًا.

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

type tree = Empty | Node of int * tree * tree

والآن، كيف نحل هذه المسألة تعاوديًا؟ من الملاحظات المهمة أن قائمة الدعوة المثلى التي لا تتضمن العقدة الجذرية في أي شجرة ستكون اتحاد قائمتي الدعوة المثليين للشجرتين الفرعيتين اليسرى واليمنى. أما قائمة الدعوة المثلى التي تتضمن العقدة الجذرية فستكون اتحاد قائمتي الدعوة المثليين للابن الأيسر والابن الأيمن دون أن تتضمن كل منهما عقدتها الجذرية. لذا يبدو مفيدًا أن تكون لدينا دوال تحسّن قوائم الدعوة في حالة اشتراط دعوة العقدة الجذرية وفي حالة استبعادها. وسنسمي هاتين الدالتين party_in وparty_out. وحينئذٍ تكون نتيجة party مجرد الأقصى بين هاتين الدالتين:

module Unmemoized = struct
  type tree =
    | Empty
    | Node of int * tree * tree
  (* Returns optimum fun for t. *)
  let rec party t = max (party_in t) (party_out t)
  (* Returns optimum fun for t assuming the root node of t
   * is included. *)
  and party_in t =
    match t with
    | Empty -> 0
    | Node (v, left, right) -> v + party_out left + party_out right
  (* Returns optimum fun for t assuming the root node of t
   * is excluded. *)
  and party_out t =
    match t with
    | Empty -> 0
    | Node (v, left, right) -> party left + party right
end

module Unmemoized :
  sig
    type tree = Empty | Node of int * tree * tree
    val party : tree -> int
    val party_in : tree -> int
    val party_out : tree -> int
  end

لهذه الشيفرة زمن تشغيل أسي. لكن لاحظ أنه لا يوجد إلا $n$ استدعاء مختلف ممكن لـ party. وإذا غيّرنا الشيفرة لتخزين نتائج هذه الاستدعاءات مؤقتًا، صار الأداء خطيًا في $n$. وإليك نسخة تخزّن نتيجة party مؤقتًا وتحسب قوائم الدعوة الفعلية أيضًا. لاحظ أن هذه الشيفرة تخزّن النتائج مؤقتًا في الشجرة مباشرةً.

module Memoized = struct
  (* This version memoizes the optimal fun value for each tree node. It
     also remembers the best invite list. Each tree node has the name of
     the employee as a string. *)
  type tree =
    | Empty
    | Node of
        int * string * tree * tree * (int * string list) option ref
  let rec party t : int * string list =
    match t with
    | Empty -> (0, [])
    | Node (_, name, left, right, memo) -> (
        match !memo with
        | Some result -> result
        | None ->
            let infun, innames = party_in t in
            let outfun, outnames = party_out t in
            let result =
              if infun > outfun then (infun, innames)
              else (outfun, outnames)
            in
            memo := Some result;
            result)
  and party_in t =
    match t with
    | Empty -> (0, [])
    | Node (v, name, l, r, _) ->
        let lfun, lnames = party_out l and rfun, rnames = party_out r in
        (v + lfun + rfun, name :: lnames @ rnames)
  and party_out t =
    match t with
    | Empty -> (0, [])
    | Node (_, _, l, r, _) ->
        let lfun, lnames = party l and rfun, rnames = party r in
        (lfun + rfun, lnames @ rnames)
end

module Memoized :
  sig
    type tree =
        Empty
      | Node of int * string * tree * tree * (int * string list) option ref
    val party : tree -> int * string list
    val party_in : tree -> int * string list
    val party_out : tree -> int * string list
  end

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

9.6. المصفوفات الدائمة

يوفر نوع array المدمج في OCaml عمليتي get و set ثابتتي الزمن. لكنه بنية بيانات عابرة. ويؤدي ذلك إلى السؤال: هل يمكن أن تكون لدينا مصفوفات دائمة، وإن أمكن، فما مقدار جودة الأداء الذي قد نحصل عليه؟

وإليك الواجهة التي نريد تنفيذها:

module type PersistentArray = sig
  type 'a t
  (** The type of persistent arrays whose elements have type ['a]. The
      array indexing is zero based, meaning that the first element is at
      index [0], and the last element is at index [n - 1], where [n] is 
      the length of the array. Any index less than [0] or greater
      than [n - 1] is out of bounds. *)
  val make : int -> 'a -> 'a t
  (** [make n x] is a persistent array of length [n], with each element
      initialized to [x]. Raises [Invalid_argument] if [n] is negative
      or too large for the system. *)
  val length : 'a t -> int
  (** [length a] is the number of elements in [a]. *)
  val get : 'a t -> int -> 'a
  (** [get a i] is the element at index [i] in [a]. Raises [Invalid_argument]
      if [i] is out of bounds. *)
  val set : 'a t -> int -> 'a -> 'a t
  (** [set a i x] is an array that stores [x] at index [i] and otherwise is
      the same as [a]. Raises: [Invalid_argument] if [i] is out of bounds. *)
end

module type PersistentArray =
  sig
    type 'a t
    val make : int -> 'a -> 'a t
    val length : 'a t -> int
    val get : 'a t -> int -> 'a
    val set : 'a t -> int -> 'a -> 'a t
  end

تلك الواجهة هي في الجوهر الواجهة نفسها لوحدة Array في OCaml، لكن مختزلة إلى أربع دوال أساسية فحسب.

وسنرى بعد ذلك ثلاثة تنفيذات لتلك الواجهة. وسيحقق كل منها أداءً أفضل تدريجيًا. وتستند واجهتنا النهائية إلى Conchon و Filliâtre (2007)؛ انظر نهاية هذا القسم للمراجع.

9.6.1. مصفوفات النسخ عند الإسناد

أسهل تنفيذ للمصفوفات الدائمة هو مجرد عمل نسخة من المصفوفة كلها عند كل عملية set. وبهذه الطريقة تبقى النسخ القديمة من المصفوفة دائمة—فلا تغيّرها عمليات set اللاحقة. وإليك التنفيذ:

module CopyOnSetArray : PersistentArray = struct
  type 'a t = 'a array
  (** Efficiency: O(n). *)
  let make = Array.make
  (** Efficiency: O(1). *)
  let length = Array.length
  (** Efficiency: O(1). *)
  let get = Array.get
  (** Efficiency: O(n). *)
  let set a i x =
    let a' = Array.copy a in (* copy the array *)
    a'.(i) <- x; (* mutate one element *)
    a'
end

module CopyOnSetArray : PersistentArray

ندفع ثمنًا باهظًا مقابل set في هذا التنفيذ: فبدلًا من $O(1)$ كما في array، هي $O(n)$. وسنحسّن ذلك في تنفيذنا التالي.

ملاحظة

قبل أن نمضي، لنتوقف وننظر في جانب من CopyOnSetArray يختلف عن أي بنية بيانات رأيناها من قبل. فالواجهة التي يحققها مكتوبة بالأسلوب الوظيفي، لكن التنفيذ يستخدم ميزات أمرية. ولاحظ أن عملية set لا تعيد unit؛ بل تنتج مصفوفة جديدة من مصفوفة قديمة. وهي تحقق تلك الدوامة في العمق رغم استخدام بنية بيانات عابرة، هي array. والدرس الذي يمكن أن نتعلمه أنه يمكن بناء بنى بيانات دائمة في اللغات الأمرية باستخدام الميزات التي توفرها.

9.6.2. مصفوفات شجرة الإصدارات

عملية set المكلفة في النسخ عند الإسناد تؤدي عملًا أكثر مما ينبغي بكثير. فرغم أن تغييرًا واحدًا فقط يجري على عنصر مصفوفة، تُنسخ كل عناصر المصفوفة. ولتحقيق أداء أفضل، يمكننا إلغاء النسخ والاحتفاظ بدلًا من ذلك بسجل صغير لجميع عمليات set التي وقعت. وستحتاج كل مدخلة في السجل إلى تسجيل تغيير واحد فقط جرى. فمثلًا، لنفترض أن لدينا المتتالية التالية من العمليات:

let a0 = make 3 0
let a1 = set a0 1 7
let a2 = set a1 2 8
let a3 = set a1 2 9

سيكون سجلنا كما يلي:

• a0 هي [|0; 0; 0|]. ويستغرق تخزينها مساحة خطية.
• a1 هي نفسها a0 إلا أن الفهرس 1 فيها 7. ويستغرق تخزينها مساحة ثابتة فقط.
• a2 هي نفسها a1 إلا أن الفهرس 2 فيها 8. ومرة أخرى، مساحة ثابتة.
• a3 هي نفسها a1 إلا أن الفهرس 2 فيها 9. ومرة أخرى، مساحة ثابتة.

لاحظ كيف تشترك a2 وa3 في المصفوفة الأساس نفسها a1، لكنهما تتفرعان بطريقتين مختلفتين بضبط الفهرس 2 على 8 أو 9. لذا فبنية هذا السجل يُمثّلها على أفضل وجه شجرة، لا قائمة:

       (entry for a0)
             |
       (entry for a1)
       /            \
(entry for a2)     (entry for a3)

تخبرنا كل عقدة في تلك الشجرة بما ينبغي أن تكون عليه إصدارات (versions) مختلفة من المصفوفة. ويقودنا ذلك إلى استحداث نوع الشجرة التالي:

type 'a version_tree =
  | Base of 'a array
  | Diff of int * 'a * 'a version_tree

type 'a version_tree = Base of 'a array | Diff of int * 'a * 'a version_tree

تحتوي عقدة Base الإصدار الأساسي من المصفوفة؛ وفي مثالنا أعلاه سيكون ذلك a0. وتسجّل عقدة Diff فرقًا ينشئه set. وستبدو شجرة الإصدارات لمثالنا أعلاه هكذا:

              (Base [|0; 0; 0|])      <---- a0
                      |
                  (Diff 1 7)          <---- a1
                 /          \
a2 ----> (Diff 2 8)        (Diff 2 9) <---- a3

وتظهر الشجرة نفسها في منتصف ذلك المخطط. ومؤشرات a0 حتى a3 تشير إلى عقد فردية من تلك الشجرة وتلتقط كل إصدار من الإصدارات الدائمة للمصفوفة.

تلميح

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

Set. لتنفيذ set a i x، كل ما علينا فعله إنشاء عقدة Diff جديدة:

let set a i x = Diff (i, x, a)

val set : 'a version_tree -> int -> 'a -> 'a version_tree = <fun>

وكفاءة ذلك $O(1)$ فحسب، وهو تحسن كبير مقارنة بمصفوفات النسخ عند الإسناد.

Get. لتنفيذ get a i، ما علينا إلا السير في مسار من الشجرة بدءًا من a لإيجاد أول Diff يسجّل تغييرًا في الفهرس i. فإن لم يُوجد مثل ذلك التغيير أبدًا، أمكننا إعادة القيمة عند ذلك الفهرس في عقدة Base:

let rec get a i =
  match a with
  | Base b -> b.(i)
  | Diff (j, v, a') ->
      if i = j then v else get a' i

val get : 'a version_tree -> int -> 'a = <fun>

وكفاءة ذلك التنفيذ $O(k)$، حيث $k$ عدد عمليات set التي أُجريت على المصفوفة الدائمة. وفي أسوأ الحالات، تكون جميع تلك العمليات قد أُجريت على فهرس مختلف عن الفهرس الذي نريد get عليه، وأُجريت كلها دون إنشاء أي فروع في الشجرة—فمثلًا make 2 0 |> set 0 1 |> set 0 2 |> ... |> set 0 k |> get 1. حينئذٍ تتدهور الشجرة إلى قائمة مترابطة، وتُضطر get إلى السير في القائمة كلها نزولًا إلى عقدة Base لإيجاد القيمة الأصلية.

لاحظ أن $k$ قد تكون أكبر بكثير أو أصغر بكثير من $n$، أي حجم المصفوفة. فبتحسيننا أداء set، ربما أفسدنا أداء get. وسنعود إلى هذه المسألة في تنفيذنا التالي ونحسّن أداء get.

تنفيذ شجرة الإصدارات. بجمع كل ذلك معًا، إليك تنفيذًا للمصفوفات الدائمة باستخدام أشجار الإصدارات:

module VersionTreeArray : PersistentArray = struct
  (** AF: A rep such as [Diff (i, x, Diff (j, y, Base a))] represents the 
      array [a] except element [j] is [y] and element [i] is [x]. If there 
      are multiple diffs for an index, the outermost wins. E.g.,
      [Diff (i, x, Diff (i, y, Base a))] represents an array whose 
      element [i] is [x], not [y]. *)
  type 'a t =
    | Base of 'a array
    | Diff of int * 'a * 'a t
  (** Efficiency: O(n). *)
  let make n x = Base (Array.make n x)
  (** Efficiency: O(k), where k is the number of [set] operations that have
      been performed on the array. *)
  let rec length = function
    | Base b -> Array.length b
    | Diff (_, _, a) -> length a
  (** Efficiency: O(k). *)
  let rec get a i =
    match a with
    | Base b -> b.(i)
    | Diff (j, x, a') ->
        if i = j then x else get a' i
  (** Efficiency: O(1). *)
  let set a i x = Diff (i, x, a)
end

module VersionTreeArray : PersistentArray

9.6.3. إعادة تأسيس مصفوفات شجرة الإصدارات

حققنا بأشجار الإصدارات عمليات set ثابتة الزمن لمصفوفة دائمة، لكن عمليات get لم تعد ثابتة الزمن—فقد صارت $O(k)$، حيث $k$ عدد عمليات set التي أُجريت. فهل توجد طريقة لجعل العمليتين ثابتتي الزمن مع بقاء المصفوفة دائمة؟ الجواب: تقريبًا!

في الوقت الحالي، الإصدار الأصلي من المصفوفة المخزَّن في عقدة Base هو الأساسي (primary)، ويكون وصوله دائمًا ثابت الزمن بـ get. وسنستحدث عملية إعادة تأسيس (rebasing) جديدة يمكنها جعل أي إصدار آخر من المصفوفة هو الأساسي. وحينئذٍ سيكون وصول ذلك الإصدار ثابت الزمن بـ get، وإن بقيت الإصدارات الأخرى $O(k)$. وعند الوصول إلى إصدار $v$ من مصفوفة (سواء بـ length أو set)، سنغيّر شجرة الإصدارات لجعل $v$ أساسيًا. ويعني ذلك تغيير عقدة Base لتخزين المحتويات وفق $v$، وتعديل عقد Diff حسب الحاجة للتعويض عن ذلك التغيير في الأساس.

وبما أننا سنغيّر الأشجار الآن، يحتاج نوع التمثيل إلى التغيير بإضافة مستوى من غير المباشرة:

type 'a rebasing_tree = 'a node ref
and 'a node =
  | Base of 'a array
  | Diff of int * 'a * 'a rebasing_tree

type 'a rebasing_tree = 'a node ref
and 'a node = Base of 'a array | Diff of int * 'a * 'a rebasing_tree

Make و set. لا تتطلب عمليتا make وset إلا إدراج استدعاء لـ ref للتكيّف مع نوع التمثيل الجديد:

let make n x = ref (Base (Array.make n x))
let set a i x = ref (Diff (i, x, a))

val make : int -> 'a -> 'a node ref = <fun>

val set : 'a rebasing_tree -> int -> 'a -> 'a node ref = <fun>

وكفاءتهما لم تتغير: $O(n)$ لـ make، و$O(1)$ لـ set.

Rebase. لإعادة تأسيس شجرة، نستحدث دالة مساعدة تعاودية جديدة rebase : 'a rebasing_tree -> 'a rebasing tree بحيث تغيّر rebase t الشجرة t لجعل الإصدار الذي تمثله t أساسيًا. لذا، حين تعود rebase، يُضمن أن تكون t مرجعًا إلى عقدة Base.

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

ثانيًا، إذا كانت t مرجعًا إلى عقدة Diff، فعندنا عمل نؤديه. وتلك العقدة بالشكل Diff(i, x, t') حيث تمثل t' إصدارًا آخر من المصفوفة. نستدعي rebase على t' لجعله أساسيًا؛ وبعد ذلك يجب أن تكون t' مرجعًا إلى عقدة Base. ويعني ذلك أن لدينا الحالة التالية، حيث a مصفوفة:

t  ---> Diff (i, x, t')
t' ---> Base a

ولجعل t أساسيًا، ما علينا إلا مبادلة تلك العقد، وكذلك مبادلة القيم الموجودة عند الفهرس i. لنفترض أن a.(i) في عقدة Base هو y. نغيّر a.(i) ليصير x؛ ولنسمِّ تلك المصفوفة a'. وننشئ عقدة Diff جديدة تحتوي y:

t  ---> Base a'
t' ---> Diff (i, y, t)

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

وإليك الشيفرة التي تنفّذ إعادة التأسيس:

let rec rebase a =
  match !a with
  | Base b -> b
  | Diff (i, x, a') ->
      let b = rebase a' in
      let old_x = b.(i) in
      b.(i) <- x;
      a := Base b;
      a' := Diff (i, old_x, a);
      b

val rebase : 'a rebasing_tree -> 'a array = <fun>

وكفاءة rebase هي $O(k)$، لأنه قد يوجد حتى $k$ عقدة Diff بين t وعقدتها Base الأصلية. ومباشرةً بعد استدعاء rebase t، لن تكون أي استدعاءات لاحقة لـ rebase t إلا $O(1)$، لأن t صارت الآن أساسية.

Get و length. والآن بعد أن صارت لدينا rebase، لا يلزم إلا تعديل صغير في length وget لاستدعاء rebase:

let length a = Array.length (rebase a)
let get a i = (rebase a).(i)

val length : 'a rebasing_tree -> int = <fun>

val get : 'a rebasing_tree -> int -> 'a = <fun>

وكفاءة هاتين الدالتين هي نفسها كفاءة rebase: $O(k)$ في الاستدعاء الأول، ثم $O(1)$ في الاستدعاءات المستقبلية ما لم يُوصل إلى إصدار آخر من المصفوفة في هذه الأثناء.

تنفيذ شجرة الإصدارات مع إعادة التأسيس: بجمع كل ذلك معًا، إليك تنفيذًا للمصفوفات الدائمة باستخدام أشجار الإصدارات مع إعادة التأسيس:

module RebasingVersionTreeArray : PersistentArray = struct
  type 'a t = 'a node ref
  (** See [VersionTreeArray]. *)
  and 'a node =
    | Base of 'a array
    | Diff of int * 'a * 'a t
  (** Efficiency: O(n). *)
  let make n x = ref (Base (Array.make n x))
  (** Efficiency: O(k), where k is the number of diffs between this version
      of the array and its base. At most, that is the number of [set] 
      operations performed on all versions of the array. If there aren't 
      any diffs, O(1). After a [rebase], remains O(1) until a different 
      version of the array is accessed. Not tail recursive. *)
  let rec rebase a =
    match !a with
    | Base b -> b
    | Diff (i, x, a') ->
        let b = rebase a' in
        let old_x = b.(i) in
        b.(i) <- x;
        a := Base b;
        a' := Diff (i, old_x, a);
        b
  (** Efficiency: Same as [rebase]. *)
  let length a = Array.length (rebase a)
  (** Efficiency: Same as [rebase]. *)
  let get a i = (rebase a).(i)
  (** Efficiency: O(1). *)
  let set a i v = ref (Diff (i, v, a))
end

module RebasingVersionTreeArray : PersistentArray

وبإعادة التأسيس صارت لدينا الآن عمليتا get وset ثابتتا الزمن $O(1)$ على الإصدار الأساسي (الأكثر وصولًا) من المصفوفة. وندفع ثمنًا $O(k)$ للانتقال إلى إصدار أساسي جديد، لكن بعد ذلك يبقى الوصول إليه $O(1)$ حتى تحدث إعادة تأسيس أخرى.

9.6.4. المراجع

تنفيذنا النهائي أشبه ما يكون بتنفيذ Sylvain Conchon و Jean-Christophe Filliâtre (A persistent union-find data structure، ورشة ACM حول ML، 2007). وهما ينسبان إلى Henry Baker فكرة أشجار الإصدارات (Shallow binding in LISP 1.5، CACM 21:7، 1978) وإعادة التأسيس (Shallow binding makes functional arrays fast، SIGPLAN Not.، 26(8):145-147، 1991).

9.7. أشجار 2-3

شجرة 2-3 (two-three tree) بنية بيانات شجرة متوازنة أخرى يمكن استخدامها لتنفيذ المجموعات والخرائط. ومثل أشجار الأحمر والأسود، تحقق شجرة 2-3 أداءً لوغاريتميًا مع تجنب القابلية للتغيير. ويُنسب اختراع أشجار 2-3 إلى John Hopcroft بحسب Cormen وآخرين في Introduction to Algorithms، 1990، ص 280.

9.7.1. نوع التمثيل

تعمّم شجرة 2-3 الشجرة الثنائية، حيث يكون لكل عقدة في شجرة 2-3 إما ابنان وإما ثلاثة أبناء. ويُسميان عقدتين (2-nodes) وعقد ثلاث (3-nodes) على الترتيب. وتحتوي عقدة 2 على قيمة واحدة، وتحتوي عقدة 3 على قيمتين:

type 'a t =
  | Leaf
  | Two of {
      lt : 'a t; (* left subtree *)
      v : 'a;    (* value *)
      rt : 'a t  (* right subtree *)
    }
  | Three of {
      lt : 'a t; (* left subtree *)
      vl : 'a;   (* left value *)
      mt : 'a t; (* middle subtree *)
      vr : 'a;   (* right value *)
      rt : 'a t  (* right subtree *)
    }
let empty = Leaf

type 'a t =
    Leaf
  | Two of { lt : 'a t; v : 'a; rt : 'a t; }
  | Three of { lt : 'a t; vl : 'a; mt : 'a t; vr : 'a; rt : 'a t; }

val empty : 'a t = Leaf

وعند استخدامها لتمثيل مجموعة، تكون دالة التجريد أن عناصر المجموعة هي القيم (من النوع 'a) المخزنة في العقد.

وثابت التمثيل لشجرة 2-3 مكوّن من جزأين. الجزء الأول هو ثابت الترتيب (ordering invariant)، الذي يعمّم ثابت شجرة البحث الثنائية. ويقول ثابت الترتيب:

• لأي عقدة ثنائية {lt; v; rt}، تكون القيم مرتبة `lt
• ولأي عقدة ثلاثية {lt; vl; mt; vr; rt}، تكون القيم مرتبة `lt

أما الجزء الثاني من ثابت التمثيل فهو ثابت التوازن (balance invariant)، ويمكن صوغه بثلاث طرق متكافئة:

1. كل ورقة في الشجرة على العمق نفسه.
2. كل شقيقتين في الشجرة على الارتفاع نفسه.
3. كل مسار كامل (أي من الجذر إلى ورقة) في الشجرة له الطول نفسه.

ولعل الصوغ الأخير هو الأنفع لثابت التوازن إذا أردنا المقارنة بأشجار الأحمر والأسود. تذكّر أن أشجار الأحمر والأسود كانت تسمح لأطوال المسارات بالاختلاف بمعامل اثنين. لذا فأشجار 2-3 أصرح في التوازن من أشجار الأحمر والأسود.

وطول كل مسار كامل في شجرة 2-3 لوغاريتمي في عدد عقد الشجرة، وهو ما يعطي عمليات لوغاريتمية الزمن.

9.7.2. العضوية

للتحقق من العضوية في شجرة 2-3، نستخدم تعميمًا لخوارزمية العضوية في أشجار البحث الثنائية. ويخبرنا ثابت الترتيب، عند كل فرع، أي اتجاه نسلك للبحث عن عنصر.

let rec mem x = function
 | Leaf -> false
 | Two { lt; v; rt } ->
     if x < v then mem x lt else if x > v then mem x rt else true
 | Three { lt; vl; mt; vr; rt } ->
     if x < vl then mem x lt
     else if x > vr then mem x rt
     else if x > vl && x < vr then mem x mt
     else true

val mem : 'a -> 'a t -> bool = <fun>

9.7.3. الإدراج: خوارزمية Appel

لإدراج عنصر، نستخدم كالمعتاد إجراء البحث نفسه المستخدم في mem لإيجاد الموضع الذي ينبغي أن يكون فيه العنصر. فإن كان العنصر في الشجرة بالفعل، فلا تغيير. وإن لم يكن في الشجرة، ينتهي البحث عند ورقة. فكيف يمكننا إدراج العنصر الجديد عند تلك الورقة مع الحفاظ على ثابت التوازن؟ الخوارزمية التالية لأداء تلك المهمة قد تكون من الفولكلور؛ فإن كان أي قارئ يعرف مرجعًا موثوقًا لها، فأخبرنا. لكن سنسميها الآن خوارزمية Appel، لأن Michael Clarkson تعلمها من Andrew Appel.

بخوارزمية Appel، نحوّل الورقة التي ينتهي عندها البحث إلى عقدة 2 جديدة بلا أبناء تحتوي القيمة المُدرجة. ويحافظ ذلك على ثابت الترتيب، لكنه يخرق ثابت التوازن عمومًا، لأن عقدة 2 الجديدة تجعل طول مسار البحث ينمو بمقدار واحد. وبعبارة أخرى: يزداد ارتفاع الشجرة بمقدار واحد.

لذا نُجري تعاودًا صعودًا في الشجرة لإعادة ثابت التوازن وضمان أن يكون لجميع المسارات الطول نفسه. والهدف إيجاد موضع لاستيعاب (absorb) تغير الارتفاع، إن أمكن. وبما أننا أنشأنا للتو عقدة 2 جديدة، فثمة حالتان يجب النظر فيهما ونحن نصعد تعاوديًا: أن يكون أب العقدة الجديدة عقدة 2، وفي هذه الحالة نُجري عملية دمج (merge)؛ أو أن يكون عقدة 3، وفي هذه الحالة نُجري عملية تقسيم (split). وتعمل هاتان العمليتان كما هو موضح أدناه.

9.7.3.1. الدمج

تذكّر أن المشكلة التي نحاول حلها أن عقدة 2 ربما صارت طويلة جدًا—فقد يكون ارتفاعها أكبر بواحد من ارتفاع أشقائها. ولنسمِّ عقدة 2 كهذه عقدة طويلة (tall). وفيما يلي، العقد الموسومة بنجمة عقد طويلة. وإذا كانت لعقدة 2 الطويلة عقدة 2 أب، فيمكن للأب أن يستوعب تغير الارتفاع بأن يصير هو نفسه عقدة 3. ويوضح المخطط التالي ذلك:

    y              x,y              x
   / \           /  |  \           / \
 *x*  c   ==>   a   b   c  <==    a  *y*
 / \                                 / \
a   b                               b   c

في ذلك المخطط، تمثل a وb وc أشجارًا فرعية. وثمة حالتان: دمج عقدة طويلة *x* من اليسار، ودمج عقدة طويلة *y* من اليمين. وفي كلتا الحالتين، تُدمج قيمة العقدة الطويلة في أبيها، وهو ما يحوّل الأب من عقدة 2 إلى عقدة 3. ويُستوعب الارتفاع الإضافي، فيُعاد بذلك ثابت التوازن.

وبعد حدوث الدمج، ننتهي من عملية الإدراج ويمكننا الصعود تعاوديًا حتى الجذر دون إجراء مزيد من التغييرات.

9.7.3.2. التقسيم

وماذا لو كانت لعقدة 2 الطويلة عقدة 3 أب؟ حينئذٍ لا يمكننا الدمج، لأن ذلك سينشئ عقدة 4.

ملاحظة

توجد ما تُسمى أشجار 2-3-4 (2-3-4 trees)، وربما على نحو مفاجئ فهي وثيقة الصلة بأشجار الأحمر والأسود. لكننا هنا سنلتزم بأشجار 2-3.

بل نقوم بدلًا من ذلك بـتقسيم عقدة 3 الأب إلى عقدتي 2. ومع عقدة 2 الطويلة الموجودة بالفعل، يحوّل ذلك شجرة فيها عقدتا 2 وعقدة 3 إلى شجرة فيها ثلاث عقد من نوع 2، كما هو موضح أدناه:

    y,z             *y*              x,y
   / | \           /   \            / | \
 *x* c  d  ==>    x     z    <==   a  b *z*
 / \             / \   / \              / \
a   b           a   b c   d            c   d

                     ⇑

                    x,z
                   / | \
                  a *y* d
                    / \
                   b   c

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

9.7.3.3. إتمام الإدراج

وبالمراجعة، قررنا إنشاء عقدة 2 طويلة كلما أدرجنا قيمة جديدة. ورأينا أنه يمكن دمج عقدة 2 الطويلة في أب من نوع عقدة 2، فيُعاد التوازن بذلك؛ أو يمكن تقسيم أب من نوع عقدة 3، فيُنشأ بذلك عقدة 2 طويلة جديدة نواصل محاولة استيعاب ارتفاعها أعلى في الشجرة. ولاحظ أننا لم نُنتج قط عقدة 3 طويلة نتيجة أي من عمليات الإدراج أو الدمج أو التقسيم هذه. لذلك لا يلزمنا النظر في أي حالات للدمج أو التقسيم مع عقدة 3 طويلة. ويعني ذلك أننا انتهينا من تصميم الخوارزمية.

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

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

let impossible () = failwith "impossible: grow returns Two"
(** [ins x t] inserts [x] into [t] using Appel's algorithm. Returns:
    [new_t, grew], where [new_t] is the new tree (including [x]) and [grew] is
    whether the tree height grew. *)
let rec ins (x : 'a) (t : 'a t) : 'a t * bool =
  match t with
  | Leaf ->
      (* Insertion into a leaf creates a new 2-node, which grows the
          height. *)
      (Two { lt = Leaf; v = x; rt = Leaf }, true)
  | Two { lt; v; rt } ->
      if x = v then
        (* If [x] is already in the tree, no change is needed. *)
        (t, false)
      else
        (* Otherwise, insert [x] into the left or right subtree, and
            incorporate the current 2-node into the result *)
        ins_sub2 x lt v rt
  | Three { lt; vl; mt; vr; rt } ->
      if x = vl || x = vr then
        (* If [x] is already in the tree, no change is needed. *)
        (t, false)
      else
        (* Otherwise, insert [x] into the left, middle, or right subtree, and
            incorporate the current 3-node into the result*)
        ins_sub3 x lt vl mt vr rt
(** [ins_sub2 x lt v rt] inserts [x] into one of the subtrees of a 2-node,
    where that two-node is [Two {lt; v; rt}]. Returns [new_t, grew], where
    [new_t] is the new tree (including [lt], [v], and [rt]) and [grew] is
    whether the tree height grew as a result of the insert. Requires:
    [x <> v]. *)
and ins_sub2 (x : 'a) (lt : 'a t) (v : 'a) (rt : 'a t) : 'a t * bool =
  if x < v then
    (* [x] belongs in [lt]. *)
    ins_sub2_left x lt v rt
  else if x > v then (* [x] belongs in [rt]. *)
    ins_sub2_right x lt v rt
  else
    (* [x] belongs in neither [lt] nor [rt], but then we should never have
        called [ins_sub2] on it. *)
    failwith "precondition violated"
(** [ins_sub2_left x lt v rt] inserts [x] into the left subtree of a 2-node,
    where that two-node is [Two {lt; v; rt}]. Returns [new_t, grew], where
    [new_t] is the new tree (including [lt], [v], and [rt]) and [grew] is
    whether the tree height grew as a result of the insert. *)
and ins_sub2_left (x : 'a) (lt : 'a t) (v : 'a) (rt : 'a t) : 'a t * bool =
  match ins x lt with
  | new_lt, false ->
      (* [x] was inserted into [lt] without growing the height, so we can
          safely reattach the resulting subtree without doing any more work to
          rebalance. *)
      (Two { lt = new_lt; v; rt }, false)
  | Two { lt = child_lt; v = child_v; rt = child_rt }, true ->
      (* [x] was inserted into [lt], and that caused [lt] to grow in height
          and have a 2-node at its root. We can merge that 2-node into the
          current 2-node to form a 3-node, which absorbs the change in
          height. *)
      (Three { lt = child_lt; vl = child_v; mt = child_rt; vr = v; rt }, false)
  | _, true ->
      (* Growth must produce a 2-node at the root, which would have been
          handled by the previous branch. *)
      impossible ()
(** [ins_sub2_right x lt v rt] inserts [x] into the right subtree of a 2-node,
    where that two-node is [Two {lt; v; rt}]. Returns [new_t, grew], where
    [new_t] is the new tree (including [lt], [v], and [rt]) and [grew] is
    whether the tree height grew as a result of the insert. *)
and ins_sub2_right (x : 'a) (lt : 'a t) (v : 'a) (rt : 'a t) : 'a t * bool =
  match ins x rt with
  | new_rt, false ->
      (* [x] was inserted into [rt] without growing the height, so we can
          safely reattach the resulting subtree without doing any more work to
          rebalance. *)
      (Two { lt; v; rt = new_rt }, false)
  | Two { lt = child_lt; v = child_v; rt = child_rt }, true ->
      (* [x] was inserted into [rt], and that caused [rt] to grow in height
          and have a 2-node at its root. We can merge that 2-node into the
          current 2-node to form a 3-node, which absorbs the change in
          height. *)
      (Three { lt; vl = v; mt = child_lt; vr = child_v; rt = child_rt }, false)
  | _, true -> impossible ()
(** [ins_sub3 x lt vl mt vr rt] inserts [x] into one of the subtrees of a
    3-node, where that 3-node is [Three {lt; vl; mt; vr; rt}]. Returns
    [new_t, grew], where [new_t] is the new tree (including [lt], [vl], [mt],
    [vr], and [rt]) and [grew] is whether the tree height grew as a result of
    the insert. Requires: [x <> vl && x <> vr]. *)
and ins_sub3 (x : 'a) (lt : 'a t) (vl : 'a) (mt : 'a t) (vr : 'a) (rt : 'a t)
    : 'a t * bool =
  if x < vl then
    (* [x] belongs in [lt]. *)
    ins_sub3_left x lt vl mt vr rt
  else if x > vr then
    (* [x] belongs in [rt]. *)
    ins_sub3_right x lt vl mt vr rt
  else if x > vl && x < vr then
    (* [x] belongs in [mt]. *)
    ins_sub3_middle x lt vl mt vr rt
  else
    (* [x] belongs in neither [lt] nor [mt] nor [rt], but then we should never
        have called [ins_sub3] on it. *)
    failwith "precondition violated"
(** [ins_sub3_left x lt vl mt vr rt] inserts [x] into the left subtree of a
    3-node, where that 3-node is [Three {lt; vl; mt; vr; rt}]. Returns
    [new_t, grew], where [new_t] is the new tree (including [lt], [vl], [mt],
    [vr], and [rt]) and [grew] is whether the tree height grew as a result of
    the insert. *)
and ins_sub3_left
    (x : 'a)
    (lt : 'a t)
    (vl : 'a)
    (mt : 'a t)
    (vr : 'a)
    (rt : 'a t) : 'a t * bool =
  match ins x lt with
  | new_lt, false ->
      (* [x] was inserted into [lt] without growing the height, so we can
          safely reattach the resulting subtree without doing any more work to
          rebalance. *)
      (Three { lt = new_lt; vl; mt; vr; rt }, false)
  | Two { lt = child_lt; v = child_v; rt = child_rt }, true ->
      (* [x] was inserted into [lt], and that caused [lt] to grow in height
          and have a 2-node at its root. We cannot merge that 2-node into the
          current 3-node. Instead, we split the 3-node into 2-nodes, which
          causes the growth to continue upward in the tree. *)
      ( Two
          {
            lt = Two { lt = child_lt; v = child_v; rt = child_rt };
            v = vl;
            rt = Two { lt = mt; v = vr; rt };
          },
        true )
  | _, true ->
      (* Growth must produce a 2-node at the root, which would have been
          handled by the previous branch. *)
      impossible ()
(** [ins_sub3_right x lt vl mt vr rt] inserts [x] into the right subtree of a
    3-node, where that 3-node is [Three {lt; vl; mt; vr; rt}]. Returns
    [new_t, grew], where [new_t] is the new tree (including [lt], [vl], [mt],
    [vr], and [rt]) and [grew] is whether the tree height grew as a result of
    the insert. *)
and ins_sub3_right
    (x : 'a)
    (lt : 'a t)
    (vl : 'a)
    (mt : 'a t)
    (vr : 'a)
    (rt : 'a t) : 'a t * bool =
  match ins x rt with
  | new_rt, false ->
      (* [x] was inserted into [rt] without growing the height, so we can
          safely reattach the resulting subtree without doing any more work to
          rebalance. *)
      (Three { lt; vl; mt; vr; rt = new_rt }, false)
  | Two { lt = child_lt; v = child_v; rt = child_rt }, true ->
      (* [x] was inserted into [rt], and that caused [rt] to grow in height
          and have a 2-node at its root. We cannot merge that 2-node into the
          current 3-node. Instead, we split the 3-node into 2-nodes, which
          causes the growth to continue upward in the tree. *)
      ( Two
          {
            lt = Two { lt; v = vl; rt = mt };
            v = vr;
            rt = Two { lt = child_lt; v = child_v; rt = child_rt };
          },
        true )
  | _, true ->
      (* Growth must produce a 2-node at the root, which would have been
          handled by the previous branch. *)
      impossible ()
(** [ins_sub3_middle x lt vl mt vr rt] inserts [x] into the middle subtree of
    a 3-node, where that 3-node is [Three {lt; vl; mt; vr; rt}]. Returns
    [new_t, grew], where [new_t] is the new tree (including [lt], [vl], [mt],
    [vr], and [rt]) and [grew] is whether the tree height grew as a result of
    the insert. *)
and ins_sub3_middle
    (x : 'a)
    (lt : 'a t)
    (vl : 'a)
    (mt : 'a t)
    (vr : 'a)
    (rt : 'a t) : 'a t * bool =
  match ins x mt with
  | new_mt, false ->
      (* [x] was inserted into [mt] without growing the height, so we can
          safely reattach the resulting subtree without doing any more work to
          rebalance. *)
      (Three { lt; vl; mt = new_mt; vr; rt }, false)
  | Two { lt = child_lt; v = child_v; rt = child_rt }, true ->
      (* [x] was inserted into [mt], and that caused [mt] to grow in height
          and have a 2-node at its root. We cannot merge that 2-node into the
          current 3-node. Instead, we split the 3-node into 2-nodes, which
          causes the growth to continue upward in the tree. *)
      ( Two
          {
            lt = Two { lt; v = vl; rt = child_lt };
            v = child_v;
            rt = Two { lt = child_rt; v = vr; rt };
          },
        true )
  | _, true ->
      (* Growth must produce a 2-node at the root, which would have been
          handled by the previous branch. *)
      impossible ()
let insert x s =
  let new_tree, _grew = ins x s in
  new_tree

val impossible : unit -> 'a = <fun>

val ins : 'a -> 'a t -> 'a t * bool = <fun>
val ins_sub2 : 'a -> 'a t -> 'a -> 'a t -> 'a t * bool = <fun>
val ins_sub2_left : 'a -> 'a t -> 'a -> 'a t -> 'a t * bool = <fun>
val ins_sub2_right : 'a -> 'a t -> 'a -> 'a t -> 'a t * bool = <fun>
val ins_sub3 : 'a -> 'a t -> 'a -> 'a t -> 'a -> 'a t -> 'a t * bool = <fun>
val ins_sub3_left : 'a -> 'a t -> 'a -> 'a t -> 'a -> 'a t -> 'a t * bool =
  <fun>
val ins_sub3_right : 'a -> 'a t -> 'a -> 'a t -> 'a -> 'a t -> 'a t * bool =
  <fun>
val ins_sub3_middle : 'a -> 'a t -> 'a -> 'a t -> 'a -> 'a t -> 'a t * bool =
  <fun>

val insert : 'a -> 'a t -> 'a t = <fun>

9.8. الخلاصة

أخذنا في هذا الفصل غوصًا عميقًا في بعض بنى البيانات المتقدمة وتقنيات التحليل وأنماط البرمجة. وقد كان هدفنا كتابة شيفرة صحيحة وفعّالة وجميلة. فهل نجحنا؟ لك أن تحكم.

9.8.1. المصطلحات والمفاهيم

• التحليل المُستهلَك (amortized analysis)
• قائمة ترابطية (association list)
• تجميعي (associative)
• مصفوفة ترابطية (associative array)
• حد مقارب (asymptotic bound)
• غير متزامن (asynchronous)
• طريقة المصرفي (banker’s method)
• O الكبيرة (big oh)
• ارتباط (binding)
• القوة الغاشمة (brute force)
• دلو (bucket)
• تخزين مؤقت (caching)
• سلسلة (chaining)
• تصادم (collision)
• تعقيد (complexity)
• أرصدة (credits)
• دورة (cycle)
• تقييم مؤجل (delayed evaluation)
• قاموس (dictionary)
• انتشار (diffusion)
• جدول عنونة مباشرة (direct address table)
• متلهف (eager)
• كفاءة (efficiency)
• خطوات التنفيذ (execution steps)
• زمن أسي (exponential time)
• إجبار (force)
• دالة تجزئة (hash function)
• بنية بيانات لا نهائية (infinite data structure)
• تبايني (injective)
• حجم المدخل (input size)
• مفتاح (key)
• كسول (lazy)
• معامل التحميل (load factor)
• خريطة (map)
• التخزين المؤقت (memoization)
• خريطة قابلة للتغيير (mutable map)
• دائم (persistent)
• طريقة الفيزيائي (physicist’s method)
• زمن كثير الحدود (polynomial time)
• طاقة كامنة (potential energy)
• استقصاء (probing)
• قيم تعاودية (recursive values)
• خريطة الأحمر والأسود (red-black map)
• إعادة التحجيم (resizing)
• تسلسل (serialization)
• مجموعة (set)
• تيار (stream)
• ثنكة (thunk)
• أداء أسوأ حالة (worst case performance)

9.8.2. قراءات إضافية

• More OCaml: Algorithms, Methods, and Diversions، الفصلان 2 و11، لـ John Whitington.
• Introduction to Objective Caml، الفصل 8، القسم 4
• Real World OCaml، الفصلان 13 و18
• Purely Functional Data Structures، لـ Chris Okasaki. Cambridge University Press، 1999.

type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree
let rec preorder = function
  | Leaf -> []
  | Node (l,v,r) -> [v] @ preorder l @ preorder r
let rec inorder = function
  | Leaf -> []
  | Node (l,v,r) ->  inorder l @ [v] @ inorder r
let rec postorder = function
  | Leaf -> []
  | Node (l,v,r) ->  postorder l @ postorder r @ [v]
let t =
  Node(Node(Node(Leaf, 1, Leaf), 2, Node(Leaf, 3, Leaf)),
       4,
       Node(Node(Leaf, 5, Leaf), 6, Node(Leaf, 7, Leaf)))
(*
  t is
        4
      /   \
     2     6
    / \   / \
   1   3 5   7
*)
let () = assert (preorder t  = [4;2;1;3;6;5;7])
let () = assert (inorder t   = [1;2;3;4;5;6;7])
let () = assert (postorder t = [1;3;2;5;7;6;4])

type 'a sequence = Cons of 'a * (unit -> 'a sequence)

type 'a sequence = Cons of (unit -> 'a * 'a sequence)