يصف هذا المقال كيفية تحقيق برمجة متزامنة في جافا، إذ يُغطي مبادئ البرمجة المتوازية والثبات والخيوط وإطار العمل التنفيذي (تجمُعات الخيوط thread pools)، إلى جانب واجهات Futures وCompletableFuture القابلة للاستدعاء وإطار عمل fork-join.

التزامن

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

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

العملية Process مقابل الخيوط Threads

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

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

يعمل تطبيق جافا افتراضيًا ضمن عمليةٍ واحدةٍ، ولتحقيق عملية المعالجة المتوازية أو السلوك غير المتزامن؛ فيجب أن يعمل تطبيق الجافا ضمن عدة خيوط.

التحسينات والمشاكل المرافقة للتزامن

حدود مكاسب التزامن

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

يُمكن حساب الربح النظري باستخدام القاعدة التالية المُشار إليها بقانون Amdahl.

إذا كانت "F" هي النسبة المئوية لأجزاء البرنامج التي يُمكن أن تعمل على التوازي و"N" هو عدد العمليات، فإن ربح الأداء الأعظمي هو:

 1/(F+((1-F)/N))

مشاكل التزامن

تمتلك الخيوط مكدساتٍ خاصة بها، إلا أنها لا تستطيع الوصول إلى البيانات المُشاركة، ولذلك توجد مشكلتان مرتبطتان بالوصول ومجال الرؤية؛ حيث تظهر مشكلة مجال الرؤية عندما يقرأ الخيط "أ" البيانات المُشاركة التي يُغيرها الخيط "ب" فيما بعد، دون معرفة الخيط "أ" بهذا التغيير؛ بينما تظهر مشكلة الوصول عند محاولة عدة خيوطٍ الوصول وتغيير نفس البيانات المُشاركة في الوقت ذاته.

تؤدي مشكلتا الوصول ومجال الرؤية إلى:

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

التزامن في جافا

العمليات والخيوط

يعمل برنامج جافا افتراضيًا ضمن عمليةٍ خاصةٍ به وضمن خيطٍ واحد، حيث تُعد الخيوط جزءًا من لغة جافا وتتعامل جافا معها باستخدام الشيفرة البرمجية Thread، ويستطيع تطبيق جافا إنشاء خيوطٍ جديدةٍ باستخدام هذا الصنف، كما يوفِّر الإصدار 1.5 من جافا دعمًا متقدمًا للتزامن باستخدام حزمة java.util.concurrent.

الأقفال ومزامنة الخيوط

توفّر لغة جافا أقفالًا لحماية أجزاءٍ مُعينةٍ من الشيفرة البرمجية لتنفيذها من قِبل عدة خيوطٍ بنفس الوقت، والطريقة الأسهل لقفل طريقة method أو صنف Class جافا هي من خلال تعريف هذه الطريقة أو الصنف باستخدام الكلمة المفتاحية synchronized.

تضمن الكلمة المفتاحية synchronized في جافا ما يلي:

• إمكانية تنفيذ كتلةٍ من الشيفرة البرمجية في نفس الوقت من قِبل خيطٍ واحدٍ فقط.
• يستطيع أي خيطٍ الاطلاع على التعديلات السابقة للكتلة المتزامنة من الشيفرة البرمجية والمحمية بنفس القفل عند دخوله إليها.

عملية التزامن ضرورية لضمان الوصول الحصري والمتبادل إلى الكتل البرمجية وضمان اتصالٍ موثوقٍ بين الخيوط.

تستطيع استخدام الكلمة المفتاحية synchronized عند تعريف الطريقة لتضمن أن خيطًا واحدًا فقط يستطيع استخدام هذه الطريقة بنفس الوقت، وبالتالي عند محاولة خيطٍ آخر لاستخدام هذه الطريقة، فسوف ينتظر حتى ينتهي الخيط الأول من استخدام هذه الطريقة.

public synchronized void critial() {
    // some thread critical stuff
    // here
}

يمكن أيضًا استخدام الكلمة المفتاحية synchronized لحماية كتل من الشيفرة البرمجية ضمن الطريقة method، حيث تكون الكتلة محميةً بمفتاحٍ من الممكن أن يكون محرفًا أو كائنًا، ويُدعى هذا المفتاح بالقفل، حيث لا يُمكن للشيفرات البرمجية المحمية بنفس القفل الوصول إلا من قِبل خيطٍ واحدٍ بنفس الوقت، فعلى سبيل المثال تضمن هيكلية البيانات التالية وصول خيطٍ واحدٍ فقط إلى داخل كتلتي الطريقتين ()add و()next.

package de.vogella.pagerank.crawler;

import java.util.ArrayList;
import java.util.List;

/**
 * Data structure for a web crawler. Keeps track of the visited sites and keeps
 * a list of sites which needs still to be crawled.
 *
 * @author Lars Vogel
 *
 */
public class CrawledSites {
    private List<String> crawledSites = new ArrayList<String>();
    private List<String> linkedSites = new ArrayList<String>();

    public void add(String site) {
        synchronized (this) {
            if (!crawledSites.contains(site)) {
                linkedSites.add(site);
            }
        }
    }

    /**
     * Get next site to crawl. Can return null (if nothing to crawl)
     */
    public String next() {
        if (linkedSites.size() == 0) {
            return null;
        }
        synchronized (this) {
            // Need to check again if size has changed
            if (linkedSites.size() > 0) {
                String s = linkedSites.get(0);
                linkedSites.remove(0);
                crawledSites.add(s);
                return s;
            }
            return null;
        }
    }

}

الذاكرة المتطايرة

يضمن التصريح عن أي متحولٍ باستخدام الكلمة المفتاحية volatile قراءة الخيط لآخر قيمة مكتوبة في الحقل، حيث أن الكلمة المفتاحية volatile لا تُطبق أي قفلٍ على المتغير.

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

نموذج الذاكرة في جافا

يصف هذا النموذج عملية الاتصال بين ذاكرة الخيوط والذاكرة الرئيسية للتطبيق، فهو يُحدد شروط انتشار التغييرات في الذاكرة بين الخيوط، والحالات التي يُحدِث فيها الخيط ذاكرته الخاصة من الذاكرة الرئيسية، والعمليات الذرية وترتيب هذه العمليات.

العمليات الذرية

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

بفرض أنه قد صُرِّح عن المتغير i على أنه صحيح int، فسوف تكون الزيادة i++‎ عمليةً غير ذرية في جافا، وهذا ينطبق على القيم الرقمية الأخرى مثل long. تقرأ العملية i++‎ أولًا القيمة المُخزنة حاليًا في i (عمليةٌ ذريةٌ)، ثم تُضيف قيمة واحد لها (عمليةٌ ذريةٌ)، ولكن يُحتمل أن تتغير القيمة بين عمليتي الكتابة والقراءة.

توفّر لغة جافا بدءًا من الإصدار 1.5 متغيراتٍ ذريةٍ مثل AtomicInteger، أو AtomicLong، والتي توفّر توابعًا مثل:

• getAndDecrement()‎
• getAndIncrement()‎
• getAndSet()‎

وجميعها ذرية.

تحديثات الذاكرة في الشيفرة البرمجية المتزامنة

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

الثبات والنسخ الوقائية

الثبات

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

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

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

النسخ الوقائية

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

يُنشئ المثال التالي نسخةً من اللائحة ArrayList ويُعيد النسخة فقط وبالتالي لا يستطيع عميل هذا الصنف إزالة العناصر من اللائحة.

package de.vogella.performance.defensivecopy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class MyDataStructure {
    List<String> list = new ArrayList<String>();

    public void add(String s) {
        list.add(s);
    }

    /**
     * Makes a defensive copy of the List and return it
     * This way cannot modify the list itself
     *
     * @return List<String>
     */
    public List<String> getList() {
        return Collections.unmodifiableList(list);
    }
}

الخيوط في جافا

إن أساس التزامن في جافا هو الصنف java.lang.Threads، حيث يُنفّذ Thread كائنًا من النوع java.lang.Runnable، وتتضمن واجهة Runnable تعريفًا للطريقة ()run التي تُستدعى من قِبل الكائن Thread وتحتوي العمل الواجب تنفيذه، لذلك فإن Runnable هو مهمة يجب تنفيذها، أما Thread فهو العامل الذي يُنفذ هذه المهمة.

يوضح المثال التالي مهمة Runnable بحساب مجموع مجال مُعطى من الأرقام، لذا أنشِئ مشروع جافا وسمِّه de.vogella.concurrency.threads لهذا المثال.

package de.vogella.concurrency.threads;

/**
 * MyRunnable will count the sum of the number from 1 to the parameter
 * countUntil and then write the result to the console.
 * <p>
 * MyRunnable is the task which will be performed
 *
 * @author Lars Vogel
 *
 */
public class MyRunnable implements Runnable {
    private final long countUntil;

    MyRunnable(long countUntil) {
        this.countUntil = countUntil;
    }

    @Override
    public void run() {
        long sum = 0;
        for (long i = 1; i < countUntil; i++) {
            sum += i;
        }
        System.out.println(sum);
    }
}

يوضح المثال التالي استخدام صنفي Thread وRunnable.

package de.vogella.concurrency.threads;

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        // We will store the threads so that we can check if they are done
        List<Thread> threads = new ArrayList<Thread>();
        // We will create 500 threads
        for (int i = 0; i < 500; i++) {
            Runnable task = new MyRunnable(10000000L + i);
            Thread worker = new Thread(task);
            // We can set the name of the thread
            worker.setName(String.valueOf(i));
            // Start the thread, never call method run() direct
            worker.start();
            // Remember the thread for later usage
            threads.add(worker);
        }
        int running = 0;
        do {
            running = 0;
            for (Thread thread : threads) {
                if (thread.isAlive()) {
                    running++;
                }
            }
            System.out.println("We have " + running + " running threads. ");
        } while (running > 0);

    }
}

سلبيات الصنف Thread:

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

اقتباس

تُقدم حزمة java.util.concurrent دعمًا مُحسّنًا للتزامن مقابل الاستخدام المُباشر للخيوط، وهذه الحزمة مشروحة في القسم التالي.

تجمعات الخيوط Thread Pools مع الإطار المنفذ Executer Framework

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

يوفر الإطار المُنفذ مثالًا لتطبيق واجهة java.util.concurrent.Executor، مثل:

(Executor.newFixedThreadPool(int n

والذي سوف يُنشئ n خيط عامل، وتُضيف ExecutorService توابع دورة الحياة للمُنفذ، مما يسمح له بإطفاء المُنفذ وانتظار عملية الإغلاق.

اقتباس

إذا كنت تريد استخدام تجمع خيوط مع خيطٍ واحدٍ يُنفذ عدة كائنات Runnable، فتستطيع استخدام طريقة ()Executors.newSingleThreadExecutor.

أنشئ Runnable مرةً ثانية.

package de.vogella.concurrency.threadpools;

/**
 * MyRunnable will count the sum of the number from 1 to the parameter
 * countUntil and then write the result to the console.
 * <p>
 * MyRunnable is the task which will be performed
 *
 * @author Lars Vogel
 *
 */
public class MyRunnable implements Runnable {
    private final long countUntil;

    MyRunnable(long countUntil) {
        this.countUntil = countUntil;
    }

    @Override
    public void run() {
        long sum = 0;
        for (long i = 1; i < countUntil; i++) {
            sum += i;
        }
        System.out.println(sum);
    }
}

تستطيع الآن تشغيل كائنات Runnable باستخدام الإطار المُنفذ.

package de.vogella.concurrency.threadpools;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
    private static final int NTHREDS = 10;

    public static void main(String[] args) {
        ExecutorService executor = Executors.newFixedThreadPool(NTHREDS);
        for (int i = 0; i < 500; i++) {
            Runnable worker = new MyRunnable(10000000L + i);
            executor.execute(worker);
        }
        // This will make the executor accept no new threads
        // and finish all existing threads in the queue
        executor.shutdown();
        // Wait until all threads are finish
        executor.awaitTermination();
        System.out.println("Finished all threads");
    }
}

تستطيع استخدام صنف java.util.concurrent.Callable عند الحاجة لإعادة قيمةٍ معينة من الخيوط.

البرمجة غير المتزامنة

يُفضل تنفيذ أي عملية تستهلك وقتًا بصورةٍ غير متزامنة حيث توجد مقاربتان للتعامل مع المهام بصورةٍ غير متزامنة ضمن تطبيق جافا، وهما:

• حجب منطق التطبيق إلى حين إكمال المهمة.
• استدعاء منطق التطبيق حالما تكتمل المهمة وتُدعى هذه بالمقاربة دون إعاقة.

يدعم CompletableFuture وهو توسّع عن واجهة Future، الاستدعاءات غير المتزامنة، فهو يستعمل واجهة CompletionStage التي توفر توابعًا تسمح بربط الاستدعاءات التي سوف تُنفذ عند إكمالها، كما يُضيف تقنيات قياسية لتنفيذ شيفرة تطبيق برمجية عند إكمال مهمةٍ ما، وهذا يتضمن طرقًا متعددةً من أجل دمج المهام. يدعم CompletableFuture أيضًا المقاربتين بإعاقة ودون إعاقة، إضافةً إلى الاستدعاءات العادية. ويٌمكن تنفيذ الاستدعاء في خيطٍ آخر عند تنفيذ CompletableFuture في الخيط ذاته.

يُوضح المثال التالي كيفية إنشاء CompletableFuture أساسي.

CompletableFuture.supplyAsync(this::doSomething);

يُشغّل CompletableFuture.supplyAsync المهمة بصورةٍ غير متزامنة ضمن تجمُّع الخيط الافتراضية لجافا، ويكون الخيار مُتاحًا بالسماح للمنفذ المُخصص بتعريف ThreadPool.

package snippet;

import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;

public class CompletableFutureSimpleSnippet {
    public static void main(String[] args) {
        long started = System.currentTimeMillis();

        // configure CompletableFuture
        CompletableFuture<Integer> futureCount = createCompletableFuture();

            // continue to do other work
            System.out.println("Took " + (started - System.currentTimeMillis()) + " milliseconds" );

            // now its time to get the result
            try {
              int count = futureCount.get();
                System.out.println("CompletableFuture took " + (started - System.currentTimeMillis()) + " milliseconds" );

               System.out.println("Result " + count);
             } catch (InterruptedException | ExecutionException ex) {
                // Exceptions from the future should be handled here
            }
    }

    private static CompletableFuture<Integer> createCompletableFuture() {
        CompletableFuture<Integer> futureCount = CompletableFuture.supplyAsync(
                () -> {
                    try {
                        // simulate long running task
                        Thread.sleep(5000);
                    } catch (InterruptedException e) { }
                    return 20;
                });
        return futureCount;
    }

}

يُمكن استخدام thenApply لتعريف استدعاء يُنفذ حالما ينتهي CompletableFuture.supplyAsync، ويوضح المثال التالي استخدام طريقة thenApply.

package snippet;

import java.util.concurrent.CompletableFuture;
import java.util.concurrent.ExecutionException;

public class CompletableFutureCallback {
    public static void main(String[] args) {
        long started = System.currentTimeMillis();

        CompletableFuture<String>  data = createCompletableFuture()
                .thenApply((Integer count) -> {
                    int transformedValue = count * 10;
                    return transformedValue;
                }).thenApply(transformed -> "Finally creates a string: " + transformed);

            try {
                System.out.println(data.get());
            } catch (InterruptedException | ExecutionException e) {

            }
    }

    public static CompletableFuture<Integer> createCompletableFuture() {
        CompletableFuture<Integer>  result = CompletableFuture.supplyAsync(() -> {
            try {
                // simulate long running task
                Thread.sleep(5000);
            } catch (InterruptedException e) { }
            return 20;
        });
        return result;
    }

}

تستطيع أيضًا تشغيل CompletableFuture مُؤخر بدءًا من الإصدار 9 لجافا.

CompletableFuture<Integer> future = new CompletableFuture<>();
 future.completeAsync(() -> {
       System.out.println("inside future: processing data...");
       return 1;
 }, CompletableFuture.delayedExecutor(3, TimeUnit.SECONDS))
 .thenAccept(result -> System.out.println("accept: " + result));

خوارزميات دون إعاقة

يوفر الإصدار 5.0 لجافا دعمًا لعملياتٍ ذريةٍ إضافية، وهذا يسمح بتطوير خوارزميات دون إعاقة لا تتطلب تزامنًا، ولكن تعتمد على تعليمات عتاد صلب ذري منخفضة المستوى مثل الموازنة والتبديل compare-and-swap أو اختصارًا CAS، حيث تتحقق عمليتا الموازنة والتبديل فيما إذا كان المتغير يحتوي على قيمةٍ ما، وفي حال احتوائه على تلك القيمة سوف تُنفذ العملية.

تكون الخوارزميات دون إعاقة عادةً أسرع من خوارزميات الإعاقة لأن تزامن الخيوط يظهر في مستويات أدنى (عتاد صلب).

يُنشئ المثال التالي عدّادا دون إعاقة يزداد باستمرار، وهذا المثال موجود ضمن مشروع project يُدعى:
 

 de.volgella.concurrency.nonblocking.counter.

package de.vogella.concurrency.nonblocking.counter;

import java.util.concurrent.atomic.AtomicInteger;

public class Counter {
    private AtomicInteger value = new AtomicInteger();
    public int getValue(){
        return value.get();
    }
    public int increment(){
        return value.incrementAndGet();
    }

    // Alternative implementation as increment but just make the
    // implementation explicit
    public int incrementLongVersion(){
        int oldValue = value.get();
        while (!value.compareAndSet(oldValue, oldValue+1)){
             oldValue = value.get();
        }
        return oldValue+1;
    }

}

واختبارًا.

package de.vogella.concurrency.nonblocking.counter;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Test {
        private static final int NTHREDS = 10;

        public static void main(String[] args) {
            final Counter counter = new Counter();
            List<Future<Integer>> list = new ArrayList<Future<Integer>>();

            ExecutorService executor = Executors.newFixedThreadPool(NTHREDS);
            for (int i = 0; i < 500; i++) {
                Callable<Integer> worker = new  Callable<Integer>() {
                    @Override
                    public Integer call() throws Exception {
                        int number = counter.increment();
                        System.out.println(number );
                        return number ;
                    }
                };
                Future<Integer> submit= executor.submit(worker);
                list.add(submit);

            }


            // This will make the executor accept no new threads
            // and finish all existing threads in the queue
            executor.shutdown();
            // Wait until all threads are finish
            while (!executor.isTerminated()) {
            }
            Set<Integer> set = new HashSet<Integer>();
            for (Future<Integer> future : list) {
                try {
                    set.add(future.get());
                } catch (InterruptedException e) {
                    e.printStackTrace();
                } catch (ExecutionException e) {
                    e.printStackTrace();
                }
            }
            if (list.size()!=set.size()){
                throw new RuntimeException("Double-entries!!!");
            }

        }


}

إن الجزء المثير للاهتمام هو كيفية تنفيذ طريقة ()incrementAndGet، فهي تستخدم عملية CAS.

public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
    }

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

إطار عمل Fork-Join ضمن جافا 7

طرح الإصدار 7 من جافا آليةً جديدةً تفرعيةً لتنفيذ المهمات المكثفة، وأُطلق الاسم fork-join على إطار العمل التابع لها، حيث يسمح إطار العمل هذا على توزيع مهمةٍ ما على عدة عاملين ثم انتظار النتيجة.

اقتباس

يمكن تنزيل الحزمة jsr166y للإصدار 6 لجافا.

أنشئ المشروع de.vogella.performance.forkjoin لتجريبها، وإن كنت تستخدم نسخةً مختلفةً عن جافا 7، فعليك إضافة jsr166y.jar إلى مسار الأصناف.

أنشئ أولًا الحزمة algorithm ثم الصنف التالي.

package algorithm;

import java.util.Random;

/**
 *
 * This class defines a long list of integers which defines the problem we will
 * later try to solve
 *
 */
public class Problem {
    private final int[] list = new int[2000000];

    public Problem() {
        Random generator = new Random(19580427);
        for (int i = 0; i < list.length; i++) {
            list[i] = generator.nextInt(500000);
        }
    }

    public int[] getList() {
        return list;
    }

}

بعد ذلك عرّف الصنف Solver كما هو موضح في المثال التالي.

package algorithm;

import java.util.Arrays;

import jsr166y.forkjoin.RecursiveAction;

public class Solver extends RecursiveAction {
    private int[] list;
    public long result;

    public Solver(int[] array) {
        this.list = array;
    }

    @Override
    protected void compute() {
        if (list.length == 1) {
            result = list[0];
        } else {
            int midpoint = list.length / 2;
            int[] l1 = Arrays.copyOfRange(list, 0, midpoint);
            int[] l2 = Arrays.copyOfRange(list, midpoint, list.length);
            Solver s1 = new Solver(l1);
            Solver s2 = new Solver(l2);
            forkJoin(s1, s2);
            result = s1.result + s2.result;
        }
    }
}

الآن عرّف صنفًا بسيطًا للتجريب وسمِّه Test.

package testing;

import jsr166y.forkjoin.ForkJoinExecutor;
import jsr166y.forkjoin.ForkJoinPool;
import algorithm.Problem;
import algorithm.Solver;

public class Test {

    public static void main(String[] args) {
        Problem test = new Problem();
        // check the number of available processors
        int nThreads = Runtime.getRuntime().availableProcessors();
        System.out.println(nThreads);
        Solver mfj = new Solver(test.getList());
        ForkJoinExecutor pool = new ForkJoinPool(nThreads);
        pool.invoke(mfj);
        long result = mfj.getResult();
        System.out.println("Done. Result: " + result);
        long sum = 0;
        // check if the result was ok
        for (int i = 0; i < test.getList().length; i++) {
            sum += test.getList()[i];
        }
        System.out.println("Done. Result: " + sum);
    }
}

التوقف التام أو الجمود Deadlock

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

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

ترجمة -وبتصرّف- للمقال Java concurrency (multi-threading) - Tutorial لصاحبه Lars Vogel.

اقرأ أيضًا

• الأحداث غير المتزامنة: حلقات الجس Polling Loops والمقاطعات Interrupts في المعالج
• الدليل السريع للغة البرمجة Java
• الأصناف المتداخلة Nested Classes في جافا
• المتغيرات والأنواع البسيطة في لغة جافا

تَعرَّضنا بالقسم الفرعي 3.8.5 للمصفوفات ثنائية البعد (two-dimensional arrays)، ولكننا لم نَستخدِمها بالقدر الكافي منذ ذلك الحين. تَملُك المصفوفات ثنائية البعد نوعًا أيضًا مثل int[][]‎ أو String[][]‎ بزوجين من الأقواس المربعة. تُرتَّب عناصر المصفوفات ثنائية البعد ضِمْن مجموعة من الصفوف والأعمدة بحيث يُخصِّص العامل new كُلًا من عدد تلك الصفوف والأعمدة كالتالي:

int[][] A;
A = new int[3][4];

تُنشِئ تلك التَعليمَة مصفوفة ثنائية البعد مُكوَّنة من 12 عنصر مُرتَّبين ضِمْن 3 صفوف و 4 أعمدة. يَتَوفَّر أيضًا مُهيِئ (initializers) للمصفوفات ثنائية البعد. فمثلًا، تُنشِئ التَعْليمَة التالية مصفوفة 3x4:

int[][]  A  =  {  {  1,  0, 12, -1 },
                  {  7, -3,  2,  5 },
                  { -5, -2,  2, -9 }
               };

يَتَكوَّن مُهيِئ المصفوفات ثنائية البعد من عدة صفوف مفصولة بفواصل (comma) ومُضمَّنة داخل أقواس. بالمثل، كل صف عبارة عن قائمة من القيم مفصولة بفواصل ومُضمَّنة داخل أقواس. إلى جانب ذلك، تَتَوفَّر قيم مُصنَّفة النوع (literals) لتَمثيِل المصفوفات ثنائية البعد لها نفس قواعد الصيغة (syntax)، ويُمكِن اِستخدَامها بأي مكان وليس فقط تَعْليمَات التّصرِيح (declarations). اُنظر المثال التالي:

A  =  new int[][] {  {  1,  0, 12, -1 },
                     {  7, -3,  2,  5 },
                     { -5, -2,  2, -9 }
                  };

في الواقع، يُمكِنك أن تُطبِق نفس الأمر على المصفوفات ثلاثية البعد ورباعية البعد..إلخ، ولكنها غَيْر شائعة الاِستخدَام في العموم.

حقيقة المصفوفات ثنائية البعد (two-dimensional arrays)

قبل أن نتعمق أكثر من ذلك، هنالك مفاجأة صغيرة! لا تَملُك الجافا مصفوفات ثنائية البعد (two-dimensional arrays) بصورة فعلية. تَحتلّ العناصر بمصفوفة فعلية ثنائية البُعد مَواضِعًا مُتصِلة من الذاكرة، ولكن هذا ليس صحيحًا بالجافا. في الحقيقة، تَكشِف الصيغة (syntax) المُستخدَمة لتمثيل أنواع المصفوفة ذلك: بِفرض وجود النوع BaseType، ينبغي إذًا أن نَكُون قادرين على إنشاء النوع BaseType[]‎، وهو ما يَعنِي "مصفوفة من النوع BaseType". إذا اِستخدَمنا النوع int[]‎ ذاته كنوع أساسي للمصفوفة، فإننا نَحصُل على النوع int[][]‎ الذي يُمثِل "مصفوفة من النوع int[]‎" أو "مصفوفة من مصفوفة من النوع int ". بمصفوفة ثنائية البعد من النوع int[][]‎، تَكُون العناصر نفسها مُتْغيِّرات من النوع int[]‎. ولمّا كان أي مُتْغيِّر من النوع int[]‎ بدوره قادرًا على حَمْل مؤشر (pointer) إلى مصفوفة من النوع int. يُمكِننا إذًا أن نقول أن أي مصفوفة ثنائية البعد هي في الواقع عبارة عن مصفوفة من المؤشرات (pointers) بحيث يُشيِر كل مؤشر منها بدوره إلى مصفوفة أحادية البعد (one-dimensional array). تُمثِل المصفوفات أحادية البعد إذًا صفوفًا (rows) ضِمْن المصفوفة ثنائية البعد (two-dimensional). تُبيِّن الصورة التالية مصفوفة مُكوَّنة من 3 صفوف و 4 أعمدة:

غالبًا ما نتجاهل تلك الحقيقة، ونُفكِر بالمصفوفة ثنائية البعد كما لو كانت شبكة (grid). ولكننا سنحتاج أحيانًا لأن نتذكَّر أن كل صف ضِمْن تلك الشبكة هو مصفوفة بحد ذاته. يُمكننا في الواقع أن نُشيِر إلى تلك المصفوفات باِستخدَام A[0]‎ و A[1]‎ و A[2]‎ أي أن كل صف هو قيمة من النوع int[]‎ يُمكِننا أن نُمرِّرها حتى إلى برنامج فرعي (subroutine) يَستقبِل مُعاملًا (parameter) من النوع int[]‎ على سبيل المثال.

يترتَّب على التفكير بمصفوفة ثنائية البعد A على أنها مصفوفة من المصفوفات عدة نتائج: أولًا، يُساوِي A.length عدد الصفوف (rows) ضِمْن المصفوفة، وهو ما يَتضِح معناه عند التفكير بها بتلك الطريقة. ثانيًا، إذا كانت A تَملُك الشكل المعتاد للمصفوفات ثنائية البعد، فسيَكُون عدد الأعمدة بالمصفوفة A هو نفسه عدد العناصر بالصف الأول أي A[0].length. لاحِظ مع ذلك أنه لا توجد قاعدة تَنصّ على ضرورة أن تَكُون جميع الصفوف ضِمْن مصفوفة ثنائية البعد بنفس الطول حيث يُعدّ كل صف بمثابة مصفوفة مُنفصِلة أحادية البعد، ويُمكِن لها إذًا أن تَملٌك طولًا مختلفًا. في الواقع، قد يَكُون صف معين ضِمْن مصفوفة فارغًا (null). اُنظر التَعْليمَة التالية على سبيل المثال:

A = new int[3][];

لا يَتَضمَّن التعريف السابق عددًا داخل الأقواس الثانية، ولهذا فإنه يُنشِئ مصفوفة مُكوَّنة من ثلاثة عناصر جميعها فارغة (null) أي أنه يُوفِّر مساحة لثلاثة صفوف (rows)، ولكنه لا يُنشِئ تلك الصفوف بشكل فعليّ. يُمكِنك أن تُنشِئ الصفوف A[0]‎ و A[1]‎ و A[2]‎ بشكل منفصل.

كمثال آخر، لنُفكِر بمصفوفة مُتماثِلة M -المصفوفة المتماثلة (symmetric) عبارة عن مصفوفة ثنائية البعد يَتساوَى عدد صفوفها مع عدد أعمدتها كما تَتَساوَى قيم M[j]‎ و M[j]‎ لجميع قيم i و j-، نحتاج لتَخْزِين قيم M[j]‎ التي تُحقِّق الشَّرط i >= j أي يُمكِننا أن نُخزِّن البيانات بمصفوفة مُثلثة (triangular array) كالتالي:

يُمكِننا أن نُنشِئ مصفوفة مثلثية (triangular array) إذا أنشأنا كل صف على حدى. تُنشِئ الشيفرة التالية مصفوفة مثلثية 7x7 من النوع double:

double[][] matrix = new double[7][]; // لم ننشئ الصفوف بعد
for (int i = 0; i < 7; i++) {
    // ‫انشئ الصف i بحيث يحتوي على i+1 من العناصر
    matrix[i] = new double[i+1];  
}

إذا أردنا أن نَجلب قيمة matrix بالمَوضِع (i,j)، وكان i < j، فإنه ينبغي أن نَجلب قيمة matrix[j]‎، ويَنطبِق الأمر نفسه على ضَبْط قيم تلك المصفوفة. تُعرِّف الشيفرة التالية صَنْفًا لتمثيل المصفوفات المُتماثِلة (symmetric matrices):

public class SymmetricMatrix {

    private double[][] matrix;  // مصفوفة مثلثية لحمل البيانات

    public SymmetricMatrix(int n) {
        matrix = new double[n][];
        for (int i = 0; i < n; i++)
            matrix[i] = new double[i+1];
    }

    public double get( int row, int col ) {
        if (row >= col)
            return matrix[row][col];
        else
            return matrix[col][row];
    }

    public void set( int row, int col, double value ) {
        if (row >= col)
            matrix[row][col] = value;
        else
            matrix[col][row] = value;
    }

    public int size() {
        return matrix.length;  // يمثل عدد الصفوف
    }

} // end class SymmetricMatrix

يُمكِنك أن تجد تعريف الصَنْف بالأعلى داخل الملف SymmetricMatrix.java كما يَحتوِي الملف TestSymmetricMatrix.java على برنامج صغير لاختبار الصَنْف.

بالمناسبة، لا تستطيع الدالة (function) القياسية Arrays.copyOf()‎ أن تُنشِئ نسخة كاملة من مصفوفة ثنائية البعد (2d array) ضِمْن خطوة واحدة، وإنما ينبغي أن تَفعَل ذلك لكل صف (row) ضِمْن المصفوفة على حدى. نستطيع إذًا كتابة الشيفرة التالية لنسخ مصفوفة ثنائية البعد من الأعداد الصحيحة:

int[][] B = new int[A.length][];  // ‫B و A لديهم نفس عدد الصفوف
for (int i = 0; i < A.length; i++) {
    B[i] = Arrays.copyOf(A[i], A[i].length)); // ‫انسخ الصف i
}

لعبة الحياة (Game of Life)

كمثال آخر على معالجة المصفوفات ثنائية البعد، سنَفْحَص مثال مشهور آخر: لعبة الحياة (Game of Life) الذي اخترعها عالم الرياضيات جون هورتون كونواي (John Horton Conway) بعام 1970. لا تُعدّ لعبة الحياة (Game of Life) لعبة بحق، فهي تُمثِل آلة أوتوماتيكية ثنائية البعد. يَعنِي ذلك أنها مُكوَّنة من شبكة (grid) من الخلايا (cells) تَتَغيَّر محتوياتها بمرور الوقت وفقًا لقواعد محدَّدة. يُمكِن لأي خلية أن تَكُون بحالة من اثنين: "حية (alive)" أو "ميتة (dead)". سنَستخدِم مصفوفة ثنائية البعد لتَمثيِل تلك الشبكة بحيث يُمثِل كل عنصر بالمصفوفة حالة خلية واحدة ضِمْن الشبكة. ستُهيِئ اللعبة شبكة (grid) مبدئية بحيث تَكُون جميع خلاياها إما "حية" أو "ميتة". بَعْد ذلك، ستتطوَّر الشبكة وفقًا لسِلسِلة من الخطوات. ستُحدَّد حالة خلايا الشبكة بكل خطوة وفقًا لحالة خلاياها بالخطوة السابقة ووفقًا لعدد من القواعد البسيطة: ستَفحَص كل خلية بالشبكة الخلايا المجاورة لها (أفقيًا ورأسيًا وقطريًا)، وتَحسِب عدد الخلايا الحية ثم تُحدَّد حالة الخلية بالخطوة التالية وفقًا للقواعد التالية:

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

تُظهِر الصورة التالية شكل شبكة الخلايا قَبْل تطبيق قواعد اللعبة وبَعْدها. تُطبَق القواعد على كل خلية بالشبكة، وتُبيِّن الصورة كيفية تطبيقها على أربعة خلايا:

تُعدّ لعبة الحياة (Game of Life) شيقة حيث تَعرِض الكثير من الأنماط المفاجئة (اُنظر بصفحة ويكيبيديا الخاصة باللعبة). نحن هنا مُهتمين فقط بكتابة برنامج لمحاكاة تلك اللعبة. يُمكِنك أن تَطلِع على شيفرة البرنامج بالكامل بالملف Life.java. تَظهَر رقعة الحياة كشبكة من المربعات بحيث تَكون المربعات الميتة سوداء اللون أما المربعات الحية فتَكُون بيضاء اللون. (سيَستخدِم البرنامج الصنف MosaicCanvas.java من القسم 4.7 لتَمثيِل تلك الشبكة، لذلك ستحتاج إلى إضافة ذلك الملف لتَصرِيف [compile] البرنامج وتَشْغِيله). يُمكِننا أن نملئ رقعة الحياة بخلايا حية وميتة عشوائيًا أو قد نَستخدِم الفأرة لضَبطها. يُوفِّر البرنامج الزر "Step" المسئول عن تحديد حالة الشبكة بَعْد خطوة واحدة فقط" بالإضافة إلى الزر "Start" المسئول عن تَشْغِيل تلك الخطوات بهيئة تحريكة (animation).

سنَفْحَص العمليات المُتعلِقة بمعالجة المصفوفات (array processing) اللازمة لتّنفِيذ برنامج لعبة الحياة (Game of Life). أولًا، يُمكِن لأي خلية أن تَكُون حية أو ميتة، لذلك سنَستخدِم بطبيعة الحال مصفوفة ثنائية البعد من النوع boolean[][]‎ لتمثيل حالة جميع الخلايا، وليَكُن اسم تلك المصفوفة هو alive. ستُساوِي قيمة أي عنصر alive[r][c]‎ القيمة true إذا كانت الخلية برقم الصف r ورقم العمود c حية. سنَستخدِم أيضًا نفس قيمة الثابت GRID_SIZE لتمثيل عدد الصفوف والأعمدة بتلك المصفوفة. يُمكِننا إذًا أن نَستخدِم حَلْقة التَكْرار for المُتداخلة (nested) التالية لمَلْئ قيم تلك المصفوفة المُمثِلة لشبكة الحياة بقيم عشوائية:

for (int r = 0; r < GRID_SIZE; r++) {
    for (int c = 0; c < GRID_SIZE; c++) {
        // ‫اضبط الخلية لتكون حية بنسبة احتمال تساوي 25%
        alive[r][c] = (Math.random() < 0.25);
    }
}

يُعيد التعبير Math.random() < 0.25 القيمة true أو false، والتي يُمكِننا أن نُسنِدها (assign) إلى عنصر مصفوفة من النوع boolean. سنَستخدِم تلك المصفوفة لضَبْط لون كل خلية بالشاشة. نظرًا لأننا سنَرسِم شبكة الخلايا على شاشة من الصَنْف MosaicCanvas، فإننا سنَستخدِم واجهة برمجة التطبيقات (ِAPI) الخاصة بذلك الصنف لضَبْط ألوانها. ونظرًا لأن الصَنْف MosaicCanvas هو المسئول عن الرسم الفعليّ، سيَكُون برنامج لعبة الحياة مسئولًا فقط عن ضَبْط الألوان باِستخدَام واجهة برمجة التطبيقات الخاصة بالصَنْف. سنُعرِّف ذلك بتابع اسمه showBoard()‎، والذي ينبغي أن يُستدعَى بكل مرة تَتَغيَّر فيها رقعة الحياة. سنَستخدِم مجددًا حَلْقة تَكْرار for مُتداخِلة لضَبْط لون كل مربع بالشبكة كالتالي:

for (int r = 0; r < GRID_SIZE; r++) {
    for (int c = 0; c < GRID_SIZE; c++) {
        if (alive[r][c])
            display.setColor(r,c,Color.WHITE);
        else
            display.setColor(r,c,null);  // اعرض لون الخلفية بالأسود
    }
}

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

let newboard be a new boolean[][] array
for each row r:
    for each column c:
        Let N be the number of neighbors of cell (r,c) in the alive array
        if ((N is 3) or (N is 2 and alive[r][c]))
            newboard[r][c] = true;
        else
            newboard[r][c] = false;
alive = newboard

سيُشيِر alive عند انتهاء المعالجة إلى مصفوفة جديدة، وهو أمر لا ينبغي أن نقلق بشأنه طالما كانت محتويات المصفوفة الجديدة مُمثِلة للحالة الجديدة لشبكة الخلايا أما المصفوفة القديمة فسيُحرِّرها كانس المُهملات (garabage collector). قد لا يَكون اختبار ما إذا كان newboard[r][c]‎ مُتحقِقًا أم لا واضحًا بما فيه الكفاية، ولكنه يُنفِّذ القواعد بشكل سليم. سنحتاج أيضًا لحِسَاب عدد الخلايا المجاورة. إذا كان لدينا خلية بالصف r والعمود c، ولم تَكُن تلك الخلية واقعة على حافة الرقعة، فإن الخلايا المجاورة لتلك الخلية هي كالتالي:

لاحِظ أن رقم الصف فوق الصف r يُساوِي r-1 أما الصف أسفله فهو r+1. يَنطبِق نفس الأمر على الأعمدة. ينبغي إذًا أن نَفْحَص القيم alive[r-1][c-1]‎ و alive[r-1][c]‎ و alive[r-1][c+1]‎ و alive[r][c-1]‎ و alive[r][c+1]‎ و alive[r+1][c-1]‎ و alive[r+1][c]‎ و alive[r+1][c+1]‎، ونَعِد منها تلكم المُحتوية على القيمة true. اِحرِص على فهم كيفية عمل فهارس المصفوفة.

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

if (r-1 >= 0 && c-1 >= 0 && alive[r-1][c-1])
    N++; // ‫خلية بالموضع (r-1,c-1) موجودة وحية
if (r-1 >= 0 && alive[r-1][c])
    N++; // خلية بالموضع‫ (r-1,c) موجودة وحية
if (r-1 >= 0 && c+1 <= GRID_SIZE && alive[r-1][c+1])
    N++; // ‫خلية بالموضع (r-1,c+1) موجودة وحية
// إلخ

سنتجنَّب بذلك كل الاعتراضات (exceptions). اِستخدَمنا في الواقع حلًا آخر شائع الاِستخدَام بألعاب الحاسوب ثنائية البعد. سنَتَظاهَر كما لو أن الحافة اليسرى للرقعة مُرتبطِة بالحافة اليمنى وكما لو أن الحافة العلوية مُرتبطِة بالحافة السفلية. بالنسبة لخلية برقم الصف 0 على سبيل المثال، فإن الصف أعلاها هو الصف الأخير أي بالرقم GRID_SIZE-1. سنَستخدِم أيضًا مُتْغيِّرات لتمثيل المَواضِع above و below و left و right الخاصة بخلية معينة. اُنظر شيفرة التابع المسئولة عن حساب الحالة الجديدة للرقعة، والتي ستَجِد أنها أبسط كثيرًا:

private void doFrame() { // احسب الحالة الجديدة لرقعة لعبة الحياة
    boolean[][] newboard = new boolean[GRID_SIZE][GRID_SIZE];
    for ( int r = 0; r < GRID_SIZE; r++ ) {
        // ‫تعد الصفوف أعلى وأسفل الصف r
        int above, below; 
        // ‫تعد الأعمدة على يمين ويسار العمود c
        int left, right;  
        above = r > 0 ? r-1 : GRID_SIZE-1;  // (for "?:" see Subsection 2.5.5)
        below = r < GRID_SIZE-1 ? r+1 : 0;
        for ( int c = 0; c < GRID_SIZE; c++ ) {
            left =  c > 0 ? c-1 : GRID_SIZE-1;
            right = c < GRID_SIZE-1 ? c+1 : 0;
            int n = 0; // عدد الخلايا الحية المجاورة
            if (alive[above][left])
                n++;
            if (alive[above][c])
                n++;
            if (alive[above][right])
                n++;
            if (alive[r][left])
                n++;
            if (alive[r][right])
                n++;
            if (alive[below][left])
                n++;
            if (alive[below][c])
                n++;
            if (alive[below][right])
                n++;
            if (n == 3 || (alive[r][c] && n == 2))
                newboard[r][c] = true;
            else
                newboard[r][c] = false;
        }
    }
    alive = newboard;
}

يُمكِنك الإطلاع على شيفرة البرنامج بالملف Life.java، وأن تُجرِبه. لا تنسى أنك ستحتاج إلى اِستخدَام الملف MosaicCanvas.java أيضًا.

لعبة داما (Checkers)

سنَفْحَص الآن مثالًا أكثر واقعية لاستخدام المصفوفات ثنائية البعد. يُعدّ هذا البرنامج هو الأطول حتى الآن حيث يَتَكوَّن من 745 سطر. يَسمَح ذلك البرنامج للمُستخدمين بلعب مباراة داما (checkers). تتكوَّن لعبة الداما من رقعة مُكوَّنة من 8 صفوف و8 أعمدة. سنعتمد على المثال الذي كتبناه بالقسم الفرعي 6.5.1. سنُسمِي اللاعبين بأسماء "أحمر" و "أسود" وفقًا للون قطع الداما الخاصة بهما. لن نشرح قواعد لعبة الداما هنا، ولربما تستطيع أن تتعلَّمها بينما تُجرِّب البرنامج.

يستطيع اللاعب أن يَتحرَك بالنَقْر على القطعة التي يريد أن يُحرِكها ثُمَّ بالنَقْر على المربع الفارغ الذي يريد أن يَنقِل إليه تلك القطعة. سيَرسِم البرنامج بأي لحظة إطارًا حول المربعات التي يستطيع اللاعب أن يَنقُر عليها بلون أفتح قليلًا كنوع من المساعدة. على سبيل المثال، سيُحَاط المربع المُتضمِّن للقطعة التي اختارها المُستخدِم للحركة بإطار أصفر اللون بينما ستُحَاط القطع الآخرى التي بإمكانه تَحرِيكها بإطار أزرق سماوي. إذا كان المُستخدِم قد اختار قطعة بالفعل لتَحرِيكها، فستُحَاط جميع المربعات الفارغة التي يستطيع أن يُحرِك إليها تلك القطعة بإطار أخضر اللون. ستَتبِع اللعبة قاعدة تَنُص على أنه إذا كان اللاعب الحالي قادرًا على القفز (jump) على إحدى قطع الخصم، فإنه لابُدّ أن يَقفِز. عندما تُصبِح إحدى القطع "قطعة ملك" أي بَعْد وصولها إلى الحافة الأخرى من الرقعة، سيَرسِم البرنامج حرف "K" أبيض كبير على تلك القطعة. تَعرِض الصورة التالية لقطة شاشة مبكرة من اللعبة، والتي تُظهِر اللاعب الأسود وقد اختار القطعة الموجودة بالمربع ذو الإطار الأصفر للحركة. يستطيع اللاعب الآن أن يَنقُر على إحدى المربعات المُحاطَة بإطار أخضر لكي يُكمِل تلك الحركة أو قد يَنقُر على إحدى المربعات المُحاطَة بإطار أزرق سماوي ليختار قطعة آخرى لتَحرِيكها.

سنَمُر عبر جزءًا من شيفرة ذلك المثال، ولكن يُمكِنك الاطلاع على الشيفرة بالكامل بالملف Checkers.java. قد يَكُون البرنامج طويلا ومعقدًا، ولكنه بقليل من الدراسة، ستَتَمكَّن من فهم جميع التقنيات المُستخدَمة به. يُعدّ البرنامج مثالًا جيدًا على البرمجة كائنية التوجه (object-oriented) المُعتمدِة على كُلًا من الأحداث (event-driven) والحالات (state-based).

سنُخزِّن بيانات قطع الرقعة بمصفوفة ثنائية البعد (two-dimensional array). نظرًا لأن البرنامج مُعقَد نوعًا ما، سنُقسِّمه إلى عدة أصناف. إلى جانب الصَنْف الأساسي، سنُعرِّف بعض الأصناف المُتداخِلة (nested) الآخرى منها الصَنْف CheckersData المُستخدَم لمعالجة بيانات الرقعة. لا يُعدّ ذلك الصَنْف مسئولًا مباشرًا عن أي جزء من الرسوم (graphics) أو مُعالجة الأحداث (event-handling)، ولكنه يُوفِّر التوابع (methods) التي يُمكِننا أن نستدعيها بأصناف آخرى لأغراض معالجة الرسوم والأحداث (events). سنناقش ذلك الصَنْف قليلًا.

يَحتوِي الصَنْف CheckersData على مُتْغيِّر نُسخة (instance variables) اسمه هو board من النوع int[][]‎‎. تُضبَط قيمة ذلك المُتْغيِّر إلى new int[8][8]‎ لتُمثِل شبكة 8x8 من الأعداد الصحيحة (integers). تُستخدَم ثوابت (constants) لتعريف القيم المُحتمَل تَخْزِينها بمربع برقعة شطرنج (checkboard):

static final int
          EMPTY = 0,           // يمثل مربعًا فارغًا
          RED = 1,             // قطعة حمراء عادية
          RED_KING = 2,        // قطعة ملك حمراء
          BLACK = 3,           // قطعة سوداء عادية
          BLACK_KING = 4;      // قطعة ملك سوداء

سنَستخدِم أيضًا الثابتين RED و BLACK بالبرنامج لتَمثيِل لاعبي المباراة. عندما تبدأ المباراة، ستُضبَط قيم المصفوفة لتمثيل الحالة المبدئية للرقعة، وستبدو كالتالي:

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

لابُدّ أن ينتبه الصَنْف CheckersData لأي تَغييرات ينبغي إجراؤها على هياكل البيانات (data structures) عندما يُحرِك أحد اللاعبين قطعة معينة بالرقعة. في الواقع، يُعرِّف الصَنْف تابع النسخة makeMove()‎ المُخصَّص لذلك الغرض. عندما يُحرِك لاعب قطعة من مربع إلى آخر، سيُعدِّل التابع قيمة عنصرين ضِمْن المصفوفة. بالإضافة إلى ذلك، إذا كانت الحركة عبارة عن قفزة (jump)، ستُحذَف القطعة التي كانت موجودة بالمربع المقفوز إليه من الرقعة. يستطيع التابع أن يُحدِّد ما إذا كانت حركة معينة عبارة عن قفزة أم لا بِفْحَص ما إذا كان المربع الذي تَحرَكت إليه القطعة يَبعُد بمقدار صفين عن المربع الذي بدأت منه. إلى جانب ما سبق، تُصبِح القطعة الحمراء RED التي تتحرك إلى الصف 0 أو القطعة السوداء Black التي تتحرك إلى الصف 7 بمثابة قطعة ملك (king). سنَضَع جميع ما سبق ببرنامج فرعي (subroutine)، وبالتالي، لن يضطّر باقي البرنامج للقلق بشأن أي من تلك التفاصيل السابقة. يُمكِنه فقط أن يَستدعِي التابع makeMove()‎:

void makeMove(int fromRow, int fromCol, int toRow, int toCol) {

   board[toRow][toCol] = board[fromRow][fromCol]; // حرك القطعة
   board[fromRow][fromCol] = EMPTY; // المربع الذي تحركت منه أصبح فارغًا

   if (fromRow - toRow == 2 || fromRow - toRow == -2) {
       // الحركة كانت قفزة لذلك احذف القطعة المقفوز إليها من الرقعة
      int jumpRow = (fromRow + toRow) / 2; // صف القطعة المقفوز إليها
      int jumpCol = (fromCol + toCol) / 2; // عمود القطعة المقفوز إليها
      board[jumpRow][jumpCol] = EMPTY;
   }

   if (toRow == 0 && board[toRow][toCol] == RED)
      board[toRow][toCol] = RED_KING;  // تصبح القطعة الحمراء ملك
   if (toRow == 7 && board[toRow][toCol] == BLACK)
      board[toRow][toCol] = BLACK_KING;  // تصبح القطعة السوداء ملك

}  // end makeMove()

ينبغي أن يَسمَح الصَنْف CheckersData بالعثور على جميع الحركات الصالحة بالرقعة. سنستخدم كائنًا ينتمي للصَنْف التالي لتمثيل الحركة داخل لعبة داما:

private static class CheckersMove {

   int fromRow, fromCol;  // موضع القطعة المطلوب تحريكها
   int toRow, toCol;      // المربع الذي انتقلت إليه القطعة

   CheckersMove(int r1, int c1, int r2, int c2) {
        // اضبط قيم متغيرات النسخة
      fromRow = r1;
      fromCol = c1;
      toRow = r2;
      toCol = c2;
   }

   boolean isJump() {
       // اختبر ما إذا كانت الحركة عبارة عن قفزة
       // بالقفزة، تتحرك القطعة مسافة صفين
      return (fromRow - toRow == 2 || fromRow - toRow == -2);
   }

}  // end class CheckersMove.

يُعرِّف الصَنْف CheckersData تابع نسخة (instance method) للعثور على جميع الحركات المتاحة حاليًا لكل لاعب. يُعدّ ذلك التابع بمثابة دالة (function) تُعيِد مصفوفة من النوع CheckersMove[]‎ تحتوي على جميع الحركات المتاحة مُمثَلة بهيئة كائنات من النوع CheckersMove. يُمكِننا إذًا كتابة توصيف التابع كالتالي:

CheckersMove[] getLegalMoves(int player)

يُمكِننا كتابة خوارزمية التابع بالشيفرة الوهمية (pseudocode) كالتالي:

// ابدأ بقائمة فارغة من الحركات
Start with an empty list of moves
// ابحث عن أي قفزات صالحة و أضفها إلى القائمة
Find any legal jumps and add them to the list
// إذا لم يكن هناك أي قفزات صالحة
if there are no jumps:
    // ابحث عن الحركات العادية الأخرى و أضفها إلى القائمة
   Find any other legal moves and add them to the list
// إذا كانت القائمة فارغة
if the list is empty:
   return null
else:
   return the list

الآن، ما هو المقصود بالقائمة (list)؟ في الواقع، ينبغي أن نُعيد الحركات المسموح بها ضِمْن مصفوفة، ولكن لأن المصفوفات ثابتة الحجم، لا يُمكِننا أن نُنشِئها حتى نَعرِف عدد الحركات، وهو في الواقع ما لا يُمكِننا معرفته حتى نَصِل إلى نهاية التابع أي بَعْد أن نَكُون قد أنشأنا القائمة بالفعل! أحد الحلول إذًا هو اِستخدَام مصفوفة ديناميكية من النوع ArrayList بدلًا من مصفوفة عادية لكي تَحمِل الحركات بينما نَجِدها. يَستخدِم البرنامج بالأسفل كائنًا من النوع ArrayList<CheckersMove>‎ لكي يُمكِّن القائمة من حَمْل كائنات من الصَنْف CheckersMove فقط. بينما نُضيِف الحركات إلى تلك القائمة، سيزداد حجمها بما يتناسب مع عدد الحركات. يُمكِننا أن نُنشِئ المصفوفة المطلوبة ونَنسَخ البيانات إليها بنهاية التابع. اُنظر الشيفرة الوهمية التالية:

// ‫أنشئ قائمة moves فارغة للحركات
Let "moves" be an empty ArrayList<CheckersMove>
// ابحث عن القفزات المسموح بها و أضفها إلى القائمة
Find any legal jumps and add them to moves
// إذا كان عدد الحركات ما يزال يساوي 0
if moves.size() is 0:  // There are no legal jumps!
    // ابحث عن الحركات العادية الصالحة و أضفها إلى القائمة
   Find any other legal moves and add them to moves
// إذا لم يكن عدد الحركات يساوي 0
if moves.size() is 0:  // There are no legal moves at all!
   return null
else:
    // ‫عرف مصفوفة moveArray من النوع CheckersMoves
    // ‫طولها يساوي moves.size()
   Let moveArray be an array of CheckersMoves of length moves.size()
   // ‫انسخ محتويات المصفوفة moves إلى moveArray
   Copy the contents of moves into moveArray
   return moveArray

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

// لكل صف بالرقعة
For each row of the board:
// لكل عمود بالرقعة
   For each column of the board:    
        // إذا كانت إحدى قطع اللاعبين بذلك المكان
      if one of the player's pieces is at this location:
          // ‫إذا كان من الممكن القفز إلى الموضع row+2,column+2
         if it is legal to jump to row + 2, column + 2
             // ‫أضف تلك الحركة إلى moves
             add this move to moves
         // ‫إذا كان من الممكن القفز إلى الموضع row-2,column+2
         if it is legal to jump to row - 2, column + 2
             add this move to moves
         // ‫إذا كان من الممكن القفز إلى الموضع row+2,column-2
         if it is legal to jump to row + 2, column - 2
             add this move to moves
         // ‫إذا كان من الممكن القفز إلى الموضع row-2,column-2
         if it is legal to jump to row - 2, column - 2
             add this move to moves

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

private boolean canMove(int player, int r1, int c1, int r2, int c2) {

   if (r2 < 0 || r2 >= 8 || c2 < 0 || c2 >= 8)
      return false;  // ‫(r2,c2) خارج الرقعة 

   if (board[r2][c2] != EMPTY)
      return false;  // ‫(r2,c2) يحتوي بالفعل على قطعة

   if (player == RED) {
      if (board[r1][c1] == RED && r2 > r1)
          return false;  // القطع الحمراء العادية يمكنها أن تتحرك للأسفل فقط
       return true;  // الحركة صالحة
   }
   else {
      if (board[r1][c1] == BLACK && r2 < r1)
          return false;  // القطع السوداء العادية يمكنها أن تتحرك للأعلى فقط
       return true;  // الحركة صالحة
   }

}  // end canMove()

يَستدعِى التابع getLegalMoves()‎ التابع canMove()‎ المُعرَّف بالأعلى ليَفْحَص ما إذا كانت حركة مُحتمَلة لقطعة معينة صالحة فعليًا أم لا. سنُعرِّف تابعًا مشابهًا لفَحْص ما إذا كانت قفزة (jump) معينة صالحة أم لا. في تلك الحالة، سنُمرِّر للتابع كُلًا من مربع القطعة والمربع الذي يُحتمَل أن تَنتقِل إليه وكذلك المربع الواقع بين هذين المربعين أي ذلك الذي سيَقفِز اللاعب فوقه. لابُدّ أن يَحتوِي المربع المقفوز إليه على إحدى قطع الخصم. يُمكننا تَوصِيف ذلك التابع كالتالي:

private boolean canJump(int player, int r1, int c1, 
                                   int r2, int c2, int r3, int c3) { . . .

ينبغي الآن أن تَكُون قادرًا على فِهم شيفرة التابع getLegalMoves()‎ بالكامل. يَدمِج ذلك التابع عدة مواضيع معًا: المصفوفات أحادية البعد (one-dimensional) والمصفوفات الديناميكية ArrayLists والمصفوفات ثنائية البعد (two-dimensional):

CheckersMove[] getLegalMoves(int player) {

   if (player != RED && player != BLACK)
      return null;  // لن يحدث هذا ببرنامج سليم

   int playerKing;  // The constant for a King belonging to the player.
   if (player == RED)
      playerKing = RED_KING;
   else
      playerKing = BLACK_KING;

   ArrayList<CheckersMove> moves = new ArrayList<CheckersMove>();  
    // ستخزن الحركة ضمن القائمة

    // تحقق من جميع القفزات الممكنة

   for (int row = 0; row < 8; row++) {
      for (int col = 0; col < 8; col++) {
        if (board[row][col] == player || board[row][col] == playerKing) {
            if (canJump(player, row, col, row+1, col+1, row+2, col+2))
               moves.add(new CheckersMove(row, col, row+2, col+2));
            if (canJump(player, row, col, row-1, col+1, row-2, col+2))
               moves.add(new CheckersMove(row, col, row-2, col+2));
            if (canJump(player, row, col, row+1, col-1, row+2, col-2))
               moves.add(new CheckersMove(row, col, row+2, col-2));
            if (canJump(player, row, col, row-1, col-1, row-2, col-2))
               moves.add(new CheckersMove(row, col, row-2, col-2));
        }
      }
   }

    // إذا وجدت أي قفزات ممكنة، فلابد أن يقفز اللاعب. لذلك لن نضيف أي 
    // حركات عادية. أما إذا لم تجد أي قفزات، ابحث عن أي حركات عادية

   if (moves.size() == 0) {
      for (int row = 0; row < 8; row++) {
         for (int col = 0; col < 8; col++) {
           if (board[row][col] == player || board[row][col] == playerKing) {
              if (canMove(player,row,col,row+1,col+1))
                 moves.add(new CheckersMove(row,col,row+1,col+1));
              if (canMove(player,row,col,row-1,col+1))
                 moves.add(new CheckersMove(row,col,row-1,col+1));
              if (canMove(player,row,col,row+1,col-1))
                 moves.add(new CheckersMove(row,col,row+1,col-1));
              if (canMove(player,row,col,row-1,col-1))
                 moves.add(new CheckersMove(row,col,row-1,col-1));
           }
         }
      }
   }

    // إذا لم تجد أي حركات صالحة، أعد فراغا
   if (moves.size() == 0)
      return null;
   else {
       // انشئ مصفوفة وأضف إليها الحركات المسموح بها
      CheckersMove[] moveArray = new CheckersMove[moves.size()];
      for (int i = 0; i < moves.size(); i++)
         moveArray[i] = moves.get(i);
      return moveArray;
   }

}  // end getLegalMoves

يُعدّ برنامج الداما مُعقدًا نوعًا ما، ويحتاج إلى الكثير من التصميم الجيد لتَقْرِير الأصناف (classes) والكائنات (classes) المُستخدمَة، وكذلك لتَقرِير التوابع (methods) التي ينبغي كتابتها، وكذلك لتقرير الخوارزميات (algorithms) التي ينبغي لتلك التوابع اِستخدَامها. يُمكِنك الاطلاع على شيفرة البرنامج بالكامل بالملف Checkers.java.

ترجمة -بتصرّف- للقسم Section 5: Two-dimensional Arrays من فصل Chapter 7: Arrays and ArrayLists من كتاب Introduction to Programming Using Java.

تُعدّ عمليتي البحث (searching) والترتيب (sorting) أكثر الأساليب شيوعًا لمعالجة المصفوفات. يُشير البحث (searching) هنا إلى محاولة العثور على عنصر بمواصفات معينة ضِمْن مصفوفة بينما يُشير الترتيب (sorting) إلى إعادة ترتيب عناصر المصفوفة ترتيبًا تصاعديًا أو تنازليًا. عادةً ما يَعتمِد المقصود بالترتيب التصاعدي والتنازلي على السياق المُستخدَم به الترتيب. في الواقع، تُوفِّر الجافا تُوفِّر بعض التوابع المَبنية مُسْبَقّا (built-in methods) الخاصة بعمليات البحث والترتيب -كما رأينا بالقسم الفرعي 7.2.2-، ومع ذلك ينبغي أن تَكُون على اطلاع ومعرفة بالخوارزميات (algorithms) التي تَستخدِمها تلك التوابع. ولهذا، سنَتعلَّم بعضًا من تلك الخوارزميات بهذا القسم.

عادةً ما يُناقَش البحث (searching) والترتيب (sorting) نظريًا باِستخدَام مصفوفة من الأعداد. ولكن من الناحية العملية، هناك أمور أكثر تشويقًا بكثير. فمثلًا، قد تَكُون المصفوفة عبارة عن قائمة بريدية بحيث يَكُون كل عنصر بها عبارة عن كائن (object) يَحتوِي على اسم وعنوان. إذا كان لدينا اسم شخص معين، يُمكِننا العثور على عنوانه، وهو ما يُعدّ مثالًا على عملية البحث (searching)؛ لأنك ببساطة تَبحَث عن كائن ضِمْن مصفوفة بالاعتماد على اسم الشخص. سيَكُون من المفيد أيضًا لو تَمَكَّنا من ترتيب المصفوفات وفقًا لمعيار معين مثل أن نُرتِّب المصفوفة السابقة بحيث تَكُون الأسماء مُرتَّبة ترتيبًا أبجديًا أو قد نُرتِّبها وفقًا للرقم البريدي.

سنُعمِّم الآن المثال السابق إلى تصور مُجرَّد بعض الشئ: لنتخيل أن لدينا مصفوفة تَحتوِي على عدة كائنات (objects)، وأننا نرغب بالبحث داخل تلك المصفوفة أو نرغب بترتيبها بالاعتماد على احدى مُتْغيِّرات النُسخ (instance variables) المُعرَّفة بتلك الكائنات. سنلجأ إلى اِستخدَام بعض المصطلحات الشائعة بقواعد البيانات (databases). سنُطلِق اسم "تسجيل (record)" على كل كائن ضِمْن المصفوفة بينما سنُطلِق اسم "الحقول (fields)" على مُتْغيِّرات النُسخ المُعرَّفة بتلك الكائنات. نستطيع الآن أن نُعيِد صياغة مثال القائمة البريدية إلى ما يلي: يَتَكوَّن كل تسجيل (record) من اسم وعنوان. قد تَتَكوَّن حقول التسجيل من الاسم الأول والأخير والعنوان والمدينة والدولة والرقم البريدي. ينبغي أن نختار إحدى تلك الحقول لتُصبِح "مفتاحًا (key)" لكي نَتَمكَّن من إجراء عمليتي البحث والترتيب. وفقًا لهذا التصور، سيُمثِل البحث محاولة العثور على تسجيل بالمصفوفة بحيث يَحتوِي مفتاحه على قيمة معينة بينما سيُمثِل الترتيب (sorting) تَبديِل مواضع تسجيلات المصفوفة إلى أن تُصبِح مفاتيحها (keys) مُرتَّبة ترتيبًا تصاعديًا أو تنازليًا.

دورة تطوير التطبيقات باستخدام لغة Python

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

اشترك الآن

البحث (Searching)

هناك خوارزمية واضحة للبحث عن عنصر معين داخل مصفوفة: افحص كل عنصر بالمصفوفة بالترتيب، واختبر ما إذا كانت قيمة ذلك العنصر هي نفسها القيمة التي تبحث عنها. إذا كان كذلك، فقد انتهت عملية البحث إذًا. أما إذا لم تعثر عليه بعد فحص جميع عناصر المصفوفة، فهو إذًا غير موجود بها. يُمكننا كتابة برنامج فرعي لتنفيذ تلك الخوارزمية (algorithm) بسهولة. بفرض أن المصفوفة التي تريد البحث بها عبارة عن مصفوفة من النوع int[]‎، يبحث التابع (method) التالي عن قيمة عددية ضمن مصفوفة. سيعيد التابع فهرس (index) العنصر بالمصفوفة إذا عثر عليه بينما سيعيد -1 إذا لم يعثر عليه كإشارة أن العدد الصحيح غير موجود:

static int find(int[] A, int N) {

   for (int index = 0; index < A.length; index++) {
      if ( A[index] == N ) 
          // ‫عثرنا على N بهذا الفهرس
         return index;  
   }

    // ‫إذا وصلنا إلى هنا، فإن N غير موجودة بأي مكان ضمن المصفوفة 
    // أعد القيمة -1

   return -1;

}

يُطلَق على طريقة البحث السابقة اسم البحث الخطي (linear search). إذا لم يَكُن لدينا أي معلومة عن كيفية ترتيب العناصر ضِمْن المصفوفة، فإنها تُمثِل الخيار الأفضل. في المقابل، إذا كنا على علم بكَوْن عناصر المصفوفة مُرتَّبة تصاعديًا أو تنازليًا، يُمكِننا إذًا أن نستغل تلك الحقيقة، ونَستخدِم خوارزميات أسرع. إذا كانت عناصر مصفوفة معينة مرتبة، يُقال عليها أنها "مصفوفة مرتبة (sorted)". يَستغرق ترتيب عناصر مصفوفة بعض الوقت بالطبع، ولكن إذا كانت المصفوفة مرتبة بالفعل، فيُمكننا إذًا أن نستغل تلك الحقيقة.

يُعدّ البحث الثنائي (binary search) أحد الطرائق المُتاحة للبحث عن عنصر ضِمْن مصفوفة مُرتَّبة (sorted). على الرغم من أن تّنْفِيذه (implement) ليس سهلًا تمامًا، فإن فكرته بسيطة: إذا كنت تَبحَث عن عنصر ضِمْن قائمة مُرتَّبة، يُمكِنك أن تَستبعِد نُصف العناصر ضِمْن القائمة بِفَحْص عنصر واحد فقط. على سبيل المثال، لنَفْترِض أننا نبحث عن العدد 42 ضِمْن مصفوفة مُرتَّبة مُكوَّنة من 1000 عدد صحيح، ولنَفْترِض أن المصفوفة مُرتَّبة ترتيبًا تصاعديًا، ولنَفْترِض أننا فَحصَنا العنصر الموجود بالفهرس 500، ووجدنا أن قيمته تُساوِي 93. لمّا كان العدد 42 أقل من 93، ولمّا كانت العناصر بالمصفوفة مُرتَّبة ترتيبًا تصاعديًا، يُمكِننا إذًا أن نَستنتج أنه في حالة كان العدد 42 موجودًا بتلك المصفوفة من الأساس، فإنه لابُدّ وأنه يَقَع بمَوضِع فهرسه أقل من 500. يُمكِننا إذًا أن نَستبِعد جميع العناصر الموجودة بمَواضِع فهرسها أكبر من 500؛ فهي بالضرورة أكبر من أو تُساوِي 93.

الخطوة التالية ببساطة هي فَحْص قيمة العنصر بالمَوْضِع 250. إذا كان العدد بذلك المَوْضِع يُساوِي -21 مثلًا، يُمكِننا إذًا أن نَستبعِد جميع العناصر قَبل المَوْضِع 250، ونُقصِر بحثنا على المَواضِع من 251 إلى 499. سيُقصِر الاختبار التالي بحثنا إلى 125 مَوضِع فقط ثُمَّ إلى 62. سيَتَبقَّى مَوضِع واحد فقط بعد 10 خطوات. تُعدّ تلك الطريقة أفضل كثيرًا من فَحْص كل عنصر ضِمْن المصفوفة. فمثلًا، إذا كانت المصفوفة تَحتوِي على مليون عنصر، ستَستغرِق خوارزمية البحث الثنائي 20 خطوة فقط للبحث بكامل المصفوفة. في العموم، يُساوِي عدد الخطوات اللازمة للبحث بأي مصفوفة لوغاريتم عدد العناصر بتلك المصفوفة بالنسبة للأساس 2.

لكي نَتَمكَّن من تَحْوِيل خوارزمية البحث الثنائي (binary search) إلى برنامج فرعي (subroutine) يَبحَث عن عنصر N ضِمْن مصفوفة A، ينبغي أن نَحتفِظ بنطاق المَوْاضِع التي يُحتمَل أن تَحتوِي على N بحيث نَستبعِد منها تدريجيًا المزيد من الاحتمالات، ونُقلِّل من حجم النطاق. سنَفْحَص دائمًا العنصر الموجود بمنتصف النطاق. إذا كانت قيمته أكبر من N، يُمكِننا إذًا أن نَستبعِد النصف الثاني من النطاق أما إذا كانت قيمته أقل من N، يُمكِننا أن نَستبعِد النصف الأول. أما إذا كانت قيمته تُساوي N، فإن البحث يَكُون قد انتهى. إذا لم يَتبقَّى أية عناصر، فإن العدد N غَيْر موجود إذًا بالمصفوفة. اُنظر شيفرة البرنامج الفرعي (subroutine):

/**
 * Precondition:  A must be sorted into increasing order.
 * Postcondition: If N is in the array, then the return value, i,
 *    satisfies A[i] == N.  If N is not in the array, then the
 *    return value is -1.
 */
static int binarySearch(int[] A, int N) {

    int lowestPossibleLoc = 0;
    int highestPossibleLoc = A.length - 1;

    while (highestPossibleLoc >= lowestPossibleLoc) {
       int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
       if (A[middle] == N) {
           // ‫عثرنا على N بهذا الفهرس
          return middle;
       }
       else if (A[middle] > N) {
           // ‫استبعد المواضع الأكبر من أو تساوي middle
          highestPossibleLoc = middle - 1;
       }
       else {
           // ‫استبعد المواضع الأقل من أو تساوي middle
          lowestPossibleLoc = middle + 1;   
       }
    }

    // ‫إذا وصلنا إلى هنا فإن highestPossibleLoc < LowestPossibleLoc
    // ‫أي أن N غير موجود بالمصفوفة.
    // أعد القيمة -1 لكي تشير إلى عدم وجود‫ N بالمصفوفة

    return -1;

}

القوائم الارتباطية (Association Lists)

تُعدّ القوائم الارتباطية (association lists) مثل القاموس (dictionary) واحدة من أشهر التطبيقات على البحث (searching). يَربُط القاموس (dictionary) مجموعة من التعريفات مع مجموعة من الكلمات. يُمكِنك مثلًا أن تَستخدِم كلمة معينة لمعرفة تَعرِيفها. قد تُفكِر بالقاموس على أنه قائمة من الأزواج (pairs) على الهيئة (w,d) حيث تُمثِل w كلمة معينة بينما d هي تعريف تلك الكلمة. بالمثل، تَتَكوَّن القوائم الارتباطية (association list) من قائمة من الأزواج (k,v) حيث تُمثِل k مفتاحًا (key) معينًا بينما تُمثِل v القيمة (value) المرتبطة بذلك المفتاح. لا يُمكِن لزوجين (pairs) ضِمْن قائمة معينة أن يَملُكا نفس قيمة المفتاح (key). عادةً ما نُطبِق عمليتين أساسيتين على القوائم الارتباطية: أولًا، إذا كان لديك مفتاح معين k، يُمكِنك أن تَجلُب القيمة v المُرتبِطة به إن وجدت. ثانيًا، يُمكِننا أن نُضيِف زوجًا جديدًا (k,v) إلى قائمة ارتباطية (association list). لاحِظ أنه في حالة إضافة زوج (pair) إلى قائمة، وكانت تلك القائمة تَحتوِي على زوج له نفس المفتاح، فإن القيمة الجديدة المضافة تَحلّ محلّ القديمة. يُطلق عادةً على تلك العمليتين اسم الجَلْب (get) والإضافة (put).

يُشاع اِستخدَام القوائم الارتباطية (association lists) في العموم بعلوم الحاسوب (computer science). على سبيل المثال، لابُدّ أن يَحتفِظ المُصرِّف (compiler) بمَوضِع الذاكرة (memory location) الخاص بكل مُْتْغيِّر. يستطيع المُصرِّف إذًا أن يَستخدِم قائمة ارتباطية بحيث يُمثِل كل مفتاح (key) بها اسمًا لمُتْغيِّر بينما تُمثِل قيمة (value) ذلك المفتاح عنوانه بالذاكرة. مثال آخر هو القوائم البريدية إذا كان العنوان مَربُوطًا باسم ضِمْن تلك القائمة. فمثلًا، يَربُط دليل الهاتف كل اسم برقم هاتف. سنَفْحَص فيما يَلي نُسخة مُبسَطة من ذلك المثال.

يُمكِننا أن نُمثِل عناصر دليل الهاتف بالقائمة الارتباطية (association list) بهيئة كائنات تنتمي إلى الصَنْف التالي:

class PhoneEntry {
   String name;
   String phoneNum;
}

تَتَكوَّن البيانات الموجودة بدليل الهاتف من مصفوفة من النوع PhoneEntry[]‎ بالإضافة إلى مُتْغيِّر من النوع العددي الصحيح (integer) للاحتفاظ بعدد المُدْخَلات المُخزَّنة فعليًا بذلك الدليل. يُمكِننا أيضًا أن نَستخدِم تقنية المصفوفات الديناميكية (dynamic arrays) -اُنظر القسم الفرعي 7.2.4- لكي نَتجنَّب وَضْع حد أقصى عشوائي على عدد المُدْخَلات التي يُمكِن لدليل الهاتف أن يَحتوِيه أو قد نَستخدِم النوع ArrayList. ينبغي أن يَحتوِي الصَنْف PhoneDirectory على توابع نسخ (instance methods) لتّنْفِيذ (implement) كلًا من عمليتي الجَلْب (get) والإضافة (put). تُمثِل الشيفرة التالية تعريفًا (definition) بسيطًا لذلك الصَنْف:

public class PhoneDirectory {

   private static class PhoneEntry {
      String name;     // الاسم
      String number;   // رقم الهاتف
   }

   private PhoneEntry[] data;  // مصفوفة لحمل أزواج مكونة من أسماء وأرقام هاتف
   private int dataCount;      // عدد الأزواج ضمن المصفوفة

   /**
    * Constructor creates an initially empty directory.
    */
   public PhoneDirectory() {
      data = new PhoneEntry[1];
      dataCount = 0;
   }

   private int find( String name ) {
      for (int i = 0; i < dataCount; i++) {
         if (data[i].name.equals(name))
            return i;  // الاسم موجود بالموضع‫ i
      }
      return -1;  // الاسم غير موجود بالمصفوفة
   }

   /**
    * @return The phone number associated with the name; if the name does
    *    not occur in the phone directory, then the return value is null.
    */
   public String getNumber( String name ) {
      int position = find(name);
      if (position == -1)
         return null;   // لا يوجد بيانات لذلك الاسم
      else
         return data[position].number;
   }

   public void putNumber( String name, String number ) {
      if (name == null || number == null)
         throw new IllegalArgumentException("name and number cannot be null");
      int i = find(name);
      if (i >= 0) {
          // ‫الاسم موجود بالفعل بالموضع i بالمصفوفة 
          // استبدل العدد الجديد بالعدد القديم بذلك الموضع
         data[i].number = number;
      }
      else {
          // أضف زوج جديد مكون من اسم وعدد إلى المصفوفة
          // إذا كانت المصفوفة ممتلئة، أنشئ مصفوفة جديدة أكبر
         if (dataCount == data.length) {
            data = Arrays.copyOf( data, 2*data.length );
         }
         PhoneEntry newEntry = new PhoneEntry();  // أنشئ زوجا جديدا
         newEntry.name = name;
         newEntry.number = number;
         data[dataCount] = newEntry;   // أضف الزوج الجديد إلى المصفوفة
         dataCount++;
      }
   }

} // end class PhoneDirectory

يُعرِّف الصَنْف تابع النسخة find()‎. يَستخدِم ذلك التابع أسلوب البحث الخطي (linear search) للعثور على مَوْضِع اسم معين بالمصفوفة المُكوَّنة من أزواج من الأسماء والأرقام. يَعتمِد كُلًا من التابعين getNumber()‎ و putNumber()‎ على التابع find()‎. لاحِظ أن التابع putNumber(name,number)‎ يَفحَص أولًا ما إذا كان الاسم موجودًا بدليل الهاتف أم لا. إذا كان موجودًا، فإنه فقط يُغيِّر الرقم المُرتبِط بذلك الاسم أما إذا لم يَكُن موجودًا، فإنه يُنشِئ مُدخلًا جديدًا ويُضيفه إلى المصفوفة.

قد نُضيِف الكثير من التحسينات بالطبع على الصَنْف المعرَّف بالأعلى. فمثلًا، قد نَستخدِم البحث الثنائي (binary search) بالتابع getNumber()‎ بدلًا من البحث الخطي، ولكن يَتَطلَّب ذلك أن تَكُون الأسماء المُخزَّنة بقائمة المُدْخَلات مُرتَّبة ترتيبًا أبجديًا، وهو ليس أمرًا صعبًا كما ستَرَى بالقسم الفرعي التالي.

عادةً ما يُطلَق اسم الخارطة (maps) على القوائم الارتباطية (association lists)، وتُوفِّر الجافا صَنْفًا قياسيًا ذو معاملات غَيْر محددة النوع (parameterized) اسمه هو Map كتنفيذ (implementation) لها. تستطيع أن تَستخدِم ذلك الصَنْف لكي تُنشِئ قوائمًا ارتباطية مُكوَّنة من مفاتيح (keys) وقيم (values) من أي نوع. يُعدّ ذلك التنفيذ (implementation) أكفأ بكثير من أي شيء قد تَفعَلُه باِستخدَام مصفوفات بسيطة. سنَتعرَّض بالفصل العاشر لذلك الصَنْف.

الترتيب بالإدراج (Insertion Sort)

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

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

static void insert(int[] A, int itemsInArray, int newItem) {

   int loc = itemsInArray - 1;  // ابدأ من نهاية المصفوفة

    // ‫حرك العناصر الأكبر من newItem للأعلى بمقدار مسافة واحدة
    // وتوقف عندما تقابل عنصر أصغر أو عندما تصل إلى بداية المصفوفة

   while (loc >= 0 && A[loc] > newItem) {
      A[loc + 1] = A[loc];  // Bump item from A[loc] up to loc+1.
      loc = loc - 1;        // انتقل إلى الموضع التالي
   }

    // ‫ضع newItem بآخر موضع فارغ
   A[loc + 1] = newItem;  

}

يُمكِننا أن نَمِد ذلك إلى تابع للترتيب (sorting) بأخذ جميع العناصر الموجودة بمصفوفة غَيْر مُرتَّبة (unsorted) ثم اضافتها تدريجيًا واحدًا تلو الآخر إلى مصفوفة آخرى مع الإبقاء عليها مُرتَّبة. نستطيع أن نَستخدِم البرنامج insert بالأعلى أثناء كل عملية إدراج (insertion) لعنصر جديد. ملحوظة: بالخوارزمية الفعليّة، لا نأخُذ جميع العناصر من المصفوفة، ولكننا فقط نتذكَّر الأجزاء المُرتَّبة منها:

static void insertionSort(int[] A) {
    // ‫رتب المصفوفة A ترتيبًا تصاعديا

   int itemsSorted; // عدد العناصر المُرتَّبة إلى الآن

   for (itemsSorted = 1; itemsSorted < A.length; itemsSorted++) {
       // ‫افترض أن العناصر A[0]‎ و A[1]‎ .. إلخ
       // ‫مرتبة بالفعل. أضف A[itemsSorted]‎ إلى الجزء المرتب من 
       // القائمة

      int temp = A[itemsSorted];  // العنصر المطلوب إضافته
      int loc = itemsSorted - 1;  // ابدأ بنهاية القائمة

      while (loc >= 0 && A[loc] > temp) {
         A[loc + 1] = A[loc]; // Bump item from A[loc] up to loc+1.
         loc = loc - 1;       // Go on to next location.
      }

       // ‫ضع temp بآخر موضع فارغ
      A[loc + 1] = temp; 
   }
}

تُوضِح الصورة التالية مرحلة واحدة من عملية الترتيب بالإدراج (insertion sort) حيث تُبيِّن ما يحدث أثناء تّنفِيذ تَكْرار واحد من الحلقة for بالأعلى بالتحديد عندما يَكُون عدد العناصر ضِمْن المصفوفة itemsSorted مُساوِيًا للقيمة 5:

الترتيب الانتقائي (Selection Sort)

تَستخدِم خوارزمية ترتيب (sorting) آخرى فكرة العُثور على أكبر عنصر ضِمْن القائمة، وتَحرِيكه إلى نهايتها حيث ينبغي أن يتواجد إذا كنا نريد ترتيبها ترتيبًا تصاعديًا. بمُجرَّد تَحرِيك أكبر عنصر بالقائمة إلى مَوْضِعه الصحيح، يُمكِننا أن نُطبِق نفس الفكرة على العناصر المُتبقَاة أي أن نَعثُر على العنصر الأكبر التالي، ونُحرِكه إلى المَوْضِع قبل الأخير، وهكذا. يُطلَق اسم "الترتيب الانتقائي (selection sort)" على تلك الخوارزمية (algorithm). يُمكِننا كتابتها كما يلي:

static void selectionSort(int[] A) {
    // رتب المصفوفة A ترتيبا تصاعديا باستخدام الترتيب الانتقائي

   for (int lastPlace = A.length-1; lastPlace > 0; lastPlace--) {
      int maxLoc = 0;  // موضع أكبر عنصر إلى الآن

      for (int j = 1; j <= lastPlace; j++) {
         if (A[j] > A[maxLoc]) {
             // ‫لأن A[j]‎ أكبر من أكبر قيمة رأيناها إلى الآن، فإن j هو
             // الموضع الجديد لأكبر قيمة وجدناها إلى الآن
            maxLoc = j;  
         }
      }

      int temp = A[maxLoc];  // Swap largest item with A[lastPlace].
      A[maxLoc] = A[lastPlace];
      A[lastPlace] = temp;

   }  // end of for loop

}

يَستخدِم الصَنْف Hand الذي كتبناه بالقسم الفرعي 5.4.1 نسخة مختلفة قليلًا من الترتيب الانتقائي (selection sort). يُعرِّف الصَنْف Hand مُتْغيِّرًا من النوع ArrayList<Card>‎ لتَمثيِل اليد (hand) يحتوي بطبيعة الحال على كائنات من النوع Card. يَحتوِي أي كائن من النوع Card على توابع النسخ getSuit()‎ و getValue()‎، والتي يُمكِننا أن نَستخدِمها لمَعرِفة كُلًا من قيمة ورقة اللعب ورمزها (suit). يُنشِئ التابع (method) المسئول عن عملية الترتيب (sorting) قائمة جديدة، بحيث يَختار ورق اللعب من القائمة القديمة تدريجيًا وبترتيب مُتصاعِد ثم يُحرِكها من القائمة القديمة إلى الجديدة. يَستخدِم التابع (method) القائمة الجديدة بالنهاية لتمثيل اليد بدلًا من القديمة. قد لا يَكُون ذلك هو الأسلوب الأكفأ لإنجاز الأمر، ولكن نظرًا لأن عدد ورق اللعب ضِمْن أي يد (hand) عادةً ما يَكون صغيرًا، فإنه لا يُمثِل مشكلة كبيرة. اُنظر شيفرة ترتيب (sorting) ورق اللعب:

public void sortBySuit() {
   ArrayList<Card> newHand = new ArrayList<Card>();
   while (hand.size() > 0) {
      int pos = 0;  // موضع البطاقة الأقل
      Card c = hand.get(0);  // البطاقة الأقل
      for (int i = 1; i < hand.size(); i++) {
         Card c1 = hand.get(i);
         if ( c1.getSuit() < c.getSuit() ||
              (c1.getSuit() == c.getSuit() && c1.getValue() < c.getValue()) ) {
            pos = i;  // Update the minimal card and location.
            c = c1;
         }
      }
      hand.remove(pos);  // احذف ورقة اللعب من اليد الأصلية
      newHand.add(c);    // أضف ورقة اللعب إلى اليد الجديدة
   }
   hand = newHand;
}

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

يُمثِل ترتيب قائمة من النوع String مشكلة مشابهة؛ فالعامل < غَيْر مُعرَّف للسَلاسِل النصية. في المقابل، يُعرِّف الصنف String التابع compareTo. إذا كان str1 و str2 من النوع String، يُمكِننا كتابة ما يلي:

str1.compareTo(str2)

يُعيِد التابع السابق قيمة من النوع int تُساوِي 0 إذا كان str1 يُساوِي str2 أو قيمة أقل من 0 عندما يأتي str1 قبل str2 أو أكبر من 0 عندما يأتي str1 بَعْد str2. تستطيع مثلًا أن تختبر ما إذا كان str1 يَسبِق str2 أو يُساويه باِستخدَام الاختبار التالي:

if ( str1.compareTo(str2) <= 0 )

يُقصَد بكلمات مثل "يَسبِق" أو "يَتبَع" -عند اِستخدَامها مع السَلاسِل النصية (string)- ترتيبها وفقًا للترتيب المعجمي (lexicographic ordering)، والذي يَعتمِد على قيمة اليونيكود (Unicode) للمحارف (characters) المُكوِّنة للسِلسِلة النصية (strings). يَختلِف الترتيب المعجمي (lexicographic ordering) عن الترتيب الأبجدي (alphabetical) حتى بالنسبة للكلمات المُكوَّنة من أحرف أبجدية فقط؛ لأن جميع الأحرف بحالتها الكبيرة (upper case) تَسبِق جميع الأحرف بحالتها الصغيرة (lower case). في المقابل، يُعدّ الترتيب الأبجدي والمعجمي للكلمات المُقتصِرة على 26 حرف بحالتها الصغيرة فقط أو الكبيرة فقط هو نفسه. يُحوِّل التابع str1.compareToIgnoreCase(str2)‎ أحرف سِلسِلتين نصيتين (strings) إلى الحالة الصغيرة (lowercsae) أولًا قبل موازنتهما.

يتناسب كُلًا من الترتيب الانتقائي (selection sort) والترتيب بالادراج (insertion sort) مع المصفوفات الصغيرة المُكوَّنة من مئات قليلة من العناصر. أما بالنسبة للمصفوفات الكبيرة، فتَتَوفَّر خوارزميات آخرى أكثر تعقيدًا ولكنها أسرع بكثير. هذه الخوارزميات أسرع بكثير ربما بنفس الكيفية التي يُعدّ بها البحث الثنائي (binary search) أسرع من البحث الخطي (linear search). يَعتمِد التابع القياسي Arrays.sort على الخوارزميات السريعة. سنَتعرَّض لإحدى تلك الخوارزميات بالفصل التاسع.

الترتيب العشوائي (unsorting)

يُعدّ الترتيب العشوائي لعناصر مصفوفة مشكلة أقل شيوعًا ولكنها شيقة. قد نحتاجها مثلًا لخَلْط مجموعة ورق لعب ضِمْن برنامج. تَتًوفَّر خوارزمية شبيهة بالترتيب الانتقائي (selection sort)، فبدلًا من تَحرِيك أكبر عنصر بالمصفوفة إلى نهايتها، سنختار عنصرًا عشوائيًا ونُحرِكه إلى نهايتها. يَخلِط البرنامج الفرعي (subroutine) التالي عناصر مصفوفة من النوع int:

/**
 * Postcondition:  The items in A have been rearranged into a random order.
 */
static void shuffle(int[] A) {
   for (int lastPlace = A.length-1; lastPlace > 0; lastPlace--) {
       // ‫اختر موضعا عشوائيًا بين 0 و 1 و... حتى lastPlace
      int randLoc = (int)(Math.random()*(lastPlace+1));
       // ‫بدل العناصر بالموضعين randLoc و lastPlace
      int temp = A[randLoc];
      A[randLoc] = A[lastPlace];
      A[lastPlace] = temp;
   }
}

ترجمة -بتصرّف- للقسم Section 4: Searching and Sorting من فصل Chapter 7: Arrays and ArrayLists من كتاب Introduction to Programming Using Java.

يُمكِننا أن نُضمِّن نمط المصفوفة الديناميكية (dynamic array) داخل صَنْف كما رأينا بالقسم الفرعي 7.2.4، ولكن بدا الأمر كما لو أننا سنحتاج إلى تعريف صَنْف مختلف لكل نوع من البيانات (data type). في الحقيقة، تُوفِّر جافا خاصية تُعرَف باسم "الأنواع ذات المعاملات غَيْر مُحدَّدة النوع (parameterized types)"، والتي يُمكِنها أن تُجنِّبنا مشكلة تعدد الأصناف كما تُوفِّر جافا الصَنْف ArrayList الذي يُنفِّذ (implement) نمط المصفوفة الديناميكية لجميع أنواع البيانات.

الصنف ArrayList والأنواع ذات المعاملات غير محددة النوع (Parameterized Types)

تُوفِّر جافا النوع القياسي ArrayList<String>‎ لتمثيل مصفوفة ديناميكية (dynamic arrays) من النوع String. وبالمثل، يُمثِل النوع ArrayList<Button>‎ مصفوفة ديناميكية من النوع Button. بنفس الكيفية، إذا كان Player صنفًا (class) يُمثِل اللاعبين ضِمْن لعبة، فإن النوع ArrayList<Player>‎ يُمثِل مصفوفة ديناميكية من النوع Player.

قد يبدو الأمر كما لو أننا نَستخدِم أصنافًا كثيرة، ولكن، في الواقع، هنالك صَنْف (class) واحد فقط هو الصَنْف ArrayList المُعرَّف بحزمة java.util. يُعدّ ذلك الصَنْف صَنْفًا ذي مُعامِلات غَيْر مُحدَّدة النوع (parameterized type) -نوع يُمكِنه أن يَأخُذ معامل نوع (type parameter)-. يُمكِننا ذلك من اِستخدَام صَنْف واحد فقط للحصول على عدة أنواع مثل ArrayList<String>‎ و ArrayList<Button>‎ وحتى ArrayList<T>‎. لابُدّ أن يَكُون معامل النوع T نوعًا كائنيًا (object type) أي اسم صَنْف (class) أو اسم واجهة (interface)، ولا يُمكِنه أن يَكُون نوعًا أساسيًا (primitive type). يعني ذلك أنك لا تستطيع الحصول على ArrayList من النوع int أو ArrayList من النوع char.

يُمكِننا مثلًا أن نَستخدِم النوع ArrayList<String>‎ للتّصرِيح (declare) عن مُتْغيِّر كالتالي:

ArrayList<String> namelist;

أو قد نَستخدِمه كنوع لمعامل صوري (formal parameter) ضِمْن تعريف برنامج فرعي (subroutine) أو كنوع مُعاد (return type) من برنامج فرعي. علاوة على ذلك، قد نَستخدِمه مع العامل new لإنشاء كائنات (objects):

namelist = new ArrayList<String>();

يَكُون الكائن المُنشَئ في هذه الحالة من النوع ArrayList<String>‎، ويُمثِل قائمة ديناميكية من السَلاسِل النصية (strings). يُوفِّر الصَنْف مجموعة من توابع النُسخ (instance methods) مثل التابع namelist.add(str)‎ لإضافة سِلسِلة نصية من النوع String إلى القائمة، والتابع namelist.get(i)‎ لجَلْب السِلسِلة النصية الموجود برقم الفهرس i، والتابع namelist.size()‎ لحِسَاب عدد العناصر الموجودة بالقائمة حاليًا.

إلى جانب ما سبق، يُستخدَم الصَنْف ArrayList مع أنواع آخرى أيضًا. فمثلًا، إذا كان الصَنْف Player يُمثِل اللاعبين ضِمْن لعبة، يُمكِننا أن نُنشِئ قائمة من اللاعبين كالتالي:

ArrayList<Player> playerList = new ArrayList<Player>();

والآن، يُمكِنك أن تَستخدِم playerList.add(plr)‎ لإضافة لاعب plr إلى اللعبة أو قد تَستخدِم playerList.remove(k)‎ لحَذْف اللاعب الموجود برقم الفهرس k.

علاوة على ذلك، إذا كان playerList مُتْغيِّرًا محليًا (local variable)، يُمكِنك أن تَستخدِم صيغة التّصرِيح (declaration) المختصرة -اُنظر القسم الفرعي 4.8.2- كما يلي:

var playlerList = new ArrayList<Player>();

يَعتمِد مُصرِّف (compiler) الجافا على القيمة المبدئية المُسنَدة إلى playerList لاستنتاج أن نوعه هو ArrayList<Player>‎.

عندما تَستخدِم نوعًا (type) مثل ArrayList<T>‎، فإن المُصرِّف يتأكد من أن جميع الكائنات (objects) المضافة إليه من النوع T، وستُعدّ أي محاولة لإضافة كائن (object) من نوع آخر خطأً في بناء الجملة (syntax error)، ولا يُصرَّف عندها البرنامج. لمّا كانت الكائنات المنتمية لصَنْف فرعي من T هي بالنهاية من النوع T، فإنه من المُمكن إضافتها أيضًا إلى القائمة. فمثلًا، يُمكِن لمُتْغيِّر من النوع ArrayList<Pane>‎ أن يَحمِل كائنات من النوع BorderPane أو TilePane أو GridPane أو أي صنف فرعي (subclass) آخر من الصَنْف Pane (في الواقع، يُشبِه ذلك طريقة عمل المصفوفات حيث يستطيع كائن من النوع T[]‎ أن يَحمِل أي كائنات تنتمي لصَنْف فرعي من T). بالمثل، إذا كان T عبارة عن واجهة (interface)، فمن الممكن إضافة أي كائن (objects) إلى القائمة طالما كان يُنفِّذ (implement) تلك الواجهة T.

تَملُك الكائنات من النوع ArrayList<T>‎ جميع توابع النسخ (instance methods) التي قد تَتَوقَّعها من مصفوفة ديناميكية (dynamic array). بِفَرْض أن list عبارة عن مُتْغيِّر من النوع ArrayList<T>‎، اُنظر التوابع التالية:

• list.size()‎: يُعيد حجم القائمة أي عدد العناصر الموجودة بها حاليًا. قد يَكون حجم القائمة مُساويًا للصفر. فمثلًا، يُنشِئ باني الكائن الافتراضي new ArrayList<T>()‎ قائمة حجمها يُساوي صفر، وفي العموم، تتراوح أرقام المواضع الصالحة من 0 وحتى list.size()-1.

• list.add(obj)‎: يُضيِف كائنًا (object) إلى نهاية القائمة مع زيادة حجمها بمقدار الواحد. لاحِظ أن المُعامل obj لابُد أن يَكُون كائنًا من النوع T أو قد يَكُون فارغًا.

• list.get(N)‎: يَستقبِل المُعامل N الذي لابُدّ أن يكون عددًا صحيحًا (integer) يتراوح من 0 إلى list.size()-1 ثُمَّ يُعيد القيمة المُخزَّنة بالمَوْضِع N، والتي بطبيعة الحال تَكُون من النوع T. إذا كان N خارج النطاق المسموح به، يَقَع اعتراض من النوع IndexOutOfBoundsException. في الواقع، تُشبه تلك الدالة الأمر A[N]‎ -بِفَرْض أن A عبارة عن مصفوفة- بفارق أنه لا يُمكِن اِستخدَام list.get(N)‎ بالجانب الأيسر من أي تَعْليمَة إِسْناد (assignment statement).

• list.set(N, obj)‎: يُسنِد الكائن obj إلى عنصر المصفوفة بالمَوْضِع N أي يَحلّ ذلك الكائن محلّ الكائن المُخزَّن مُسْبَقًا بذلك الموضع. لابُدّ أن يَكُون المُعامل obj من النوع T كما ينبغي أن يَكُون N عددًا صحيحًا (integer) يتراوح بين 0 و list.size()-1. في الواقع، تُشبِه تلك الدالة الأمر A[N] = obj بِفَرْض أن A عبارة عن مصفوفة.

• list.clear()‎: يحذِف جميع العناصر الموجودة بالقائمة، ويَضبُط حجمها إلى الصفر.

• list.remove(N)‎: يَحذِف العنصر الموجود بالمَوْضِع N من القائمة، ويُنقِص حجمها بمقدار الواحد كما يَنقِل العناصر الموجودة بَعْد العنصر المحذوف مَوْضِعًا للأعلى. لاحِظ أن المُعامل N لابُدّ أن يَكُون عددًا صحيحًا (integer) يتراوح بين 0 و list.size()-1.

• list.remove(obj)‎: يَحذِف الكائن المُمرَّر من القائمة إذا كان موجودًا بها، ويُنقِص حجمها بمقدار الواحد كما يَنقِل العناصر الموجودة بَعْد العنصر المحذوف مَوضِعًا للأعلى. لاحِظ أنه في حالة وجود الكائن obj أكثر من مرة ضِمْن القائمة، فإنه يَحذِف أول حدوث له فقط أما إذا لم يَكُن موجودًا، فإنه لا يَفعَل أي شيء أي لا يُعدّ ذلك بمثابة خطأ.

• list.indexOf(obj)‎: يَبحَث عن الكائن obj داخل القائمة، ويُعيد أول مَوْضِع لحدوثه إذا كان موجودًا أما إذا لم يَكُن موجودًا، فإنه يُعيِد العدد -1.

ملحوظة: يَستخدِم آخر تابعين الاستدعاء obj.equals(item)‎ لموازنة obj -لو لم يَكُن obj فارغًا- مع عناصر القائمة أي أنهما يَفْحَصا تَساوِي السَلاسِل النصية بِفْحَص محتوياتها وليس مَواضِعها بالذاكرة.

تُوفِّر جافا أصنافًا كثيرة ذات مُعاملات غَيْر مُحدَّدة النوع (parameterized classes) لتمثيل هياكل البيانات المختلفة (data structure)، وتُشكِّل تلك الأصناف إطار جافا للتجميعات (Java Collection Framework). لقد ناقشنا هنا الصَنْف ArrayList فقط، ولكننا سنُعود لمناقشة هذا الموضوع على نحو أكثر تفصيلًا بالفصل 10.

ملحوظة: يُستخدَم الصَنْف ArrayList أيضًا بشكل عادي بدون مُعاملات غَيْر مُحدَّدة النوع (non-parametrized) أي يُمكنِنا أن نُصرِّح (declare) عن مُتْغيرِّات، ونُنشِئ كائنات من النوع ArrayList كالتالي:

ArrayList list = new ArrayList();

يُكافِئ ذلك التّصرِيح عن مُتْغيٍّر list من النوع ArrayList<Object>‎. يَعنِي ذلك أن list يُمكِنه أن يَحمِل أي كائن ينتمي إلى صَنْف فرعي من Object. ولأن أي صَنْف هو بالنهاية صَنْف فرعي (subclass) من Object، فإنه من الممكن إضافة أي كائن (object) إلى list.

الأصناف المُغلِّفة (Wrapper Classes)

كما أوضحنا مُسْبَقًا، لا تتوافق الأنواع ذات المعاملات غير محدَّدة النوع (parameterized types) مع الأنواع الأساسية (primitive types) أي لا يُمكِنك مثلًا أن تَستخدِم شيئًا مثل ArrayList<int>‎. مع ذلك، نظرًا لتوفُّر أصناف مُغلِّفة (wrapper classes) مثل Integer و Character، فلربما الأمر ليس مُقيَدًا تمامًا.

لقد تَعرضنا بالقسم 2.5 للأصناف Double و Integer. تُعرِّف تلك الأصناف التوابع الساكنة Double.parseDouble()‎ و Integer.parseInteger()‎ المُستخدَمة لتَحْوِيل سِلسِلة نصية (string) إلى قيمة عددية. تَتَضمَّن تلك الأصناف أيضًا ثوابتًا (constants) مثل Integer.MAX_VALUE و Double.NaN. لقد تَعرضنا أيضًا للصَنْف Character ببعض الأمثلة. يُعرِّف ذلك الصَنْف التابع الساكن Character.isLetter()‎ المُستخدَم لفْحَص ما إذا كانت قيمة معينة من النوع char عبارة عن حرف أبجدي (letter) أم لا. تَتوفَّر في الواقع أصناف مشابهة لكل نوع أساسي (primitive type) مثل Long و Short و Byte و Float و Boolean. تُعدّ جميع تلك الأصناف أصنافًا مُغلِّفة (wrapper classes)، وعلى الرغم من أنها تَحوِي بعض الأعضاء الساكنة (static members) المفيدة عمومًا، فإنها تُستخدَم أيضًا لغرض آخر: تَمثيِل الأنواع الأساسية ككائنات (objects).

تذكَّر دومًا أن الأنواع الأساسية ليست أصنافًا (classes)، وأن قيم تلك الأنواع ليست كائنات (objects). مع ذلك، قد يَكُون من المفيد أحيانًا التَعامُل مع قيمة من نوع أساسي كما لو كانت كائنًا (object)، فمثلًا قد نرغب بتَخْزِين قيمة من نوع أساسي (primitive type) داخل قائمة من النوع ArrayList. لا نستطيع في الواقع فِعِل ذلك حرفيًا، ولكن يُمكِننا التَحايُل على ذلك قليلًا بتَغْليف (wrap) تلك القيمة داخل كائن ينتمي إلى صَنْف مُغلِّف (wrapper classes).

على سبيل المثال، يحتوي أي كائن من النوع Double على مُتْغيِّر نُسخة (instance variable) وحيد من النوع double. يَعمَل ذلك الكائن بمثابة مُغلِّف (wrapper) للقيمة العددية. يُمكِنك إذًا أن تُنشِئ كائنًا (object) لتَغليف قيمة من النوع double مثل 6.0221415e23 كالتالي:

Double d = new Double(6.0221415e23);

في الواقع، يَحتوِي d على نفس المعلومات التي تَحتوِيها قيمة من النوع double، ولكنه كائن (object). يُمكِنك أن تَستدِعي d.doubleValue()‎ لاسترجاع القيمة العددية المُغلَّفة داخل الكائن. بالمثل، يُمكِنك أن تُغلِّف قيمة من النوع int ضِمْن كائن من النوع Integer أو قيمة من النوع boolean ضِمْن كائن من النوع Boolean، وهكذا.

إذا كنت تريد أن تُنشِئ كائنًًا من النوع Double لتَغْلِيف قيمة عددية x، يُفضَّل أن تَستخدِم التابع الساكن Double.valueOf(x)‎ بدلًا من أن تَستدعِي الباني new Double(x)‎؛ لأن استدعاء التابع Double.valueOf()‎ بنفس قيمة المُعامل (parameter) أكثر من مرة دائمًا ما يُعيِد نفس ذات الكائن. تحديدًا، بَعْد أول استدعاء لذلك التابع بقيمة مُعامِل معينة، فإنه سيُعيد نفس ذلك الكائن بالاستدعاءات المتتالية لنفس قيمة المُعامل. لا يُعدّ ذلك مشكلة كما قد تَظّن؛ لأن الكائنات من النوع Double غَيْر قابلة للتَعْدِيل (immutable) أي أن الكائنات التي لها نفس القيمة المبدئية ستَظِلّ دائمًا متطابقة. يُعدّ التابع Double.valueOf تابعًا مُصنِّعًا (factory method) مثل تلك التوابع التي تَعرَّضنا لها بالقسم 6.2 أثناء تَعامُلنا مع الصَنْفين Color و Font، وتحتوي جميع الأصناف المُغلِّفة عمومًا على تابع مُصنِّع مشابه مثل Character.valueOf(ch)‎ و Integer.valueOf(n)‎.

يَتَوفَّر أيضًا تحويل أتوماتيكي بين كل نوع أساسي (primitive type) وصَنْفه المُغلِّف (wrapper class) لتسهيل الاِستخدَام. على سبيل المثال، إذا كنت تَستخدِم قيمة من النوع int ضِمْن سياق يَتَطلَّب كائنًا (object) من النوع Integer، يُمكِنك أن تُغلِّف تلك القيمة ضِمْن كائن من النوع Integer أتوماتيكيًا كالتالي:

Integer answer = 42;

سيقرأ الحاسوب التَعْليمَة بالأعلى كما لو كانت مَكْتُوبة كالتالي:

Integer answer = Integer.valueOf(42);

يُطلَق على ذلك اسم "التغليف الأوتوماتيكي (autoboxing)"، ويَعمَل من الجهة الآخرى أيضًا. فمثلًا، إذا كان d يُشير إلى كائن من النوع Double، يُمكِنك أن تَستخدِم d بتعبير عددي (numerical expression) مثل 2*d. تُفَك (unboxing) القيمة العددية داخل d أتوماتيكيًا، ويُحسَب حاصل ضربها مع العدد 2. كثيرًا ما يَسمَح لك التَغْلِيف الأتوماتيكي (autoboxing) وفكه بتَجاهُل الفارق بين الأنواع الأساسية (primitive types) والكائنات (objects).

يُعدّ ما سبق صحيحًا فيما يَتَعلَّق بالأنواع ذات المعاملات غَيْر مُحدَّدة النوع (parameterized types). على الرغم من عدم توفُّر النوع ArrayList<int>‎، يَتَوفَّر ArrayList<Integer>‎ حيث تَحمِل مصفوفة من ذلك النوع كائنات من النوع Integer التي تُمثِل مُجرّد قيمة من النوع int ضِمْن مُغلِّف صغير. لنَفْترِض أن لدينا كائن (object) من النوع ArrayList<Integer>‎، اُنظر التالي:

ArrayList<Integer> integerList;
integerList = new ArrayList<Integer>();

يُمكِننا الآن أن نُضيف كائنًا مُمثلًا للعدد 42 مثلًا إلى integerList كالتالي:

integerList.add( Integer.valueOf(42) );

أو قد نعتمد على التَغْلِيف الأتوماتيكي (autoboxing) كالتالي:

integerList.add( 42 );

سيُغلِّف المُصرِّف (compiler) العدد 42 أتوماتيكيًا داخل كائن (object) من النوع Integer قبل إضافته إلى القائمة. بالمثل، يُمكِننا كتابة التالي:

int num = integerList.get(3);

يُعيد التابع integerList.get(3)‎ قيمة من النوع Integer، ولكن بِفَضل خاصية فك التَغْلِيف (unboxing)، سيُحوِّل المُصرِّف (compiler) القيمة المُعادة (return value) أتوماتيكيًا إلى قيمة من النوع int كما لو كنا قد كتبنا ما يلي:

int num = integerList.get(3).intValue();

نستطيع إذًا أن نَستخدِم المصفوفة integerList كما لو كانت مصفوفة ديناميكية (dynamic array) من النوع int لا من النوع Integer. وفي العموم، يَنطبِق نفس الأمر على القوائم (lists) من الأصناف المُغلِّفة الآخرى مثل ArrayList<Double>‎ و ArrayList<Character>‎. يَتَبقَّى لنا مشكلة أخيرة: يُمكِن لأي قائمة أن تَحمِل القيمة null، ولكن لا تَتَوفَّر قيمة من النوع الأساسي (primitive type) مناظرة للقيمة null. وبالتالي، إذا أعاد استدعاء مثل integerList.get(3)‎ ضِمْن التَعْليمَة int num = integerList.get(3);‎ القيمة null، سيَحدُث اِعتراض مُتعلِّق بوجود مُؤشر فارغ (null pointer). ينبغي إذًا أن تَأخُذ ذلك بالحسبان إذا لم تَكُن متأكدًا بشأن وجود قيم فارغة ضِمْن القائمة.

البرمجة باستخدام ArrayList

كمثال بسيط، سنُعيِد كتابة البرنامج ReverseWithDynamicArray.java من القسم السابق باِستخدَام النوع ArrayList بدلًا من الصَنْف المُخصَّص (custom) الذي كنا قد كتبناه. نظرًا لأننا سنُخزِّن أعدادً صحيحة (integers) ضِمْن القائمة، سنَستخدِم إذًا النوع ArrayList<Integer>‎. اُنظر شيفرة البرنامج بالكامل:

import textio.TextIO;
import java.util.ArrayList;

public class ReverseWithArrayList {

    public static void main(String[] args) {
        ArrayList<Integer> list;
        list = new ArrayList<Integer>();
        System.out.println("Enter some non-zero integers.  Enter 0 to end.");
        while (true) {
            System.out.print("? ");
            int number = TextIO.getlnInt();
            if (number == 0)
                break;
            list.add(number);
        }
        System.out.println();
        System.out.println("Your numbers in reverse are:");
        for (int i = list.size() - 1; i >= 0; i--) {
            System.out.printf("%10d%n", list.get(i));
        }
    }

}

كما أوضحنا مُسْبَقًا، عادةً ما تُستخدَم حَلْقة التَكْرار for لمعالجة المصفوفات الديناميكية من النوع ArrayList بنفس طريقة مُعالجة المصفوفات العادية. على سبيل المثال، تَطبَع حَلْقة التَكْرار (loop) التالية جميع العناصر بالمصفوفة namelist من النوع ArrayList<String>‎:

for ( int i = 0; i < namelist.size(); i++ ) {
    String item = namelist.get(i);
    System.out.println(item);
}

يُمكِنك أيضًا أن تَستخدِم حَلْقة التَكْرار for-each مع المصفوفات من النوع ArrayList كالتالي:

for ( String item : namelist ) {
    System.out.println(item);
}

عند التَعامُل مع الأصناف المُغلِّفة (wrapper classes)، يُمكن للمُتْغيِّر المُتحكِّم بحَلْقة التَكْرار for-each أن يَكُون من النوع الأساسي (primitive type) بفضل خاصية فك التغليف (unboxing). على سبيل المثال، إذا كان numbers مُتْغيِّر من النوع ArrayList<Double>‎، يُمكِنك أن تَستخدِم حَلْقة التَكْرار التالية لحِسَاب حاصل مجموع القيم بالقائمة:

double sum = 0;
for ( double num : numbers ) {
   sum = sum + num;
}

ستَعمَل الشيفرة بالأعلى طالما لم يَكُن هناك أي عنصر ضِمْن القائمة مُساوِي للقيمة null. إذا كان هنالك احتمالية لحُدوث ذلك، فينبغي أن تَستخدِم مُتْغيِّرًا مُتحكِّمًا بالحَلْقة (loop control variable) من النوع Double ثُمَّ تَفْحَص ما إذا كانت قيمته فارغة أم لا. على سبيل المثال، تَحسِب الشيفرة التالية حاصل مجموع القيم غَيْر الفارغة بالقائمة:

double sum;
for ( Double num : numbers ) {
    if ( num != null ) {
        // يتم فك التغليف للحصول على قيمة‫ double
        sum = sum + num;  
    }
}

سنَفْحَص الآن البرنامج SimplePaint2.java الذي يُعدّ نسخة مُحسَّنة من البرنامج SimplePaint.java الذي كتبناه بالقسم الفرعي 6.3.3. بالبرنامج الجديد، يستطيع المُستخدِم أن يَرسِم منحنيات داخل مساحة رسم (drawing area) بالنَقْر على زر الفأرة والسَحب كما يستطيع أن يختار كُلًا من اللون المُستخدَم للرسم ولون خلفية مساحة الرسم من قائمة. تحتوي أيضًا قائمة "Control" على عدة أوامر منها: الأمر "Undo" المُستخدَم لحَذْف آخر منحنى رسمه المُستخدِم على الشاشة، والأمر "Clear" المُستخدَم لحَذْف جميع المنحنيات. يَتَوفَّر أيضًا مربع الاختيار "Use Symmetry" المسئول عن تَفْعِيل خاصية التماثلية أو تَعْطِيلها. تَنعكِس المنحنيات التي يَرسِمها المُستخدِم أثناء تَفْعِيل تلك الخاصية أفقيًا ورأسيًا لتُنتِج نمطًا متماثلًا.

بخلاف البرنامج الأصلي SimplePaint، تَستخدِم النسخة الجديدة هيكلًا بيانيًا (data structure) لتَخْزِين عدة معلومات عما رَسمه المُستخدِم. عندما يختار المُستخدِم لون خلفية جديد، تُملَئ الحاوية (canvas) بذلك اللون ثم يُعاد رَسْم جميع المنحنيات مجددًا على الخلفية الجديدة، ولذلك لابُدّ أن نُخزِّن كل المعلومات اللازمة لإعادة رَسْم تلك المنحنيات. بالمثل، عندما يختار المُستخدِم الأمر "Undo"، تُحَذَف بيانات آخر منحنى رسمه المُستخدِم ثُمَّ يُعاد رَسْم الصورة بالكامل مُجددًا بالاعتماد على البيانات المُتبقية.

سنعتمد في العموم على الهيكل البياني ArrayList لتَخْزِين تلك البيانات. تَتَكوَّن البيانات الأساسية لأي منحنى من قائمة من النقط الواقعة على المنحنى، والتي سنُخزِّنها بكائن من النوع ArrayList<Point2D>‎. لاحِظ أن الصَنْف Point2D هو صَنْف قياسي (standard) مُعرَّف بحزمة javafx.geometry، ويُمكِننا أن نُنشِئ كائنًا منه باِستخدَام قيمتين من النوع double يُمثِلان الإحداثي x والإحداثي y. يَمتلك أي كائن من النوع Point2D تابعي جَلْب pt.getX()‎ و pt.getY()‎ لاسترجاع قيمة x و y. إلى جانب ذلك، سنحتاج إلى مَعرِفة لون المنحنى، وما إذا كان ينبغي تطبيق خاصية التماثلية عليه أم لا. سنُخزِّن جميع البيانات المطلوبة لرَسْم منحنى ضِمْن كائن من النوع CurveData، والذي سنُعرِّفه كصَنْف مُتْدِاخل (nested class) بالبرنامج:

private static class CurveData {
   Color color;  // لون المنحنى
   boolean symmetric;  // خاصية التماثلية
   ArrayList<Point2D> points;  // نقاط المنحنى
}

نظرًا لأن الصورة قد تَحتوِي على عدة منحنيات وليس فقط منحنى وحيد، ولأننا نحتاج إلى تَخْزِين كل البيانات الضرورية لإعادة رَسْم الصورة بالكامل، سنحتاج إذًا إلى قائمة من الكائنات من النوع CurveData. سيَستخدِم البرنامج المُتْغيِّر curves من النوع ArrayList لذلك الغرض، وسنُصرِّح عنه كالتالي:

ArrayList<CurveData> curves = new ArrayList<CurveData>();

لدينا هنا قائمة من الكائنات (objects)، ويَحتوِي كل كائن منها على قائمة من النقط كجزء من البيانات المُعرَّفة بداخله. سنَفْحَص الآن عدة أمثلة على معالجة ذلك الهيكل البياني (data structure). أولًا، عندما يَنقُر المُستخدِم بزر الفأرة على مساحة الرسم (drawing surface)، يَعنِي ذلك أنه يَرسِم منحنى جديدًا، ولذلك ينبغي أن نُنشِئ كائنًا جديدًا من النوع CurveData، ونُهيئ جميع مُتْغيِّرات النُسخ (instance variables) المُعرَّفة بداخله. بَفْرَض أن currentCurve هو مُتْغيِّر عام (global) من النوع CurveData، يُمكِننا تعريف البرنامج mousePressed()‎ كالتالي:

currentCurve = new CurveData();       // ‫أنشئ كائن من النوع CurveData

// ‫يُنسخ اللون المستخدم لرسم المنحنى من متغير النسخة الممثل للون 
// المستخدم للرسم
currentCurve.color = currentColor;    

// ‫تنسخ خاصية التماثلية أيضًا من القيمة الحالية للمتغير useSymmetry
currentCurve.symmetric = useSymmetry; 

currentCurve.points = new ArrayList<Point2D>();  // A new point list object.

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

curves.add( currentCurve );

عندما يُغيِّر المُستخدِم لون الخلفية أو يختار الأمر "Undo"، ينبغي أن نُعيِد رَسْم الصورة. يَحتوِي البرنامج على التابع redraw()‎ المسئول عن إعادة رَسْم الصورة بالكامل. يَعتمِد التابع على البيانات الموجودة بالمُتْغيِّر curves لإعادة رَسْم جميع المنحنيات، ويَستخدِم حَلْقة تَكْرار for-each لمعالجة بيانات كل منحنى على حدى كالتالي:

for ( CurveData curve : curves ) {
   .
       // ‫ارسم المنحنى الذي يمثله الكائن curve من النوع CurveData
   .  
}

لاحِظ أن curve.points عبارة عن مُتْغيِّر من النوع ArrayList<Point2D>‎ أي عبارة عن قائمة من النقط الواقعة على المنحنى. يُمكِننا على سبيل المثال أن نَسترجِع النقطة i على المنحنى باستدعاء التابع get()‎ المُعرَّف بالقائمة curve.points.get(i)‎. يُعيِد ذلك الاستدعاء قيمة من النوع Point2D التي تُعرِّف بدورها توابع الجَلْب getX()‎ و getY()‎.

يُمكِننا إذًا أن نُشير إلى الإحداثي x للنقطة i على المنحنى مباشرةً كالتالي:

curve.points.get(i).getX()

قد يبدو الاستدعاء السابق مُعقدًا، ولكنه مثال جيد على الأسماء المركبة (complex names). يُخصِّص ذلك الاسم مسارًا إلى جزء من البيانات: اذهب إلى الكائن curve. بداخل ذلك الكائن، إذهب إلى points. بداخل points، إذهب إلى العنصر برقم المَوْضِع i. من هذا العنصر، اِسترجِع الإحداثي x من خلال استدعاء تابعه getX()‎. اُنظر تعريف التابع redraw()‎ بالكامل:

private void redraw() {
    g.setFill(backgroundColor);
    g.fillRect(0,0,canvas.getWidth(),canvas.getHeight());
    for ( CurveData curve : curves ) {
        g.setStroke(curve.color);
        for (int i = 1; i < curve.points.size(); i++) {
            // ‫ارسم قطعة مستقيمة من رقم الموضع i-1 إلى رقم الموضع i
            double x1 = curve.points.get(i-1).getX();
            double y1 = curve.points.get(i-1).getY();
            double x2 = curve.points.get(i).getX();
            double y2 = curve.points.get(i).getY();
            drawSegment(curve.symmetric,x1,y1,x2,y2);
        }
    }
}

يَرسِم التابع drawSegment()‎ قطعة مستقيمة من (x1,y1) إلى (x2,y2). بالإضافة إلى ذلك، إذا كان المُعامل (parameter) الأول يُساوِي true، فإنه أيضًا يَرسِم انعكاسًا أفقيًا ورأسيًا لتلك القطعة.

لقد رَكَّزنا هنا على اِستخدَام الصَنْف ArrayList ضِمْن البرنامج، ولكن يُفضَّل بالطبع أن تَتَطلِع على الشيفرة الكاملة للبرنامج SimplePaint2.java. بالإضافة إلى كَوْنه مثال على اِستخدَام الأنواع ذات المُعاملات غَيْر محدَّدة النوع (parameterized types)، فإنه يُعدّ أيضًا مثالًا جيدًا على إنشاء القوائم (menus) واِستخدَامها. ينبغي عمومًا أن تَكُون قادرًا على فهم البرنامج بالكامل.

ترجمة -بتصرّف- للقسم Section 3: ArrayList من فصل Chapter 7: Arrays and ArrayLists من كتاب Introduction to Programming Using Java.

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

أمثلة على المعالجة

لابُدّ أن تكون حريصًا فيما يتعلَّق بالفهارس من خارج نطاق المصفوفة. لنَفْترِض مثلًا أن lines عبارة عن مصفوفة من النوع String[]‎، وأننا نريد مَعرِفة ما إذا كانت تلك المصفوفة تحتوي على أية عناصر مكررة بموضعين متتاليين. ينبغي إذًا أن نَفْحَص الاختبار lines.equals(lines[i+1])‎ لأي فهرس i. اُنظر المحاولة الخاطئة التالية:

boolean dupp = false;  // Assume there are no duplicates
for ( int i = 0; i < list.length; i++ ) {
    if ( lines[i].equals(lines[i+1]) ) {  // THERE IS AN ERROR HERE!
        dupp = true;   // we have found a duplicate!
        break;
    }
}

تبدو حلقة التكرار for بالأعلى مثل الكثير من الحلقات التي تعرضنا لها من قبل، لذلك ما هي المشكلة إذًا؟ يحدث الخطأ عندما تسند القيمة النهائية إلى i بالحلقة أي عندما i تساوي lines.length-1. في هذه الحالة، i+1 تساوي lines.length. لكن فهرس العنصر الأخير بالمصفوفة هو lines.length-1، لذلك lines.length ليست فهرس صالح. يعني ذلك أن lines[i+1]‎ يتسبب بحدوث اعتراض من النوع ArrayIndexOutOfBoundsException. يمكنك إصلاح ذلك بسهولة عن طريق إيقاف حلقة التكرار قبل i+1 من النطاق المسموح به، كالتالي:

boolean dupp = false;  // Assume there are no duplicates
for ( int i = 0; i < list.length - 1 ; i++ ) {
    if ( lines[i].equals(lines[i+1]) ) { 
        dupp = true;   // we have found a duplicate!
        break;
    }
}

يظهر أحيانًا نوع شبيه من الأخطاء عند العمل مع المصفوفات المملوءة جزئيًا (partially full arrays) -اُنظر القسم الفرعي 3.8.4-، ولكنه قد لا يَكُون بهذا الوضوح. إذا كان جزء معين فقط من المصفوفة مملوءًا بحيث يُستخدَم عداد (counter) لمعرفة عدد الخانات المُستخدَمة فعليًا ضِمْن تلك المصفوفة. لا تتعلَّق المشكلة في تلك الحالة بمحاولة الوصول لعنصر بموضع خارج المصفوفة ولكنها تتعلق بفحص جزء من المصفوفة قيد الاستخدام بالفعل. عندما يُحاوِل البرنامج الوصول إلى مَوْضِع خارج المصفوفة، ينهار (crash) البرنامج على الأقل مما يَسمَح لك برصد المشكلة لكن في حالة المصفوفات المملوءة جزئيًا، لن تتمكن من رصد الخطأ بسهولة.

لقد رأينا الكيفية التي يُمكِننا بها أن نُضيف عناصر إلى مصفوفة مملوءة جزئيًا، ولكننا لم نَتعرَّض لطريقة حَذْف تلك العناصر؟ لنَفْترِض مثلًا أننا نَكْتُب برنامجًا عبارة عن لعبة يستطيع اللاعبون الانضمام إليها ومغادرتها بأي وقت. يُمكِننا إذًا أن نُنشِئ الصَنْف Player لتمثيل كل لاعب موجود باللعبة. سنُخزِّن بطبيعة الحال قائمة اللاعبين الموجودين باللعبة داخل مصفوفة من النوع Player[]‎، وليَكُن اسمها هو playerList. نظرًا لأن عدد اللاعبين قد يَتَغيَّر بأي وقت، سنُطبِق نمط المصفوفة المملوءة جزئيًا، لذا سنُعرِّف مُتغيِّر playerCt لتَخْزِين عدد اللاعبين الموجودين باللعبة. بفَرْض عدم احتمالية وجود أكثر من 10 لاعبين بأي لحظة، يُمكِننا إذًا أن نُصرِّح عن المُتْغيِّرات كالتالي:

Player[] playerList = new Player[10];  // Up to 10 players.
int      playerCt = 0;  // At the start, there are no players.

بَعْد انضمام بعض اللاعبين إلى اللعبة، سيُصبِح المُتْغيِّر playerCt أكبر من الصفر كما ستُخزَّن الكائنات (objects) المُمثِلة للاعبين داخل عناصر المصفوفة playerList[0]‎ و playerList[1]‎ .. وحتى playerList[playerCt-1]‎. لاحِظ أننا لم نُشِر إلى العنصر playerList[playerCt]‎. يُمثِل المُتْغيِّر playerCt كُلًا من عدد العناصر الفعلية الموجودة داخل المصفوفة، وكذلك فهرس (index) الخانة التالية المتاحة بالمصفوفة. تُضيِف الشيفرة التالية كائنًا جديدًا newPlayer إلى اللعبة:

playerList[playerCt] = newPlayer; // Put new player in next
                                  //     available spot.
playerCt++;  // And increment playerCt to count the new player.

في المقابل، قد يَكُون حَذْف لاعب من اللعبة أصعب قليلًا، لأننا لا نُريد بالطبع أن نَترُك مَوْضِع اللاعب المطلوب حَذْفه فارغًا. لنَفْترِض مثلًا أننا نُريد حَذْف اللاعب الموجود بالفهرس k داخل المصفوفة playerList. يَعنِي ذلك أن عدد الخانات المُستخدَمة فعليًا بالمصفوفة سيُصبِح أقل بمقدار الواحد. إذا لم يَكُن ترتيب اللاعبين داخل المصفوفة مُهِمًا، يُمكنِنا إذًا أن نَنقِل اللاعب الأخير الموجود فعليًا داخل المصفوفة إلى المَوْضِع k ثُمَّ نُنقِص قيمة playerCt بمقدار الواحد كالتالي:

playerList[k] = playerList[playerCt - 1];
playerCt--;

لم يَعُد اللاعب الذي كان موجودًا مُسْبَقًا بالمَوْضِع k موجودًا بالمصفوفة، فقد حَذْفناه ببساطة من القائمة. في المقابل، أصبح اللاعب الذي كان موجودًا مُسْبَقًا بالموضع playerCt - 1 موجودًا بالمصفوفة مرتين، ولكن نظرًا لأننا انقصنا المُتْغيِّر playerCt بمقدار الواحد، فإن واحدة منهما فقط تَقَع ضِمْن الجزء المُستخدَم فعليًا بالمصفوفة. يَحمِل أي عنصر بالمصفوفة في العموم قيمة ما، ولكن القيم من الموضع 0 وحتى playerCt - 1 هي فقط الصالحة أي يُمكِننا معالجتها. حاول أن تُفكِر بما سيَحدُث إذا كان اللاعب المطلوب حَذْفه هو اللاعب الأخير بالمصفوفة، وهل ترى أن الشيفرة بالأعلى ستَظِل صالحة؟

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

for (int i = k+1; i < playerCt; i++) {
    playerList[i-1] = playerList[i];
}
playerCt--;

تُوضِح الصورة التالية طريقتي حَذْف عنصر -اللاعب "C" تحديدًا- من مصفوفة مملوءة جزئيًا (partially full array):

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

لنَفْترِض أن A و B عبارة عن مُتْغيِّري مصفوفة (array variables) لهما نفس النوع الأساسي (base type). تُشير A بالفعل إلى مصفوفة، ونريد الآن جَعْل B تُشيِر إلى نُسخة من A. أول ما ينبغي أن تُدركه هو أن تَعْليمَة الإِسْناد (assignment statement) التالية:

B = A;

لا تُنشِئ نسخة من A. نظرًا لأن المصفوفات عبارة عن كائنات (objects)، يَحمِل أي مُتْغيِّر مصفوفة (array variable) -إن لم يَكُن فارغًا- مؤشِرًا (pointer) إلى مصفوفة. تَنَسَخ تَعْليمَة الإِسْناد (assignment) بالأعلى ذلك المُؤشر من A إلى B، وبالتالي سيُشيِر كُلًا من A و B إلى نفس ذات المصفوفة، فيُعدّ مثلًا كُلًا من A[0]‎ و B[0]‎ أسماءً مختلفة لنفس عناصر المصفوفة (array element). في المقابل، إذا كنا نريد جَعْل B يُشيِر إلى نسخة من A، ينبغي إذًا أن نُنشِئ مصفوفة جديدة كليًا ثُمَّ نَنَسخ العناصر من A إلى B. بِفَرض أن A و B من النوع double[]‎، يُمكِننا إذًا كتابة ما يَلي لإنشاء نسخة من A:

double[] B;
B = new double[A.length];  // Make a new array with the same length as A.
for ( int i = 0; i < A.length; i++ ) {
    B[i] = A[i];
}

لكي نَتَمكَّن من إضافة عناصر جديدة إلى مصفوفة مملوءة جزئيًا (partially full array) ممتلئة، ينبغي أن نُنشِئ مصفوفة جديدة أكبر، وعادةً ما تَكُون بحجم يُساوِي ضعف المصفوفة الحالية. لما كان مُتْغيِّر المصفوفة هو ما يَسمَح لنا بالوصول إلى البيانات التي أصبحت موجودة بالمصفوفة الجديدة، ينبغي إذًا أن نُعدِّل ذلك المُتْغيِّر لكي يُشير إلى المصفوفة الجديدة. يُمكِننا أن نُجرِي ذلك لحسن الحظ بتَعْليمَة إِسْناد (assignment statement) بسيطة. بِفَرْض اِستخدَام playerList و playerCt لتَخْزِين اللاعبين باللعبة -كالمثال بالأعلى-، تُوضِح الشيفرة التالية طريقة إضافة لاعب جديد newPlayer إلى اللعبة حتى لو كانت المصفوفة playerList ممتلئة:

if ( playerCt == playerList.length ) {
        // The number of players is already equal to the size of the array.
        // The array is full.  Make a new array that has more space.
    Player[] temp;   // A variable to point to the new array.
    temp = new Player[ 2*playerList.length ];  // Twice as big as the old array.
    for ( int i = 0; i < playerList.length; i++ ) {
        temp[i] = playerList[i];  // Copy item from old array into new array.
    }
    playerList = temp;  // playerList now points to the new, bigger array.    
}
// At this point, we know that there is room in the array for newPlayer.
playerList[playerCt] = newPlayer;
playerCt++;