ทบทวน 1: การสร้างเลขสุ่มแบบไม่ซ้ำ

    เราได้เรียนรู้หลักการเขียนโปรแกรมภาษา C# อย่างง่ายสำหรับ function เดียวไปแล้ว มาบทนี้เรามาทบทวนความรู้ที่เราเคยเรียนรู้มาด้วยการเอาของที่เรียนมายำเป็นโปรแกรมอย่างง่าย โปรแกรมที่ผมกำลังแสดงให้ดูเป็นโปรแกรมที่สร้างเลขสุ่มจำนวนหนึ่งแต่มีเงื่อนไขว่าต้องไม่ซ้ำ เรื่องนี้สามารถนำไปประยุกต์ได้กว้างขวาง เช่นเอาไปทำเป็นเกมส์ ยกตัวอย่างเช่นเกมส์ไพ่ เราต้องสร้างไพ่ 52 ใบไม่ซ้ำ หรือใช้ในการสร้างแบบจำลองทางธุรกิจต่าง เป็นต้น ในที่นี้ผมขอเสนอสองวิธี ซึ่งเดี๋ยวเรามาเปรียบเทียบกันดูประสิทธิภาพว่าวิธีไหนดูดีกว่ากัน 

 

             rand.cs

class Global
{
   public static int MAX = 10000;
   public static int SEED = 10;
}

class Rand
{
   public static void Main()
   {
      Random r = new Random(Global.SEED);
      int[] arr = new int[Global.MAX+1];
      int rand;
      long count = 0;

      for (int i=1; i<=Global.MAX; i++) {
         arr[i] = 0;
         count++;
      }

      for (int i=1; i<=Global.MAX; i++) {
         do {
            count++;
            rand = r.Next() % Global.MAX + 1;

            if (arr[rand] == 0) {
               arr[rand] = i;
               break;
            }
         } while(true);
      }

     // for (int i=1; i<=Global.MAX; i++) {
      //   Console.Write("{0:00} ", arr[i]);
     // }
      Console.WriteLine("\n\nCount = {0}", count);
  
}
}

class Rand2
{

   public static void Main()
   {
      Random r = new Random(Global.SEED);
      int[] arr = new int[Global.MAX+1];
      int rand, i, j;
      long count = 0;

      for (i=1; i<=Global.MAX; i++) {
         do {
            rand = r.Next() % Global.MAX + 1;
            for (j=1; j<i; j++) {
               count++;
               if (arr[j] == rand) break;
            }
                  } while (i != j);
              arr[i] = rand;
           }
       //for (i=1; i<=Global.MAX; i++) {
             // Console.Write("{0:00} ", arr[i]);
            //}
           Console.WriteLine("\n\nCount = {0}", count);
      }
}

 

จะสังเกตได้ว่าเรามี class อยู่สาม class ดังนี้

class Global

     class แรกที่ชื่อว่า Global เอาไว้เก็บ ค่าคงที่ทั้งหลาย เราไม่สามารถสร้างตัวแปรนอก class ได้ ดังนั้นถ้าเราต้องการให้ตัวแปรหรือค่าคงที่มองเห็นได้จากหลายๆ class เราเลี่ยงได้โดยสร้าง class ขึ้นมา แล้วเอาตัวแปร หรือค่าคงที่นั้นใส่เข้าไป แล้วกำหนดให้เป็น public static ใครๆ ก็สามารถมองเห็น

class Rand2

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

class Rand

    วิธีนี้ผมมองในมุมกลับครับ คือเริ่มต้นผมทำให้ทุก element ใน array เป็น 0 หมายถึงยังไม่จอง แล้วผมก็วน loop เท่ากับจำนวนเลขสุ่มที่ต้องการ ในรอบแรกของ loop คือ 1 ผมสร้างเลขสุ่มเพื่อหาตำแหน่งในการเก็บเลข 1 นี้ ยกตัวอย่างเช่น random ได้เลข 30 หมายความว่า เลข 1 ให้เก็บที่ตำแหน่ง 30 แต่ถ้าตำแหน่ง 30 มีค่าที่ไม่ใช่ 0 อยู่แล้ว นั่นหมายความว่า element นั้นมีเลขอื่นจองอยู่แล้ว ถ้าเจอแบบนี้ก็ต้อง random เพื่อหาตำแหน่งต่อไป ทำอย่างนี้ไปจนหมดทุกค่า

การ Run Program

   สังเกตดูนะครับ โปรแกรมนี้มี 2 Main() compiler ตอนนี้มันสับสนครับไม่รู้จะเริ่ม Main() ไหนดี เรามีวิธีบอก compiler ครับว่าจะเลือก เอา Main() จาก class ไหนมา run เรา compile แบบนี้ครับ
csc /main:Rand  rand.cs     ในกรณีต้องการทดสอบ algorithm Rand
csc /main:Rand2 rand.cs     ในกรณีต้องการทดสอบ algorithm Rand2

ประสิทธิภาพ

    คุณว่า algorithm ไหนมีประสิทธิภาพกว่ากัน Rand หรือ Rand2 ผมว่าคุณน่าจะลอง run program ดูเองดีกว่า ผมแอบเอาตัวแปร count ดักจำนวนรอบในการคำนวณ ในกรณีที่คุณไม่อยากทดสอบเอง ผมมีผลการทดสอบโดยการสร้างเลขสุ่ม จำนวน 10,000 ตัว ผลปรากฏว่า

Rand  ใช้ 128,205 รอบ
Rand2 ใช้ 563,816,368 รอบ

จากตัวอย่างนี้คุณคงเห็นได้ว่า การเลือกใช้ algorithm นั้นก็สำคัญเหมือนกัน