สมมติว่าเรามีสิ่งของอยู่ทั้งหมด $n$ ชิ้น (เรียกว่าชิ้นที่ $0,1,2$ ไล่ไปจนถึงชิ้นที่ $n-1$) และต้องการสุ่มหยิบของเหล่านั้นออกมาเพียง $k$ ชิ้น อัลกอริทึมของเราจะมีหน้าตาเป็นอย่างไร? ในชั่วอึดใจแรกเราอาจจะเขียนโค้ดอย่างรวดเร็วเช่นนี้ออกมา

def pick_1(n, k):
    result = set()
    for _ in range(k):
        result.add(randint(0, n-1))
    return result

อัลกอริทึมนี้ก็ดูใช้งานได้ดีหาก $k$ มีขนาดเล็กๆ แต่ถ้าเพิ่มจำนวนสิ่งของที่ต้องการสุ่มหยิบขึ้นไป อาจพบว่าจำนวนสิ่งของจากผลลัพธ์มีน้อยกว่าจำนวนสิ่งของที่ต้องการสุ่มหยิบจริงๆ เพราะเราสามารถหยิบของซ้ำได้โดยไม่ทันระวังนั่นเอง¹

ตระหนักในข้อจำกัดข้างต้น เราอาจแก้โค้ดใหม่ให้กลายเป็น

def pick_2(n, k):
    result = set()
    while len(result) < k:
        result.add(randint(0, n-1))
    return result

แม้อัลกอริทึมนี้จะแก้ปัญหาการสุ่มสิ่งของแล้วได้ไม่ครบจำนวนชิ้นลงไป แต่มันก็ก่อให้เกิดปัญหาใหม่ขึ้นมาแทน นั่นก็คือเมื่อ $k$ มีค่าใหญ่ๆ (โดยเฉพาะอย่างยิ่งเมื่อเข้าใกล้ $n$) การจะสุ่มของชิ้นใหม่ให้ไม่ซ้ำกับชิ้นเดิมที่เคยสุ่มไปแล้วนั้นเป็นไปได้ยากมาก และทำให้เสียเวลาอยู่ในลูป while อย่างมากมายมหาศาล โค้ดชุดนี้จึงยังไม่เข้าท่าเท่าใดนัก …

อัลกอริทึมการสุ่มของที่ถูกต้องและทำงานได้อย่างรวดเร็วพอ จึงต้องเลียนแบบการสุ่มของในโลกความจริงที่เราอาศัยอยู่ นั่นก็คือเริ่มจากนำของทั้งหมดไปกองรวมกันยังที่หนึ่งก่อน (จะเรียกว่า “กองของเหลือ”) แล้วค่อยๆ สุ่มหยิบของออกมาจากกองของเหลือนั้น ซึ่งพอแปลเป็นโค้ดแล้วอาจเขียนได้แบบนี้

def pick_3(n, k):
    remain = list(range(n))
    result = set()
    for i in range(k):
        x = randint(0, n-1-i)
        remain[x], remain[-1] = remain[-1], remain[x]
        result.add(remain.pop())
    return result

โค้ดข้างต้นนี้²ใช้พื้นที่เก็บข้อมูล $O(n)$ เนื่องจากเรามีสิ่งของในกองของเหลือทุกชิ้น นอกจากนี้มันยังดูเหมือนว่าจะใช้เวลาเป็น $O(k)$ เพราะมีการวนลูปสุ่มหยิบของออกมาทั้งหมด $k$ รอบ … แต่เราต้องไม่ลืมว่าตอนแรกที่สร้างกองของเหลือนั้นก็กินเวลาไป $O(n)$ แล้ว ดังนั้นเวลารวมทั้งหมดจึงโตไปเป็น $O(n+k)$

แล้วจะทำยังไงให้ประหยัดพื้นที่ (และเวลา) ดีหละ? สังเกตว่าส่วนที่กินพื้นที่มากที่สุดคือ list ของสิ่งของทั้งหมดที่เราตระเตรียมไว้ตั้งแต่เริ่ม ทั้งที่ค่าส่วนใหญ่ใน list นี้ไม่ได้ถูกเปลี่ยนแปลงหรือนำมาใช้คำนวณเลยในแต่ละลูป ดังนั้นถ้าเปลี่ยนไปใช้โครงสร้างข้อมูลแบบ dict และเก็บเฉพาะค่าสำคัญที่เปลี่ยนแปลงในแต่ละลูป ก็จะช่วยประหยัดพื้นที่ลงไปได้ ดังนี้

def pick_4(n, k):
    remain = dict()
    result = set()
    for i in range(k):
        x = randint(0, n-1-i)
        if n-1-i not in remain:
            remain[n-1-i] = n-1-i
        if x not in remain:
            remain[x] = x
        remain[x], remain[n-1-i] = remain[n-1-i], remain[x]
        result.add(remain.pop(n-1-i))
    return result

ถึงตอนนี้ ทั้งพื้นที่และเวลาก็จะ $O(k)$ แล้ว 👌

หมายเหตุ: ใน Python มีฟังก์ชันให้ใช้ไม่ต้องเขียนเอง เรียกผ่าน random.sample(range(n), k) ได้เลย

neizod

author