البرمجة الديناميكية

11. البرمجة الديناميكية والحفظ (memoization)

البرمجة الديناميكية (dynamic programming) والحفظ (memoization) تقنيتان وثيقتا الصلة، تقومان على فكرة أنّ من الأفضل تجنّب حساب الشيء نفسه مرّتين.

11.1 الفكرة الأساسية

نوضّح التقنيتين من خلال المثال البسيط لمتتالية فيبوناتشي (Fibonacci). ونتذكّر أنّ هذه المتتالية من الأعداد الصحيحة (Fn) تُعرَّف كما يلي:

$$\begin{cases} F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-2} + F_{n-1} & \text{إذا كان } n \ge 2 \end{cases}$$

من السهل بما يكفي كتابة دالة تخصيصية (recursive) تحسب Fn انطلاقًا من هذا التعريف:

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

غير أنّ هذا الحل يبقى بدائيًّا إلى حدٍّ ما. فحساب F50 يستغرق أكثر من دقيقة. والمشكلة هنا لا تكمن في التخصيص (recursion) نفسه، بل في أنّنا نحسب القيم ذاتها لـ Fn عدّة مرّات. فمثلًا، لحساب F5 سيُحسب F3 مرّتين وF2 ثلاث مرّات، كما يظهر في مخطط الاستدعاء في الشكل 11.1.

الشكل 11.1: مخطط الاستدعاء لـ F5.

من السهل ملاحظة أنّ حساب Fn يتطلّب، في الحالة العامة، عددًا من عمليات الجمع يساوي Fn+1 − 1، لأنّ معادلة التخصيص مطابقة تمامًا لتلك التي تُعرّف Fn. ويمكننا ملاحظة ذلك تجريبيًّا. فحاسوب من نحو عام 2011 يستغرق ثانيتين لحساب F42، وثلاث ثوانٍ لحساب F43، وخمس ثوانٍ لحساب F44، وهكذا. ونُلاحظ هنا حدود متتالية فيبوناتشي. وبالاستقراء، يمكننا القول إنّ حساب F50 سيستغرق 89 ثانية، وهذا صحيح بدقّة تصل إلى نصف ثانية! وبما أنّ Fn ينمو نموًّا أُسِّيًّا، فلا يمكننا أن نأمل في المضي قدمًا في حساب المتتالية بهذه الطريقة.

11.1.1 الحفظ (memoization)

لكوننا نحسب الشيء نفسه عدّة مرّات، يتبادر إلينا بشكل طبيعي جدًّا أنّه يمكننا تخزين النتائج الوسيطة في جدول. ومن شأن جدول كهذا أن يربط كل عدد صحيح n بالقيمة Fn. وبناءً على ذلك، نتّبع ما يلي: لحساب fibn، نبدأ بالتحقق ممّا إذا كان هناك مدخل في الجدول يقابل n، وفي هذه الحالة نعيد القيمة الموافقة. وإلا نحسب fibn بدلالة fib(n-2)+fib(n-1)، أي بالتخصيص. ثم نعيد النتيجة بعد إضافتها إلى الجدول. وهذه التقنية، التي تقوم على استخدام جدول لتخزين النتائج الوسيطة، تُسمّى الحفظ (memoization)، وهو مصطلح صاغه الباحث دونالد ميتشي (Donald Michie) عام 1968.

ولنُنفّذ هذه الفكرة في دالة fib_memo. نبدأ بإدخال جدول تجزئة (hash table) لتخزين النتائج الوسيطة، ونختار له حجمًا ابتدائيًّا اعتباطيًّا:

  let memo = Hashtbl.create 17

تبدأ الدالة fib_memo بالتحقق ممّا إذا كانت قيمة fib n موجودة بالفعل في الجدول memo. فإن كانت كذلك، تُعاد:

  let rec fib_memo n =
    try
      Hashtbl.find memo n

وإلا نحسب النتيجة تمامًا كما في الدالة fib، أي باستخدام استدعاءين تخصيصيَّين:

    with Not_found ->
      let fn = if n <= 1 then n
               else fib_memo (n-2) + fib_memo (n-1) in

ثم نخزّنها في الجدول memo قبل إعادتها:

      Hashtbl.add memo n fn;
      fn

وبهذا تنتهي الدالة fib_memo. وفعّاليتها أكبر بكثير من فعالية fib. فحساب F50، على سبيل المثال، يصبح فوريًّا (خلافًا للثواني الـ 89 التي تستغرقها fib). ويمكننا أن نبيّن أنّ تعقيد fib_memo خطّي. وبديهيًّا، نفهم أنّ حساب Fn لم يعد يستلزم حساب Fi إلا مرّة واحدة لكل i ≤ n. ويرد الكود الكامل للدالة fib_memo في البرنامج 84 أدناه. ولاحظ أنّ الجدول memo مُعرَّف خارج الدالة fib_memo، لأنّه يجب أن يكون نفسه في جميع الاستدعاءات التخصيصية.

11.1.2 البرمجة الديناميكية

قد يبدو استخدام جدول تجزئة لحفظ حساب متتالية فيبوناتشي مكلفًا بلا ضرورة. ففي النهاية لن نخزّن سوى قيم Fi من أجل i ≤ n، وهي قيم تكفي لها مصفوفة (array) بحجم n + 1. ولو أردنا إعادة كتابة الدالة fib_memo وفقًا لهذه الفكرة، لأمكننا، على سبيل المثال، أن نبدأ بإسناد القيمة −1 إلى كل خلية في المصفوفة، للدلالة على أنّ القيمة لم تُحسب بعد. وثمّة احتمال آخر يتمثّل في ملء المصفوفة بترتيب معيّن. وفي حالتنا هذه، نرى أنّه يكفي ملء المصفوفة بترتيب متزايد، لأنّ حساب Fi يتطلّب قيمتَي Fi−2 وFi−1. وهذه التقنية، التي تقوم على استخدام جدول وملئه تدريجيًّا بنتائج الحسابات الوسيطة، تُسمّى البرمجة الديناميكية (dynamic programming)، وغالبًا ما تُختصر بـ DP.

ولنُنفّذ هذه الفكرة في دالة fib_dp. نبدأ بمعالجة الحالة الخاصة n = 0. وفي الحالة العامة، عندما n > 0، نخصّص مصفوفة f بحجم n + 1، ستضمّ قيم Fi.

  let fib_dp n =
    if n = 0 then 0 else
    let f = Array.make (n+1) 0 in

يجوز تخصيص هذه المصفوفة داخل الدالة fib_dp، لأنّها، خلافًا لـ fib_memo، لن تكون تخصيصية. بعد ذلك نملأ خلايا المصفوفة f بترتيب متزايد، مع معاملة f.(1) كحالة خاصة.

    f.(1) <- 1;
    for i = 2 to n do f.(i) <- f.(i-2) + f.(i-1) done;

وبمجرد أن تُملأ المصفوفة، ما علينا إلا إعادة القيمة الموجودة في خليتها الأخيرة.

    f.(n)

وبهذا تنتهي الدالة fib_dp. وكما في حالة fib_memo، فإنّ تعقيدها خطّي. ويمكن ملاحظة ذلك بسهولة، لأنّ الكود لا يعدو أن يكون حلقة for بسيطة. ويرد الكود الكامل للدالة fib_dp في البرنامج 85.

ملاحظة

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

11.2 الحفظ الآلي

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

ومع ذلك، من المهم أن نفهم أنّنا، لكتابة fib_dp، اعتمدنا على أمرين: كان علينا حساب Fi من أجل كل i ≤ n؛ وكان بمقدورنا حسابها بترتيب متزايد. وفي الحالة العامة، قد لا تكون مدخلات الدالة التي نريد حسابها أعدادًا صحيحة متتالية بالضرورة. وقد لا تكون أعدادًا صحيحة إطلاقًا، أو قد لا تكون التبعيات بين القيم المختلفة بهذه البساطة.

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

والأفضل من ذلك، يمكننا تنفيذ إجراء الحفظ مرّة واحدة وإلى الأبد، في صورة دالة عالية الرتبة (higher-order function) هي memo_fun، تأخذ وسيطًا دالة f يُراد حفظها. نبدأ بإنشاء جدول تجزئة نخزّن فيه النتائج المحسوبة مسبقًا.

  let memo_fun f =
    let h = Hashtbl.create 17 in

ثم نُعيد دالة تُجري الحفظ، أي تستشير الجدول وتملؤه حسب الحاجة.

    fun x ->
      try Hashtbl.find h x
      with Not_found -> let v = f x in Hashtbl.add h x v; v

نوع الدالة memo_fun كما يلي:

    memo_fun : (’a -> ’b) -> ’a -> ’b

وكما نرى، تأخذ memo_fun وسيطًا دالةً بنوع اعتباطي وتُعيد دالة من النوع نفسه. وتنبع الصفة المتعدّدة الأشكال (polymorphic) للدالة من استخدام جداول التجزئة العامة في OCaml (انظر التمرين 11.2).

ولحفظ الدالة fib، يكفي أن نكتب:

  let fib_memo2 = memo_fun fib

إذا حسبنا fib_memo250 مرّتين، يصبح الحساب الثاني فوريًّا لأنّ النتيجة موجودة في الجدول. غير أنّ الحساب الأول يستغرق وقتًا مماثلًا لِما يستغرقه دون حفظ. فخلال الاستدعاء الأول، نحسب fib50 لأنّ القيمة غير موجودة في الجدول. وأثناء هذا الحساب، تُوجَّه استدعاءات تخصيصية إلى الدالة fib لا إلى نسختها المحفوظة fib_memo2.

وقد نعتقد أنّ حلًّا يكمن في كتابة الكود التالي:

  let rec fib_memo3 =
    memo_fun (fun n -> if n <= 1 then n
                       else fib_memo3 (n-2) + fib_memo3 (n-1))

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

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

  let fib_memo4 =
    memo_rec (fun f n -> if n <= 1 then n else f (n-2) + f (n-1))

هنا، يضمن الاستدعاء الوحيد لـ memo_rec إنشاء جدول واحد. وتُمرَّر الدالة التي يُراد حفظها في صورة وسيط إضافي f.

وتُكتب الدالة memo_rec كما يلي. نبدأ، كما في حالة memo_fun، بإنشاء جدول:

  let memo_rec ff =
    let h = Hashtbl.create 5003 in

ثم نُعرّف الدالة التخصيصية f التي تُجري الحفظ:

    let rec f x =
      try Hashtbl.find h x
      with Not_found -> let v = ff f x in Hashtbl.add h x v; v
    in
    f

عندما لا تكون النتيجة في الجدول، نحسب النتيجة v باستخدام fffx، أي بتمرير الدالة f والوسيط x إلى الدالة ff التي يوفّرها المستخدم. ويرد الكود الكامل لـ memo_rec في البرنامج 86.

وكما في حالة memo_fun، فإنّ نوع memo_rec متعدّد الأشكال، لكنّه أكثر تعقيدًا:

memo_rec: ((’a -> ’b) -> ’a -> ’b) -> ’a -> ’b

نوع الدالة ff هو (’a->’b)->’a->’b، ويمكن قراءته على أنّه (’a->’b)->(’a->’b). أي أنّها تأخذ وسيطًا دالةً من النوع ’a->’b وتُعيد دالة من النوع نفسه.

11.3 الفروق بين الحفظ والبرمجة الديناميكية

في بعض الحالات، قد يُفضَّل اعتماد البرمجة الديناميكية على الحفظ. خُذ مثال حساب معاملات ذات الحدّين (binomial coefficients) C(n,k)، التي يكون تعريفها التخصيصي كما يلي:

$$\begin{cases} C(n,0) = 1 \\ C(n,n) = 1 \\ C(n,k) = C(n - 1,k - 1) + C(n - 1,k) & \text{إذا كان } 0 < k < n \end{cases}$$

يمكن تطبيق كلٍّ من الحفظ والبرمجة الديناميكية على هذا التعريف. في الحالة الأولى سيكون لدينا جدول تجزئة مفهرس بالزوج (n,k)، وفي الحالة الثانية مصفوفة (matrix) مفهرسة بـ n و k. غير أنّنا، إذا سعينا إلى حساب C(n,k) من أجل n = 2 × 105 و k = 105، فمن المرجّح أن نتجاوز الذاكرة المتاحة في الآلة (بافتراض حاسوب مكتبي عادي). وفي الحالة الأولى، سيحدث ذلك عند ملء جدول التجزئة، وفي الثانية عند محاولة تخصيص المصفوفة. والسبب هو أنّ التعقيد في الزمن وفي المساحة من الرتبة O(nk). وفي المثال السابق، سيتعيّن علينا تخزين 15 مليار نتيجة وسيطة على الأقل.

ومع ذلك، إذا نظرنا عن كثب، نجد أنّ حساب C(n,k) من أجل قيمة معطاة لـ n لا يتطلّب سوى قيم C(n− 1,k). وبناءً على ذلك، يمكننا إجراء الحساب من أجل قيم متزايدة لـ n، حتى وإن لم تكن جميع القيم المحسوبة مفيدة في النهاية. ويمكننا تصوّر الوضع برسم مثلث باسكال كما في الشكل 11.2. وسنحسب القيم سطرًا سطرًا، مع الاحتفاظ بسطر واحد فقط في أي لحظة.

الشكل 11.2: مثلث باسكال.

1
1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1
⋮

ولنُنفّذ هذه الفكرة في دالة comb_smart_dp. نبدأ بتخصيص مصفوفة row بحجم n+1 ستضمّ سطر مثلث باسكال الجاري حسابه:

  let comb_smart_dp n k =
    let row = Array.make (n+1) 0 in

في الواقع، تكفي مصفوفة بحجم k+1 (انظر التمرين 11.3).

في البداية، تُملأ هذه المصفوفة بالأصفار. ونُهيّئ الخلية الأولى بالقيمة 1.

    row.(0) <- 1;

لن تتغيّر هذه القيمة فيما يلي، لأنّ العمود الأول من مثلث باسكال لا يحتوي إلا على الآحاد. بعد ذلك، نكتب حلقة لحساب السطر i من مثلث باسكال:

    for i = 1 to n do

سيُجرى هذا الحساب في المكان نفسه داخل المصفوفة row، بافتراض أنّها تضمّ قيم السطر (i− 1). ولتجنّب طمس قيم لم تُستخدم بعد، سنحسب القيم الجديدة من اليمين إلى اليسار، لأنّ هذه القيم لا تعتمد على تلك الواقعة إلى أقصى اليمين. ونُتابع بحلقة ثانية:

      for j = i downto 1 do row.(j) <- row.(j) + row.(j-1) done

هنا نستفيد من كون row.(i) تحتوي على 0، ما يمكّننا من تجنّب إدخال حالة خاصة. ونتوقّف عندما j = 1 لأنّ القيمة row.(0) لا تحتاج إلى إعادة حساب، كما أوضحنا أعلاه. وبعد أن نخرج من الحلقة المزدوجة، تكون المصفوفة row قد أصبحت تضمّ السطر n من مثلث باسكال، ولم يتبقّ لنا إلا إعادة row.(k):

    done;
    row.(k)

يبقى التعقيد الزمني من الرتبة O(nk)، أمّا تعقيد المساحة فهو O(n) فقط. وفي المثال المعطى أعلاه، حيث n = 2 × 105 و k = 105، تُحصَّل النتيجة الآن في بضع ثوانٍ. ولاحظ، مع ذلك، أنّها تُسبّب طفحًا حسابيًّا (arithmetic overflow) (انظر التمرين 11.4).

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

11.4 التجزئة (hash-consing)

وكما يمكننا تجنّب حساب الشيء نفسه مرّتين، كما فعلنا أعلاه، يمكننا بالمثل تجنّب بناء البيانات نفسها عدّة مرّات، لتوفير الذاكرة. ويمكننا القيام بذلك بأمان ما دمنا نتعامل مع قيم لن تُعدَّل لاحقًا. فمثلًا، إذا كنا قد بنينا القائمة [1;2;3] بالفعل، فلا جدوى من إعادة بنائها من جديد. ويمكننا بدلًا من ذلك إعادة استخدامها.

وتُعرف تقنية إعادة استخدام القيم التي بُنيت بالفعل بـ التجزئة (hash-consing). وهي ببساطة تطبيق تقنية الحفظ على بناء القيم. ويجمع مصطلح التجزئة (hash-consing) على وجه التحديد فكرة التجزئة (hashing) المستخدمة في الحفظ مع فكرة التخصيص[^1]. وهنا سوف نوضّح كيفية تنفيذ هذه التقنية، متخذين مثالًا أشجارًا ثنائية تحتوي على محارف، أي:

  type tree = E | N of tree * char * tree

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

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

  type tree = E | N of int * tree * char * tree

وسنرى أدناه كيف يُحسب هذا العدد الصحيح. نكتب دالة تُعيد هذا العدد الصحيح عندما يُعطى الباني N، والعدد الصحيح 0 في غير ذلك.

  let unique = function
    | E -> 0
    | N (u, _, _, _) -> u

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

  let hash = function
    | E ->
        0
    | N (_, l, c, r) ->
        (19 * (19 * unique l + Char.code c) + unique r) land max_int

لا تستخدم هذه الدالة العدد الصحيح المخزَّن في الباني N. فدالة hash ستُستخدم تحديدًا لتحديد ما إذا كانت شجرة جذرها c وشجرتاها الفرعيتان l و r قد بُنيت بالفعل. لذا يجب ألّا تعتمد إلا على القيم l و c و r. ولحساب النتيجة في زمن ثابت، تستخدم دالة hash الأعداد الصحيحة المخزَّنة في الشجرتين الفرعيتين l و r، عبر دالة unique. وتُستخدم العملية landmax_int هنا لضمان نتيجة غير سالبة.

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

  let equal t1 t2 = match t1, t2 with
    | E, E -> true
    | N (_, l1, c1, r1), N (_, l2, c2, r2) ->
        l1 == l2 && c1 == c2 && r1 == r2
    | _ -> false

وبتزوّدنا بهاتين الدالتين، يمكننا الآن بناء جدول تجزئة لحفظ بناء الأشجار. ويمكننا فعل ذلك باستخدام الفونكتور (functor) Hashtbl.Make من المكتبة القياسية لـ OCaml. غير أنّ جدولًا كهذا سيحتفظ بالقيم المبنية إلى الأبد. أمّا ما نريده، في المقابل، فهو أن يتمكّن جامع القمامة (GC) من استعادة المساحة المخصَّصة لقيم لم تعد مستخدَمة، كما يفعل عادةً.

ولهذا، سنستخدم بنية جدول تجزئة أخرى مضمّنة في المكتبة القياسية لـ OCaml، ألا وهي الفونكتور Weak.Make. وتوقيعه مطابق لتوقيع الفونكتور Hashtbl.Make.

  module X = struct
    type t = tree
    let hash = ...
    let equal = ...
  end
  module W = Weak.Make(X)

توفّر الوحدة W الناتجة بنية مجموعة (set) من قيم النوع tree، تختفي عناصرها عندما لا يُشار إليها في أي مكان سوى بمؤشر من هذه البنية. وتُسمّى مؤشرات كهذه، التي لا يأخذها جامع القمامة في الحسبان، مراجع ضعيفة (weak references). ومن هنا اسم الوحدة: Weak.

ويمكننا الآن بناء الجدول الذي سيضمّ قيم النوع tree المبنية. ونهيّئه بحجم اعتباطي.

  let nodes = W.create 5003

ولم يتبقّ إلا كتابة الدالة node التي ستُجري الحفظ الفعلي. وهي تستخدم عدّادًا عامًّا، مهيّأً بالقيمة 1.

  let node =
    let cpt = ref 1 in
    fun l c r ->

نبدأ ببناء الشجرة المطلوبة، باستخدام القيمة الحالية للعدّاد.

      let n0 = N (!cpt, l, c, r) in

بعد ذلك نستشير جدول التجزئة لتحديد ما إذا كانت قيمة كهذه قد بُنيت بالفعل. وتوفّر الوحدة W بسهولة دالة merge تحدّد ما إذا كانت قيمة مماثلة موجودة بالفعل في المجموعة، وإن لم تكن، تضيفها. وفي كلتا الحالتين، تكون القيمة المُعادة محتواةً في الجدول.

      let n = W.merge nodes n0 in

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

      if n == n0 then incr cpt;
      n

ويرد الكود الكامل في البرنامج 87.

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

ومزايا التجزئة (hash-consing) عديدة. أولًا، تتيح لنا الاقتصاد في الذاكرة. صحيح أنّ ثمّة كلفة إضافية مرتبطة بالحفظ، لكنّ هذه الكلفة من الزمن الثابت. فقد حرصنا على كتابة دالة مساواة ودالة تجزئة بكلفة ثابتة. والميزة الثانية للتجزئة (hash-consing) هي أنّه يمكننا الآن استخدام المساواة الفيزيائية == بدلًا من المساواة البنيوية. فقيمتان من النوع tree متساويتان إذا وفقط إذا كانتا متساويتين فيزيائيًّا. وهذا مضمون بتغليف النوع tree خلف نوع خاص. وثالثًا، لدينا ترتيب كلّي على النوع tree، بكلفة ثابتة، بمقارنة القيم التي تُعيدها الدالة unique. وعلى وجه الخصوص، يمكننا الآن بناء بنى بيانات، مثلًا باستخدام الفونكتورين Set.Make أو Map.Make، تكون فعّالة كما في حالة الأعداد الصحيحة. وأخيرًا، لدينا دالة تجزئة ممتازة على النوع tree، ألا وهي الدالة unique. ويقترح التمرين 11.6 استخدامها لحفظ دالة تخصيصية على الأشجار.

ومن المهم أن نُكرّر هنا أنّ تقنية التجزئة (hash-consing) لا تنطبق إلا على البنى القابلة للمشاركة. وبالتالي، تنطبق التقنية على البنى الدائمة (persistent)، لا على البنى القابلة للتغيير (mutable).