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...

จัดการข้อมูลบน Pandas ยังไงให้เร็ว 1000x ด้วย Vectorisation

จัดการข้อมูลบน Pandas ยังไงให้เร็ว 1000x ด้วย Vectorisation

เวลาเราทำงานกับข้อมูลอย่าง Pandas DataFrame หนึ่งในงานที่เราเขียนลงไปให้มันทำคือ การ Apply Function เข้าไป ถ้าข้อมูลมีขนาดเล็ก มันไม่มีปัญหาเท่าไหร่ แต่ถ้าข้อมูลของเราใหญ่ มันอีกเรื่องเลย ถ้าเราจะเขียนให้เร็วที่สุด เราจะทำได้โดยวิธีใดบ้าง วันนี้เรามาดูกัน...

ปั่นความเร็ว Python Script เกือบ 700 เท่าด้วย JIT บน Numba

ปั่นความเร็ว Python Script เกือบ 700 เท่าด้วย JIT บน Numba

Python เป็นภาษาที่เราใช้งานกันเยอะมาก ๆ เพราะความยืดหยุ่นของมัน แต่ปัญหาของมันก็เกิดจากข้อดีของมันนี่แหละ ทำให้เมื่อเราต้องการ Performance แต่ถ้าเราจะบอกว่า เราสามารถทำได้ดีทั้งคู่เลยละ จะเป็นยังไง เราขอแนะนำ Numba ที่ใช้งาน JIT บอกเลยว่า เร็วขึ้นแบบ 700 เท่าตอนที่ทดลองกันเลย...

Humanise the Number in Python with "Humanize"

Humanise the Number in Python with "Humanize"

หลายวันก่อน เราทำงานแล้วเราต้องการทำงานกับตัวเลขเพื่อให้มันอ่านได้ง่ายขึ้น จะมานั่งเขียนเองก็เสียเวลา เลยไปนั่งหา Library มาใช้ จนไปเจอ Humanize วันนี้เลยจะเอามาเล่าให้อ่านกันว่า มันทำอะไรได้ แล้วมันล่นเวลาการทำงานของเราได้ยังไง...

ทำไม 0.3 + 0.6 ถึงได้ 0.8999999 กับปัญหา Floating Point Approximation

ทำไม 0.3 + 0.6 ถึงได้ 0.8999999 กับปัญหา Floating Point Approximation

การทำงานกับตัวเลขทศนิยมบนคอมพิวเตอร์มันมีความลับซ่อนอยู่ เราอาจจะเคยเจอเคสที่ เอา 0.3 + 0.6 แล้วมันได้ 0.899 ซ้ำไปเรื่อย ๆ ไม่ได้ 0.9 เพราะคอมพิวเตอร์ไม่ได้มองระบบทศนิยมเหมือนกับคนนั่นเอง บางตัวมันไม่สามารถเก็บได้ เลยจำเป็นจะต้องประมาณเอา เราเลยเรียกว่า Floating Point Approximation...