[0]zero-index clytie0x/zero-index

13.5 counting sort และการค้นหา

หน้านี้มีสองเรื่อง เรื่องแรกคือวิธีเรียงที่เร็วกว่า qsort อีก แต่ใช้ได้เฉพาะเมื่อค่าอยู่ในช่วงแคบ เช่น คะแนน 0 ถึง 100 ซึ่งน้องเกือบเขียนเป็นแล้วตั้งแต่หน้า 5.3 เรื่องที่สองคือการค้นหา ทั้งค้นหาตัวเลขในอาเรย์ ค้นหาชื่อในอาเรย์ของ struct และค้นหาคำในประโยค ซึ่งเป็นโจทย์ที่เจอทั้งใน TOI Zero และในข้อสอบค่าย

counting sort เรียงด้วยการนับ

ในหน้า 5.3 เรานับว่าคะแนนแต่ละค่ามีกี่คนด้วยอาเรย์นับ แล้ววนตามค่าคะแนนจาก 0 ถึง 100 เพื่อพิมพ์ผล ถ้าตอนพิมพ์ เราพิมพ์คะแนน s ซ้ำ count[s] ครั้ง ก็จะได้คะแนนทุกคนเรียงจากน้อยไปมาก โดยไม่ได้เทียบค่าสองค่าเลยสักครั้ง วิธีนี้เรียกว่า counting sort

#include <stdio.h>

int count[101];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++; // (1)!
    }
    int printed = 0;
    for (int value = 0; value <= 100; value++) { // (2)!
        for (int c = 0; c < count[value]; c++) {
            if (printed > 0) {
                printf(" ");
            }
            printf("%d", value);
            printed++;
        }
    }
    printf("\n");
    return 0;
}
  1. รอบแรกอ่านแล้วนับ ไม่ต้องเก็บคะแนนของแต่ละคนไว้เลย
  2. รอบสองวนตามค่า จากน้อยไปมาก พิมพ์ค่านั้นซ้ำตามจำนวนที่นับได้ ถ้าอยากได้จากมากไปน้อย ให้วน value จาก 100 ลงมาถึง 0
10
72 85 64 85 90 72 85 58 72 100

58 64 72 72 72 85 85 85 90 100

งานทั้งหมดคืออ่าน n ตัวหนึ่งรอบ บวกวนค่าอีก 101 รอบ ซึ่งรวมกันแล้วพิมพ์ออกมา n ตัว ไม่มีลูปซ้อนที่โตตาม n2 ลองวัดด้วยโปรแกรมจับเวลาแบบหน้า 13.3 โดยใช้ข้อมูล rand() % 101 หนึ่งล้านตัว (อาเรย์ขยายเป็นล้านช่อง) จับเฉพาะช่วงที่เรียง บนเครื่องเดิม ค่ากลางของ 5 ครั้ง

วิธีnแบบ Code::Blocksแบบ -O2
counting sort1,000,0000.002 วินาที0.001 วินาที
qsort1,000,0000.038 วินาที0.030 วินาที

เร็วกว่า qsort อีกราว 20 ถึง 30 เท่า แต่ทั้งสองแบบเร็วพอสำหรับโจทย์ 1 วินาทีอยู่แล้ว ข้อดีที่สำคัญกว่าในการแข่งขันคือ counting sort เขียนสั้น และไม่มีฟังก์ชันเปรียบเทียบให้เขียนผิด

counting sort ใช้ได้เมื่อไร

  • ค่าเป็นจำนวนเต็มและช่วงแคบ อาเรย์นับต้องมีหนึ่งช่องต่อหนึ่งค่าที่เป็นไปได้ คะแนน 0 ถึง 100 ใช้ 101 ช่อง อายุ 0 ถึง 150 ใช้ 151 ช่อง แต่ถ้าค่าไปถึง 109 ต้องใช้พันล้านช่อง ทั้งประกาศไม่ได้และวนไม่ทัน ให้ใช้ qsort
  • ค่าติดลบก็ได้ ถ้าเลื่อนก่อน แบบหน้า 5.3 เช่น อุณหภูมิ -50 ถึง 50 องศา ใช้ช่อง t + 50 ตอนพิมพ์ค่อยลบ 50 กลับ
  • เรียงแค่ตัวเลข ถ้าต้องเรียงข้อมูลที่มีอย่างอื่นติดมาด้วย เช่น ชื่อกับคะแนน counting sort แบบนี้ทำไม่ได้ เพราะเหลือแค่จำนวน ไม่รู้ว่าใครได้คะแนนนั้น ใช้ qsort กับอาเรย์ของ struct แทน
#include <stdio.h>

int count[101];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        count[t + 50]++;
    }
    int printed = 0;
    for (int index = 0; index <= 100; index++) {
        for (int c = 0; c < count[index]; c++) {
            if (printed > 0) {
                printf(" ");
            }
            printf("%d", index - 50);
            printed++;
        }
    }
    printf("\n");
    return 0;
}

7
12 -5 30 -50 0 -5 50

-50 -5 -5 0 12 30 50

ลานจอดรถจดเลขบัตรจอดของรถทุกคันไว้ตามลำดับที่เข้ามา เจ้าของรถยื่นบัตรมา อยากรู้ว่ารถคันนั้นอยู่ในรายการไหม วิธีที่ตรงที่สุดคือไล่ดูทีละช่องตั้งแต่ช่องแรก เจอเมื่อไรก็ตอบเลย ไล่จนสุดแล้วไม่เจอก็คือไม่มี วิธีนี้เรียกว่า ค้นหาแบบไล่ (linear search) ใช้ได้กับข้อมูลที่ไม่ได้เรียง

#include <stdio.h>

int ticket[1000];

int linear_search(int a[], int n, int target)
{
    for (int i = 0; i < n; i++) {
        if (a[i] == target) {
            return i; // (1)!
        }
    }
    return -1; // (2)!
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ticket[i]);
    }
    int target;
    while (scanf("%d", &target) == 1) {
        int index = linear_search(ticket, n, target);
        if (index == -1) {
            printf("%d not found\n", target);
        } else {
            printf("%d found at index %d\n", target, index);
        }
    }
    return 0;
}
  1. เจอแล้ว return ออกจากฟังก์ชันทันที ช่องที่เหลือไม่ต้องดู จึงได้ตำแหน่งแรกที่เจอเสมอ
  2. มาถึงบรรทัดนี้ได้แปลว่าไล่ครบทุกช่องแล้วไม่เจอ คืน -1 เพราะไม่มีช่องไหนที่ index ติดลบ คนเรียกจึงแยกออกว่าไม่เจอ
6
1024 5531 870 4410 870 9902
870
9902
1234

870 found at index 2
9902 found at index 5
1234 not found

870 มีสองช่อง คือ index 2 กับ 4 ฟังก์ชันตอบ 2 เพราะเจอก่อน ถ้าโจทย์ถามอย่างอื่น ก็แค่เปลี่ยนสิ่งที่ทำตอนเจอ

#include <stdio.h>

int ticket[1000];

int main()
{
    int n, target;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ticket[i]);
    }
    scanf("%d", &target);
    int count = 0;
    int last = -1;
    printf("indexes:");
    for (int i = 0; i < n; i++) {
        if (ticket[i] == target) {
            printf(" %d", i);
            count++;
            last = i;
        }
    }
    printf("\n");
    printf("count = %d, last = %d\n", count, last);
    return 0;
}

6
1024 5531 870 4410 870 9902
870

indexes: 2 4
count = 2, last = 4

หาทุกตำแหน่ง นับจำนวน หรือหาตำแหน่งสุดท้าย ต้องไล่จนครบทุกช่อง ห้ามหยุดที่ตัวแรก ส่วนตำแหน่งสุดท้ายจะไล่จากท้ายแถวมาแล้วหยุดที่ตัวแรกที่เจอก็ได้

ค้นหาชื่อในอาเรย์ของ struct

ค้นหาด้วยข้อความก็ไล่แบบเดียวกัน แค่เทียบด้วย strcmp แทน == ตัวอย่างนี้คือเมนูของโรงอาหาร ค้นหาราคาจากชื่อเมนู

#include <stdio.h>
#include <string.h>

struct dish {
    char name[21];
    int price;
};

struct dish menu[100];

int find_dish(struct dish list[], int n, const char *name)
{
    for (int i = 0; i < n; i++) {
        if (strcmp(list[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s %d", menu[i].name, &menu[i].price);
    }
    char order[21];
    while (scanf("%s", order) == 1) {
        int index = find_dish(menu, n, order);
        if (index == -1) {
            printf("%s: no such dish\n", order);
        } else {
            printf("%s: %d baht\n", order, menu[index].price);
        }
    }
    return 0;
}

4
padthai 50
somtam 40
khaomankai 45
kaprao 50
somtam
pizza
kaprao

somtam: 40 baht
pizza: no such dish
kaprao: 50 baht

ค้นหาแบบไล่ใช้เวลาเท่าไร

หนึ่งคำถาม ไล่ไม่เกิน n ช่อง ถ้า n เป็นแสนก็ยังเร็วมาก ปัญหาอยู่ที่โจทย์ที่มีหลายคำถาม เช่น รายการ n = 100,000 ตัว และคำถาม Q = 100,000 ข้อ กรณีที่แย่ที่สุดคือทุกคำถามไม่เจอ ต้องไล่ครบทุกครั้ง รวม n × Q = 1010 ครั้ง ตามหลักในหน้า 4.5 ไม่มีทางทัน 1 วินาที ทางออกมีสองแบบ

  • ถ้าค่าเป็นจำนวนเต็มช่วงแคบ ใช้อาเรย์ seen หรืออาเรย์นับแบบหน้า 5.3 ตอบแต่ละคำถามได้ทันทีโดยไม่ต้องไล่
  • ถ้าค่าใหญ่ เรียงข้อมูลด้วย qsort ก่อนครั้งเดียว แล้วใช้ binary search ที่เขียนแบบ recursion ไปแล้วในหน้า 9.4 ซึ่งตัดครึ่งไปทีละรอบ ข้อมูลแสนตัวใช้ไม่เกิน 17 รอบต่อคำถาม บทที่ 19 จะทำครบทุกกรณี เช่น หาตัวแรกที่มากกว่าหรือเท่ากับค่าที่ถาม นี่คืออีกเหตุผลหนึ่งที่ต้องเรียง

อยากรู้ว่าคำว่า the อยู่ตรงไหนบ้างในประโยค ให้ลองวางคำไว้ใต้ประโยคที่ตำแหน่งเริ่ม i = 0 เทียบทีละตัวอักษร ถ้าตรงครบทุกตัวก็คือเจอ แล้วเลื่อนคำไปทางขวาหนึ่งช่อง ทำซ้ำจนคำเลยท้ายประโยค ประโยคยาว n ตัว คำยาว m ตัว ตำแหน่งเริ่มสุดท้ายที่เป็นไปได้คือ n - m

#include <stdio.h>
#include <string.h>

char text[1005], word[105];

void strip_newline(char s[])
{
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '\n' || s[i] == '\r') {
            s[i] = '\0';
        }
    }
}

int main()
{
    fgets(text, sizeof text, stdin);
    fgets(word, sizeof word, stdin);
    strip_newline(text); // (1)!
    strip_newline(word);
    int n = strlen(text);
    int m = strlen(word);
    int count = 0;
    for (int i = 0; i + m <= n; i++) { // (2)!
        int j = 0;
        while (j < m && text[i + j] == word[j]) { // (3)!
            j++;
        }
        if (j == m) {
            printf("found at %d\n", i);
            count++;
        }
    }
    printf("count = %d\n", count);
    return 0;
}
  1. ตัด '\n' กับ '\r' ที่ fgets ติดมาด้วยแบบหน้า 6.3 ทั้งประโยคและคำ ลืมตัดของคำแล้วจะไม่เจออะไรเลย ดูในส่วนลองทำให้พัง
  2. เริ่มได้ถึง i = n - m เขียนเป็น i + m <= n จะเห็นชัดว่าคำทั้งคำยังอยู่ในประโยค ความยาวเก็บไว้ในตัวแปรก่อน ไม่เรียก strlen ในเงื่อนไขลูปตามหน้า 6.4
  3. เทียบไปเรื่อยๆ จนกว่าจะเจอตัวที่ไม่ตรง ถ้าหลุดลูปตอน j == m แปลว่าตรงครบทุกตัว
the cat sat on the mat with the other cat
the

found at 0
found at 15
found at 28
found at 33
count = 4

เจอสี่ครั้ง ไม่ใช่สาม ครั้งที่ 4 คือ the ที่อยู่ข้างในคำว่า other โปรแกรมนี้หาข้อความ ไม่ได้หาคำ ถ้าโจทย์ต้องการเฉพาะคำที่อยู่เดี่ยวๆ ให้เช็กเพิ่มว่าตัวก่อนหน้าและตัวถัดไปเป็นช่องว่างหรือเป็นขอบของประโยค

#include <stdio.h>
#include <string.h>

char text[1005], word[105];

void strip_newline(char s[])
{
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '\n' || s[i] == '\r') {
            s[i] = '\0';
        }
    }
}

int main()
{
    fgets(text, sizeof text, stdin);
    fgets(word, sizeof word, stdin);
    strip_newline(text);
    strip_newline(word);
    int n = strlen(text);
    int m = strlen(word);
    int count = 0;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text[i + j] == word[j]) {
            j++;
        }
        int left_ok = (i == 0 || text[i - 1] == ' ');
        int right_ok = (i + m == n || text[i + m] == ' ');
        if (j == m && left_ok && right_ok) {
            printf("found at %d\n", i);
            count++;
        }
    }
    printf("count = %d\n", count);
    return 0;
}

the cat sat on the mat with the other cat
the

found at 0
found at 15
found at 28
count = 3

เงื่อนไข i == 0 ต้องอยู่หน้า text[i - 1] เพื่อไม่ให้แตะ text[-1] ส่วน text[i + m] เมื่อ i + m == n คือ '\0' ซึ่งอยู่ในอาเรย์จริง แต่เช็กให้ชัดก็อ่านง่ายกว่า

นับซ้อนกันหรือไม่ซ้อน

หา ana ใน banana เจอที่ตำแหน่ง 1 และ 3 สองครั้งนี้ใช้ตัว a ตรงกลางร่วมกัน ถ้าโจทย์บอกว่า "นับโดยไม่ให้ซ้อนกัน" เช่น ตัดคำออกจากแถบกระดาษ ตัดแล้วตัวอักษรนั้นหายไป พอเจอแล้วต้องกระโดดข้ามไปทั้งคำ คือเพิ่ม i อีก m แทน 1

#include <stdio.h>
#include <string.h>

char text[1005], word[105];

int matches_at(int i, int m)
{
    for (int j = 0; j < m; j++) {
        if (text[i + j] != word[j]) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    while (scanf("%s %s", text, word) == 2) {
        int n = strlen(text);
        int m = strlen(word);
        int overlapping = 0;
        for (int i = 0; i + m <= n; i++) {
            if (matches_at(i, m)) {
                overlapping++;
            }
        }
        int separate = 0;
        int i = 0;
        while (i + m <= n) {
            if (matches_at(i, m)) {
                separate++;
                i += m; // (1)!
            } else {
                i++;
            }
        }
        printf("%s in %s: overlapping %d, separate %d\n", word, text, overlapping, separate);
    }
    return 0;
}
  1. เจอแล้วข้ามทั้งคำ ไม่เจอเลื่อนทีละช่อง การนับแบบไม่ซ้อนจึงต้องใช้ while ที่เลือกได้ว่าจะเพิ่ม i เท่าไร
banana ana
aaaaa aa
mississippi issi
abcabc abc

ana in banana: overlapping 2, separate 1
aa in aaaaa: overlapping 4, separate 2
issi in mississippi: overlapping 2, separate 1
abc in abcabc: overlapping 2, separate 2

ตัวอย่างนี้อ่านด้วย %s ทีละคู่จนหมดข้อมูล เพราะแต่ละบรรทัดไม่มีช่องว่างในข้อความ อ่านโจทย์ให้ดีว่าต้องการนับแบบไหน สองแบบได้คำตอบต่างกันเฉพาะเมื่อคำซ้อนทับตัวเองได้ อย่าง aa หรือ issi

strstr ใน string.h

string.h มีฟังก์ชันหาข้อความให้ชื่อ strstr(text, word) คืนที่อยู่ของตำแหน่งแรกที่เจอ หรือ NULL ถ้าไม่เจอ เอาที่อยู่ที่ได้ลบกับที่อยู่ของช่องแรก ก็ได้เป็นตำแหน่ง แบบการลบ pointer ในบทที่ 10 ถ้าจะหาต่อ ให้เริ่มหาใหม่จากตำแหน่งถัดไป

#include <stdio.h>
#include <string.h>

char text[1005], word[105];

int main()
{
    scanf("%s %s", text, word);
    int count = 0;
    char *found = strstr(text, word);
    while (found != NULL) {
        printf("found at %d\n", (int)(found - text));
        count++;
        found = strstr(found + 1, word);
    }
    printf("count = %d\n", count);
    return 0;
}

banana ana

found at 1
found at 3
count = 2

หาต่อจาก found + 1 จึงนับแบบซ้อนกัน ถ้าต้องการแบบไม่ซ้อนให้หาต่อจาก found + m แต่ให้เขียนเองให้เป็นก่อน เพราะโจทย์ค่ายหลายข้อให้ปรับการเทียบ เช่น ไม่สนตัวพิมพ์ใหญ่เล็ก หรือให้ผิดได้หนึ่งตัว ซึ่ง strstr ทำไม่ได้

การหาแบบนี้เทียบได้ถึงราว n × m ตัวอักษร เช่น ประโยคเป็น a แสนตัว และคำเป็น a 999 ตัวตามด้วย b ทุกตำแหน่งเริ่มต้องเทียบเกือบครบทั้งคำ รวมราว 108 ครั้ง ยังพอไหว แต่ถ้าทั้งคู่ยาวเป็นแสนก็ไม่ทัน วิธีค้นหาข้อความที่เร็วกว่านี้อยู่ในบทที่ 30

ลองทำให้พัง

แบบที่ 1 พิมพ์ไม่เจอไว้ในลูป

ความผิดพลาดที่เจอบ่อยที่สุดของการค้นหาแบบไล่ คือตัดสินว่าไม่เจอทั้งที่ยังดูไม่ครบ

#include <stdio.h>

int ticket[1000];

int main()
{
    int n, target;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ticket[i]);
    }
    scanf("%d", &target);
    for (int i = 0; i < n; i++) {
        if (ticket[i] == target) {
            printf("found at index %d\n", i);
        } else {
            printf("not found\n");
        }
    }
    return 0;
}

6
1024 5531 870 4410 870 9902
870

not found
not found
found at index 2
not found
found at index 4
not found

ทุกช่องที่ไม่ใช่ 870 พิมพ์ not found หนึ่งบรรทัด ช่องที่ไม่ตรงหนึ่งช่องบอกได้แค่ว่าช่องนั้นไม่ใช่ จะสรุปว่าไม่เจอได้ก็ต่อเมื่อดูครบทุกช่องแล้ว คือหลังลูปจบ ใช้ฟังก์ชันที่คืน -1 แบบตัวอย่างแรก หรือใช้ตัวแปรนับที่เช็กหลังลูป

แบบที่ 2 ลืมตัด '\n' ของคำ

ในโปรแกรม find_word ลบบรรทัด strip_newline(word); ออก

#include <stdio.h>
#include <string.h>

char text[1005], word[105];

void strip_newline(char s[])
{
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '\n' || s[i] == '\r') {
            s[i] = '\0';
        }
    }
}

int main()
{
    fgets(text, sizeof text, stdin);
    fgets(word, sizeof word, stdin);
    strip_newline(text);
    int n = strlen(text);
    int m = strlen(word);
    int count = 0;
    for (int i = 0; i + m <= n; i++) {
        int j = 0;
        while (j < m && text[i + j] == word[j]) {
            j++;
        }
        if (j == m) {
            printf("found at %d\n", i);
            count++;
        }
    }
    printf("count = %d\n", count);
    return 0;
}

the cat sat on the mat with the other cat
the

count = 0

ไม่เจอเลยสักครั้ง เพราะ word คือ the ตามด้วย '\n' ยาว 4 ตัว ตำแหน่งที่มี the ตรงสามตัวแรก แต่ตัวที่สี่ในประโยคเป็นช่องว่างหรือตัวอักษร ไม่ใช่ '\n' ไม่มีอะไรเตือน ยังดีที่ตัวอย่างในโจทย์จะผิดให้เห็นทันที ถ้าได้ 0 ทั้งที่เห็นกับตาว่ามี ให้สงสัย '\n' ก่อน

สรุป

  • counting sort นับด้วยอาเรย์นับแล้วพิมพ์ตามค่า ไม่ต้องเทียบ เร็วมาก ใช้ได้เมื่อค่าเป็นจำนวนเต็มในช่วงแคบ ค่าติดลบให้เลื่อนก่อน
  • ค้นหาแบบไล่ดูทีละช่อง เจอแล้วคืนตำแหน่ง ไม่เจอคืน -1 ใช้กับข้อมูลที่ไม่เรียงได้ สรุปว่าไม่เจอได้หลังลูปจบเท่านั้น
  • ค้นหาข้อความในอาเรย์ของ struct ใช้ strcmp(...) == 0
  • คำถามเป็นแสนกับข้อมูลเป็นแสน ไล่ไม่ทัน ใช้อาเรย์นับเมื่อค่าเล็ก หรือเรียงแล้วใช้ binary search จากหน้า 9.4 ซึ่งบทที่ 19 จะทำครบทุกกรณี
  • หาคำในประโยค ลองทุกตำแหน่งเริ่ม i + m <= n เทียบทีละตัว ระวังคำที่ซ่อนอยู่ในคำอื่น และอ่านโจทย์ว่านับแบบซ้อนหรือไม่ซ้อน
  • ข้อความที่อ่านด้วย fgets ต้องตัด '\n' ทุกครั้ง ทั้งประโยคและคำที่จะหา