אלגוריתמי גרוק או מבוא ללא כאבים לאלגוריתמים

סקירה על הספר "אלגוריתמים גרושים". קצת דעה אישית, כמה דוגמאות. אני מקווה שסקירה זו תעזור לך להבין אם אתה רוצה לקרוא את הספר הזה או שהוא לא יתפוס את מקומו על המדף שלך. אזהרה: הרבה טקסט)

"אלגוריתמים מטלטלים" או מבוא ללא כאבים לאלגוריתמים

מבוא

כמעט לכל משרה פנויה ברמת ג'וניור יש דרישות כמו "ידע במבני נתונים ואלגוריתמים". לבעלי השכלה מיוחדת, אלגוריתמים כלולים בקורס הכללי ולא אמורות להיות בעיות. אבל מה אם הפיתוח הובא מערבות אחרות? כל מה שנשאר זה ללמוד לבד. יש תשובה לשאלה "מי אשם", אבל לשאלה "מה לעשות" יש לחפש את התשובה. בואו נסתכל בספרים. ואני רוצה לספר לכם על אחד.

אלגוריתמים של גרוק

בין כל היצירות, נתקלתי בספר כזה כמו "אלגוריתמים גרוקים". אתה יכול לגלות עוד כאן: " הספר "אלגוריתמים גדלים. מדריך מאויר למתכנתים ולסקרנים ." שמתי לב לספר מזמן, אבל על אוזון זה עלה 680 רובל. יקר או זול - כל אחד מחליט בעצמו. אני כבר קונה את הספר השני על אביטו בחצי מחיר. אז מצאתי אותו בסנט פטרסבורג, קניתי אותו והלכתי לחטט. וזה מה שהחלטתי לשתף אתכם. כן, אין קוד ג'אווה בספר, אבל יש... קוד אחר, אבל על כך בהמשך.

מבוא לאלגוריתמים (מיון בחירה)

אז, בצורה קלה של קריינות, אנחנו מגיעים למיון הראשון בהופעה שלנו. זהו מיון בחירה. המהות שלו היא שאנחנו עוברים על האלמנטים משמאל לימין (מאלמנט 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]))

עכשיו בואו נציג את זה בצורה של קוד Java:

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, אין צורך למיין אותו. אם הוא גדול יותר, ניקח את האלמנט הראשון של המערך ורואים בו את "אלמנט הציר". אנו יוצרים 2 מערכים חדשים - האחד מכיל אלמנטים גדולים מהציר, והשני מכיל אלמנטים קטנים יותר. ואנחנו חוזרים באופן רקורסיבי. לא האפשרות הטובה ביותר, אבל שוב, זכור טוב יותר. בואו ליישם את האלגוריתם הזה בג'אווה, אבל יותר נכון. החומר מהסקירה " מדעי המחשב ב-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;
  }

  פרטים בקישור למעלה. בקיצור, נעביר את הסמן השמאלי עד שהאלמנט קטן מהציר. באופן דומה, הזז את הסמן הימני מהקצה השני. ואנחנו עושים החלפה אם הסמנים לא תואמים. אנחנו ממשיכים עד שהסמנים מתכנסים. אנו מחזירים אינדקס המחלק את המשך העיבוד ל-2 חלקים.

• יש הפרדה, אנחנו צריכים את המיון עצמו:

  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));
  }

הספר מציין כי אלגוריתם זה שייך למה שנקרא "הפרד וכבש", כאשר מערך הנתונים המעובד מחולק לחצי בכל פעם. מורכבות האלגוריתם: 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));

טבלאות חשיש

הספר נוגע גם בטבלאות חשיש. אתה לא צריך ליישם את זה בעצמך, והמהות של טבלאות חשיש היא די פשוטה. הרי לג'אווה יש גם מימוש של טבלאות hash, java.util.HashTable. אם נסתכל על מכשיר ה-HashTable, נראה שמערך ה-Entry חי בפנים. כניסה היא רשומה שהיא שילוב של מפתח - ערך. ל-HashTable יש initialCapacity - כלומר, הגודל ההתחלתי. ו-loadFactor - גורם עומס. ברירת המחדל היא 0.75. מספר זה אומר לך באיזה עומס של המערך (מספר אלמנטים/מספר כולל) יש להגדיל את הגודל. ב-Java זה גדל פי 2. הספר מסביר שטבלאות Hash נקראות טבלאות Hash כי בהתבסס על פונקציית Hash, תא המערך (סל) שבו ה- Entry. ניתן לקרוא עוד כאן: מבני נתונים בתמונות. HashMap ו- LinkedHashMap . אפשר לקרוא את זה גם בספרים. לדוגמה כאן: " יסודות HashTable "

גרפים, חיפוש רוחב ראשון (חיפוש הנתיב הקצר ביותר)

כנראה אחד הנושאים המעניינים ביותר הוא גרפים. וכאן, למען ההגינות, הספר נותן להם תשומת לב רבה. אולי בגלל זה כדאי לקרוא את הספר הזה. אמנם, אולי, אפשר היה לומר את זה קצת יותר ברור)) אבל, יש לנו אינטרנט ובנוסף לספר, אתה יכול להסתכל על הפלייליסט הזה על התיאוריה עבור "אלה ששומעים על גרפים בפעם הראשונה . ” ובכן, באופן טבעי, ממש בתחילת הספר, breadth-first-searchניתן אלגוריתם החיפוש הראשון, הידוע גם בשם BFS. הספר מכיל את הגרף הבא: בספר נכתב שתור יעזור לנו. יתרה מכך, כזו שנוכל להוסיף אלמנטים לסוף ולעבד את התור מההתחלה. תורים כאלה נקראים דו כיווני queues או Deque באנגלית. הספר מציע להשתמש במבנה נתונים - טבלת hash. לקשר בין השם לבין השכנים. עם קודקודים ממוספרים, אתה יכול פשוט להשתמש במערך. אחסון זה של קודקודים נקרא "רשימת קודקודים סמוכים", שאינה מוזכרת בספר. זה מינוס עבורם. בואו ליישם את זה ב-Java:

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 ואת הגרפים המשוקללים. הגרף הבא מוצע לפתרון: ראשית, עלינו להבין כיצד לייצג את הגרפים שלנו. נוכל לייצג את זה כמטריצה. מאמר על Habré יעזור לנו כאן: האלגוריתם של Dijkstra. מציאת מסלולים אופטימליים בגרף . בואו נשתמש במטריצת הסמיכות:

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);
}

הספר מפרק את זה די צעד אחר צעד. אם תוסיף מאמר על Habré באינטרנט + תסתכל על הקוד, תוכל לזכור אותו. מצאתי את הניתוח שלב אחר שלב קצת עמוס. אבל עבור הטבע צעד אחר צעד עצמו זה יתרון. בסך הכל, בסדר, למרות שזה יכול היה להיות טוב יותר)

אלגוריתמים חמדנים

הסעיף הבא מוקדש ל"אלגוריתמים חמדנים". הקטע הזה מעניין כי הוא משתמש בסטים (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

חפש את השכנים הקרובים ביותר

הספר גם מדבר בצורה ברורה מאוד על אלגוריתם השכנים הקרובים ביותר: והנוסחה לחישוב ניתנת:

שורה תחתונה

הספר מסתיים בחלק מעניין של "מה הלאה?", המספק סקירה מהירה של אלגוריתמים מעניינים. הנה תיאור קצר של המשמעות של עצים ואלגוריתמים אחרים. בסך הכל, אהבתי את הספר. אין להתייחס אליו ברצינות כסוג של מידע מקיף. תצטרך לחפש ולהבין בעצמך. אבל בתור מידע מבוא לעניין ולתת רעיון ראשוני, זה די טוב. כן, הקוד בספר כתוב בפייתון. אז כל הדוגמאות לעיל ניתנות לקומפילציה) אני מקווה שסקירה זו תעזור לך לקבל מושג על מה הספר מכיל והאם כדאי לקנות אותו.

בנוסף

אתה יכול גם לבדוק את המשאבים הבאים בנושא זה:

1. EdX - מבוא לתכנות Java: מבני נתונים ואלגוריתמים בסיסיים
2. LinkedIn - מבוא למבני נתונים ואלגוריתמים ב-Java (בתשלום)
3. 27 אתרים עם חידות כדי לחדד את כישורי התכנות שלך
4. Java CodingBat
5. משימות למתכנתים, תשובות למשימות במורכבות משתנה

#ויאצ'סלב