خوارزميات Grocking أو مقدمة غير مؤلمة للخوارزميات

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

"خوارزميات Grocking" أو مقدمة غير مؤلمة للخوارزميات

مقدمة

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

خوارزميات جروك

من بين جميع الأعمال، صادفت كتابًا باسم "Grocking Algorithms". يمكنك معرفة المزيد هنا: " كتاب "الخوارزميات المتنامية. دليل مصور للمبرمجين وعشاق الفضول ". لقد لاحظت الكتاب منذ فترة طويلة، ولكن على الأوزون يكلف 680 روبل. باهظة الثمن أو رخيصة - الجميع يقرر بنفسه. أنا بالفعل أشتري الكتاب الثاني عن Avito بنصف السعر. لذلك وجدته في سانت بطرسبرغ، واشتريته، وذهبت للتنزه. وهو ما قررت أن أشارككم به. نعم، لا يوجد كود Java في الكتاب، ولكن يوجد... كود آخر، ولكن المزيد عن ذلك لاحقًا.

مقدمة إلى الخوارزميات (فرز التحديد)

لذلك، في شكل سرد سهل، نصل إلى الترتيب الأول في أدائنا. هذا هو فرز التحديد. جوهرها هو أننا ننتقل عبر العناصر من اليسار إلى اليمين (من 0 عنصر إلى الأخير)، ونبحث عن الأكبر بين العناصر المتبقية. فإذا وجدناه فإننا نستبدل العنصر الذي نحن عليه الآن والعنصر الأكبر. إن أبسط طريقة للتفكير أولاً في المصفوفة هي: [5، 3، 6، 2، 10]. خذ قطعة من الورق، قلمًا (أبسط طريقة وأكثرها تكلفة) وتخيل كيف لدينا حد أيسر (يسار)، فهرس حالي (أو حد يمين)، يوجد فهرس للحد الأدنى من العناصر. وكيف نعمل معها. على سبيل المثال: غالبًا ما يتم وصف الخوارزميات بالكود الزائف، على سبيل المثال، في ويكيبيديا. إن كودنا ليس كودًا زائفًا تمامًا، ولكن سنتحدث عن ذلك لاحقًا. الآن دعونا نرى:

def selectionSort(array):
    for left in range(0, len(array)):
        minIndex = left
        for right in range (left+1, len(array)):
            if array[right] < array[minIndex]:
                minIndex = right
        if minIndex != left:
            temp = array[left]
            array[left] = array[minIndex]
            array[minIndex] = temp
    return array

print(selectionSort([5, 3, 6, 2, 10]))

الآن دعونا نقدمها في شكل كود جافا:

public static void selectionSort(int[] array) {
        for (int left = 0; left < array.length; left++) {
            int minIndex = left;
            for (int right = left+1; right < array.length; right++) {
                if (array[right] < array[minIndex]) {
                    minIndex = right;
                }
            }
            if (minIndex != left) {
                int temp = array[left];
                array[left] = array[minIndex];
                array[minIndex] = temp;
            }
        }
}

كما ترون، الرمز هو نفسه تقريبا. الكود الأول هو مثال من الكتاب. والثاني هو التنفيذ المجاني لكود Java.

العودية

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

def euclidean(a, b):
    if a == 0 : return b
    if b == 0 : return a
    return euclidean (b, a % b)

دعونا نكتب نفس الكود في جافا. إذا رغبت في ذلك، يمكننا استخدام المترجم عبر الإنترنت :

public static int euclid(int a, int b) {
        if (a == 0) return b;
        if (b == 0) return a;
        return euclid(b, a%b);
}

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

فرز سريع

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

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i <= pivot]
        greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

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

• يجب أن نكون قادرين على تبديل العناصر في المصفوفة:

  private static void swap(int[] array, int firstIndex, int secondIndex) {
          int temp = array[firstIndex];
          array[firstIndex] = array[secondIndex];
          array[secondIndex] = temp;
  }




• نحتاج إلى طريقة تقسم المصفوفة في الفاصل الزمني المحدد إلى 3 أجزاء

  
  

  private static int partition(int[] array, int left, int right) {
          int pivot = array[(right + left) / 2];
          while (left <= right) {
              while (array[left] < pivot) {
                  left++;
              }
              while (array[right] > pivot) {
                  right--;
              }
              if (left <= right) {
                  swap(array, left, right);
                  left++;
                  right--;
              }
          }
          return left;
  }

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

• هناك فصل، ونحن بحاجة إلى الفرز نفسه:

  public static void quickSort(int[] array, int left, int right) {
          int index = 0;
          if (array.length > 1) {
              index = partition(array, left, right);
              if (left < index - 1) {
                  quickSort(array, left, index - 1);
              }
              if (index < right) {
                  quickSort(array, index, right);
              }
          }
  }

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

  و للاختبار:

  public static void main(String []args){
          int[] array = {8,9,3,7,6,7,1};
          quickSort(array, 0, array.length-1);
          System.out.println(Arrays.toString(array));
  }

ويذكر الكتاب أن هذه الخوارزمية تنتمي إلى ما يسمى بخوارزميات “Divide and Conquer”، حيث يتم تقسيم مجموعة البيانات المعالجة إلى نصفين في كل مرة. تعقيد الخوارزمية: O(nLogn) الأمر السيئ (أي ما لم يعجبني) هو أن الكتاب يذكر نوع الدمج بشكل عابر، لكنه لا يقدم أي مثال أو كود. يمكن العثور على مزيد من التفاصيل هنا: " المعلوماتية. خوارزميات البحث والفرز: دمج الفرز ". لذلك، من أجل الاتساق، دعونا نفعل ذلك بأنفسنا. الخوارزمية نفسها، بطبيعة الحال، بسيطة ومباشرة بطبيعتها:

public static void mergeSort(int[] source, int left, int right) {
    if ((right - left) > 1) {
        int middle = (right + left) / 2;
        mergeSort(source, left, middle);
        mergeSort(source, middle + 1, right);
    }
    merge(source, left, right);
}

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

public static void merge(int[] array, int from, int to) {
    int middle = ((from + to) / 2) + 1;
    int left = from;
    int right = middle;
    int cursor = 0;

    int[] tmp = new int[to - from + 1];
    while (left < middle || right <= to) {
        if (left >= middle) {
            tmp[cursor] = array[right];
            System.out.println("Остаток справа: " + array[right]);
            right++;
        } else if (right > to) {
            tmp[cursor] = array[left];
            System.out.println("Остаток слева: " + array[left]);
            left++;
        } else if (array[left] <= array[right]) {
            tmp[cursor] = array[left];
            System.out.println("Слева меньше: " + array[left]);
            left++;
        } else if (array[right] < array[left]) {
            tmp[cursor] = array[right];
            System.out.println("Справа меньше: " + array[right]);
            right++;
        }
        cursor++;
    }
    System.arraycopy(tmp, 0, array, from, tmp.length);
}

ليس هناك الكثير للتعليق عليه هنا. من أسماء المتغيرات printlnكل شيء واضح. حسنا للتحقق:

int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));

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

يتطرق الكتاب أيضًا إلى جداول التجزئة. ليس عليك تنفيذ ذلك بنفسك، وجوهر جداول التجزئة بسيط للغاية. بعد كل شيء، لدى Java أيضًا تطبيق لجداول التجزئة، java.util.HashTable. إذا نظرنا إلى جهاز HashTable، فسنرى أن مصفوفة الإدخال موجودة بداخله. الإدخال هو سجل عبارة عن مزيج من المفتاح - القيمة. يحتوي HashTable على سعة أولية - أي الحجم الأولي. وloadFactor – عامل التحميل. الافتراضي هو 0.75. يخبرك هذا الرقم بمقدار حمل المصفوفة (عدد العناصر/الكمية الإجمالية) الذي يجب زيادة الحجم. في جافا يزيد بمقدار 2 مرات. يشرح الكتاب أن جداول التجزئة تسمى جداول التجزئة لأنه بناءً على وظيفة التجزئة، فإن خلية الصفيف (السلة) التي يوجد بها Entry. يمكنك أيضًا قراءة المزيد هنا: هياكل البيانات في الصور. HashMap و LinkedHashMap . يمكنك أيضًا قراءتها في الكتب. على سبيل المثال هنا: " أساسيات HashTable "

الرسوم البيانية، البحث عن العرض أولاً (البحث عن المسار الأقصر)

ربما يكون أحد المواضيع الأكثر إثارة للاهتمام هو الرسوم البيانية. وهنا، لكي نكون منصفين، يولي الكتاب لهم الكثير من الاهتمام. ربما لهذا السبب يستحق قراءة هذا الكتاب. على الرغم من أنه ربما كان من الممكن ذكر ذلك بشكل أكثر وضوحًا)) ولكن لدينا الإنترنت وبالإضافة إلى الكتاب، يمكنك إلقاء نظرة على قائمة التشغيل هذه حول النظرية "لأولئك الذين يسمعون عن الرسوم البيانية لأول مرة . " حسنًا، بطبيعة الحال، في بداية الكتاب، breadth-first-searchتم تقديم خوارزمية بحث العرض الأول، والمعروفة أيضًا باسم BFS. يحتوي الكتاب على الرسم البياني التالي: يذكر الكتاب أن قائمة الانتظار ستساعدنا. علاوة على ذلك، حتى نتمكن من إضافة عناصر إلى النهاية ومعالجة قائمة الانتظار من البداية. تسمى قوائم الانتظار هذه بقوائم الانتظار ذات الاتجاهين أو Deque باللغة الإنجليزية. يقترح الكتاب استخدام بنية البيانات - جدول التجزئة. لربط الاسم والجيران. مع القمم المرقمة، يمكنك ببساطة استخدام مصفوفة. يُطلق على تخزين القمم هذا اسم "قائمة القمم المجاورة"، وهو ما لم يتم ذكره في الكتاب. وهذا ناقص بالنسبة لهم. دعونا ننفذ هذا في جافا:

private Map<String, String[]> getGraph() {
    Map<String, String[]> map = new HashMap<>();
    map.put("you", new String[]{"alice", "bob", "claire"});
    map.put("bob", new String[]{"anuj", "peggy"});
    map.put("alice", new String[]{"peggy"});
    map.put("claire", new String[]{"thom", "jonny"});
    map.put("annuj", null);
    map.put("peggy", null);
    map.put("thom", null);
    map.put("johny", null);
    return map;
}

الآن البحث نفسه مبني على هذه البيانات:

private String search() {
    Map<String, String[]> graph = getGraph();
    Set<String> searched = new HashSet<>();
    Deque<String> searchQue = new ArrayDeque<>();
    searchQue.add("you");
    while (!searchQue.isEmpty()) {
        String person = searchQue.pollFirst();
        System.out.println(person);
        if (personIsSeller(person)) {
            return person;
        } else {
            String[] friends = graph.get(person);
            if (friends == null) continue;
            for (String friend : friends) {
                if (friend != null && !searched.contains(friend)) {
                    searchQue.addLast(friend);
                }
            }
        }
    }
    return null;
}

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

الرسوم البيانية، خوارزمية ديكسترا

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

public Integer[][] getGraphMatrix(int size) {
    Integer[][] matrix = new Integer[size][size];
    matrix[0][1] = 6;
    matrix[0][2] = 2;
    matrix[2][1] = 3;
    matrix[1][3] = 1;
    matrix[2][3] = 5;
    return matrix;
}

والآن المنطق نفسه:

@Test
public void dijkstra() {
    Integer[][] graph = getGraphMatrix();           // Данные графа
    Integer[] costs = new Integer[graph.length];    // Стоимость перехода
    Integer[] parents = new Integer[graph.length];  // Родительский узел
    BitSet visited = new BitSet(graph.length);      // "Ферма" маркеров посещённости

    Integer w = 0;
    do {
        System.out.println("-> Рассматриваем вершину: " + w);
        Integer min = null;
        for (int i = 0; i < graph.length; i++) {    // Обрабатываем каждую дугу
            if (graph[w][i] == null) continue;      // Дуги нет - идём дальше
            if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
                min = i;
            }
            if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
                System.out.print("Меням вес с " + costs[i]);
                costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
                System.out.println(" на " + costs[i] + " для вершины " + i);
                parents[i] = w;
            }
        }
        System.out.println("Вершина с минимальным весом: " + min);
        visited.set(w);
        w = min;
    } while (w != null);

    System.out.println(Arrays.toString(costs));
    printPath(parents, 3);
}

public void printPath(Integer[] parents, int target) {
    Integer parent = target;
    do {
        System.out.print(parent + " <- ");
        parent = parents[parent];
    } while (parent != null);
}

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

خوارزميات الجشع

القسم التالي مخصص لـ "الخوارزميات الجشعة". هذا القسم مثير للاهتمام لأنه يستخدم مجموعات (java.util.Set). وأخيرا يمكننا أن نرى لماذا قد تكون هناك حاجة إليها. نستخدم قائمة الحالات كمدخل:

Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));

وأيضا قائمة بمحطات الراديو التي تغطي بعض هذه الولايات:

Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));

يستمر الكتاب في الإشارة إلى الخوارزمية نفسها وشرحها:

Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
    String bestStation = null;
    Set<String> statesCovered = new HashSet();
    for (String station: stations.keySet()) {
        Set covered = new HashSet(statesNeeded);
        covered.retainAll(stations.get(station));
        if (covered.size() > statesCovered.size()) {
           bestStation = station;
           statesCovered = covered;
        }
    }
    statesNeeded.removeAll(statesCovered);
    finalStations.add(bestStation);
}
System.out.println(finalStations);

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

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

List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));

الآن الخوارزمية نفسها:

int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
    cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
    for (int j = 0; j < cell[i].length; j++) {
        // Если вещь не влезает - берём прошлый максимум
        if (things.get(i).weight > j+1) {
            cell[i][j] = cell[i - 1][j];
        } else {
            // Иначе текущая стоимость + предыдущий максимум оставшегося размера
            cell[i][j] = things.get(i).cost;
            if (j + 1 - things.get(i).weight > 0) {
                cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
            }
        }
    }
}
System.out.println(Arrays.deepToString(cell));

هناك أيضًا مهمة مثيرة للاهتمام للعثور على الكلمات الأكثر تشابهًا. مثير للاهتمام، أليس كذلك؟ مزيد من التفاصيل هنا: LongestCommonSubsequence.java

البحث عن أقرب الجيران

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

الحد الأدنى

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

بالإضافة إلى ذلك

يمكنك أيضًا الاطلاع على الموارد التالية حول هذا الموضوع:

1. EdX - مقدمة إلى برمجة Java: هياكل البيانات الأساسية والخوارزميات
2. LinkedIn - مقدمة إلى هياكل البيانات والخوارزميات في Java (مدفوعة)
3. 27 موقعًا به ألغاز لصقل مهاراتك في البرمجة
4. جافا كودينغ بات
5. مهام للمبرمجين، إجابات على مهام متفاوتة التعقيد

# فياتشيسلاف