<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Anurak Jairak on Medium]]></title>
        <description><![CDATA[Stories by Anurak Jairak on Medium]]></description>
        <link>https://medium.com/@hamzcheeze?source=rss-ea2c9e23fd0------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*gQFqmVbHmrDiIwhJaq3gvA.jpeg</url>
            <title>Stories by Anurak Jairak on Medium</title>
            <link>https://medium.com/@hamzcheeze?source=rss-ea2c9e23fd0------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 22:48:05 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@hamzcheeze/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[สรุปหนังสือ Grokking Algorithms [Part 4]]]></title>
            <link>https://medium.com/@hamzcheeze/%E0%B8%AA%E0%B8%A3%E0%B8%B8%E0%B8%9B%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-4-ec926fb73aa8?source=rss-ea2c9e23fd0------2</link>
            <guid isPermaLink="false">https://medium.com/p/ec926fb73aa8</guid>
            <dc:creator><![CDATA[Anurak Jairak]]></dc:creator>
            <pubDate>Tue, 07 Jan 2025 12:06:40 GMT</pubDate>
            <atom:updated>2025-01-07T12:11:34.066Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/proxy/1*KD6dfLl6giLhnCX9KkTyMw.png" /></figure><p>เปิดศักราชใหม่ด้วย Part 4 กันเลย โดย Part นี้จะพูดถึง<strong>การเวียนเกิด</strong> หรือ <strong><em>Recursion</em></strong> ที่เรารู้จักกันเป็นอย่างดี (แต่ไม่เคยใช้เลย 555) ซึ่งเจ้า Recursion เนี่ย คนส่วนมากถ้าไม่รักก็เกลียดมันไปเลย เพราะมันค่อนข้างเข้าใจยากแต่ถ้าได้ลองเปิดใจดูสักครั้งแล้วล่ะก็.. ไม่เข้าใจเหมือนเดิม 555 ไม่ใช่ละ โดยผู้เขียนได้ถ่ายทอดออกมาด้วยโค้ดโปรแกรมและ <a href="https://www.borntodev.com/2024/10/09/pseudocode/"><strong>Psudo Code</strong></a> ในหลายๆตัวอย่าง ซึ่งถือว่าช่วยให้เห็นภาพและเข้าใจได้เป็นอย่างดีเลยทีเดียว โอเค เรามาเข้าเรื่องกันเลยดีกว่า</p><h4>Recursion</h4><p>สมมติว่าวันหนึ่งคุณไปเจอหีบโบราณของคุณย่าที่ห้องใต้หลังคา แต่หีบนี้ได้ถูกล็อกไว้ คุณย่าจึงใช้ให้คุณไปหากุญแจเปิดหีบในกล่องลังซึ่งบรรจุไปด้วยกล่องเล็กๆในนั้นอีกมากมาย</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tLR2eTJGdNSYYTFuxOklug.png" /></figure><p>ปรากฏกล่องเล็กๆในลังนั้นมีกล่องซ้อนกล่องในนั้นอีกหลายชั้นเลย คุณย่าบอกว่าให้ลองไล่เปิดดูทีละกล่องทีละชั้น มันต้องมีสักกล่องในนั่นแหละที่ย่าเก็บกุญแจเอาไว้ ย่าก็จำไม่ได้เหมือนกัน = = ” เขียนขั้นตอนออกมาได้ดังนี้</p><ol><li>หยิบกล่องขึ้นมา</li><li>เปิดกล่องใบนั้น ถ้าเจอกล่องอีกให้กลับไปข้อ 1</li><li>ถ้าพบกุญแจก็เสร็จสิ้นการค้นหา</li></ol><p>เขียน <strong>Psudo Code</strong> ออกมาได้ประมาณนี้</p><pre>def look_for_key(box):<br>  for item in box:<br>    if item.is_a_box():<br>      look_for_key(item)     # Recursion ตรงนี้ (เรียกตัวเองอีกรอบ)<br>    elif item.is_a_key():    <br>      print “found the key!”</pre><h4>Base-case และ Recursive-case</h4><p>ฟังก์ชัน Recursive นั้นจะเรียกตัวเองเรื่อยๆ หากเขียนโค้ดไม่ถูกต้องอาจจะทำให้เกิด Infinite Loop (วนลูปไม่รู้จบทำให้โปรแกรมของเราพังได้) สมมติคุณต้องการเขียนฟังก์ชันเพื่อแสดงผลตัวเลขแบบนับถอย เช่น 3 &gt; 2 &gt; 1 โดยใช้การ Recursive</p><pre>def countdown(i):<br>  print i<br>  countdown(i-1)</pre><p>เมื่อเขียนโค้ดออกมาในลักษณะนี้จะพบว่าโปรแกรมจะแสดงผลตัวแบบนับถอยหลัง 3 &gt; 2 &gt; 1 &gt; 0 &gt; -1 &gt; -2 … ไปเรื่อยๆไม่รู้จบ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*T3QoNoqr-bfNHwp0K_FVvQ.png" /></figure><p>เพื่อไม่ให้เกิดสิ่งนี้ขึ้นทุกครั้งที่เราเขียนฟังก์ชัน Recursive ต้องมีการหยุดการเรียกตัวเองเมื่อถึงจุดๆหนึ่ง จุดนั้นเรียกว่า Base-case โดยเราจะทำการเพิ่มมันลงไปในฟังก์ชัน countdown เพื่อให้การนับถอยหลังหยุดที่ 0 ก็พอ</p><pre>def countdown(i):<br>  print i<br>  if i &lt;= 0:          # Base-case<br>    return<br>  else:<br>    countdown(i-1)    # Recursive-case</pre><p>โดยการเขียนโค้ดบอกตัวโปรแกรมว่าเราต้องการหยุดการเรียกตัวเองเมื่อ i น้อยกว่าหรือเท่ากับ 0 หากไม่ใช่ก็เรียกตัวเองไปเรื่อยๆ ก็จะได้ผลลัพธ์อย่างที่เราต้องการ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cNe9TOtyaDqtYlEzOYbQCw.png" /></figure><h4>Stack</h4><p>สมมติคุณต้องการจะจัดปาร์ตี้โดยชวนเพื่อนๆมาย่างบาบีคิวกินกันที่บ้านเย็นนี้ แต่ก่อนอื่นต้องจดรายการวัตถุดิบที่ต้องออกไปซื้อลงใน Post it แปะๆซ้อนกันไว้เป็น To-do List หลักการเดียวกันกับ <strong>Stack</strong> เมื่อคุณต้องการเขียนรายการใหม่ก็แค่แปะทับซ้อนลงไปกับรายการก่อนหน้านี้ หากคุณต้องการเริ่มอ่านสิ่งที่ต้องทำก็แค่ดึงรายการบนสุดมาดูก่อน (ดึงจากล่างหรือตรงกลางไม่ได้นะ) การแปะและการดึงใน Stack เราเรียกว่า <strong>Push</strong> และ <strong>Pop</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*njGSaayDiowI2ZWQ21fIwQ.png" /></figure><p><strong>Stack</strong> เป็นโครงสร้างข้อมูล<strong> </strong>(Data Structure)<strong> </strong>ที่สำคัญมากในการเขียนโปรแกรมและบางทีเราก็ใช้มันโดยที่เราไม่รู้ตัว อย่างเช่นการเขียนฟังก์ชันที่ต้องเรียกฟังก์ชันอื่นอีกที (ซึ่งเราทำกันเป็นปกติอยู่แล้ว) โดยระบบข้างในคอมพิวเตอร์ของเราจะมีการ <strong><em>Call Stack</em></strong> ซ่อนอยู่เบื้องหลัง คอล(เรียก)ยังไง.. ลองดูตัวอย่างโค้ดด้านล่าง</p><pre>def bye():                              <br>    print(&quot;OK bye&quot;)                      # 8.แสดงผล OK bye แล้วจบโปรแกรม<br><br>def greet2(name):                        # 4.ส่งค่า Maggie มาที่นี่<br>    print(&quot;How are you &quot; + name)         # 5.แสดงผล How are you Maggie<br><br>def greet(name):<br>    print(&quot;Hello &quot; + name)               # 2.แสดงผล Hello Maggie<br>    greet2(name)                         # 3.ฟังก์ชัน greet2 ถูกเรียก (Call Stack)<br>    print(&quot;Getting ready to say bye..&quot;)  # 6.แสดงผล Getting ready to say bye..<br>    bye()                                # 7.ฟังก์ชัน bye ถูกเรียก (Call Stack)<br><br>greet(&quot;Maggie&quot;)                          # 1.เรียกใช้งานฟังก์ชัน greet <br>                                         # โดยส่งค่า Maggieเข้าไป</pre><p>จะเห็นว่าฟังก์ชัน greet ได้เรียกใช้งานอีก 2 ฟังก์ชันด้านในคือฟังก์ชัน greet2 และ bye สมมติว่าคุณเรียกฟังก์ชัน greet(“Maggie”) อันดับแรกระบบจะทำการจองบล็อกหน่วยความจำไว้สำหรับเรียกใช้งานฟังก์ชัน</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jztJlEw9Rp4ffARR8J6tng.png" /></figure><p>เมื่อเราส่งค่าพารามิเตอร์ name ในฟังก์ชัน greet ให้เป็นคำว่า “Maggie” แล้วระบบจะบันทึกค่านี้ไว้ในหน่วยความจำที่ได้จองไว้</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1016/1*X99NnjicLxmVPEDKR3upiw.png" /></figure><p>หลังจากโปรแกรมแสดงผลคำว่า Hello Maggie แล้วระบบก็จะทำการจองบล็อกหน่วยความจำไว้สำหรับการเรียกฟังก์ชัน greet2 เพิ่มโดยการ Stack ทับหน่วยความจำบล็อกแรกลงไปแบบนี้ ขั้นตอนนี้เรียกว่าการ <strong>Push</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*B5EevRSKTK1dfFqeBSiTYQ.png" /></figure><p>เมื่อฟังก์ชัน greet2 แสดงผล How are you Maggie แล้ว ระบบจะทำการ <strong>Pop </strong>ฟังก์ชัน greet2 ออกไปโดยอัตโนมัติเพื่อให้โปรแกรมทำงานส่วนอื่นต่อ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Nt348O_MMjg8Sq_4zJAu8A.png" /></figure><p>ขั้นตอนการทำงานของระบบแบบนี้ทำให้ฟังก์ชัน greet ทำงานเสร็จไปบางส่วน แต่ไม่ทั้งหมด เนื่องจากต้องรอให้ฟังก์ชันที่ Stack อยู่ด้านบนของตัวเอง (greet2) ทำงานให้เสร็จสิ้นก่อน จากนั้นก็กลับมาทำงานที่ฟังก์ชันของตัวเองต่อคือการแสดงผล Getting ready to say bye.. แล้วจึงเรียกใช้งานฟังก์ชัน bye (จองหน่วยความจำแล้ว Stack ไว้เหมือนเดิม)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UQnqIFMby4J2sdwx8qIKWA.png" /></figure><p>เมื่อฟังก์ชัน bye แสดงผล OK bye แล้วก็ Pop ออกไป จากนั้นจึงกลับมาที่ greet อีกครั้ง พบว่าเสร็จสิ้นการทำงานหมดทุกขั้นตอนแล้วระบบก็จะทำการ Pop บล็อกหน่วยความจำ greet ออกไปเช่นกันเพื่อคืนหน่วยความจำให้กับคอมพิวเตอร์ของเรา</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ygkk5U6KoeaACLcUWLOu_Q.png" /></figure><h4>Call Stack กับ Recursion</h4><p>ฟังก์ชัน Recursive นั้นก็มีการใช้งาน Call Stack เช่นเดียวกัน วิธีการหนึ่งที่ใช้สำหรับการอธิบายเรื่อง Recursion คือการใช้ <strong>Factorial</strong> หลายๆคนอาจจะงง Factorial คืออะไร 555 ง่ายๆเลย มันคือฟังก์ชันที่เอาไว้คูณตัวเลขที่ป้อนเข้าไปย้อนกลับไปเรื่อยๆจนถึง 1 เช่น factorial(5) เขียนในรูปของคณิตศาสตร์ได้ 5! คำนวณออกมาได้เป็น 5*4*3*2*1 = 120 ถ้า factorial(3) ก็เขียนเป็น 3! = 3*2*1 = 6 แค่นี้เอง ง่ายป่ะล่ะ ส่วนในการเขียนโปรแกรมนั้นเราต้องอาศัยการ Recursive คล้ายๆกับตอนที่เราเขียนฟังก์ชัน countdown เลย ได้โค้ดออกมาหน้าตาเป็นแบบนี้</p><pre>def fact(x):<br>  if x == 1:<br>    return 1<br>  else:<br>    return x * fact(x-1)<br><br>print(fact(3))</pre><p>ลองเรียกฟังก์ชัน fact(3) ดูว่าโปรแกรมจะมีอะไรเปลี่ยนไปบ้างในแต่ละขั้นตอน</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*iE6Pz7WL9PXoP7_fXXf6_g.jpeg" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*mahtiLIgfK4u3lAhqb6Dng.jpeg" /></figure><h4>สรุป</h4><ul><li>Recursion คือฟังก์ชันเรียกตัวเอง</li><li>ฟังก์ชัน Recursive ประกอบไปด้วย Base-case และ Recursive-case</li><li>Stack คือโครงสร้างข้อมูลที่สำคัญชนิดหนึ่ง สามารถทำได้ทั้ง Push และ Pop</li><li>Call Stack คือฟังก์ชันที่ต้องเรียกฟังก์ชันอื่นอีกที</li><li>ฟังก์ชันเรียกตัวเองจะมีการ Call Stack อยู่เสมอ</li><li>Call Stack นั้นใช้หน่วยความจำมากและจะใหญ่ขึ้นไปๆเรื่อยตามจำนวนครั้งที่มีการเรียกตัวเอง</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ec926fb73aa8" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[สรุปหนังสือ Grokking Algorithms [Part 3]]]></title>
            <link>https://medium.com/@hamzcheeze/%E0%B8%AA%E0%B8%A3%E0%B8%B8%E0%B8%9B%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-3-6c49a7605260?source=rss-ea2c9e23fd0------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c49a7605260</guid>
            <dc:creator><![CDATA[Anurak Jairak]]></dc:creator>
            <pubDate>Tue, 29 Oct 2024 10:12:13 GMT</pubDate>
            <atom:updated>2025-01-03T07:48:29.993Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yiVC4GYmS__1MgQqARwiTA.jpeg" /></figure><h4>หน่วยความจำทำงานอย่างไร?</h4><p>ให้ลองจินตนาการว่าสมมติคุณต้องการเก็บของ 2 ชิ้นไว้ในลิ้นชัก โดยลิ้นชัก 1 ช่องสามารถเก็บของได้แค่ 1 ชิ้นเท่านั้น หมายความว่าถ้าต้องการเก็บของ 2 ชิ้น เราต้องใส่ของไว้ในลิ้นชัก 2 ช่อง แบบนี้</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d-hULTk-MtMJhxKxqexeJQ.png" /></figure><p>ซึ่งหลักการทำงานของหน่วยความจำในคอมพิวเตอร์ก็คล้ายคลึงกัน แต่จะมีที่อยู่ <strong>(Address)</strong> กำกับในแต่ละช่องว่าง ทุกครั้งที่เราต้องการเก็บข้อมูล คอมพิวเตอร์จะส่งที่อยู่ที่ว่างมาให้</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*A4X8A4wT43QrufYAfhq9yg.png" /></figure><p>โดยสมมติว่า fe0ffeeb เป็นที่อยู่ของหน่วยความจำ หากเราต้องการเก็บข้อมูลใดๆ เราต้องบอกคอมพิวเตอร์ก่อน หลังจากนั้นมันจะส่งที่อยู่ที่ว่างมาให้ ถ้าเราต้องการเก็บข้อมูลเป็นจำนวนมากๆ หลักๆแล้วจะมีด้วยกัน 2 วิธี คือใช้ <strong><em>Array</em></strong> และ <strong><em>Linked List</em></strong></p><h4>Array</h4><p>สมมติว่าคุณต้องการไปดูหนังกับเพื่อนอีก 3 คน (รวมคุณอีกคนเป็น 4) และต้องการนั่งติดกัน แต่ที่นั่งในแถวแรกนั้นว่างแค่ 3 ที่ คุณจึงจำเป็นต้องย้ายไปแถวอื่นเพื่อหาที่นั่งที่ว่างติดกัน 4 ที่ บังเอิญว่าแถวที่สองว่างติดกัน 4 ที่พอดี คุณกับเพื่อนก็ได้นั่งด้วยกัน แล้วถ้าสมมติว่ามีเพื่อนมาเพิ่มอีกคนล่ะ คุณกับเพื่อนอีก 4 คน (รวมคุณเป็น 5) ก็ต้องย้ายไปแถวอื่นอีก เพื่อหาที่ว่างที่ติดกัน 5 ที่ และต้องทำแบบนี้ไปเรื่อยๆเมื่อมีคนมาเพิ่ม</p><p>ในทางคอมพิวเตอร์แล้วการเขียนข้อมูลใหม่ด้วยวิธีนี้ถือว่าทำได้ช้า วิธีแก้คือ <strong><em>จองหน่วยความจำ(เก้าอี้)เผื่อไว้</em></strong> สมมติต้องการเขียนข้อมูล 3 ช่อง เราก็ต้องจองหน่วยความจำเผื่อไว้เลย 10 ช่อง ถ้าใช้หมด 10 ช่องก็ถือว่าใช้งานหน่วยจำได้อย่างคุ้มค่า แต่ถ้าใช้ไม่หมดก็จะเป็นการกั๊กที่ไว้เปล่าๆ คนอื่นจะมาขอใช้ก็ไม่ได้ แล้วถ้าต้องการเขียนข้อมูลเกิน 10 ช่องก็ต้องย้ายแถวใหม่ทั้งหมดอีก แต่ปัญหานี้จะหมดไปเมื่อได้รู้จักกับ…</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*L01DzIAR1dGyC8qU2M4swQ.png" /></figure><h4>Linked List</h4><p>ซึ่ง Linked List จะไม่เจอปัญหาแบบ Array แน่นอน สมมติถ้ามีเพื่อนที่ต้องการดูหนังมาเพิ่มอีก เราไม่จำเป็นต้องนั่งติดกันก็ได้ แค่หาที่นั่งอื่นๆที่ว่างก็สามารถนั่งได้เลย โดยที่นั่งของเพื่อนคนปัจจุบันจะมีที่อยู่ของเพื่อนคนถัดไปบอกด้วย เช่น ที่นั่ง 01 มีเพื่อนนั่งที่ 13, ที่นั่ง 13 มีเพื่อนที่มาเพิ่มนั่งเก้าอี้ 22 เป็นระบบที่จับมัดกลุ่มเพื่อนที่มานั่งดูหนังด้วยกันโดยไม่จำเป็นต้องนั่งติดกันก็ได้</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/998/1*ea_FUbkWb-PZ0CyZmW24HA.png" /></figure><p>แต่ปัญหาก็คือถ้าเราอยากรู้ที่นั่งสุดท้ายของกลุ่มเพื่อนที่มาด้วยกันนั้น เราต้องหาที่อยู่ของที่นั่งแรกให้ได้ก่อน ถ้าดูจากตัวอย่างเราก็รู้เลยใช่ไหมล่ะว่าคือที่นั่ง 22 แต่ในหน่วยความจำของคอมพิวเตอร์มันเป็นเลขฐาน 16 ซึ่งเราไม่มีทางรู้ได้เลยถ้าไม่หาที่อยู่ที่นั่งแรกของข้อมูลชุดนั้นๆก่อน และกว่าจะหาที่อยู่ที่นั่งแรกเจอเพื่อสาวไปถึงที่นั่งสุดท้าย (ตามชื่อของมัน Linked List ลิสต์ที่เชื่อมต่อกัน) มันคงเป็นอะไรที่เปลืองทรัพยากรของเครื่องมากๆ</p><p>แต่ Array ไม่เป็นแบบนั้น ถ้าคุณอยากรู้ที่อยู่ของที่นั่งลำดับที่ 5 ก็คณิตศาสตร์ง่ายๆเลย Array ลำดับแรกเริ่มต้นที่ 00 นับไปอีก 5 ก็เป็น 04 (n-1)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/930/1*st48AtAmZz0Qw_vtSpEgRw.png" /></figure><p>ซึ่งตำแหน่งของข้อมูลที่อยู่ใน Array (ที่นั่ง) จะมีการเรียงตามลำดับอยู่เสมอ เราเรียกมันว่า <strong><em>Index</em></strong> แทนที่เราจะเรียกว่าที่นั่ง 04 จากนี้ไปถ้าพูดถึง Array เราจะเรียกว่า Index ที่ 4 และนี่คือ Time Complexity ของ Array และ Linked List</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/708/1*TRFyVpY_rxO0DP3jDGdmJw.png" /></figure><p>จะสังเกตว่าเราสามารถเข้าถึง <strong>(Reading)</strong> ที่อยู่ของ Array ได้ไวมากๆ (O(1)ไวที่สุด) เนื่องจากเราแค่ระบุ Index ใน Array นั้นๆเราก็จะเจอข้อมูลในตำแหน่งนั้นๆเลย แต่การเขียนข้อมูลใหม่จะช้ากว่า Linked List เพราะเราต้องจองหน่วยความจำที่ว่างติดต่อกันทั้งแถวเพื่อที่จะเขียนข้อมูลใหม่ <strong>(Insertion)</strong> นั่นหมายความว่าเราต้องอ่านข้อมูลทั้งหมดขึ้นมาก่อน ถ้าว่างไม่เพียงพอกับข้อมูลใหม่ที่จะเขียนเข้าไปก็ต้องย้ายข้อมูลเก่าทั้งหมดไปยังแถวใหม่ (Slot) ที่สามารถทำเช่นนั้นได้ นี่เป็นสาเหตุที่ทำให้การเขียนข้อมูลของ Array เป็น O(n) แต่ Linked List สามารถเขียนข้อมูลตรงไหนก็ได้เลยโดยไม่ต้องย้ายข้อมูลหมดทั้งแถว ทำให้การเขียนข้อมูลของ Linked List เป็น O(1) และการลบข้อมูล <strong>(Deletion)</strong> ก็มีหลักการเช่นเดียวกัน</p><blockquote>คุณอาจจะงงเหมือนผมว่า เอ๊ะทำไมการลบข้อมูลถึงเป็น O(n) เหมือนการเขียน เพราะจุดเด่นของ Array คือความต่อเนื่องของลำดับใน Index อย่างที่ได้กล่าวไป ทำให้เราสามารถเข้าถึงข้อมูลได้อย่างรวดเร็ว ดังนั้นเมื่อมีการลบข้อมูลเกิดขึ้น จะต้องมีการนำข้อมูลทั้งชุดมาจัดเรียง Index ใหม่อยู่เสมอ เพื่อไม่ให้มีที่ว่างตรงกลางแถว</blockquote><p>แต่ถึงอย่างนั้น Array ก็เป็นที่นิยมในการใช้งานมากกว่า เนื่องจากอนุญาตให้สามารถเข้าถึงข้อมูลแบบสุ่มได้ <strong>(Ramdom Access)</strong> อย่างที่ได้บอกไปว่าถ้าอยากเข้าถึงข้อมูลตำแหน่งที่ 5 ก็คือชี้ไปที่ Index 4 ได้เลย โดยที่ไม่ต้องอ่านข้อมูลตั้งแต่ Index 0 เหมือน Linked List ทำให้การเข้าถึงข้อมูลแบบนี้ทำได้อย่างรวดเร็วและมีการใช้งานอยู่บ่อยๆ แต่ถึงอย่างนั้น Linked List ก็ยังมีประโยชน์ในบางกรณี ซึ่งเดี๋ยวเราจะมีการพูดถึงในบทต่อๆไป แต่ก่อนจะปิดท้าย Part นี้ต้องพูดถึง Selection Sort ก่อน</p><h4>Selection Sort</h4><p>คุณยังจำ <strong>Binary Search</strong> ใน Part ที่ 1 ได้ไหม ข้อจำกัดของมันคือสามารถค้นหาตัวเลขใน Array แบบเรียงลำดับมาแล้วเท่านั้น แต่ในโลกของความเป็นจริงนั้นข้อมูลต่างๆอาจจะไม่ได้เรียงลำดับมาให้เสมอไป สิ่งสำคัญคือเราจึงรู้จัก Algorithm สำหรับการจัดเรียงข้อมูลก่อน ถึงแม้ Selection Sort จะไม่เร็วมากเท่า <strong>Quick Sort</strong> (ซึ่งถือว่าเป็น Algorithm ที่สำคัญ) แต่มันก็เข้าใจง่าย หากเข้าใจมันแล้วจะทำให้การเรียนรู้ Quick Sort ง่ายขึ้นเยอะ</p><p>สมมติว่าคุณมีรายชื่อศิลปินต่างๆ พร้อมด้วยจำนวนครั้งในการเล่นเพลงของพวกเขา คุณต้องการที่จะเรียงลำดับจากมากไปหาน้อยเพื่อจัด ranking ศิลปินในดวงใจของคุณ เราจะทำอย่างไรกันดี?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/797/1*WKQHTGP1_CobO0JXZqOzdg.png" /></figure><p>ขั้นตอนแรกก็ง่ายมาก เราแค่มองหาตัวเลขของศิลปินที่มี Play Count ที่มากที่สุดแล้วก็ย้ายเข้าไปในตารางด้านขวาซะ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/844/1*w_S3JBRAM-bJm--AEEWPlQ.png" /></figure><p>โอเค.. เราได้สุดยอดศิลปินในดวงใจอันดับ 1 มาแล้วนั่นก็คือ Radiohead ต่อมาเราก็มองตัวเลขที่มากที่สุดรองลงมาแล้วก็ทำเหมือนเดิม</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/837/1*rrUvb2pfz1ek6kGGpEAt9A.png" /></figure><p>ในทุกๆครั้งที่ทำแบบนี้เราเรียกมันว่า <strong>n times</strong> จากตารางด้านซ้าย เรามองหาตัวเลขที่มากที่สุดจากบนลงล่าง มี Time Complexity เป็น O(n) แต่ยังไม่จบแค่นั้น เพราะเราต้องทำแบบนี้อีกจนครบเพื่อย้ายรายชื่อศิลปินไปยังตารางด้านขวาแล้วหาต่อจากรายชื่อที่เหลือ แบบนี้ถือว่าเป็น O(n*n) หรือ O(n²)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1019/1*Laerpu-x8Z2jeRQa9oZ0hA.png" /></figure><p>ทำแบบนี้ไปเรื่อยๆจนครบก็จะได้รายชื่อของศิลปินที่ผ่านการ ranking เรียบร้อย</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/820/1*LSK5WXe6IGRCL99vOviCXQ.png" /></figure><h4><strong>และนี่คือโค้ดตัวอย่าง</strong></h4><pre>def find_largest(arr):<br>    largest = arr[0]               # กำหนดค่าตัวแรกเป็นค่ามากที่สุดชั่วคราว (156)<br>    largest_index = 0              # กำหนด index เริ่มต้นเป็น 0<br>    for i in range(1, len(arr)):   # วนลูปตั้งแต่ index 1 ถึงความยาวของ array<br>        if arr[i] &gt; largest:       # ถ้าเจอตัวที่มากกว่า largest ปัจจุบัน<br>            largest = arr[i]       # กำหนดค่า largest ใหม่<br>            largest_index = i      # เก็บ index ของค่าที่มากที่สุดใหม่<br>    return largest_index           # ส่งคืน index ของค่าที่มากที่สุด<br><br>def selection_sort(arr):<br>    new_arr = []                   # สร้าง array ใหม่เปล่าๆ<br>    for i in range(len(arr)):      # วนลูปตามจำนวนสมาชิกใน array<br>        largest = find_largest(arr)        # หา index ของค่าที่มากที่สุด<br>        new_arr.append(arr.pop(largest))   # ดึงค่าที่มากที่สุดไปใส่ array ใหม่<br>    return new_arr                 # ส่งคืน array ที่เรียงแล้ว<br><br>print(selection_sort([156, 141, 111, 35, 94, 88, 61, 111]))<br># [156, 141, 111, 111, 94, 88, 61, 35]</pre><h4><strong>สรุป</strong></h4><ul><li>หน่วยความจำในคอมพิวเตอร์ของเราเปรียบเสมือนลิ้นชักขนาดใหญ่</li><li>หากคุณต้องเก็บข้อมูลเป็นจำนวนมากๆ สามารถใช้ได้ทั้ง Array และ Linked List</li><li>ในการเก็บข้อมูลแบบ Array นั้น ที่อยู่และข้อมูลจะอยู่ติดกันเสมอ</li><li>ในการเก็บข้อมูลแบบ Linked List นั้นข้อมูลจะกระจัดกระจาย โดยที่อยู่ของข้อมูลปัจจุบันจะเก็บที่อยู่ของข้อมูลถัดไปไว้ด้วย</li><li>Array นั้นเข้าถึงข้อมูลได้ไวกว่า</li><li>Linked List นั้นเขียนและลบข้อมูลได้ไวกว่า</li><li>ข้อมูลใน Array <strong>ควรจะ</strong>เป็นประเภทเดียวกันทั้งหมด</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c49a7605260" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[สรุปหนังสือ Grokking Algorithms [Part 2]]]></title>
            <link>https://medium.com/@hamzcheeze/%E0%B8%AA%E0%B8%A3%E0%B8%B8%E0%B8%9B%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-2-b1a74323e0df?source=rss-ea2c9e23fd0------2</link>
            <guid isPermaLink="false">https://medium.com/p/b1a74323e0df</guid>
            <category><![CDATA[big-o-notation]]></category>
            <category><![CDATA[algorithms]]></category>
            <dc:creator><![CDATA[Anurak Jairak]]></dc:creator>
            <pubDate>Wed, 14 Aug 2024 07:37:14 GMT</pubDate>
            <atom:updated>2025-01-05T06:13:45.900Z</atom:updated>
            <cc:license>http://creativecommons.org/publicdomain/zero/1.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yiVC4GYmS__1MgQqARwiTA.jpeg" /></figure><p>และแล้วก็ได้เวลามาต่อ Part 2 หลังจากที่หายหน้าหายตาไป 1 ปี 555 ซึ่งใน <a href="https://medium.com/@hamzcheeze/%E0%B9%81%E0%B8%9B%E0%B8%A5%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-1-a075f94e0680">Part 1</a> นั้นเราได้พูดถึงว่า <strong>Algorithm</strong> และ <strong>Logarithm </strong>คืออะไร หลักการทำงานของ <strong>Binary Search</strong> เป็นอย่างไร โดยใน Part 2 นั้นเราจะเริ่มจาก</p><h4>Running Time</h4><p>ย้อนกลับไป Part ที่แล้วที่เราพูดการเล่นทายตัวเลข หากมี 100 เลข ถ้าเราใช้ Algorithm แบบ Simple Search จะใช้จำนวนในการทาย 100 ครั้ง ถ้ามี 4 พันล้านเลขก็ใช้จำนวนในการทาย 4 พันล้านครั้งในกรณีที่แย่ที่สุดกว่าจะทายได้ถูกต้อง ซึ่งสิ่งนี้เรียกว่า Linear Time หรือเวลาเชิงเส้น แต่ถ้าเราใช้ Binary Search ตัวเลข 100 ตัวจะให้จำนวนการทายอย่างมากที่สุดคือ 7 ครั้ง ถ้า 4 พันล้านเลขจะใช้จำนวนในการทายแค่ 32 ครั้งเท่านั้น!! บ้าไปแล้ววว สำหรับกรณีนี้เรียกว่า Logarithm Time ซึ่งเราได้พูดถึงไปแล้วใน <a href="https://medium.com/@hamzcheeze/%E0%B9%81%E0%B8%9B%E0%B8%A5%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-1-a075f94e0680">Part 1</a> ไปย้อนอ่านดูได้เลย</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/585/1*3N2LDzvXnUET52M7g5atNw.png" /></figure><h4>Big O Notation คืออะไร?</h4><p>คือสิ่งที่ใช้ในวัดกรณีที่แย่ที่สุดใน Algorithm ของเรา ถ้าเราอยากรู้ว่าการทายตัวเลข 4 พันล้านครั้งโดยใช้ Binary Search นั้นมี Big O เท่าไหร่ คำตอบคือ O(log n) เนื่องจากใช้วิธีการหั่นครึ่งของเลขทั้งหมดแล้วทายเลขตรงกลาง (log n operation) ในขณะที่ Big O ของ Simple Search นั้นขึ้นอยู่กับจำนวนของการทาย (n operation) ฉะนั้น Big O ของ Simple Search คือ O(n) เพราะต้องทายเลขไปเรื่อยๆเริ่มตั้งแต่ 1 ไปจนถึง 4 พันล้าน ส่วนเหตุผลที่เรียกว่า Big O เนื่องจากขึ้นต้นด้วย O ใหญ่ แล้วตามด้วย Number of Operation (จำนวนครั้งในการทำ) เขียนแทนด้วยสัญลักษณ์แบบนี้</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/520/1*ggcV0cP51-0P4nOpOMMQLQ.png" /></figure><h4>Algorithm มีผลอย่างไรกับ Big O</h4><p>เพื่อให้เห็นภาพมากขึ้น เราลองมาวาดช่อง 4 เหลี่ยม 16 ช่องลงในกระดาษด้วย Algorithm ที่ต่างกันดู</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/519/1*f_9oKVEBQnGMvfWgp1_nTA.png" /></figure><h4>Algorithm ที่ 1</h4><p>วาดช่อง 4 เหลี่ยมทีละช่องไปเรื่อยๆ เริ่มตั้งแต่มุมของกระดาษต่อกันไปจนเต็มครบ 16 ช่องของกระดาษ อย่าลืมว่า Big O จะนับจาก Number of Operation นั่นหมายความว่าเราต้องวาดช่อง 4 เหลี่ยมทั้งสิ้น 16 ครั้ง ดังนั้น Algorithm นี้มี Running Time เท่ากับ O(n)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/859/1*Ud5tQh0BMaAiksLeGqHPdA.png" /></figure><h4>Algorithm ที่ 2</h4><p>พับกระดาษทีละครึ่งแล้วคลี่ออก โดยทุกๆ 1 พับ เราจะได้รอย 4 เหลี่ยม 2 ช่อง จากก็ลากเส้นไปตามรอยพับที่ได้มาก็จะได้ช่อง 4 เหลี่ยมมาทั้งหมด 16 ช่องจากการพับเพียงแค่ 4 ครั้งเท่านั้น ดังนั้น Running Time ของ Algorithm นี้จึงเท่ากับ O(log n)</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/852/1*2Aul0_vW-1-rc_eKdQoO7Q.png" /></figure><h4>Big O เป็นตัววัดกรณีที่แย่ที่สุด</h4><p>สาเหตุที่ต้องการวัดกรณีที่แย่ที่สุด (worst-case scenario) นั่นก็เป็นเพราะว่าเราอยากจะรู้ว่า Algorithm จะทำงานช้าที่สุดแค่ไหน ช่วยให้สามารถรับประกันประสิทธิภาพขั้นต่ำของระบบคอมพิวเตอร์ได้ โดยไม่สนว่า input หรือข้อมูลที่เข้ามาจะมีหน้าตาแบบใด การรู้ถึงข้อจำกัดสูงสุดนั้นยังช่วยในการวางแผนทรัพยากรและการออกแบบระบบได้ดีขึ้นด้วย</p><blockquote>นอกจาก O(log n) และ O(n) แล้วยังมี Big O แบบอื่นอีกนะ เช่น O(n * log n) ได้แก่ Quick Sort, O(n²) ได้แก่ Selection Sort, O(n!) ได้แก่ Traveling Saleperson</blockquote><p>ทีนี้เราลองมาวาดช่อง 4 เหลี่ยม 16 ช่องกันดูอีกสักครั้งจาก 5 Algorithm ที่ได้กล่าวมา โดยเริ่มจาก Algorithm แรก Binary Search ซึ่งมี Big O เท่ากับ O(log n) <strong>โดยสมมติว่าใช้เวลา 1 วินาทีต่อ 10 Operation</strong> ด้วย O(log n) ที่มี Number of Operation เท่ากับ 4 ดังนั้นจะใช้เวลา 0.4 วินาทีในการวาด 16 ช่อง (log 16 = 4 เอา 4/10 = 0.4) แล้วถ้าต้องการวาด 1024 ช่องล่ะ log 1024 = 10 จากนั้นเอา 10/10 = 1 วินาที และนี่คือการจำลองเวลาที่ใช้ในการวาดช่อง 4 เหลี่ยมจากทั้งหมด 5 Algorithm เรียงลำดับจากเร็วที่สุดไปยังช้าที่สุด</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2PIR_6SsS2NyHXotu94Zag.png" /></figure><p>อย่าลืมว่านี่เป็นเพียงการจำลองสถานการณ์เท่านั้น ในความเป็นจริงเราไม่สามารถแปลง Running Time ไปเป็น Number of Operation แบบตรงไปตรงมาได้ แต่ก็พอจะทำให้เห็นภาพมากขึ้นว่าในแต่ละ Algorithm นั้นมี worst-case scenario ที่ต่างกันขนาดไหน</p><h4>สรุป</h4><ul><li>Big O เป็นตัววัดกรณีที่แย่ที่สุด ใช้เขียนแทน Running Time ของ Algorithm นั้นๆ</li><li>Algorithm ไม่ได้วัดความเร็วเป็นวินาที แต่เป็นตัววัดความเติบโตของ Number of Operation ยิ่งมีมากก็มีแนวโน้มจะใช้เวลามากขึ้น</li><li>ยิ่งมี Input มากขึ้น (จำนวนช่อง 4 เหลี่ยม) Number of Operation ก็จะยิ่งมากขึ้นตาม</li><li>ถึง O(log n) จะเร็วกว่า O(n) ไม่มากเมื่อวาด 4 เหลี่ยม 16 ช่อง แต่เห็นผลมากเมื่อวาด 1024 ช่องและยิ่งมากขึ้นเรื่อยๆ ยิ่งเห็นความแตกต่าง</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b1a74323e0df" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[สรุปหนังสือ Grokking Algorithms [Part 1]]]></title>
            <link>https://medium.com/@hamzcheeze/%E0%B9%81%E0%B8%9B%E0%B8%A5%E0%B8%AB%E0%B8%99%E0%B8%B1%E0%B8%87%E0%B8%AA%E0%B8%B7%E0%B8%AD-grokking-algorithms-part-1-a075f94e0680?source=rss-ea2c9e23fd0------2</link>
            <guid isPermaLink="false">https://medium.com/p/a075f94e0680</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[grokking-algorithm]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[data-structure-algorithm]]></category>
            <dc:creator><![CDATA[Anurak Jairak]]></dc:creator>
            <pubDate>Mon, 17 Jul 2023 12:33:18 GMT</pubDate>
            <atom:updated>2025-01-05T06:10:42.204Z</atom:updated>
            <cc:license>http://creativecommons.org/publicdomain/zero/1.0/</cc:license>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KD6dfLl6giLhnCX9KkTyMw.png" /></figure><p>ที่ผ่านมาผมเคยอ่านหนังสือเกี่ยวกับ Data Structure &amp; Algorithms หลายๆเล่มนั้นล้วนยากต่อความเข้าใจ เนื่องจากเป็นเรื่องที่หนักไปทางทฤษฎีและเราก็ไม่รู้ว่าจะเอาไปประยุกต์ในงานจริงได้อย่างไร (หรืองานเราอาจจะไม่ได้ยากและซับซ้อนขนาดนั้น 555) แต่โปรแกรมเมอร์ที่ดีก็ควรจะรู้ว่างานไหนจะต้องใช้ Data Structure หรือ Algorithms ไหนเพื่อให้เหมาะสมกับงานนั้นๆ</p><p>พอเมื่อได้อ่านหนังสือเล่มนี้ ชื่อเต็มคือ <strong>Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People</strong> เขียนโดย <strong>Aditya Y. Bhargava</strong> ก็รู้สึกว่าเป็นหนังสือที่อ่านเข้าใจง่าย มีภาพประกอบที่เป็นตัวการ์ตูนค่อนข้างเยอะ มีการเปรียบเทียบกับเคสต่างๆในชีวิตจริง ใช้ศัพท์ที่ไม่ยากมาก ผมจึงอยากลองแปลหนังสือเล่มนี้ดูเพื่อทบทวนในสิ่งที่ตัวเองได้อ่านมา บวกกับบริษัทเทคชื่อดังหลายๆเจ้าก็นิยมใช้วิธีการ Coding Interview เพื่อคัดคนเข้าทำงาน จึงเป็นโอกาสที่ดีหากใครผ่านเข้ามาอ่านแล้วได้ความรู้เพื่อนำไปใช้ประโยชน์ได้จริง ว่าแล้วก็เข้าสู่เนื้อหากันเลยดีกว่า</p><blockquote><em>แต่ก่อนจะเข้าสู่เนื้อหา สิ่งที่ควรรู้ก่อนอ่านหนังสือเล่มนี้คือ “พีชคณิตพื้นฐาน” ถ้าคุณเข้าใจว่า</em> f(x) = x * 2<em> แล้ว</em> f(5) = 10 <em>ถือว่าโอเคเลย ยิ่งถ้าเคยเขียนโปรแกรมมาก่อนจะเข้าใจเนื้อหาได้อย่างรวดเร็ว โค้ดในหนังสือเล่มนี้ใช้ภาษา </em><strong><em>Python 3 </em></strong><em>ซึ่งถ้าคุณไม่เคยเขียนโปรแกรมมาก่อน </em><strong><em>Python</em></strong><em> ถือว่าเป็นภาษาที่ดี เหมาะสำหรับผู้เริ่มต้นเลยแหละ</em></blockquote><h4>Algorithm คืออะไร?</h4><p>สำหรับคนที่เรียนหรือทำงานด้านการเขียนโปรแกรมคงไม่สงสัยเท่าไหร่ แต่สำหรับคนที่ไม่ทราบ Algorithm คือ <em>“วิธีการที่ใช้แก้ปัญหางานบางอย่างให้สำเร็จ” </em>ยกตัวอย่างเช่น ถ้าคุณต้องการเล่นทายตัวเลขกับเพื่อน โดยตัวเลขมีตั้งแต่ 1–100 คุณจะใช้ Algorithm ไหน? ถ้าคุณทายตั้งแต่ 1 2 3 4 5 … ไปเรื่อยๆ Algorithm นี้เรียกว่า <strong>Simple Search </strong>(การหาแบบถึกทน) ให้ลองนึกภาพถ้าคำตอบคือ 99 เราต้องใช้เวลาทายถึง 99 ครั้งกว่าจะเจอคำตอบ แต่ว่าเจอแน่นอนถ้าเทียบกับการเดาแบบสะเปะสะปะโดยไม่มีวิธีที่แน่นอน</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*LALBbkQaM6n-JT0K9MvpcA.jpeg" /></figure><h4>แล้วมีวิธีที่ดีกว่านี้ไหม?</h4><p>แน่นอน! วิธีนั้นเรียกว่า <strong>Binary Search</strong> (การหาแบบหั่นครึ่ง) โดยวิธีการนี้เราจะเริ่มจากการหาเลขจากตรงกลางก่อนเสมอ โดยเราจะเริ่มทายจากเลข 50 ก่อน ถ้าเพื่อนบอกว่าต่ำไป ให้เราตัดเลข 1–50 ทิ้งไปได้เลย</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*VXxBA5BVqs_SKhQjmScb_w.png" /></figure><p>จากนั้นก็เอาเลขชุดหลัง (50–100) มาหั่นครึ่งแล้วทายต่อ นั่นคือเลข 75</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*QvYxOHlo4soBVNc3fOWfOg.png" /></figure><p>เพื่อนบอกว่าสูงไป แสดงว่าเราก็ต้องตัดเลขชุดหลังจาก 75 ออก (75-100) แล้วเอาเลขชุดหน้า (50–75 ) หั่นครึ่งแล้วทายต่อนั่นคือเลข 63</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*o37NYE6b2S_sIyW8Q3nIZA.png" /></figure><p>เพื่อนบอกสูงไป ทีนี้เราก็เหลือแค่เลขที่สามารถทายได้แค่ 50–63 เอามาหั่นครึ่งอีกครั้งได้เลข 57 เพื่อนบอกถูกต้อง! วิธีการนี้เราจะใช้การทายเพียงแค่ 7 ครั้งเท่านั้น ประหยัดเวลาสุดๆ โดยในทุกๆการหา (<em>n</em>) ของ Binary Search จะใช้ log ของ <em>n</em> ฐาน 2 เพื่อหาในกรณีที่แย่ที่สุด (Worst-case) โดยมีข้อแม้คือส่ิงที่ต้องการค้นหานั้นต้องผ่านการเรียงลำดับมาก่อนเสมอ</p><h4>Logarithms คืออะไร?</h4><p>บางคนอาจจะลืมไปแล้วว่า Logarithms คืออะไร แต่คิดว่าทุกคนต้องรู้จัก<strong>เลขยกกำลัง</strong>แน่นอน สมมติถามว่า 10 ยกกำลังอะไรได้ 100 คำตอบ 2 เพราะ 10 * 10 = 100 (10 คูณกัน 2 ครั้ง) เพราะฉะนั้น Logs จึงเป็นด้านกลับของเลขยกกำลัง</p><blockquote>10 ยกกำลัง 2 = 100 ←→ log ของ 100 ฐาน 10 = 2</blockquote><blockquote>10 ยกกำลัง 3 = 1000 ←→ log ของ 1000 ฐาน 10 = 3</blockquote><blockquote>2 ยกกำลัง 3 = 8 ←→ log ของ 8 ฐาน 2 = 3</blockquote><blockquote>2 ยกกำลัง 4 = 16 ←→ log ของ 16 ฐาน 2 = 4</blockquote><blockquote>2 ยกกำลัง 5 = 32 ←→ log ของ 32 ฐาน 2 = 5</blockquote><p>โดยในหนังสือเล่มนี้จะพูดถึง running time ในรูปของ Big O (โดยจะกล่าวถึงในคราวต่อไป) log ในที่นี้จะหมายถึง log ฐาน 2 เสมอ</p><h4>มาดูโค้ด Binary Search ใน Python กันดีกว่า</h4><p>โค้ดตัวอย่างนี้ใช้อาเรย์ (Array) เป็นหลัก ส่วนใครที่ไม่รู้จักไม่ต้องกังวลไป จะมีการพูดถึงในบทถัดไป คุณแค่ต้องรู้ว่าอาเรย์ใช้สำหรับในการเก็บ element หรือข้อมูลใดๆแบบเรียงลำดับ โดยข้อมูลจะเริ่มต้นที่ตำแหน่ง 0 ตามด้วย 1, 2, 3 ไปเรื่อยๆ โดยตำแหน่งสุดท้ายต้อง -1 เสมอ (เนื่องจากเริ่มด้วย 0)</p><p>โดยฟังก์ชัน binary_search นี้จะรับข้อมูลในอาเรย์ที่เรียงมาแล้วกับตัวเลขที่เป็นคำตอบ จากนั้นก็เช็คว่ามีข้อมูลในอาเรย์นั้นไหม ถ้ามีให้ return ตำแหน่ง (index) ที่ตัวเลขนั้นอยู่ โดยเริ่มจากการกำหนด<strong>เลขน้อย</strong>กับ<strong>เลขมาก</strong>ก่อน</p><pre>low = 0<br>high = len(list) - 1</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/389/1*hmhmhCR65_8F1bKuSMzYgw.png" /></figure><p>จากนั้นหา<strong>เลขกลาง</strong>ด้วยสูตร “<strong>เลขน้อย</strong>บวก<strong>เลขมาก</strong>หาร 2” โดยเลขกลางจะถูกปัดลงโดยอัตโนมัติถ้าหากไม่ใช่เลขคู่</p><pre>mid = (low + high) // 2<br>guess = list[mid]</pre><p>ถ้าเลขที่ทายต่ำไป ให้อัพเดต low ถ้าหากเลขที่ทายสูงไปก็ให้อัพเดต high เช่นกัน</p><pre>if guess &lt; item:<br>  low = mid + 1<br>else: <br>  high = mid - 1</pre><figure><img alt="" src="https://cdn-images-1.medium.com/max/531/1*yic_kcKO1r5pNsMn0CfpKw.png" /></figure><p>และนี่คือโค้ดเต็ม</p><pre>def binary_search(list, item):<br>  low = 0                        # กำหนดเลขต่ำ<br>  high = len(list) - 1           # กำหนดเลขสูง<br>  <br>  while low &lt;= high:             # วนรอบไปจนเลขน้อยชนกับเลขมาก<br>    mid = (low + high) // 2      # กำหนดเลขกลาง<br>    guess = list[mid]            # กำหนดตำแหน่งของเลขที่ทาย<br>    if guess == item:            # ถ้าเลขที่ทายถูกต้องให้ return ตำแหน่งนั้นๆ<br>      return mid<br>    if guess &lt;= item:            # อัพเดตเลขน้อยถ้าบอกว่าต่ำไป           <br>      low = mid + 1<br>    else: <br>      high = mid - 1             # อัพเดตเลขมากถ้าบอกว่าสูงไป<br>  return None<br><br>my_list = [1, 3, 5, 7, 9]<br><br>print(binary_search(my_list, 3))    # เลข 3 อยู่ index ที่ 1<br>print(binary_search(my_list, -1))   # return None เมื่อไม่เจอ -1 ในอาเรย์</pre><p>หากใครที่ยังไม่ได้ติดตั้ง <strong>Python</strong> ลงในคอมพิวเตอร์ ผมมีเว็บไซต์ที่สามารถใช้รันโค้ดออนไลน์ได้มาแนะนำ โดยคัดลอกโค้ดด้านบนไปวางแล้วกด Run เพื่อดูผลลัพธ์ได้เลย</p><p><a href="https://www.mycompiler.io/new/python">https://www.mycompiler.io/new/python</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=a075f94e0680" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>