ทบทวนและทดสอบวิธีการคัดแยก ส่วนที่ 1

วันก่อนในความคิดเห็นของ VKontakte ฉันทะเลาะกับนักเรียนคนอื่น ๆ ของโครงการ สาระสำคัญของข้อพิพาทคือ "ใครจะชนะ" - วิธีการsort()จากคลาสjava.util.Arraysหรือการใช้งานอัลกอริธึมอย่างง่ายที่เขียนเอง: ฟอง , การแทรก , การเลือก , เชลล์ (อัลกอริธึมเชลล์) สำหรับบางคน คำตอบสำหรับคำถามนี้อาจชัดเจน แต่เนื่องจากข้อพิพาทเกิดขึ้น แม้ว่าแต่ละฝ่ายจะมี "แหล่งข้อมูลที่เคารพ" เพื่อสนับสนุนมุมมองของตน จึงมีการตัดสินใจที่จะดำเนินการศึกษาโดยขยายสสารสีเทาใน กระบวนการการนำอัลกอริธึมต่างๆ ไปใช้ TL; DR: java.util.Arrays.sort() เป็นผู้นำในอาร์เรย์ที่มีองค์ประกอบ 100,000 องค์ประกอบขึ้นไปโดยไม่มีเงื่อนไข ด้วยขนาดที่เล็กกว่า บางครั้งวิธี Shell ก็สามารถแข่งขันกับมันได้ อัลกอริธึมที่พิจารณาส่วนที่เหลือนั้นว่างเปล่าโดยสิ้นเชิงและสามารถมีประโยชน์ภายใต้เงื่อนไขแปลกใหม่บางประการเท่านั้น ตอนนี้เรามาดูวิธีการจัดเรียงอาร์เรย์ในอุปกรณ์ uber ซิลิคอนของเรา

เรียงลำดับการเลือก เรียงตามการเลือก

เริ่มจากวิธีที่ง่ายและชัดเจนที่สุดกันก่อน สาระสำคัญของสิ่งนี้แสดงให้เห็นอย่างสมบูรณ์แบบแก่เราโดยRobert Sedgwickในวิดีโอบรรยายของเขาใน coursera (ฉันจะอ้างอิงแอนิเมชั่นจากที่นั่นซึ่งฉันบีบอัดเป็น GIF ไม่ดี): ดู การวิ่งผ่านอาเรย์จากองค์ประกอบแรก ในแต่ละขั้นตอนเรา มองหาองค์ประกอบขั้นต่ำทางด้านขวา ซึ่งเราจะสลับองค์ประกอบปัจจุบัน ด้วยเหตุนี้ เราจึงสงวนเวอร์ชันสุดท้ายของอาร์เรย์ของเราไว้ในรูปแบบที่เรียงลำดับ นี่คือโค้ดที่ใช้อัลกอริทึมนี้ใน Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

การวิเคราะห์อัลกอริทึมแสดงให้เห็นว่าจำเป็นต้องรวมส่วนที่เหลือของอาร์เรย์ในแต่ละรอบนั่นคือเราจะต้องมี N + (N-1) + (N-2) + ... + 1 = N^ การเปรียบเทียบ 2/2 ดังนั้นความซับซ้อนของอัลกอริทึมคือ O(N^2) สิ่งนี้หมายความว่า? ซึ่งหมายความว่าการเพิ่มจำนวนองค์ประกอบในอาร์เรย์ (N) 2 เท่า เราจะเพิ่มเวลาการทำงานของอัลกอริทึมไม่ใช่ 2 แต่ 2^2 = 4 เท่า เมื่อเพิ่ม N 10 เท่า เราจะเพิ่มเวลาการทำงาน 100 เท่า และต่อๆ ไป ในแล็ปท็อปปี 2012 ของฉันที่ใช้โปรเซสเซอร์ Core i3 ที่ใช้ Ubuntu 14.4 ฉันได้รับเวลาทำงานดังต่อไปนี้:

การเรียงลำดับการแทรก การเรียงลำดับการแทรก

ที่นี่แนวคิดแตกต่างออกไปเล็กน้อย มาดูแอนิเมชั่นจาก Doctor Sedgwick อีกครั้ง: ดู สิ่งที่อยู่ข้างหน้าเรายังไม่ได้ดูด้วยซ้ำและทุกสิ่งที่เราทิ้งไว้ข้างหลังจะยังคงอยู่ในลำดับเสมอ ประเด็นก็คือเรา "คืน" แต่ละองค์ประกอบใหม่ของอาเรย์ดั้งเดิมไปยังจุดเริ่มต้นจนกว่ามันจะ "พัก" บนองค์ประกอบที่เล็กกว่า ดังนั้นเราจึงมี N pass อีกครั้ง (สำหรับแต่ละองค์ประกอบของอาเรย์เดิม) แต่ในแต่ละ pass ในกรณีส่วนใหญ่ เราไม่ได้ดูส่วนที่เหลือทั้งหมด แต่จะดูเพียงบางส่วนเท่านั้น นั่นคือเราจะได้รับตัวเลือก 1 + (N-1) + (N-2) + … + N = N^2/2 เฉพาะในกรณีที่เราต้องส่งคืนแต่ละองค์ประกอบถัดไปไปยังจุดเริ่มต้นนั่นคือในกรณีนี้ ของอินพุตที่เรียงลำดับ "แบบย้อนกลับ" (โชคร้าย, โชคร้าย) ในกรณีของอาร์เรย์ที่เรียงลำดับแล้ว (โชคดี) จะมีของแจกฟรีที่สมบูรณ์ - ในแต่ละรอบจะมีการเปรียบเทียบเพียงครั้งเดียวและปล่อยให้องค์ประกอบอยู่ในตำแหน่งนั่นคืออัลกอริทึมจะทำงานในเวลาตามสัดส่วนกับ N ความซับซ้อน ของอัลกอริธึมจะถูกกำหนดโดยกรณีทางทฤษฎีที่แย่ที่สุด คือ O( N^2) โดยเฉลี่ย เวลาดำเนินการจะเป็นสัดส่วนกับ N^2/4 ซึ่งเร็วกว่าอัลกอริธึมก่อนหน้าถึงสองเท่า ในการนำไปใช้งานของฉัน เนื่องจากการใช้การเรียงสับเปลี่ยนที่ไม่เหมาะสม เวลาทำงานจึงนานกว่าการเลือก ฉันวางแผนที่จะแก้ไขและอัปเดตโพสต์ในไม่ช้า นี่คือโค้ดและผลลัพธ์ของการทำงานบนเครื่องเดียวกัน:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

การเรียงลำดับเปลือก การเรียงลำดับเปลือก

Donald Schell ผู้ฉลาดคนหนึ่งสังเกตเห็นย้อนกลับไปในปี 1959 ว่ากรณีที่แพงที่สุดในอัลกอริธึมสำหรับการแทรกคือเมื่อองค์ประกอบเคลื่อนกลับไปยังจุดเริ่มต้นของอาร์เรย์มาก: ในบางการส่งผ่าน เราจะคืนค่าองค์ประกอบไปยังจุดเริ่มต้นด้วยตำแหน่ง 2-3 ตำแหน่ง และในอีกทางหนึ่งผ่านไปเกือบตลอดทั้งอาร์เรย์จนถึงจุดเริ่มต้นนั้นไกลและยาว เป็นไปได้ไหมที่จะทำสิ่งนี้พร้อมกันโดยข้ามองค์ประกอบหลายอย่าง? และเขาก็พบวิธีดังกล่าว ประกอบด้วยการเรียงลำดับบางส่วนแบบพิเศษตามลำดับ โดยทั่วไปเรียกว่า d-sort หรือตาม Sedgwick คำว่า h-sort (ฉันสงสัยว่า h หมายถึงฮอป) ตัวอย่างเช่น การเรียงลำดับแบบ 3 จะเปรียบเทียบองค์ประกอบที่เป็นปัญหาไม่ใช่กับองค์ประกอบก่อนหน้า แต่จะข้ามสองรายการและเปรียบเทียบกับองค์ประกอบ 3 ตำแหน่งที่ด้านหลัง หากมีการเปลี่ยนแปลงก็จะเปรียบเทียบอีกครั้งกับตำแหน่งธาตุ 3 ย้อนหลังไปเรื่อยๆ บรรทัดล่างคืออาร์เรย์ผลลัพธ์จะเป็น "3-sorted" นั่นคือตำแหน่งที่ไม่ถูกต้องขององค์ประกอบจะน้อยกว่า 3 ตำแหน่ง การทำงานกับอัลกอริธึมการแทรกนี้จะง่ายและน่าพึงพอใจ อย่างไรก็ตาม “1-sort” ไม่มีอะไรมากไปกว่าแค่อัลกอริธึมการแทรก =) เมื่อใช้ h-sort กับอาร์เรย์ตามลำดับโดยมีค่า h ที่ลดลง เราสามารถจัดเรียงอาร์เรย์ขนาดใหญ่ได้เร็วขึ้น หน้าตาจะเป็นดังนี้: ดู ความท้าทายที่นี่คือวิธีเลือกลำดับที่ถูกต้องของการเรียงลำดับบางส่วน ในที่สุดประสิทธิภาพของอัลกอริทึมก็ขึ้นอยู่กับสิ่งนี้ ลำดับที่พบบ่อยที่สุดคือลำดับที่เสนอโดย Donald Knuth: h = h*3 + 1 นั่นคือ 1, 4, 13, 40, ... และอื่นๆ จนถึง 1/3 ของขนาดอาร์เรย์ ลำดับนี้ให้ประสิทธิภาพที่เหมาะสมและยังนำไปปฏิบัติได้ง่ายอีกด้วย การวิเคราะห์อัลกอริทึมต้องใช้ภาษามากมายและเกินความสามารถของฉัน ความกว้างของการวิเคราะห์ยังถูกกำหนดโดยตัวแปรต่างๆ ของลำดับ h ตามเชิงประจักษ์ เราสามารถพูดได้ว่าความเร็วของอัลกอริธึมนั้นดีมาก - ดูด้วยตัวคุณเอง: องค์ประกอบล้านรายการในเวลาไม่ถึงวินาที! และนี่คือโค้ด Java ที่มีลำดับ Knut

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

การเรียงลำดับฟอง วิธีบับเบิ้ล

นี่มันคลาสสิก! โปรแกรมเมอร์มือใหม่เกือบทุกคนใช้อัลกอริทึมนี้ มันคลาสสิกมากจนดร.เซดจ์วิคไม่มีแม้แต่แอนิเมชั่นด้วยซ้ำ ฉันก็เลยต้องทำงานนี้ด้วยตัวเอง ดู ที่นี่ ในแต่ละรอบ เราจะสำรวจอาร์เรย์ตั้งแต่ต้นจนจบ โดยสลับองค์ประกอบข้างเคียงที่ไม่เป็นระเบียบ เป็นผลให้องค์ประกอบที่ใหญ่ที่สุด “ลอย” (ดังนั้นชื่อ) ไปที่ส่วนท้ายของอาร์เรย์ เราเริ่มต้นการส่งผ่านใหม่แต่ละครั้งในแง่ดีโดยหวังว่าอาร์เรย์จะถูกจัดเรียงแล้ว ( sorted = true) ในตอนท้ายของตอนถ้าเราเห็นว่าเราทำผิดเราก็เริ่มตอนใหม่ ความยากที่นี่คืออีกครั้งที่เรากำลังสำรวจ (เกือบ) อาร์เรย์ทั้งหมดในแต่ละรอบ การเปรียบเทียบเกิดขึ้นในทุกขั้นตอน การแลกเปลี่ยนเกิดขึ้นในเกือบทุกขั้นตอน ซึ่งทำให้อัลกอริทึมนี้เป็นหนึ่งในขั้นตอนที่ช้าที่สุด (หากเราพิจารณาถึงการดำเนินการอย่างมีเหตุผล ไม่ใช่ "การเรียงลำดับแบบสั่น" และอย่างอื่นที่คล้ายกัน) สิ่งที่น่าสนใจคือความซับซ้อนอย่างเป็นทางการที่นี่จะเท่ากับ O(N^2) ด้วย แต่ค่าสัมประสิทธิ์จะสูงกว่าค่าสัมประสิทธิ์การแทรกและการเลือกมาก รหัสอัลกอริทึม:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

เวลาทำการ: รู้สึกถึงความแตกต่าง: มากกว่าครึ่งชั่วโมงกับองค์ประกอบนับล้าน! สรุป: อย่าใช้อัลกอริธึมนี้!!!

สรุปภาคแรก

ด้วยเหตุนี้ ฉันขอแนะนำให้ดูตารางทั่วไปสำหรับอัลกอริทึมเหล่านี้ คุณยังสามารถเปรียบเทียบกับผลลัพธ์สำหรับวิธีการในตัวjava.util.Arrays.sort()ได้ ดูเหมือนมีเวทย์มนตร์อะไรจะเร็วกว่าเชลล์? ฉันจะเขียนเกี่ยวกับเรื่องนี้ในส่วนถัดไป เราจะดูอัลกอริธึมการเรียงลำดับด่วนที่ใช้กันอย่างแพร่หลายรวมถึงการเรียงลำดับแบบผสานเรียนรู้เกี่ยวกับความแตกต่างในวิธีการเรียงลำดับอาร์เรย์จากประเภทดั้งเดิมและประเภทการอ้างอิงและทำความคุ้นเคยกับอินเทอร์เฟซที่สำคัญมากในเรื่องนี้Comparable;) คุณสามารถศึกษาด้านล่าง กราฟที่สร้างขึ้นในระดับลอการิทึมโดยใช้ตารางข้อมูล ยิ่งเส้นประจบเท่าไร อัลกอริธึมก็ยิ่งดีเท่านั้น =) สำหรับผู้ที่ต้องการดาวน์โหลดทั้งโปรเจ็กต์และทำการทดสอบด้วยตนเอง ให้เก็บลิงก์ไว้: Java เจอกันใหม่ตอนหน้า! =)