[0]zero-index clytie0x/zero-index

16.3 sort และ lambda

ในหน้า 13.4 การเรียงด้วย qsort ต้องเขียนฟังก์ชันเปรียบเทียบที่รับ const void * แปลงชนิดเอง คืน -1 0 1 เอง และบอกขนาดของหนึ่งช่องเป็น byte ให้ถูก sort ของ C++ ทำงานเดียวกันในบรรทัดเดียว รู้ชนิดของข้อมูลเอง เรียงจากมากไปน้อยหรือตามเงื่อนไขอะไรก็ได้ด้วยฟังก์ชันสั้นๆ ที่เขียนไว้ตรงที่เรียกเลย และเมื่อคอมไพล์แบบเดียวกับ grader ก็เร็วกว่า qsort ด้วย หน้านี้ใช้ sort กับ vector อาเรย์ และข้อความ แล้วปิดท้ายด้วยกติกาของฟังก์ชันเปรียบเทียบที่ถ้าทำผิด โปรแกรมพังแบบหาสาเหตุยาก

เรียง vector

ใช้ข้อมูลชุดเดียวกับโปรแกรม scores ในหน้า 13.4

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> score(n);
    for (int &s : score) {
        cin >> s;
    }
    sort(score.begin(), score.end());
    for (int i = 0; i < n; i++) {
        cout << score[i];
        if (i + 1 < n) {
            cout << ' ';
        }
    }
    cout << '\n';
    return 0;
}

8
72 85 64 85 90 58 100 64

58 64 64 72 85 85 90 100

บรรทัดที่ 14 แทนฟังก์ชันเปรียบเทียบสิบบรรทัดกับการเรียก qsort ในหน้า 13.4 ทั้งหมด sort ไม่ต้องรู้ขนาดของหนึ่งช่อง เพราะรู้จากชนิดของ vector อยู่แล้ว และเรียงจากน้อยไปมากด้วย < ของชนิดนั้นเป็นค่าเริ่มต้น

sort รับสองค่า คือตำแหน่งเริ่มต้นและตำแหน่งสิ้นสุดของช่วงที่จะเรียง score.begin() คือตำแหน่งของช่องแรก ส่วน score.end() คือตำแหน่งถัดจากช่องสุดท้าย ไม่ใช่ช่องสุดท้าย ตำแหน่งแบบนี้เรียกว่า iterator ทำตัวคล้าย pointer ในบทที่ 10 ฟังก์ชันใน <algorithm> ทุกตัวในบทนี้รับช่วงแบบนี้ คือรวมตัวแรก ไม่รวมตัวสุดท้าย

index      0    1    2    3    4    5    6    7
score     72   85   64   85   90   58  100   64
           ^                                       ^
     score.begin()                            score.end()

ข้อดีของการไม่รวมตัวสุดท้ายคือ จำนวนช่องในช่วงเท่ากับ end() - begin() พอดี และช่วงว่างคือช่วงที่ต้นกับปลายเป็นตำแหน่งเดียวกัน ซึ่งจะได้ใช้ในหน้า 16.5

เรียงอาเรย์และบางส่วน

อาเรย์ธรรมดาก็ใช้ sort ได้ ชื่ออาเรย์ a คือตำแหน่งของช่องแรก ส่วน a + n คือตำแหน่งถัดจากช่องที่ n - 1 โค้ดค่ายหลายที่เก็บข้อมูลเริ่มจากช่องที่ 1 ก็เลื่อนช่วงไปหนึ่งช่องเป็น a + 1 ถึง a + n + 1

#include <bits/stdc++.h>
using namespace std;

int a[100001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        cout << a[i] << (i < n ? ' ' : '\n');
    }
    vector<int> first_three = {90, 58, 100, 64, 72};
    sort(first_three.begin(), first_three.begin() + 3);
    for (int x : first_three) {
        cout << x << '\n';
    }
    return 0;
}

5
160 148 171 155 149

148 149 155 160 171
58
90
100
64
72
  • บรรทัดที่ 17 ใช้ ? : จากหน้า 3.4 พิมพ์ช่องว่างหลังทุกตัวยกเว้นตัวสุดท้ายที่พิมพ์ขึ้นบรรทัดใหม่แทน
  • บรรทัดที่ 20 เรียงแค่สามช่องแรก begin() + 3 คือตำแหน่งของช่องที่ 3 ซึ่งไม่รวมในช่วง สองช่องท้ายจึงอยู่ที่เดิม

เรียงจากมากไปน้อย

มีสองวิธีที่ใช้บ่อย ส่งตัวเปรียบเทียบ greater<int>() ที่แปลว่า "ตัวที่มากกว่ามาก่อน" เป็นค่าที่สาม หรือเรียงแบบปกติแต่จากท้ายมาหน้าด้วย rbegin() กับ rend() ซึ่งเป็นตำแหน่งที่เดินถอยหลัง (r มาจาก reverse)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<int> a = {72, 85, 64, 85, 90, 58, 100, 64};
    vector<int> b = a;
    sort(a.begin(), a.end(), greater<int>());
    sort(b.rbegin(), b.rend());
    for (int x : a) {
        cout << x << ' ';
    }
    cout << '\n';
    cout << (a == b) << '\n';
    return 0;
}

100 90 85 85 72 64 64 58
1

สองวิธีได้ผลเหมือนกันทุกช่อง เลือกแบบไหนก็ได้ ตัวอย่างนี้พิมพ์ช่องว่างตามหลังทุกตัวเพื่อให้โค้ดสั้น ตัวสุดท้ายจึงมีช่องว่างเกินหนึ่งตัว กล่องผลลัพธ์มองไม่เห็น แต่ grader บางระบบนับ ในงานส่งจริงให้ใช้แบบตัวอย่างก่อนหน้า

เรียงข้อความ

string เทียบกันด้วย < ได้ตามลำดับพจนานุกรมอยู่แล้วตามหน้า 15.4 ผลเหมือน strcmp ในหน้า 6.4 vector ของ string จึงเรียงได้ทันที เทียบกับโปรแกรม names ในหน้า 13.4 ที่ต้องจองอาเรย์ char name[1000][21] และระวัง sizeof(name[0])

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<string> name(n);
    for (string &s : name) {
        cin >> s;
    }
    sort(name.begin(), name.end());
    for (const string &s : name) {
        cout << s << '\n';
    }
    return 0;
}

6
songkhla
nan
phuket
chiangmai
nakhonpathom
nakhonnayok

chiangmai
nakhonnayok
nakhonpathom
nan
phuket
songkhla

บรรทัดที่ 13 ใช้ const string & เพื่อไม่ให้คัดลอกข้อความทุกรอบ เหตุผลเดียวกับการส่ง vector ให้ฟังก์ชันในหน้า 16.2 ตัวพิมพ์ใหญ่ยังมาก่อนตัวพิมพ์เล็กทุกตัวเหมือน strcmp

เรียงตามเงื่อนไขของเราเองด้วย lambda

ห้องเรียนแต่ละห้องวัดอุณหภูมิได้ไม่เท่ากัน ครูอยากเรียงห้องจากที่อุณหภูมิใกล้ค่าที่สบายที่สุด T มากที่สุด ถ้าห่างจาก T เท่ากัน ห้องที่เย็นกว่ามาก่อน < หรือ greater ทำแบบนี้ไม่ได้ ต้องบอก sort เองว่าสองค่าไหนอะไรมาก่อน ด้วยฟังก์ชันเปรียบเทียบที่ส่งเป็นค่าที่สาม

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int target, n;
    cin >> target >> n;
    vector<int> temp(n);
    for (int &t : temp) {
        cin >> t;
    }
    sort(temp.begin(), temp.end(), [&](int a, int b) { // (1)!
        int gap_a = abs(a - target);
        int gap_b = abs(b - target);
        if (gap_a != gap_b) {
            return gap_a < gap_b; // (2)!
        }
        return a < b; // (3)!
    });
    for (int i = 0; i < n; i++) {
        cout << temp[i] << (i + 1 < n ? ' ' : '\n');
    }
    return 0;
}
  1. lambda คือฟังก์ชันไม่มีชื่อที่เขียนไว้ตรงที่ใช้ [&] บอกว่าข้างในใช้ตัวแปรของ main ได้ ในที่นี้คือ target ถ้าไม่ใช้ตัวแปรข้างนอกเลยเขียน [] เฉยๆ ได้ ต่อด้วยพารามิเตอร์ในวงเล็บ แล้วตัวฟังก์ชันในปีกกา ปิดท้ายด้วย ) ของ sort และ ;
  2. คืน true เมื่อ a ต้องมาก่อน b คืน false ในกรณีอื่นทั้งหมด ต่างจาก qsort ที่คืน -1 0 1
  3. ระยะห่างเท่ากัน ตัวที่น้อยกว่ามาก่อน และถ้า a เท่ากับ b บรรทัดนี้คืน false ตามกติกาท้ายหน้า
25 7
29 21 25 31 23 27 18

25 23 27 21 29 31 18

23 กับ 27 ห่างจาก 25 เท่ากันคือ 2 องศา 23 จึงมาก่อนตามเงื่อนไขที่สอง เช่นเดียวกับ 21 กับ 29 ส่วน 31 ห่าง 6 และ 18 ห่าง 7 จะเขียนฟังก์ชันเปรียบเทียบเป็นฟังก์ชันธรรมดาที่มีชื่อ แล้วส่งชื่อไปแบบ qsort ก็ได้ แต่ lambda อ่านง่ายกว่าเพราะเงื่อนไขอยู่ตรงที่เรียงพอดี

เร็วกว่า qsort จริงไหม

ใช้วิธีจับเวลาแบบหน้า 13.3 จับเฉพาะช่วงที่เรียง ให้ทั้งสองฝั่งเรียงอาเรย์ global ชุดเดียวกัน ต่างกันแค่บรรทัดที่เรียก เพราะเวลาที่วัดกับคนละชนิดข้อมูลเทียบกันตรงๆ ไม่ได้

#include <bits/stdc++.h>
using namespace std;

int a[1000000];

int main()
{
    int n;
    cin >> n;
    mt19937 rng(2569); // (1)!
    for (int i = 0; i < n; i++) {
        a[i] = rng() % 1000000000;
    }
    clock_t start = clock();
    sort(a, a + n); // (2)!
    clock_t end = clock();
    cout << fixed << setprecision(3);
    cout << "n = " << n << ", time = " << (double)(end - start) / CLOCKS_PER_SEC << " seconds\n";
    return 0;
}
  1. mt19937 เป็นตัวสุ่มของ C++ ที่ให้เลขได้ถึงราว 4 × 109 ต่างจาก rand() บน Windows ที่ให้ได้แค่ 32767 ข้อมูลล้านตัวจาก rand() จึงซ้ำกันเต็มไปหมด เลข 2569 ในวงเล็บคือจุดเริ่ม รันกี่ครั้งก็ได้ชุดเดิม rng() คืนเลขสุ่มหนึ่งตัวทุกครั้งที่เรียก หน้า 20.2 จะใช้ตัวสุ่มนี้อีก
  2. ฝั่ง qsort เปลี่ยนบรรทัดนี้เป็น qsort(a, n, sizeof(int), compare_int); แล้วคัดลอกฟังก์ชัน compare_int จากหน้า 13.4 มาไว้ก่อน main
1000000

n = 1000000, time = 0.116 seconds

วัดทั้งสองฝั่งบนเครื่องเดียวกับหน้า 16.2 รันแต่ละช่อง 12 ครั้ง ทิ้งครั้งแรก ใช้ค่ากลางของ 11 ครั้งที่เหลือ หน่วยเป็นวินาที

วิธีnแบบ Code::Blocksแบบ -O2
qsort100,0000.0090.010
sort100,0000.0090.005
qsort1,000,0000.1260.108
sort1,000,0000.1160.051

อ่านตารางได้สองเรื่อง

  • แบบ Code::Blocks สองวิธีพอๆ กัน sort เขียนเป็นฟังก์ชันเล็กๆ ซ้อนกันหลายชั้น ซึ่งออกแบบมาให้ compiler รวมเป็นโค้ดก้อนเดียวตอนเปิด -O2 พอไม่เปิด ทุกชั้นจึงเป็นการเรียกฟังก์ชันจริง ส่วนตัว qsort คอมไพล์มาเสร็จแล้วในไลบรารีของระบบ แฟล็กของเรามีผลแค่กับฟังก์ชันเปรียบเทียบ ถ้าเปลี่ยนฝั่ง sort ไปเรียง vector<int> แทนอาเรย์ แบบ Code::Blocks ที่ล้านตัวจะช้าลงเป็นราว 0.25 วินาที เพราะการหยิบช่องของ vector ก็เป็นการเรียกฟังก์ชันเหมือนกัน ส่วนแบบ -O2 ยังได้ราว 0.05 วินาทีเท่าเดิม
  • แบบ -O2 sort เร็วกว่า qsort ราวสองเท่า เพราะการเทียบถูกรวมเข้าไปในโค้ดเรียงเลย ขณะที่ qsort ต้องเรียกฟังก์ชันเปรียบเทียบของเราผ่าน pointer ทุกครั้งที่เทียบ

grader คอมไพล์ด้วย -O2 จึงดูคอลัมน์ขวาเป็นหลัก และทั้งสองวิธีเรียงล้านตัวได้ในเวลาไม่ถึงหนึ่งในสี่วินาทีแม้ไม่เปิด -O2 เหตุผลที่ควรใช้ sort จึงไม่ใช่ความเร็วอย่างเดียว แต่คือเขียนสั้น และไม่มีที่ให้ผิดแบบ sizeof ผิดหรือ return x - y ล้น ตัวเลข qsort ในตารางนี้เทียบกับตารางในหน้า 13.4 ตรงๆ ไม่ได้ เพราะข้อมูลคนละชุด หน้านั้นใช้ rand() ที่ได้ค่าซ้ำกันมาก และวัดคนละวัน เวลาที่วัดได้แกว่งตามสภาพเครื่องเสมอ ให้ดูที่อัตราส่วนของสองวิธีที่วัดพร้อมกันมากกว่าตัวเลขแต่ละตัว

กติกาของฟังก์ชันเปรียบเทียบ

sort เชื่อฟังก์ชันเปรียบเทียบของเราทุกคำ และใช้ความเชื่อนั้นทำให้ตัวเองเร็ว เช่น ตอนเลื่อนค่าไปทางซ้าย มันไม่เช็กว่าเลยช่องแรกของ vector หรือยัง เพราะเชื่อว่าฟังก์ชันจะตอบว่า "ไม่ต้องมาก่อน" เมื่อเจอค่าที่ไม่มากกว่า ฟังก์ชันเปรียบเทียบ comp(a, b) จึงต้องทำตัวเหมือน < ตามกติกานี้ ซึ่งเรียกว่า strict weak ordering

  1. comp(a, a) ต้องเป็น false เสมอ ค่าหนึ่งไม่มาก่อนตัวเอง
  2. ถ้า comp(a, b) เป็น true แล้ว comp(b, a) ต้องเป็น false
  3. ถ้า a มาก่อน b และ b มาก่อน c แล้ว a ต้องมาก่อน c

ในทางปฏิบัติจำแค่ว่า ใช้ < หรือ > เท่านั้น ห้ามใช้ <= หรือ >= และเมื่อสองค่าเท่ากันทุกเงื่อนไข ต้องคืน false แบบบรรทัดสุดท้ายของ lambda ในตัวอย่าง rooms

ลองทำให้พัง

แบบที่ 1 ใช้ <= ในฟังก์ชันเปรียบเทียบ

ในโปรแกรม scores ถ้าเขียนบรรทัดที่ 14 ใหม่ให้เรียงด้วย lambda ที่ใช้ <=

sort(score.begin(), score.end(), [](int a, int b) {
    return a <= b;
});

ป้อนข้อมูลชุดเดิมแปดตัว ได้ 58 64 64 72 85 85 90 100 ถูกต้อง ป้อนเลข 50 สิบหกตัวก็ยังถูก แต่พอป้อน 50 สิบเจ็ดตัว ซึ่งคำตอบที่ถูกคือ 50 สิบเจ็ดตัวเหมือนเดิม ผลเริ่มเพี้ยน บนเครื่องที่เขียนเอกสารนี้ รันในหน้าต่าง cmd สิบครั้งได้ผลไม่ซ้ำกัน ห้าครั้งถูก อีกห้าครั้งโปรแกรมจบปกติ แต่เลข 50 บางตัวหายไป มีเลขที่ไม่เคยป้อน เช่น 0 หรือ -1811933696 โผล่มาแทนที่หัวแถว พอเพิ่มเป็น 50 ยี่สิบตัว สิบครั้งได้ค่าขยะสามครั้ง และพังหนึ่งครั้งโดยไม่พิมพ์อะไรเลย

Process returned -1073740940 (0xC0000374)

ผลเปลี่ยนไปทุกครั้งที่รันแบบนี้คือสัญญาณว่าโปรแกรมกำลังอ่านเขียนหน่วยความจำที่ไม่ใช่ของตัวเอง 0xC0000374 คือรหัสที่ Windows บอกว่าหน่วยความจำส่วน heap ถูกเขียนทับจนเสีย

สาเหตุมาจากวิธีที่ sort ของ g++ ทำงาน มันเป็นวิธีผสมชื่อ introsort ถ้าช่วงยาวเกิน 16 ตัว จะเลือกตัวแบ่งแล้วย้ายตัวที่ควรมาก่อนตัวแบ่งไปไว้ทางซ้าย ตัวที่ควรมาทีหลังไปไว้ทางขวา (หลักเดียวกับ quicksort ที่จะได้เรียนในหน้า 22.4) ลูปที่เดินหาตัวถัดไปเชื่อว่าจะเจอตัวที่ทำให้หยุดก่อนถึงท้ายช่วงเสมอ จึงไม่เช็กขอบ เมื่อทุกค่าเท่ากัน a <= b ตอบ true ทุกครั้ง ลูปจึงเดินเลยช่องสุดท้ายของ vector ออกไป ลองนับด้วยตัวนับในฟังก์ชันเปรียบเทียบ กับ 50 สิบเจ็ดตัว ช่องแรกที่หลุดออกไปคือช่องที่ 17 ซึ่งอยู่ถัดจากช่องสุดท้ายพอดี ค่าขยะจากตรงนั้นจึงถูกสลับเข้ามาในข้อมูล และของ 50 ถูกเขียนลงที่ที่ไม่ใช่ของเรา ช่วงที่ไม่เกิน 16 ตัว sort ข้ามขั้นแบ่งไปใช้ insertion sort ทันที และกับข้อมูลที่เท่ากันหมด insertion sort ของมันใช้ทางที่เช็กหัวช่วงทุกครั้ง จึงบังเอิญรอด ชุดทดสอบเล็กที่เราลองเองจึงผ่านหมด แล้วไปพังบน grader กับชุดใหญ่ที่มีค่าซ้ำ

แบบที่ 2 ติดนิสัย return a - b จาก qsort

sort(score.begin(), score.end(), [](int a, int b) {
    return a - b;
});

คอมไพล์ผ่านด้วย -Wall โดยไม่มีคำเตือน lambda ที่ไม่ได้บอกชนิดที่คืน จะคืนชนิดเดียวกับค่าหลัง return lambda นี้จึงคืน int แต่ sort เอาค่าที่ได้ไปใช้เป็นเงื่อนไขจริงหรือเท็จ ตัวเลข a - b จึงถูกแปลงเป็น true ทุกครั้งที่ไม่เป็น 0 แปลว่าทุกคู่ที่ไม่เท่ากันตอบว่า "a มาก่อน b" ทั้งสองทิศ ผิดกติกาข้อ 2 บนเครื่องที่เขียนเอกสารนี้ ข้อมูลชุดเดิมแปดตัวได้

64 100 58 90 85 64 85 72

ซึ่งคือข้อมูลเข้ากลับหลัง ไม่ได้เรียงเลย ส่วนข้อมูลสามสิบตัวที่มีค่าซ้ำ รันสามครั้งพังด้วย 0xC0000005 ทั้งสามครั้ง ฟังก์ชันเปรียบเทียบของ sort ตอบคำถามว่า "a มาก่อน b ไหม" ด้วยจริงหรือเท็จ ไม่ใช่ลบ ไม่ใช่ -1 0 1

แบบที่ 3 ลืมวงเล็บหลัง greater<int>

ในโปรแกรม desc ถ้าลบ () หลัง greater<int> ในบรรทัดที่ 8

desc.cpp:8:42: error: expected primary-expression before ')' token
    8 |     sort(a.begin(), a.end(), greater<int>);
      |                                          ^

greater<int> เป็นชื่อชนิด ไม่ใช่ค่า ต้องมี () ต่อท้ายเพื่อสร้างตัวเปรียบเทียบขึ้นมาหนึ่งตัวก่อนส่งให้ sort ข้อความ expected primary-expression แปลว่า compiler รอค่าอยู่แต่เจอเครื่องหมาย ) แทน

สรุป

  • sort(v.begin(), v.end()) เรียง vector จากน้อยไปมาก อาเรย์ใช้ sort(a, a + n) หรือ sort(a + 1, a + n + 1) ถ้าเริ่มที่ช่อง 1
  • ช่วงในฟังก์ชันของ <algorithm> รวมตัวแรก ไม่รวมตัวสุดท้าย end() คือตำแหน่งถัดจากช่องสุดท้าย
  • มากไปน้อยใช้ greater<int>() มีวงเล็บ หรือ sort(v.rbegin(), v.rend())
  • เงื่อนไขอื่นใช้ lambda [](int a, int b) { return ...; } คืน true เมื่อ a ต้องมาก่อน b [&] ให้ใช้ตัวแปรข้างนอกได้
  • แบบ -O2 sort เร็วกว่า qsort แบบ Code::Blocks ช้ากว่า แต่ทั้งคู่เรียงล้านตัวได้ไม่ถึงวินาที
  • ฟังก์ชันเปรียบเทียบใช้ < หรือ > ห้าม <= >= และห้าม return a - b ค่าเท่ากันต้องได้ false