Tutorial

Loop FASTER is not to LOOP in Python

By Arnon Puitrakul - 21 พฤศจิกายน 2022

Loop FASTER is not to LOOP in Python

หลาย ๆ วันมาละ เรานั่งคุยกับเพื่อนกันว่า ถ้าเราต้องบวกเลขเยอะ ๆ เราจะ Loop เข้าไป ถามว่า เราจะทำเร็วกว่ากันแค่ไหน และที่เราบอกว่า For-Loop กับ While-Loop มันใช้แทนกันได้ มันแทนกันได้จริงแหละ แต่ Performance ละมันเป็นยังไง เราลองมาเล่นกันขำ ๆ ดีกว่า

Problem Statement

โจทย์ที่เราเอามาเล่นกันในวันนี้ ขำ ๆ ง่าย ๆ เลยคือ เราต้องการหาผลรวมของ 1 + 2 + ... + N หรือผลรวมตั้งแต่ 1 ถึง N บวกกันไปเรื่อย ๆ

เช่น เรากำหนด N = 5 ผลลัพธ์ก็จะเป็น 1 + 2 + 3 + 4 + 5 = 15 นั่นเอง ดูเป็นโจทย์ง่าย ๆ เลยสินะ ถ้าเราบวกกันสัก พันนึง เราว่าไม่น่ามีปัญหาอะไรหรอก แต่ในบางปัญหา เราต้องบวกกันระดับล้าน ๆ หรือมากกว่านั้น ทำให้ Performance สำคัญมาก ๆ

Experimental Design

ในการทดลองนี้ เราจะเน้นการจับเวลาในการทำงานของแต่ละวิธีการเป็นหลัก โดยเราจะเลือกใช้ time module ที่อยู่ใน Python เอง

def timer (func: Callable[[int], int], message:str, n:int) -> None :
    start_time = time.time()
    
    func(n)
    
    print(message, 'took', time.time()-start_time, 'sec(s)')

โดยเราจะเขียน Function ขึ้นมาง่าย ๆ ตัวนึงชื่อว่า timer ข้ามพวกเรื่อง Typing ไปนะ เราติดเขียนพวกนี้เข้ามา เวลา Debug อะไรมันจะได้ง่ายขึ้นแค่นั้น ไม่มีผลอะไรเท่าไหร่ ซึ่งจะรับ Function ที่เราต้องการรันเข้ามา พร้อมกับ Message เพื่อให้เราระบุว่ามันเป็นการทดลองอะไร และ สุดท้าย เราเอา N ใส่เข้ามา

ใน Function นี้ เมื่อเข้ามา เราจะให้มันเก็บ Timestamp ไว้ก่อน แล้วเรียก Function สุดท้าย เราอยากรู้เวลาในการทำงาน เราก็เอา Timestamp ปัจจุบัน ลบกับ Timestamp ที่เราเก็บไว้ก่อนหน้าก็ได้ออกมาแล้ว จากนั้นเราก็ Print ออกไปที่หน้าจอให้เราเท่านั้นเอง

เบื้องต้น เพื่อให้เห็นผลกันชัด เราจะตั้ง N ไว้ที่ 10 ล้าน น่าจะพอเห็นผลกันบ้างแล้วละ

For, While Loop

ปัญหานี้ เราใช้ For-Loop และ While-Loop ในการแก้ปัญหาง่ายมาก ๆ

def simple_for_loop (n: int) -> int :
    result = 0
    
    for i in range(n) :
        result += i
    
    return result

สำหรับ For-Loop เป็นอะไรที่เขียนง่ายมาก ๆ ใน For-Loop มันจัดการเรื่องพวก Iteration ให้เราหมดแล้ว เราไม่ต้องเขียน Logic เพื่อบวกเลขเองด้วยซ้ำ เพราะ range() มันจัดการให้เราหมดแล้ว เราก็แค่เอา result ที่เป็น int ไปบวก กับ i ที่วนผ่าน Iterator ได้ตรง ๆ เลย

def simple_while_loop (n: int) -> int :
    result = 0
    counter = 0
    
    while (counter < n) :
        result += counter
        counter += 1
    
    return result

สำหรับ While-Loop เราก็เขียนตามปกติเลย คือ เราเริ่มจากสร้างตัวแปรสำหรับเก็บผลลัพธ์ของเราชื่อ result และ counter เป็นตัวเก็บว่า ตอนนี้เรานับถึงไหนแล้ว ใน Loop เราก็กำหนดเงื่อนไขขึ้นมาว่า counter มันต้องน้อยกว่า n เสมอนะ เพื่อให้มันไม่นับเกิน แล้วใน Loop เราก็ให้มันบวก counter เข้าไปใน result และ บวก counter ขึ้น 1 เพื่อไปรอบต่อไป ธรรมดา ๆ เลย

For Loop took 0.27052903175354004 sec(s)
While Loop took 0.4504220485687256 sec(s)

จากผลการทดลองรัน เราจะเห็นเลยว่า For-Loop รันเร็วกว่า While-Loop เยอะมาก ๆ ดูขำ ๆ เกือบ ๆ 2 เท่าเลยนะ (ไม่ถึงหรอก) หารออกมาได้สัก 1.5 เท่าได้ ถือว่าเยอะมาก ๆ นะ สำหรับความที่เราบอกไปว่า มันใช้อะไรก็ได้ Performance มันห่างกันเยอะมาก ๆ ถ้าเราทำจำนวนเยอะ ๆ

Why ???????

ผลการทดลองทำให้เกิดคำถามว่า Why??? ทำไมฟร๊ะ แค่การเขียน Loop จาก While เป็น For มันก็ทำให้ผลมันต่างกันได้ขนาดนี้เลยเหรอ นั่งคิดอยู่นาน นึกได้ว่า อ่อ CPython นิหว่า

CPython เบื้องหลังของมันถูกเขียนด้วยภาษา C ทำให้ จริง ๆ แล้วเราสามารถที่จะเอาพวก Function ที่เขียนใน C เข้ามาใช้งานในภาษา Python ได้ เหตุผลหนึ่งก็คือเรื่อง Performance เพราะ Python เป็นภาษาแบบ Interpreter ทำให้มันต้องมีพวก Runtime ช่วยแปลภาษาอีกที ณ ขณะที่รัน แต่พวกภาษา C เป็นภาษาที่เรา Compile เป็น Machine Code ล่วงหน้าแล้ว ทำให้ทำงานได้ตรง ๆ เลย นั่นส่งผลเรื่องความเร็วมหาศาล

กลับมาที่ For และ While ของเรากัน ว่า ทำไมมันเป็นแบบนั้นละ นั่นเป็นเพราะใน For Loop เรายัด Iterator เข้าไปตรง ๆ ซึ่งตัว Iterator นี้มันถูกเขียนโดย C ทำให้ Operation ที่ทำงานบน Python จริง ๆ ก็น่าจะมีแค่คำสั่งสำหรับการบวกเลขเข้าไปแค่จุดเดียว กลับกัน ใน While Loop มันมีอะไรมากกว่าที่เราเห็น

while (counter < n) :
        result += counter
        counter += 1

เราขอยก While Loop ด้านบนลงมา เราจะเห็นแค่โอเค มันเป็นแค่ While Loop ปกติ แต่เบื้องหลังของมัน ไม่ได้มีแค่นั้น เพราะ ใน While บรรทัดบนสุด เราจะเห็นว่า เราป้อนเงื่อนไขเข้าไป นั่นก็ทำงานบน Python และ ด้านล่างที่เป็นการบวกเลขทั้งหมด ก็ทำงานบน Python เช่นกัน ทำให้การทำงานของ For Loop ที่พึ่งฝั่งของ C ทำงานเร็วกว่ามาก ๆ

Built-in sum()

ในเมื่ออะไรที่ทำงานบน C เร็วกว่าไปซะหมด และ CPython ที่เราใช้งานกัน ก็เขียนด้วย C อยู่แล้ว แปลว่าพวก Function หลาย ๆ อย่างก็เขียนด้วย C ด้วยเช่นกัน ถ้าเราเข้าไปดูคำสั่งใน Documentation เราน่าจะเคยเห็นคำสั่ง sum() ผ่านตา

def python_sum (n: int) -> int:
    return sum(range(n))

สิ่งที่มันทำคือ มันจะรับ Iterator เข้าไป และ หาผลรวมให้เราเลย ทำให้เราสร้าง Function ง่าย ๆ เลย คือ Return ผลลัพธ์ที่ได้จาก sum() กลับไปตรง ๆ ก็เรียบร้อย

While Loop took 0.4504220485687256 sec(s)
For Loop took 0.27052903175354004 sec(s)
Python Sum took 0.10359907150268555 sec(s)

ผลที่ได้ โอ้ววววว เร็วขึ้นแบบเห็นได้ชัดมาก ๆ เท่าตัวเลยเมื่อเทียบกับ For-Loop และ 4 เท่ากว่า ๆ เมื่อเทียบกับ While-Loop เร็วขนาดนี้ใครละจะทนไหว ฮ่า ๆ

โอเคแหละ มันก็แก้ปัญหาที่เราเล่นกันในบทความนี้ได้จริง ๆ แต่ ถ้าเราเอาว่า Loop เน้น ๆ เลย วิธีนี้ก็ใช้ไม่ได้กับทุกปัญหาที่ใช้ Loop สินะ ดังนั้นก็ผ่านไป เอาเป็นว่า ถ้าเราต้องการจะบวกเลข เราก็ใช้คำสั่ง sum() ได้

Go Faster with Numpy

เอาหละ เราอยากไปให้เร็วขึ้นอีก ไปอี๊กค่าาาา เราจะทำยังไงดี นึกได้ว่า Numpy นี่คือของดีเลย เพราะทั้งหมดของมันเขียนด้วย C และ เลือกใช้วิธีการที่เร็วสุด ๆ อยู่แล้วละ งั้นเราลองเขียนมันด้วย Numpy ล้วน ๆ เลยดีกว่า

def numpy_sum (n : int) -> int :
    return np.sum(np.arange(n))

สำหรับใน Numpy มันก็จะมีคำสั่ง Sum เหมือนกับใน Python เลย มันจะรับ Array-Like Data Structure เข้ามา ทำให้เราสามารถยัดได้ทั้ง Python List และ Numpy Array ได้หมดเลย แล้วมันจะหาผลรวมออกมาให้เรา ซึ่งจาก Python Sum เรายัด Iterator เข้าไป แต่อันนี้ไม่รองรับ

ใน Numpy ก็มีคำสั่งสำหรับการสร้าง Numpy Array ที่เป็นเลขเรียงแบบที่เราต้องการด้วยเช่นกันผ่านคำสั่งที่ชื่อว่า numpy.arange แต่ปัญหาของ Code ชุดนี้คือ มันจะคืนค่ากลับมาเป็น Numpy Array นี่แหละ แปลว่า เราจะต้องเก็บตัวเลขขนาดเท่า N เอาไว้ใน Memory เลยนะ ถ้าตัวเลขเรามีเยอะมาก ๆ เราไม่ชิบหายเลยเหรอ นั่นก็เป็นข้อเสียของวิธีนี้ไปละกันเนอะ

While Loop took 0.4504220485687256 sec(s)
For Loop took 0.27052903175354004 sec(s)
Python Sum took 0.10359907150268555 sec(s)
Numpy took 0.018093109130859375 sec(s)

หลังจากรันออกมา เราจะเห็นได้เลยว่า เวลา มัน ช่าง ต่าง มาก ๆ ขนาดเทียบกับ Python Sum เอง ห่างกัน 10 เท่าได้ และห่างจาก While เกือบ ๆ 25 เท่าไปเลย ต่างกันแบบ ยับ ๆ เลย

Conclusion

หลังจาก 4 วิธีที่เราทดลองกันมา วิธีการที่ช้าที่สุด ก็จะเป็น While Loop และ เร็วที่สุดก็จะเป็นการใช้ Numpy Sum เข้าไป สาเหตุที่เป็นแบบนั้น เป็นเพราะจริง ๆ แล้ว Python เป็นภาษาที่ทำงานได้ค่อนข้างช้า เมื่อเทียบกับภาษา C เพราะลักษณะการทำงานที่แตกต่างกัน ตัว Python จำเป็นที่จะต้องมี Interpreter คั่นเวลาทำงานเสมอ ต่างจาก C ที่มันถูก Compile เป็น Machine Code ตรง ๆ แล้วรันได้เลย ทำให้ Performance ค่อนข้างที่จะต่างกันสักหน่อย

ทำให้ ถ้าเราอยากจะ Optmise Python Script ของเราให้มากที่สุด เราจะต้องพยายามลดการใช้ Python ลงไปให้ได้มากที่สุด เหมือนที่เราทดสอบให้ดูในวันนี้ ดังนั้น Loop ที่เร็วที่สุดคือการไม่ Loop เลยเหมือนชื่อหัวเรื่องของบทความนี้นั่นเอง

รันโปรแกรมเร็วขึ้นด้วย SIMD บน Apple Silicon โคตรเร็ว
จะเป็นอย่างไร ถ้าเราบอกว่า เราสามารถเขียนโปรแกรมของเราให้เร็วขึ้นแบบก้าวกระโดด โดยเราไม่ต้องแบ่ง Core ไม่ต้อง Overclock CPU ของเรา แต่เราใช้ประโยชน์จากความสามารถ CPU ของเราได้ ผ่านการทำ SIMD

นอกจากนั้น อีกความลับที่เราไม่ได้บอกคือ จริง ๆ แล้วเคสของ Numpy มันจะโกงขึ้นไปอีกขั้น เพราะจริง ๆ แล้ว Numpy มันไม่ได้บวกกันตรง ๆ เหมือนที่เราทำกัน แต่มันใช้ SIMD ในการ Parallelise การทำงานทั้งหมดอีกที เราเคยเขียนเล่าในบทความด้านบนละ

และ ถ้าเราไม่สามารถละ เราจำเป็นต้องใช้ Loop ให้เราจำไว้ว่า การ Loop มีราคาที่ค่อนข้างแพงมาก ๆ พยายามใช้ Expression ที่ Evaluate ผ่าน C มากกว่า Python ก็จะช่วยเพิ่ม Perforance ได้มหาศาลจากเคส While Loop และ For Loop ที่เราแสดงให้เห็นในบทความนี้

Read Next...

สร้าง Book Tracking Library ด้วย Obsidian

สร้าง Book Tracking Library ด้วย Obsidian

เราเป็นคนที่อ่านกับซื้อหนังสือเยอะมาก ปัญหานึงที่ประสบมาหลายรอบและน่าหงุดหงิดมาก ๆ คือ ซื้อหนังสือซ้ำเจ้าค่ะ ทำให้เราจะต้องมีระบบง่าย ๆ สักตัวในการจัดการ วันนี้เลยจะมาเล่าวิธีการที่เราใช้ Obsidian ในการจัดการหนังสือที่เรามีกัน...

Garbage Collector บน Python ทำงานอย่างไร

Garbage Collector บน Python ทำงานอย่างไร

หากเราเรียนลงลึกไปในภาษาใหม่ ๆ อย่าง Python และ Java โดยเฉพาะในเรื่องของการจัดการ Memory ว่าเขาใช้ Garbage Collection นะ ว่าแต่มันทำงานยังไง วันนี้เราจะมาเล่าให้อ่านกันว่า จริง ๆ แล้วมันทำงานอย่างไร และมันมีเคสใดที่อาจจะหลุดจนเราต้องเข้ามาจัดการเองบ้าง...

ติดตั้ง Zigbee Dongle บน Synology NAS กับ Home Assistant

ติดตั้ง Zigbee Dongle บน Synology NAS กับ Home Assistant

ก่อนหน้านี้เราเปลี่ยนมาใช้ Zigbee Dongle กับ Home Assistant พบว่าเสถียรขึ้นเยอะมาก อุปกรณ์แทบไม่หลุดออกจากระบบเลย แต่การติดตั้งมันเข้ากับ Synology DSM นั้นมีรายละเอียดมากกว่าอันอื่นนิดหน่อย วันนี้เราจะมาเล่าวิธีการเพื่อใครเอาไปทำกัน...

โหลด CSV วิธีไหนเร็วที่สุด ?

โหลด CSV วิธีไหนเร็วที่สุด ?

เมื่อหลายวันก่อนมีพี่ที่รู้จักกันมาถามว่า เราจะโหลด CSV ยังไงให้เร็วที่สุด เป็นคำถามที่ดูเหมือนง่ายนะ แต่พอมานั่งคิด ๆ ต่อ เห้ย มันมีอะไรสนุก ๆ ในนั้นเยอะเลยนี่หว่า วันนี้เราจะมาเล่าให้อ่านกันว่า มันมีวิธีการอย่างไรบ้าง และวิธีไหนเร็วที่สุด เหมาะกับงานแบบไหน...