algorithm-bigo-python
algorithm-bigo-python

ไม่ว่าจะทํางานเป็น Sofware Engineer หรือ QA Engineer หรือ Software Engineer in Test สิ่งที่สําคัญที่สุดก็คือเรื่องของ การเขียนและออกแบบโปรแกรม เสมอ เพราว่าการที่เราจะทํางานในตําแหน่งพวกนี้ได้ ไม่ควรเลยที่จะละทิ้งเรื่องพวกนี้ เช่น ถ้าคุณเป็น SE แต่พื้นฐานไม่ดี ส่วนใหญ่คุณก็จะ copy คําตอบจาก stackoverflow นั้นเอง ถ้าเป็น QA/SET พื้นฐานไม่ดีก็เป็นได้แค่ tester เท่านั้นแหละ 🙂

เพราะฉะนั้นวันนี้ จะเขียนเรื่องพื้นฐานสุดๆๆๆๆเลย นั้นก็ก็คือเรื่องของ Algorithm, Data structure และใช้ Big-O วัดผล เชื่อสิจงใส่ใจพื้นฐานยิ่งชีพเลยยย เคยอ่านนิยายจีนหรือการ์ตูนมั้ยที่นักดาบฝึกฟันท่าพื้นฐานเป็นพันเป็นหมื่นครั้งจนแข็งแกร่งสามารถใช้กิ่งไม้แทนดาบได้ ไรแบบนั้น การเรียนพื้นฐานก็แบบเดียวกัน เพราะมันเอาไปต่อยอดได้ วันนี้เราก็จะมาเรียนรู้เรื่องของ Algorithm แบบต่างๆ และการวัดผลด้วย Big O กัน 🙂

FYI: สาเหตุที่หลายคนสมัครงานแล้วไม่ผ่านก็เพราะเรื่องพื้นฐานพวกนี้นั้นแหละ LOL

Asymptotic analysis (หรือ Big-O นั้นเอง)

ก่อนจะเริ่มงงกันกับคําข้างบนจริงๆแล้ว หมายถึง การวิเคราะห์การทํางานของ algorithm ว่ามันทํางานได้ดีแค่ไหน เพราะ algorithm นึงอาจจะเขียนได้เป็นสิบวิธี ซึ่งการเขียนที่แตกต่างกันให้ประสิทธิ์ภาพที่แตกต่างกันด้วยเหมือนกันนั้นเอง เราจึงต้องเลือกวิธีการที่ดีที่สุดออกมาใช้ เพราะเมื่อเราทํางานกับ Scale ใหญ่ๆ เรื่องประสิทธิ์ภาพอย่าง Loop เพิ่มขึ้นเพียงแค่ Loop เดียวนี้ก็ให้ผลต่างกันมากแล้วล่ะ

ซึ่ง Big-O จะเลือกเอา worst cases เป็นตัวชี้วัดเท่านั้นน่ะ 🙂

ประเภทของ Big-O 

  1. Constant Complexity : O(1)
  2. Linear Complexity : O(N)
  3. Quadratic Complexity : O(N²)
  4. Exponential Complexity : O(2^N)
  5. Logarithmic Complexity : O(log n)
  6. Linearithmic Complexity : O(n log n)

Big-O ให้พูดวนไปมาแค่ไหนก็มีแค่นี้แหละ ที่จะแสดงความแตกต่างของ algorithm แต่ละประเภทเดี๋ยวมาดูกันว่ามันแตกต่างกันยังไง

big-o-alogrithm-graph
big-o-alogrithm-graph (http://bigocheatsheet.com/)

Constant Complexity : O(1)

เจ้าตัวนี้อธิบายง่ายสุดเลยเพราะมันคือ constant ครับ … ตรงตัวเลยอะ สั่งไรมามันก็ทํายังงั้นแหละ ทําแบบเดิมซํ้าๆๆๆๆๆๆทุกครั้งไม่ต้องคิดไร เช่น เมื่อเรียก Algorithm นี้ก็จะ return Array ช่องท่ี 0 ออกไปนั้นเอง

 

def return_first_array(self,array):

   return array[0]

เพราะฉะนั้นคงไม่ต้องบอกน่ะ ถ้าแบบนี้ย่อมดีสุดอยู่แล้วล่ะ แต่ในชีวิตจริง algorithm ไหนมันจะ return แค่ specific แบบนี้ล่ะ

Linear Complexity : O(N)

เจ้า O(N) หมายถึง algorithm ที่ใช้เวลาทํางานเพิ่มขึ้นเป็นเส้นตรงตามจํานวนของข้อมูลที่ถูกใส่เข้ามา ฟังแล้วอาจจะงงๆแต่ให้นึกถึง for-loop array ขนาด 2000 ช่อง ระยะเวลาของกว่ามันจะเสร็จ ก็ตาม size ซึ่งก็คือ 2,000 ช่องนั้นเอง ซึ่งในกรณีคํานวณ Big O ก็อย่างที่บอกคือเอา worst case ซึ่งก็คือจํานวนมากสุดนั้นเอง 2,000 ช่อง

 
def loop_over_data(self,array): 
   for data in array: 
   print(data) 

หรือให้คิดง่ายๆก็ Loop เดียวนั้นแหละ แล้ววิ่งตามขนาดของ data set ก็จะวิ่งวนไปเรื่อยๆ (ถ้าดูจากกราฟก็จะอยู่ในช่วงที่รับได้น่ะ Fair)

Quadratic Complexity : O(N²)

มาดูตัวแสบๆบ้างดีกว่า เมื่อกี้ดู algorithm ที่ใช้เวลาดีๆแล้ว มาดู case Quadratic (ยกกําลัง) กันบ้างน่ะ ไม่ต้องคิดไรมากเลย คือ “Nested Iteration” นับเป็น quadratic ทั้งหมดแหละ เพราะว่า algorithm แบบนี้นับตามยกกําลังของ data set ที่เราใส่เข้าไป เช่น ใส่ 2,000 มันก็วนรอบโลกได้เลยอ่ะ ฮ่าๆ

แต่ถ้ามี Nested Iteation หลายๆตัวมันก็ไม่ใช่ O(N2) น่ะ มันก็จะเป็น O(N3) หรือ O(N4) แล้วไปเรื่อยๆ ตามจํานวนที่เรามี nested นั้นเอง

 

def nested_iteration(self,elements_value):

   for elements_a in elements_value:

     for elements_b in elements_value:

       print(elements_b)

Exponential Complexity : O(2^N)

เริ่มเข้ามาถึงตัวยากๆล่ะ เจ้าตัวนี้หมายถึง algorithm ที่ใช้เวลา กับการเติบโตแบบ DOUBLE เลย เช่น N เริ่มจาก 1-5 น่ะ ตอนแรกก็จะเป็น 2,4,8,16,32 เป็นต้น โดยเจ้าพวกนี้ส่วนใหญ่จะเป็น algorithm แบบ recursive โดยลองคิดถึงสภาพของข้อมูลที่มีมากกว่า 2 layer ล่ะ สมมุติถ้าเริ่มจากเป็น 3^n งี้ มีกระอักอยู่เหมือนกันเลยล่ะ 🙁

Logarithmic Complexity : O(log n)

เจ้าตัวนี้เป็นตัวที่ค่อนข้างมีทริกนิดหน่อยแต่เป็น Algorithm ที่จะตัดส่วนที่ไม่จําเป็นออกไปในการรันลูปแต่ล่ะครั้ง ถ้านึกไม่ออกให้นึกถึงสมัยก่อนที่เราทําเรียนเรื่อง Binary Search ออกมานั้นเอง โดยที่การสนลูปแต่ล่ะครั้งจะตัด data set ออกมาทีล่ะครึ่งนั้นเอง ตัวอย่างที่ชอบยกกันเลยก็พวก เรามีสมุด phonebook เล่มนึงต้องการหา นาย A เราจะทํายังไง … เราก็หารสองแล้วดูว่า A น้อยกว่าหรือมากกว่าที่หารออกมานั้นเอง แล้วก็ทํายังงี้ไปเรื่อยๆจนจบ นี้คือลักษณะของ Algorithm แบบ Log ซึ่งเหมาะกับ data ใหญ่ๆมากๆ เพราะการ double size ของ data set มันมีผลกับ algorithm น้อยมาก

exmaple-python-binary-search
exmaple-python-binary-search (https://gist.github.com/JonathanSpeek/1f4c7c283c7c3c475ee13d57381765d8)

อย่างตัวอย่างข้างบนจะเห็นว่ามันโยน data set เข้ามาพร้อมตัวที่ต้องการจะหา แล้วก็หารสองไปเรื่อยๆ ซึ่ง log n แบบนี้ดีมากๆ เพราะตัดตัวไม่จําเป็นออกไป 🙂 (Binary Search ใช้กับ Sorted data set น่ะ) ของเล่น Binary Search Tree

Linearithmic Complexity : O(n log n)

จริงๆเจ้าตัวนี้ก็แอบเหมือน Log นั้นแหละ แต่คือนอกจากที่มันจะใช้วิธีการตัดครึ่งของ data set แล้ว มันจะใช้ loop ซ้อนกันด้วยทีนึงก่อน แล้วค่อยตัดเป็นส่วนๆออกไป ซึ่งพบได้ใน merged sort นั้นเอง

merge-sort-example
merge-sort-example (https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-8.php)

โดยขั้นตอนการคิดง่ายมากๆเลย แค่

big-o-merged-sorted
big-o-merged-sorted (https://www.geeksforgeeks.org/merge-sort/)

ตัวอย่าง

เจ้ารูปตัวอย่างข้างล่างคือเมื่อเราใช้ Data Size เท่ากับ 10 แล้ว algorithm แบบต่างๆจะมีผลยังไงต่อเวลา

ลองดูสิถ้าเราเขียน algorithm นึงที่เป็น O(2^N) หรือ O(N^2) เยอะๆ นี้คือไปกู่ไม่กลับเลยน่ะ ดูจากปลายเส้นกราฟแล้วยาวอะ บินไปยาวเลย มีสิทธิ์ทําให้ application เราตายได้ง่ายๆเลยล่ะ เพราะนี้แค่ใช้ data size 10 ยังซะขนาดนี้ ลองคิดภาพ data size 2,000 ล่ะ 🙂

big-o-exmaple-time-vs-data-set
big-o-exmaple-time-vs-data-set (http://www.wolframalpha.com/input/?i=plot++2%5Ex,x%5E2,+x,1+from+x%3D0+to+10)

อีกสองสิ่งที่สําคัญ Logic และ Data structure

อธิบายไปก็เท่านั้น … กับหัวข้อนี้ ลงมือทําให้เข้าใจจะดีกว่า

จริงๆแล้วเวลาเราสมัครงานหรือใช้ในชีวิตจริงๆนี้เราจะมีแค่ 3 อย่างเองที่จะโดนถามนั้นก็คือ data structure, algorithm แล้วที่เหลือจะเป็นเรื่องของ ปสก การทํางานแล้วล่ะ ซึ่งการจะพัฒนาสิ่งนี้ขึ้นมาได้อะ คือการฝึกฝนอย่างเดียวเลย ซึ่งสมัยนี้มันมีของให้เล่นเยอะแล้ว เช่น การเขียนโค้ดเหมือนเล่นเกม เพื่อให้เราไม่เบื่อ

example-coding-is-fun
example-coding-is-fun (https://www.codingame.com/start)

หรือถ้าแบบที่ใช้สมัครงานก็พวก HackerRank ที่จะเริ่มยากหน่อยล่ะ แล้วก็จริงจัง 🙂 ซึ่งการฝึกฝนน่ะอยากให้ฝึกตามบทความนี้เลย เป็นขั้นตอนไปตาม Beginner,Intermediate และยาวไปจนถึง Advance

ส่วนสําหรับ Data structure จากที่หาๆมา ไม่มีที่ไหนดีเกิน GeeksforGeeks และ บทความของ freecodecamp อันนี้แล้วล่ะ บอกเลยอ่านบทความไปก็ช่วยไม่ได้ ลองฝึกทําโจทยท์จากในเว็ปที่ให้ไป แล้วอ่านว่าทําไมถึงต้องใช้ Data structure แบบนี้ที่ GeeksforGeeks ก็จะทําให้เข้าใจมากขึ้น ซึ่งการสมัครงานหรือทํางานก็ตามทีสมัยนี้ยังไงก็จะต้องมีเรื่องของการทดสอบ logic เราแน่ๆ ไม่ online ก็ offline โดนชัวร์ (นอกเหนือจากพวกนี้ก็หาจากในที่ทํางานละ เรื่อง ปสกการทํางาน)

ฝึกฝนตลอดเวลาเพื่อเป็น Software Engineer ที่เขียนโค้ดได้ดี ไม่ใช่แค่เขียนโค้ดได้น่ะ

 

 

Leave a Reply

avatar

This site uses Akismet to reduce spam. Learn how your comment data is processed.