الگوریتم های غوغایی یا مقدمه ای بی دردسر برای الگوریتم ها

نقد و بررسی کتاب «الگوریتم های غم انگیز». کمی نظر شخصی، چند مثال. امیدوارم این بررسی به شما کمک کند تا بفهمید که آیا می خواهید این کتاب را بخوانید یا جای آن را در قفسه شما نخواهد گرفت. هشدار: متن زیاد)

"الگوریتم های غم انگیز" یا مقدمه ای بدون درد برای الگوریتم ها

معرفی

تقریباً هر جای خالی سطح جونیور دارای الزاماتی مانند "دانش ساختار داده ها و الگوریتم ها" است. برای کسانی که تحصیلات تخصصی دارند، الگوریتم ها در دوره عمومی گنجانده شده است و نباید مشکلی وجود داشته باشد. اما اگر توسعه از استپ های دیگر وارد شده باشد چه؟ تنها چیزی که باقی می ماند این است که خودتان یاد بگیرید. برای سؤال «مقصر کیست» پاسخی وجود دارد، اما برای سؤال «چه باید کرد» باید به دنبال پاسخ بود. بیایید در کتاب ها نگاه کنیم. و من می خواهم در مورد یکی به شما بگویم.

الگوریتم های گروک

در بین همه آثار، به کتابی به نام «الگوریتم های غم انگیز» برخوردم. در اینجا می توانید اطلاعات بیشتری کسب کنید: " کتاب "الگوریتم های در حال رشد. راهنمای مصور برای برنامه نویسان و کنجکاوها ." من خیلی وقت پیش متوجه کتاب شدم، اما روی اوزون 680 روبل قیمت داشت. گران یا ارزان - هر کس برای خودش تصمیم می گیرد. من در حال حاضر کتاب دوم را در Avito به نصف قیمت می خرم. بنابراین من آن را در سنت پترزبورگ پیدا کردم، آن را خریدم و به غواصی رفتم. چیزی که تصمیم گرفتم با شما به اشتراک بگذارم. بله، هیچ کد جاوا در کتاب وجود ندارد، اما کد دیگری وجود دارد، اما بعداً در مورد آن بیشتر توضیح خواهیم داد.

مقدمه ای بر الگوریتم ها (مرتب سازی انتخابی)

بنابراین در یک روایت آسان به اولین مرتب سازی در اجرای خود می رسیم. این مرتب سازی انتخاب است. ماهیت آن این است که ما عناصر را از چپ به راست (از عنصر 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;
            }
        }
}

همانطور که می بینید، کد تقریباً یکسان است. کد اول نمونه ای از کتاب است. دومی اجرای رایگان من در کد جاوا است.

بازگشت

بعد به ما می گویند که چیزی به نام بازگشت وجود دارد. اول از همه، یک مشکل در مورد یک کشاورز است که مزرعه ای به اندازه 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 بسازیم! ترکیبات. شما می توانید در مورد بازگشت اطلاعات بیشتر در اینجا بخوانید: " Recursion. Training tasks ." مقایسه رویکردهای تکراری و بازگشتی: « بازگشت ».

مرتب سازی سریع

مرتب سازی سریع یک الگوریتم نسبتاً جالب است. کتاب توجه زیادی به او ندارد. علاوه بر این، کد فقط برای بدترین حالت، زمانی که اولین عنصر انتخاب شده است، داده می شود. با این حال، شاید برای اولین آشنایی، یادآوری این مثال آسان تر باشد. و بهتر است یک مرتب سازی سریع بد بنویسید تا اینکه اصلا ننویسید. در اینجا یک نمونه از کتاب آورده شده است:

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 آرایه جدید ایجاد می کنیم - یکی حاوی عناصر بزرگتر از pivot و دومی حاوی عناصر کوچکتر است. و به صورت بازگشتی تکرار می کنیم. بهترین گزینه نیست، اما باز هم بهتر است به خاطر بسپارید. بیایید این الگوریتم را در جاوا پیاده سازی کنیم، اما درست تر. مطالب از بررسی " علوم کامپیوتر در جاوا اسکریپت: 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;
  }

  جزئیات در لینک بالا به طور خلاصه، ما مکان نما را به سمت چپ حرکت می دهیم تا عنصر کمتر از pivot شود. به طور مشابه، نشانگر سمت راست را از انتهای دیگر حرکت دهید. و اگر مکان نماها مطابقت نداشتند، تعویض می کنیم. ادامه می دهیم تا مکان نماها همگرا شوند. شاخصی را برمی گردانیم که پردازش بیشتر را به 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);
              }
          }
  }

  یعنی اگر آرایه از حداقل دو عنصر تشکیل شده باشد، می توان آنها را از قبل مرتب کرد. ابتدا کل آرایه را به دو قسمت تقسیم می کنیم، عناصر کوچکتر از pivot و عناصر بزرگتر. سپس اقدامات مشابهی را برای هر یک از قسمت های حاصل انجام می دهیم.

  و برای تست:

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

جداول هش

این کتاب همچنین به جداول هش می پردازد. لازم نیست خودتان آن را پیاده سازی کنید، و ماهیت جداول هش بسیار ساده است. پس از همه، جاوا همچنین دارای پیاده سازی جداول هش، java.util.HashTable است. اگر به دستگاه HashTable نگاه کنیم، خواهیم دید که آرایه Entry در داخل آن قرار دارد. Entry رکوردی است که ترکیبی از Key – Value است. 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 و نمودارهای وزنی دعوت می کند. نمودار زیر برای حل پیشنهاد شده است: ابتدا باید بدانیم که چگونه نمودارهای خود را نشان دهیم. ما می توانیم آن را به عنوان یک ماتریس نشان دهیم. مقاله ای در مورد 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

نزدیکترین همسایگان را جستجو کنید

این کتاب همچنین به وضوح در مورد الگوریتم k-نزدیکترین همسایه صحبت می کند: و فرمول محاسبه داده شده است:

خط پایین

کتاب با بخش جالب «بعدش چیست؟» به پایان می‌رسد که مروری سریع بر الگوریتم‌های جالب ارائه می‌دهد. در اینجا توضیح مختصری از معنای درختان و سایر الگوریتم ها ارائه می شود. در کل کتاب را دوست داشتم. نباید آن را به عنوان نوعی اطلاعات جامع جدی گرفت. باید خودتان جستجو کنید و بفهمید. اما به عنوان اطلاعات مقدماتی برای علاقه مندی و ارائه یک ایده اولیه، بسیار خوب است. بله، کد داخل کتاب به زبان پایتون نوشته شده است. بنابراین همه نمونه‌های بالا قابل جمع‌آوری هستند) امیدوارم این بررسی به شما کمک کند تا در مورد محتوای کتاب و ارزش خرید آن ایده بگیرید.

علاوه بر این

همچنین می توانید منابع زیر را در این زمینه بررسی کنید:

1. EdX - مقدمه ای بر برنامه نویسی جاوا: ساختارها و الگوریتم های داده بنیادی
2. LinkedIn - مقدمه ای بر ساختارهای داده و الگوریتم ها در جاوا (پرداخت شده)
3. 27 سایت با پازل برای تقویت مهارت های برنامه نویسی شما
4. جاوا کدینگ بت
5. وظایف برای برنامه نویسان، پاسخ به وظایف با پیچیدگی های مختلف

#ویاچسلاو