5.5 แทรก ลบ และขอบของอาเรย์

คนในแถวซื้อข้าวออกจากแถวกลางคัน คนข้างหลังทุกคนก็ขยับขึ้นมาหนึ่งที่ มีคนแซงเข้ามา คนข้างหลังก็ถอยไปหนึ่งที่ อาเรย์ทำงานแบบเดียวกัน ช่องวางติดกันตายตัว จะลบหรือแทรกตรงกลางต้องเลื่อนสมาชิกที่เหลือเอง ครึ่งหลังของหน้าดูว่าเกิดอะไรขึ้นเมื่อใช้ช่องที่ไม่มีอยู่จริง และทำไมอาเรย์ใหญ่ต้องประกาศไว้นอก main

ลบสมาชิก

แถวมี N คน แต่ละคนถือบัตรคิวคนละเลข คนที่ยืนลำดับที่ p ออกจากแถว ลำดับที่ p อยู่ช่อง p - 1 ทุกคนที่อยู่หลังเขาต้องขยับขึ้นมาหนึ่งช่อง แล้วแถวก็สั้นลงหนึ่ง

#include <stdio.h>

int main()
{
    int line[100];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &line[i]);
    }
    int p;
    scanf("%d", &p);
    for (int i = p - 1; i < n - 1; i++) { // (1)!
        line[i] = line[i + 1];
    }
    n--; // (2)!
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", line[i]);
    }
    printf("\n");
    return 0;
}

เริ่มจากช่องของคนที่ออก เอาค่าช่องถัดไปมาทับ ทำจาก ซ้ายไปขวา หยุดที่ n - 2 เพราะช่องสุดท้ายที่ต้องอ่านคือ line[n - 1]
ช่องสุดท้ายเดิมยังมีค่าค้างอยู่ ไม่ต้องลบ แค่ลด n ลง ช่องนั้นก็อยู่นอกแถวแล้ว

6
11 12 13 14 15 16
3

11 12 14 15 16

แทรกสมาชิก

คราวนี้มีคนถือบัตรเลข x แทรกเข้ามาให้ตัวเองเป็นคนลำดับที่ p ทุกคนตั้งแต่ช่อง p - 1 ไปต้องถอยหลังหนึ่งช่องก่อน ให้ช่องนั้นว่าง แล้วค่อยใส่ x ลงไป

ลำดับการเลื่อนสำคัญมาก ต้องเริ่มจาก คนท้ายแถวก่อน คนท้ายถอยไปช่องว่างที่อยู่หลังแถว คนรองสุดท้ายจึงถอยไปช่องที่คนท้ายเพิ่งออกมาได้ ถ้าเริ่มจากคนหน้าก่อน เขาจะไปยืนทับคนข้างหลังที่ยังไม่ได้ขยับ

#include <stdio.h>

int main()
{
    int line[101]; // (1)!
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &line[i]);
    }
    int p, x;
    scanf("%d %d", &p, &x);
    for (int i = n; i > p - 1; i--) { // (2)!
        line[i] = line[i - 1];
    }
    line[p - 1] = x;
    n++;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", line[i]);
    }
    printf("\n");
    return 0;
}

N ไม่เกิน 100 แต่แทรกแล้วมี N + 1 คน จึงต้องเผื่อไว้ 101 ช่อง
วนจาก ขวาไปซ้าย เริ่มที่ช่อง n ซึ่งว่างอยู่ ให้รับค่าจากช่อง n - 1 แล้วถอยลงมาเรื่อยๆ รอบสุดท้ายคือ i = p ช่อง p รับค่าจากช่อง p - 1 ช่อง p - 1 จึงพร้อมรับ x

5
11 12 13 14 15
2 99

11 99 12 13 14 15

ลองกับขอบด้วยทุกครั้ง p = 1 แทรกหัวแถว ทุกคนต้องถอย และ p = n + 1 แทรกท้ายแถว ลูปไม่ทำงานเลยสักรอบ แค่ใส่ x ที่ช่อง n ทั้งสองกรณีโปรแกรมนี้ทำได้ถูกโดยไม่ต้องเขียนกรณีพิเศษ

หมุนแถว

หมุนแถวไปทางซ้ายหนึ่งช่อง คือคนหัวแถวออกไปต่อท้าย ก็คือลบช่อง 0 แล้วใส่ค่านั้นที่ท้าย ต้องจำค่าหัวแถวไว้ในตัวแปรพักก่อนจะโดนทับ

#include <stdio.h>

int main()
{
    int line[100];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &line[i]);
    }
    int first = line[0];
    for (int i = 0; i < n - 1; i++) {
        line[i] = line[i + 1];
    }
    line[n - 1] = first;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", line[i]);
    }
    printf("\n");
    return 0;
}

5
11 12 13 14 15

12 13 14 15 11

ถ้าต้องหมุน K ช่อง อย่าวนหมุนทีละช่อง K รอบ เพราะ K อาจเป็นพันล้าน ลองคิดดูว่าหลังหมุน K ช่อง ช่อง i ควรได้ค่ามาจากช่องไหนของอาเรย์เดิม แล้วใช้ % จากหน้า 1.2 ช่วย

ลองทำให้พัง เลื่อนผิดทาง

ในโปรแกรม cut-in เปลี่ยนลูปเลื่อนให้วนจากซ้ายไปขวา เหมือนตอนลบ

#include <stdio.h>

int main()
{
    int line[101];
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &line[i]);
    }
    int p, x;
    scanf("%d %d", &p, &x);
    for (int i = p; i <= n; i++) {
        line[i] = line[i - 1];
    }
    line[p - 1] = x;
    n++;
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", line[i]);
    }
    printf("\n");
    return 0;
}

5
11 12 13 14 15
2 99

11 99 12 12 12 12

รอบแรก 12 ถูกคัดลอกไปทับ 13 รอบถัดไปคัดลอกช่องนั้น ซึ่งตอนนี้เป็น 12 ไปทับ 14 ต่อไปเรื่อยๆ จน 12 ไหลไปเต็มแถว ค่าเดิมหายหมดก่อนจะได้ขยับ จำง่ายๆ ลบเลื่อนจากซ้าย แทรกเลื่อนจากขวา เริ่มจากฝั่งที่ไม่ทับค่าที่ยังไม่ได้ใช้

ใช้ช่องที่ไม่มีอยู่จริง

ภาษา C ไม่ตรวจว่า index อยู่ในขอบเขต อาเรย์ int score[5] มีช่อง 0 ถึง 4 แต่ถ้าเขียน score[5] หรือ score[-1] โปรแกรมก็ยังคอมไพล์ได้ และตอนรันจะไปอ่านหรือเขียนหน่วยความจำตรงที่ควรเป็นช่องนั้นถ้ามันมีอยู่จริง ซึ่งเป็นของอย่างอื่น ผลที่ได้ขึ้นกับว่าตรงนั้นเป็นของอะไร จึงไม่มีอะไรรับประกัน ทุกอาการด้านล่างเกิดบนเครื่องที่เขียนเอกสารนี้ ถ้าน้องลองเองอาจได้ไม่เหมือน

อาการที่ 1 อ่านได้ค่าที่ดูปกติ

ลูปที่ใช้ <= แทน < คือสาเหตุอันดับหนึ่ง

#include <stdio.h>

int main()
{
    int score[5] = {70, 85, 90, 65, 80};
    for (int i = 0; i <= 5; i++) {
        printf("score[%d] = %d\n", i, score[i]);
    }
    return 0;
}

คอมไพล์ใน Code::Blocks ไม่มีคำเตือน รันสี่ครั้ง บรรทัดสุดท้ายเป็น score[5] = 0 ทุกครั้ง ห้าบรรทัดแรกถูกหมด และ 0 ก็ดูเป็นคะแนนที่เป็นไปได้ ถ้าโจทย์ให้หาค่าน้อยสุด คำตอบจะผิดเป็น 0 โดยไม่มีอะไรเตือนเลย

พอคอมไพล์ด้วย -O2 -Wall -Wextra แบบตัวตรวจของเว็บนี้ gcc ถึงจะเตือน

oob_read.c:7:9: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
    7 |         printf("score[%d] = %d\n", i, score[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oob_read.c:6:23: note: within this loop
    6 |     for (int i = 0; i <= 5; i++) {
      |                     ~~^~~~

ข้อความแปลว่ารอบที่ i เป็น 5 ทำสิ่งที่มาตรฐานไม่ได้กำหนดผลไว้ และโปรแกรมที่คอมไพล์แบบนี้พิมพ์ score[5] เป็น 426 321 413 648 เปลี่ยนไปทุกครั้งที่รัน การเตือนนี้ขึ้นเพราะ -O2 ทำให้ gcc วิเคราะห์ลูปละเอียดขึ้น ซึ่ง Code::Blocks ที่ตั้งไว้ในบทที่ 0 ไม่ได้เปิด อย่าคาดหวังว่าจะมีคนเตือน

อาการที่ 2 เขียนทับของคนอื่น

เอาโปรแกรม cut-in ที่ถูกต้องมาเปลี่ยนแค่บรรทัดประกาศเป็น int line[5]; แล้วแทรกคนที่หกเข้าไปในแถวที่มีห้าคน ลูปเลื่อนจะเขียนลง line[5] ซึ่งไม่มีอยู่จริง คอมไพล์ใน Code::Blocks ไม่มีคำเตือน ป้อนข้อมูลชุดเดิม ผลที่ได้คือ

11 99 12 13 14 5

ห้าตัวแรกถูก แต่ตัวท้ายเป็น 5 แทนที่จะเป็น 15 รันกี่ครั้งก็ได้แบบนี้ ลองให้ลูปพิมพ์ค่าของ line[5] ออกมาทุกรอบ ได้ 0 1 2 3 4 5 ตรงกับ i ของลูปพิมพ์ทุกรอบ แปลว่าบนเครื่องที่เขียนเอกสารนี้ ตำแหน่งที่ควรเป็น line[5] คือที่เดียวกับตัวแปร i ของลูปพิมพ์ ค่า 15 ที่เลื่อนไปไว้ถูกทับทันทีที่ลูปตั้ง i = 0 และตอนพิมพ์ช่องสุดท้ายก็ได้ค่าของ i ซึ่งเป็น 5 กลับมา ถ้าเปลี่ยนเครื่อง เปลี่ยน compiler หรือแก้โค้ดส่วนอื่น ตัวแปรที่โดนทับก็อาจเป็นตัวอื่น บั๊กแบบนี้จึงหายากมาก

อาการที่ 3 โปรแกรมพัง

ถ้า index ไกลจากขอบมาก จะไปโดนหน่วยความจำที่โปรแกรมไม่มีสิทธิ์ใช้ Windows จะปิดโปรแกรมทันที

#include <stdio.h>

int main()
{
    int seat[100] = {0};
    int number;
    scanf("%d", &number);
    seat[number] = 1;
    printf("seat %d booked\n", number);
    printf("%d\n", seat[0]);
    return 0;
}

ป้อน 120 โปรแกรมพิมพ์ seat 120 booked แล้วจบปกติ ทั้งที่ช่อง 120 ไม่มีอยู่จริง ป้อน 100000 โปรแกรมปิดตัวโดยไม่พิมพ์อะไรเลย และ Code::Blocks ขึ้นว่า

Process returned -1073741819 (0xC0000005)

0xC0000005 คือรหัสของ Windows ที่แปลว่าเข้าถึงหน่วยความจำที่ไม่มีสิทธิ์ (access violation) ถ้าส่ง grader จะได้ผลว่า runtime error เหมือนหารด้วยศูนย์ในหน้า 1.2

ไม่พังไม่ได้แปลว่าถูก

ในสามอาการ มีแค่แบบที่ 3 ที่บอกตัวเองว่าผิด อีกสองแบบได้คำตอบที่ดูปกติ ก่อนส่งให้ไล่ดูทุกจุดที่ใช้ index ถามตัวเองว่าค่าน้อยสุดกับมากสุดของ index ตรงนั้นคือเท่าไร และอาเรย์มีช่องนั้นจริงไหม จุดที่ต้องดูเป็นพิเศษคือ <= ในลูป i - 1 ตอน i เป็น 0 i + 1 ตอน i เป็นตัวสุดท้าย และอาเรย์นับที่ขาดไปหนึ่งช่องแบบหน้า 5.3

อาเรย์ใหญ่ต้องอยู่นอก main

โจทย์ให้ N ถึง 10⁷ ก็ประกาศ 10⁷ ช่องตามขอบเขต ดูเหมือนไม่มีอะไรผิด

#include <stdio.h>

int main()
{
    int heights[10000000];
    int n;
    printf("start\n");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &heights[i]);
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += heights[i];
    }
    printf("%lld\n", sum);
    return 0;
}

คอมไพล์ผ่าน ไม่มีคำเตือน แต่พอรัน ไม่มีอะไรพิมพ์ออกมาเลยแม้แต่ start ที่อยู่ก่อนบรรทัดอื่น และ Code::Blocks ขึ้นว่า

Process returned -1073741571 (0xC00000FD)

0xC00000FD คือ stack overflow ตัวแปรที่ประกาศใน main อยู่ในหน่วยความจำส่วนที่เรียกว่า stack ซึ่งมีขนาดจำกัด อาเรย์ int สิบล้านช่องใช้ 40 ล้าน byte หรือประมาณ 40 MB ใหญ่กว่า stack หลายเท่า โปรแกรมจึงพังตั้งแต่ตอนเข้า main ก่อนจะได้ทำบรรทัดแรกเสียอีก

บนเครื่องที่เขียนเอกสารนี้ ลองเปลี่ยนขนาดดูทีละค่า int 500000 ช่อง (2 ล้าน byte) ยังรันได้ แต่ 520000 ช่องพังแล้ว stack ของโปรแกรมที่ GCC ของ Code::Blocks สร้างจึงประมาณ 2 MB เท่านั้น เทียบเป็นอาเรย์ int ได้ราวห้าแสนช่อง long long ได้แค่ครึ่งหนึ่งของนั้น

วิธีแก้คือย้ายบรรทัดประกาศออกไปไว้ นอก main ก่อนบรรทัด int main() ตัวแปรที่ประกาศนอกฟังก์ชันเรียกว่า ตัวแปร global ไม่ได้อยู่ใน stack แต่อยู่ในพื้นที่ที่จองไว้ตามขนาดจริงตั้งแต่โปรแกรมเริ่ม

#include <stdio.h>

int heights[10000000]; // (1)!

int main()
{
    int n;
    printf("start\n");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &heights[i]);
    }
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += heights[i];
    }
    printf("%lld\n", sum);
    printf("%d\n", heights[9999999]); // (2)!
    return 0;
}

ย้ายมาไว้นอก main ข้างล่างใช้งานเหมือนเดิมทุกอย่าง
ช่องสุดท้ายที่ไม่เคยใส่ค่าเป็น 0 ไม่ใช่ค่าขยะ

3
150 160 170

start
480
0

ได้ของแถมด้วย อาเรย์ global ทุกช่องเริ่มเป็น 0 เสมอ ไม่ต้องเขียน = {0} อาเรย์นับขนาด 10⁶ ช่องในหน้า 5.3 ก็ต้องประกาศแบบนี้

คนเขียนโปรแกรมแข่งขันส่วนใหญ่ประกาศอาเรย์ที่มีขนาดตามขอบเขตโจทย์ไว้นอก main ตั้งแต่แรกจนเป็นนิสัย เพราะไม่ต้องคิดว่าเกินสองเมกะไบต์หรือยัง และไม่ต้องห่วงเรื่องลืมใส่ค่าเริ่มต้น เฉลยแบบฝึกหัดของบทนี้ก็ทำแบบนั้น ข้อเสียของตัวแปร global และเหตุผลที่ไม่ควรใช้กับทุกอย่าง จะได้เห็นในบทที่ 8 ตอนเรียนเรื่องขอบเขตตัวแปร

ขนาดก็ยังมีขีดจำกัดอยู่ดี อาเรย์ทุกตัวในโปรแกรมรวมกันต้องไม่เกินหน่วยความจำที่โจทย์กำหนด ให้คูณจำนวนช่องกับขนาดของชนิดดูก่อน int ช่องละ 4 byte long long ช่องละ 8 byte

สรุป

ลบช่องตรงกลาง เลื่อนตัวที่อยู่หลังมาทางซ้าย วนจากซ้ายไปขวา แล้วลด n
แทรกช่องตรงกลาง เลื่อนไปทางขวา วนจาก ขวาไปซ้าย แล้วเพิ่ม n อาเรย์ต้องมีช่องเผื่อ
ภาษา C ไม่ตรวจขอบเขตของ index ใช้ช่องที่ไม่มีอยู่จริงอาจได้ค่าที่ดูปกติ ทับตัวแปรอื่น หรือพังด้วย 0xC0000005
อาเรย์ใน main ใหญ่เกินประมาณ 2 MB พังด้วย stack overflow 0xC00000FD
อาเรย์ใหญ่ประกาศนอก main ทุกช่องเริ่มเป็น 0 ให้เอง

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด