5.3 นับความถี่ด้วยอาเรย์นับ

ครูตรวจข้อสอบย่อยคะแนนเต็ม 10 เสร็จ อยากรู้ว่าคะแนนแต่ละค่ามีกี่คน ได้ 10 กี่คน ได้ 9 กี่คน ไล่ลงไปถึง 0 คำถามแบบ "แต่ละค่าเกิดขึ้นกี่ครั้ง" เรียกว่าหา ความถี่ (frequency) เป็นโจทย์ที่เจอบ่อยมาก และมีวิธีที่เร็วมากถ้าค่าที่ต้องนับเป็นจำนวนเต็มช่วงไม่กว้าง หน้านี้คือวิธีนั้น

ให้ค่าเป็นเลขช่อง

ในหน้าก่อน เราใช้ index บอกว่า "คนที่เท่าไร" แล้วเก็บคะแนนไว้ในช่อง ครั้งนี้กลับด้าน ให้ คะแนนเป็น index แล้วเก็บ จำนวนคน ไว้ในช่อง

• มีอาเรย์ count ที่ช่อง count[s] เก็บว่ามีกี่คนที่ได้คะแนน s เริ่มต้นทุกช่องเป็น 0
• อ่านคะแนนมาทีละคน ได้ score เท่าไร ก็ไปเพิ่มช่องนั้นหนึ่ง count[score]++

อาเรย์ที่ใช้นับแบบนี้เรียกว่า อาเรย์นับ (counting array) คะแนนมีได้ 0 ถึง 10 รวม 11 ค่า จึงต้องมี 11 ช่อง

#include <stdio.h>

int main()
{
    int count[11] = {0}; // (1)!
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++; // (2)!
    }
    for (int s = 0; s <= 10; s++) { // (3)!
        printf("%d: %d\n", s, count[s]);
    }
    return 0;
}

1. 11 ช่องสำหรับคะแนน 0 ถึง 10 และ = {0} ให้ทุกช่องเริ่มที่ 0 ห้ามลืม
2. count[score] เป็นตัวแปร int ธรรมดาตัวหนึ่ง ++ จึงใช้ได้เหมือนเพิ่มค่าตัวนับในบทที่ 4
3. วนตามค่าคะแนน ไม่ใช่ตามจำนวนคน ช่องสุดท้ายคือ 10 จึงใช้ <= ได้ เพราะอาเรย์มี 11 ช่อง

8
7 8 7 10 9 7 3 8

0: 0
1: 0
2: 0
3: 1
4: 0
5: 0
6: 0
7: 3
8: 2
9: 1
10: 1

โปรแกรมนี้ไม่ได้เก็บคะแนนของแต่ละคนเลย อ่านแล้วเพิ่มช่องที่ตรงกันทันที ข้อมูลที่ต้องจำมีแค่ 11 ตัวนับ จะมีนักเรียนกี่คนก็ใช้หน่วยความจำเท่าเดิม และอ่านข้อมูลแค่รอบเดียว

คะแนนที่มีคนได้มากที่สุด

พอมีอาเรย์นับแล้ว คำถามอื่นตอบได้ด้วยเครื่องมือจากหน้า 5.2 เช่น คะแนนไหนมีคนได้มากที่สุด ก็คือหา index ของช่องที่มีค่ามากสุดในอาเรย์ count ตัวอย่างนี้คะแนนเต็ม 100 จึงต้องมี 101 ช่อง และพิมพ์เฉพาะคะแนนที่มีคนได้

#include <stdio.h>

int main()
{
    int count[101] = {0};
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++;
    }
    for (int s = 0; s <= 100; s++) {
        if (count[s] > 0) {
            printf("%d %d\n", s, count[s]);
        }
    }
    int mode = 0;
    for (int s = 1; s <= 100; s++) {
        if (count[s] > count[mode]) {
            mode = s;
        }
    }
    printf("most common = %d (%d students)\n", mode, count[mode]);
    return 0;
}

10
72 85 64 85 90 72 85 58 72 100

58 1
64 1
72 3
85 3
90 1
100 1
most common = 72 (3 students)

• ผลออกมาเรียงจากคะแนนน้อยไปมากเอง เพราะเราวน index จาก 0 ขึ้นไป ทั้งที่ข้อมูลเข้าไม่ได้เรียง
• 72 กับ 85 มีคนได้ 3 คนเท่ากัน ใช้ > จึงได้คะแนนที่น้อยกว่า ถ้าโจทย์อยากได้คะแนนที่มากกว่าให้ใช้ >= เหมือนหน้า 5.2

เช็กว่าเคยเห็นหรือยัง

บางโจทย์ไม่ได้ต้องการจำนวนครั้ง แค่อยากรู้ว่ามีหรือไม่มี เช่น ห้องหนึ่งมีนักเรียน N คน เลขที่ 1 ถึง N ครูเก็บรายชื่อการส่งการบ้านไว้ M ครั้ง บางคนส่งซ้ำ ครูอยากรู้ว่ามีกี่คนที่ส่งแล้ว และเลขที่ไหนยังไม่ส่ง

#include <stdio.h>

int main()
{
    int sent[41] = {0}; // (1)!
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int number;
        scanf("%d", &number);
        sent[number] = 1; // (2)!
    }
    int done = 0;
    for (int number = 1; number <= n; number++) {
        if (sent[number] == 1) {
            done++;
        }
    }
    printf("sent = %d\n", done);
    printf("missing:");
    for (int number = 1; number <= n; number++) {
        if (sent[number] == 0) {
            printf(" %d", number);
        }
    }
    printf("\n");
    return 0;
}

1. เลขที่มีได้ 1 ถึง 40 ขอ 41 ช่อง แล้วไม่ใช้ช่อง 0 ยอมเสียหนึ่งช่อง แลกกับการที่เลขที่ตรงกับ index พอดี ไม่ต้องลบหนึ่งทุกครั้ง
2. ใส่ 1 แทน ++ ส่งกี่ครั้งก็ยังเป็น 1 จึงนับคนที่ส่งซ้ำแค่ครั้งเดียว

8 9
3 1 5 3 8 2 5 3 6

sent = 6
missing: 4 7

อาเรย์แบบนี้มักตั้งชื่อว่า seen หรือ visited แปลว่าเคยเห็นแล้ว จะได้เจออีกหลายครั้งจนถึงบทกราฟ

ค่าที่ติดลบ

index ติดลบไม่ได้ ถ้าค่าที่จะนับมีติดลบ ให้ เลื่อนทุกค่าด้วยค่าคงที่ ก่อนใช้เป็น index เช่น อุณหภูมิต่ำสุดของแต่ละวันบนยอดดอยอยู่ระหว่าง -10 ถึง 30 องศา รวม 41 ค่า บวก 10 เข้าไปทุกค่า -10 จะกลายเป็นช่อง 0 และ 30 กลายเป็นช่อง 40 ตอนพิมพ์ก็ลบ 10 กลับ

#include <stdio.h>

int main()
{
    int count[41] = {0};
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        count[temp + 10]++;
    }
    for (int k = 0; k <= 40; k++) {
        if (count[k] > 0) {
            printf("%d degrees: %d days\n", k - 10, count[k]);
        }
    }
    return 0;
}

7
2 -1 0 2 -3 5 -1

-3 degrees: 1 days
-1 degrees: 2 days
0 degrees: 1 days
2 degrees: 2 days
5 degrees: 1 days

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

ลองนึกถึงวิธีที่ไม่ใช้อาเรย์นับ ถ้าจะหาว่าคะแนนแต่ละค่ามีกี่คน ต้องวนคะแนนทุกค่า 0 ถึง 100 แล้วในแต่ละค่าวนดูนักเรียนทุกคน นักเรียนแสนคนก็ต้องเทียบ 101 × 100000 ประมาณสิบล้านครั้ง ส่วนอาเรย์นับดูนักเรียนแต่ละคนครั้งเดียว แค่แสนครั้ง ยิ่งช่วงของค่ากว้าง ความต่างก็ยิ่งมาก

เงื่อนไขของวิธีนี้คือ

• ค่าที่นับต้องเป็นจำนวนเต็ม เพราะต้องใช้เป็น index
• ช่วงของค่าต้องไม่กว้างเกินจำนวนช่องที่ประกาศได้ ค่าถึง 10⁶ ยังพอไหว แต่ต้องประกาศอาเรย์นอก main ซึ่งอธิบายในหน้า 5.5 ถ้าค่าถึง 10⁹ ใช้วิธีนี้ไม่ได้ ต้องเรียงข้อมูลก่อน ซึ่งอยู่ในบทที่ 13

ลองทำให้พัง

แบบที่ 1 ลืม = {0}

ในโปรแกรม quiz ลบ = {0} ออก เหลือ int count[11]; คอมไพล์ด้วย -Wall แล้วไม่มีคำเตือนเลย บนเครื่องที่เขียนเอกสารนี้ ป้อนข้อมูลเดิมแล้วได้แบบนี้

0: 0
1: 0
2: 0
3: 2
4: -1361052432
5: 63
6: 36313160
7: 32762
8: 223994994
9: 380
10: 1

ช่องที่ไม่ได้ใส่ค่าเริ่มต้นมีค่าขยะค้างอยู่ ++ จึงไปบวกต่อจากค่าขยะ ที่น่ากลัวคือบางช่องดูเหมือนถูก ช่อง 0 ถึง 2 เป็น 0 และช่อง 3 ได้ 2 ทั้งที่มีคนได้ 3 คะแนนแค่คนเดียว รันซ้ำสามครั้ง ช่อง 4 5 8 9 เปลี่ยนไปทุกครั้ง ส่วนช่องอื่นได้เท่าเดิม ถ้าเห็นตัวนับมีค่าแปลกๆ ให้สงสัยเรื่องค่าเริ่มต้นก่อน

แบบที่ 2 ขอช่องขาดไปหนึ่ง

คะแนนเต็ม 100 แต่ประกาศ int count[100] = {0}; ช่องมีแค่ 0 ถึง 99 ไม่มีช่อง 100

#include <stdio.h>

int main()
{
    int count[100] = {0};
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++;
    }
    printf("score 100: %d students\n", count[100]);
    printf("score 99: %d students\n", count[99]);
    return 0;
}

4
100 99 100 100

ใน Code::Blocks คอมไพล์ผ่านโดยไม่มีคำเตือน บนเครื่องที่เขียนเอกสารนี้ รันสี่ครั้งได้บรรทัดแรกเป็น score 100: 2068505747 students 1900800483 1275980067 และ 1071769603 ไม่ซ้ำกันเลย ส่วนบรรทัดของคะแนน 99 ได้ 1 ถูกทุกครั้ง ผิดเฉพาะคนที่ได้เต็ม ซึ่งเป็นชุดทดสอบที่ grader ชอบใส่

กฎคือ ค่าตั้งแต่ 0 ถึง K ต้องมี K + 1 ช่อง ทำไมช่องที่ไม่มีอยู่จริงถึงให้ค่าแปลกแบบนี้ และอาการอื่นที่หนักกว่านี้ อยู่ในหน้า 5.5

สรุป

• อาเรย์นับใช้ค่าเป็น index แล้วเก็บจำนวนครั้งไว้ในช่อง count[x]++
• ต้องเริ่มทุกช่องที่ 0 ด้วย = {0} ลืมแล้วได้ค่าขยะโดยไม่มีคำเตือน
• ค่า 0 ถึง K ต้องมี K + 1 ช่อง
• วน index จากน้อยไปมาก ผลจะเรียงตามค่าให้เอง
• อยากรู้แค่มีหรือไม่มี ใช้อาเรย์ seen ใส่ 1
• ค่าติดลบให้บวกค่าคงที่ก่อนใช้เป็น index ค่าที่ช่วงกว้างมากใช้วิธีนี้ไม่ได้