โครงสร้างข้อมูล & อัลกอริธึมใน Python: ทุกสิ่งที่คุณจำเป็นต้องรู้

โครงสร้างข้อมูลและอัลกอริทึมใน Python เป็นแนวคิดพื้นฐานสองประการในวิทยาการคอมพิวเตอร์ เป็นเครื่องมือที่จำเป็นสำหรับโปรแกรมเมอร์ทุกคน โครงสร้างข้อมูลใน Python จัดการกับองค์กรและการจัดเก็บข้อมูลในหน่วยความจำในขณะที่โปรแกรมกำลังประมวลผล ในทางกลับกัน อัลกอริทึมของ Python อ้างถึงชุดคำสั่งโดยละเอียดที่ช่วยในการประมวลผลข้อมูลเพื่อวัตถุประสงค์เฉพาะ

อีกวิธีหนึ่ง อาจกล่าวได้ว่าโครงสร้างข้อมูลที่แตกต่างกันถูกใช้อย่างมีตรรกะโดยอัลกอริธึมเพื่อแก้ปัญหาเฉพาะของการวิเคราะห์ข้อมูล ไม่ว่าจะเป็นปัญหาในโลกแห่งความเป็นจริงหรือคำถามเกี่ยวกับการเข้ารหัสทั่วไป การทำความเข้าใจ โครงสร้างข้อมูลและอัลกอริทึมใน Python นั้นมีความสำคัญมาก หากคุณต้องการหาวิธีแก้ไขปัญหาที่แม่นยำ ในบทความนี้ คุณจะได้พบกับการอภิปรายโดยละเอียดเกี่ยวกับ อัลกอริธึม และโครงสร้างข้อมูล ของ Python แบบต่างๆ หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับ Python โปรดดู ที่ หลักสูตรวิทยาศาสตร์ข้อมูล ของเรา

เรียนรู้เพิ่มเติม: โครงสร้างข้อมูลหกโครงสร้างที่ใช้บ่อยที่สุดใน R

โครงสร้างข้อมูลใน Python คืออะไร?

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

ในขณะที่ชนิดข้อมูลพื้นฐานประกอบด้วยจำนวนเต็ม โฟลต สตริง และบูลีน ชนิดข้อมูลที่ไม่ใช่แบบพื้นฐานได้แก่ อาร์เรย์ รายการ ทูเพิล พจนานุกรม ชุด และไฟล์ ชนิดข้อมูลที่ไม่ใช่แบบพื้นฐานเหล่านี้บางประเภท เช่น รายการ ทูเพิล พจนานุกรม และชุด สร้างขึ้นใน Python มีโครงสร้างข้อมูลอีกประเภทหนึ่งใน Python ที่ผู้ใช้กำหนด นั่นคือผู้ใช้กำหนดพวกเขา ซึ่งรวมถึง Stack, Queue, Linked List, Tree, Graph และ HashMap

โครงสร้างข้อมูลดั้งเดิม

เหล่านี้เป็นโครงสร้างข้อมูลพื้นฐานใน Python ที่มีค่าข้อมูลที่บริสุทธิ์และเรียบง่ายและทำหน้าที่เป็นหน่วยการสร้างสำหรับการจัดการข้อมูล ให้เราพูดถึงตัวแปรพื้นฐานสี่ประเภทใน Python:

• จำนวนเต็ม – ชนิดข้อมูลนี้ใช้เพื่อแสดงข้อมูลตัวเลข กล่าวคือ จำนวนเต็มบวกหรือลบโดยไม่มีจุดทศนิยม พูดว่า -1, 3 หรือ 6
• ทุ่น – ลอยหมายถึง 'จำนวนจริงจุดลอยตัว' ใช้เพื่อแสดงจำนวนตรรกยะ ซึ่งมักจะมีจุดทศนิยมเช่น 2.0 หรือ 5.77 เนื่องจาก Python เป็นภาษาการเขียนโปรแกรมที่พิมพ์แบบไดนามิก ชนิดข้อมูลที่จัดเก็บอ็อบเจ็กต์จึงเปลี่ยนแปลงได้ และไม่จำเป็นต้องระบุประเภทของตัวแปรของคุณอย่างชัดเจน
• สตริง – ชนิดข้อมูลนี้แสดงถึงชุดของตัวอักษร คำ หรืออักขระที่เป็นตัวอักษรและตัวเลขคละกัน มันถูกสร้างขึ้นโดยการรวมชุดของอักขระไว้ในเครื่องหมายคำพูดคู่หรือเดี่ยว ในการต่อสตริงตั้งแต่สองสตริงขึ้นไป สามารถใช้การดำเนินการ '+' กับสตริงเหล่านั้นได้ การทำซ้ำ การประกบ การใช้อักษรตัวพิมพ์ใหญ่ และการดึงข้อมูลคือการดำเนินการสตริงอื่นๆ ใน Python ตัวอย่าง: 'สีน้ำเงิน' 'สีแดง' เป็นต้น
• บูลีน – ชนิดข้อมูลนี้มีประโยชน์ในการเปรียบเทียบและนิพจน์เงื่อนไข และสามารถใช้ค่า TRUE หรือ FALSE

เรียนรู้เพิ่มเติม: Data Frames ใน Python

โครงสร้างข้อมูลแบบ non-primitive ที่สร้างขึ้น

ตรงกันข้ามกับโครงสร้างข้อมูลดั้งเดิม ชนิดข้อมูลที่ไม่ใช่แบบดั้งเดิมไม่เพียงเก็บค่าเท่านั้น แต่ยังเก็บค่าในรูปแบบต่างๆ ให้เราดูที่โครงสร้างข้อมูลที่ไม่ใช่แบบดั้งเดิมใน Python:

• • รายการ – นี่คือโครงสร้างข้อมูลที่หลากหลายที่สุดใน Python และเขียนเป็นรายการองค์ประกอบที่คั่นด้วยเครื่องหมายจุลภาคภายในวงเล็บเหลี่ยม รายการสามารถประกอบด้วยทั้งองค์ประกอบที่แตกต่างกันและเป็นเนื้อเดียวกัน วิธีการบางอย่างที่ใช้กับ List ได้แก่ index(), append(), expand(), insert(), remove(), pop() เป็นต้น รายการจะเปลี่ยนแปลงได้ กล่าวคือ เนื้อหาสามารถเปลี่ยนแปลงได้ โดยคงเอกลักษณ์ไว้ได้

แหล่งที่มา

• Tuples – Tuples คล้ายกับ Lists แต่ไม่สามารถเปลี่ยนแปลงได้ นอกจากนี้ ทูเพิลต่างจาก Lists ตรงที่ประกาศไว้ในวงเล็บแทนที่จะเป็นวงเล็บเหลี่ยม คุณลักษณะของการไม่เปลี่ยนรูปหมายความว่าเมื่อองค์ประกอบถูกกำหนดในทูเพิลแล้ว จะไม่สามารถลบ กำหนดใหม่ หรือแก้ไขได้ ช่วยให้มั่นใจได้ว่าค่าที่ประกาศของโครงสร้างข้อมูลจะไม่ถูกจัดการหรือแทนที่

แหล่งที่มา

• พจนานุกรม – พจนานุกรมประกอบด้วยคู่คีย์-ค่า 'คีย์' ระบุรายการ และ 'ค่า' เก็บมูลค่าของรายการ โคลอนแยกคีย์ออกจากค่า รายการจะถูกคั่นด้วยเครื่องหมายจุลภาค โดยที่รายการทั้งหมดอยู่ในวงเล็บปีกกา แม้ว่าคีย์จะไม่เปลี่ยนรูปแบบ (ตัวเลข สตริง หรือทูเพิล) ค่าจะเป็นประเภทใดก็ได้

แหล่งที่มา

• ชุด – ชุดคือชุดขององค์ประกอบที่ไม่ซ้ำกันที่ไม่เรียงลำดับ เช่นเดียวกับรายการ ชุดสามารถเปลี่ยนแปลงได้และเขียนในวงเล็บเหลี่ยม แต่ไม่มีค่าสองค่าใดที่เหมือนกัน เมธอด Set บางวิธีรวมถึง count(), index(), any(), all() เป็นต้น

แหล่งที่มา

• รายการเทียบกับอาร์เรย์ – ไม่มีแนวคิดในอาร์เรย์ของอาร์เรย์ใน Python สามารถนำเข้าอาร์เรย์ได้โดยใช้แพ็คเกจ NumPy ก่อนที่จะเริ่มต้น หากต้องการทราบข้อมูลเพิ่มเติมเกี่ยวกับ NumPy สามารถชำระเงิน บทช่วยสอน python NumPy ของ เรา Lists and Arrays ส่วนใหญ่จะคล้ายกัน ยกเว้นหนึ่งความแตกต่าง – ในขณะที่ Arrays เป็นคอลเลกชันขององค์ประกอบที่เป็นเนื้อเดียวกันเท่านั้น Lists จะรวมรายการที่เป็นเนื้อเดียวกันและต่างกัน

ชำระเงิน: ประเภทของไบนารีทรี

โครงสร้างข้อมูลที่ผู้ใช้กำหนดใน Python

ต่อไปในการอภิปรายของเราเกี่ยวกับ โครงสร้างข้อมูลและอัลกอริทึมใน Python เป็นภาพรวมโดยย่อของโครงสร้างข้อมูลที่ผู้ใช้กำหนดเองที่แตกต่างกัน:

• กอง – กองเป็นโครงสร้างข้อมูลเชิงเส้นใน Python การจัดเก็บไอเท็มใน Stacks ขึ้นอยู่กับหลักการของ First-In/Last-Out (FILO) หรือ Last-In/First-Out (LIFO) ใน Stacks การเพิ่มองค์ประกอบใหม่ที่ปลายด้านหนึ่งจะมาพร้อมกับการนำองค์ประกอบออกจากส่วนท้ายเดียวกัน การดำเนินการ 'พุช' และ 'ป๊อป' ใช้สำหรับแทรกและลบตามลำดับ ฟังก์ชั่นอื่น ๆ ที่เกี่ยวข้องกับ Stack คือ empty(), size() และ top() สแต็คสามารถใช้งานได้โดยใช้โมดูลและโครงสร้างข้อมูลจากไลบรารี Python – list, collections.deque และ queue.LifoQueue
• คิว – คล้ายกับสแต็ค คิวคือโครงสร้างข้อมูลเชิงเส้น อย่างไรก็ตาม รายการต่างๆ จะถูกจัดเก็บตามหลักการเข้าก่อน/ออกก่อน (FIFO) ในคิว รายการที่เพิ่งเพิ่มล่าสุดจะถูกลบออกก่อน การดำเนินการที่เกี่ยวข้องกับ Queue ได้แก่ Enqueue (การเพิ่มองค์ประกอบ) Dequeue (การลบองค์ประกอบ) ด้านหน้าและด้านหลัง เช่นเดียวกับ Stacks คิวสามารถใช้งานได้โดยใช้โมดูลและโครงสร้างข้อมูลจากไลบรารี Python – list, collections.deque และ Queue
• ต้นไม้ – ต้นไม้เป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้นใน Python และประกอบด้วยโหนดที่เชื่อมต่อด้วยขอบ คุณสมบัติของ Tree คือโหนดหนึ่งโหนดถูกกำหนดให้เป็นโหนดรูท นอกเหนือจากรูท โหนดอื่นทุกโหนดมีโหนดหลักที่เกี่ยวข้อง และแต่ละโหนดสามารถมีจำนวนโหนดย่อยตามจำนวนที่กำหนด โครงสร้างข้อมูลไบนารีทรีคือโครงสร้างที่มีองค์ประกอบมีลูกไม่เกินสองคน
• รายการที่เชื่อมโยง – ชุดขององค์ประกอบข้อมูลที่เชื่อมต่อเข้าด้วยกันผ่านลิงก์เรียกว่ารายการที่เชื่อมโยงใน Python นอกจากนี้ยังเป็นโครงสร้างข้อมูลเชิงเส้น องค์ประกอบข้อมูลแต่ละรายการในรายการที่เชื่อมโยงจะเชื่อมต่อกับอีกองค์ประกอบหนึ่งโดยใช้ตัวชี้ เนื่องจากไลบรารี Python ไม่มี Linked Lists จึงถูกใช้งานโดยใช้แนวคิดของโหนด รายการที่เชื่อมโยงมีข้อได้เปรียบเหนืออาร์เรย์ในการมีขนาดไดนามิก โดยง่ายต่อการแทรก/ลบองค์ประกอบ
• กราฟ – กราฟใน Python จะแสดงภาพชุดของออบเจกต์ โดยมีบางคู่ของอ็อบเจ็กต์เชื่อมต่อกันด้วยลิงก์ จุดยอดเป็นตัวแทนของวัตถุที่เชื่อมต่อถึงกัน และลิงก์ที่เข้าร่วมจุดยอดจะเรียกว่าเป็นขอบ ชนิดข้อมูลพจนานุกรม Python สามารถใช้ในการนำเสนอกราฟได้ โดยพื้นฐานแล้ว 'กุญแจ' ของพจนานุกรมแสดงถึงจุดยอด และ 'ค่า' บ่งบอกถึงการเชื่อมต่อหรือขอบระหว่างจุดยอด
• HashMaps/ตารางแฮช – ในโครงสร้างข้อมูลประเภทนี้ ฟังก์ชัน Hash จะสร้างที่อยู่หรือค่าดัชนีขององค์ประกอบข้อมูล ค่าดัชนีทำหน้าที่เป็นกุญแจสำคัญในค่าข้อมูลที่ช่วยให้เข้าถึงข้อมูลได้เร็วขึ้น ในประเภทข้อมูลพจนานุกรม ตารางแฮชมีคู่คีย์-ค่า แต่ฟังก์ชันแฮชจะสร้างคีย์

อัลกอริทึมใน Python คืออะไร

อัลกอริธึมของ Python คือชุดคำสั่งที่ดำเนินการเพื่อแก้ไขปัญหาที่กำหนด เนื่องจากอัลกอริธึมไม่ได้เจาะจงภาษา จึงสามารถนำไปใช้กับภาษาโปรแกรมได้หลายภาษา ไม่มีกฎเกณฑ์มาตรฐานใดเป็นแนวทางในการเขียนอัลกอริธึม สิ่งเหล่านี้ขึ้นอยู่กับทรัพยากรและปัญหา แต่ใช้โครงสร้างโค้ดทั่วไปร่วมกัน เช่น การควบคุมการไหล (if-else) และลูป (do, while, for) ในส่วนต่อไปนี้ เราจะอธิบายคร่าวๆ เกี่ยวกับ Tree Traversal, Sorting, Searching และ Graph Algorithms

อัลกอริทึมการข้ามต้นไม้

Traversal เป็นกระบวนการของการเยี่ยมชมโหนดทั้งหมดของ Tree โดยเริ่มจากโหนดรูท ต้นไม้สามารถสำรวจได้สามวิธี:

– การข้ามผ่านในลำดับเกี่ยวข้องกับการเยี่ยมชมทรีย่อยทางด้านซ้ายก่อน ตามด้วยรูท และจากนั้นไปที่ทรีย่อยทางขวา

– ในการข้ามผ่านของการสั่งซื้อล่วงหน้า โหนดแรกที่เข้าชมคือโหนดรูท ตามด้วยทรีย่อยทางซ้าย และสุดท้ายคือทรีย่อยทางขวา

– ในอัลกอริธึมหลังการสั่งซื้อ ทรีย่อยด้านซ้ายจะถูกเยี่ยมชมก่อน จากนั้น ทรีย่อยด้านขวาจะถูกเยี่ยมชม โดยที่โหนดรูทจะถูกเยี่ยมชมเป็นลำดับสุดท้าย

เรียนรู้เพิ่มเติม: วิธีสร้างแผนภูมิการตัดสินใจที่สมบูรณ์แบบ

อัลกอริทึมการเรียงลำดับ

อัลกอริทึมการเรียงลำดับแสดงถึงวิธีการจัดเรียงข้อมูลในรูปแบบเฉพาะ การเรียงลำดับช่วยให้แน่ใจว่าการค้นหาข้อมูลได้รับการปรับให้เหมาะสมในระดับสูง และนำเสนอข้อมูลในรูปแบบที่อ่านได้ ให้เราดูอัลกอริธึมการเรียงลำดับห้าประเภทใน Python:

• Bubble Sort – อัลกอริธึมนี้อิงจากการเปรียบเทียบซึ่งมีการสลับองค์ประกอบที่อยู่ติดกันซ้ำๆ หากเรียงตามลำดับที่ไม่ถูกต้อง
• Merge Sort – ขึ้นอยู่กับอัลกอริธึมการแบ่งและพิชิต Merge sort แบ่ง Array ออกเป็นสองส่วน เรียงลำดับ แล้วรวมเข้าด้วยกัน
• การเรียงลำดับการแทรก – การเรียงลำดับนี้เริ่มต้นด้วยการเปรียบเทียบและการเรียงลำดับองค์ประกอบสองรายการแรก จากนั้นองค์ประกอบที่สามจะถูกเปรียบเทียบกับองค์ประกอบที่จัดเรียงไว้ก่อนหน้านี้สององค์ประกอบเป็นต้น
• การ เรียงลำดับเชลล์ - เป็นรูปแบบของการเรียงลำดับการแทรก แต่ที่นี่ มีการจัดเรียงองค์ประกอบที่อยู่ห่างไกลออกไป รายการย่อยขนาดใหญ่ของรายการที่กำหนดจะถูกจัดเรียง และขนาดของรายการจะลดลงเรื่อยๆ จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง
• การเรียงลำดับการเลือก – อัลกอริธึมนี้เริ่มต้นด้วยการค้นหาค่าต่ำสุดจากรายการองค์ประกอบและใส่ลงในรายการที่เรียงลำดับ จากนั้น กระบวนการจะทำซ้ำสำหรับองค์ประกอบที่เหลือแต่ละรายการในรายการที่ไม่ได้จัดเรียง องค์ประกอบใหม่ที่เข้าสู่รายการที่จัดเรียงจะถูกเปรียบเทียบกับองค์ประกอบที่มีอยู่และวางไว้ในตำแหน่งที่ถูกต้อง กระบวนการจะดำเนินต่อไปจนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง

อัลกอริทึมการค้นหา

อัลกอริทึมการค้นหาช่วยในการตรวจสอบและดึงองค์ประกอบจากโครงสร้างข้อมูลต่างๆ อัลกอริธึมการค้นหาประเภทหนึ่งใช้วิธีการค้นหาตามลำดับโดยที่รายการถูกสำรวจตามลำดับ และทุกองค์ประกอบจะถูกตรวจสอบ (การค้นหาเชิงเส้น) ในอีกประเภทหนึ่ง การค้นหาตามช่วงเวลา องค์ประกอบจะถูกค้นหาในโครงสร้างข้อมูลที่เรียงลำดับ (การค้นหาแบบไบนารี) ให้เราดูตัวอย่างบางส่วน:

• การค้นหาเชิงเส้น – ในอัลกอริธึมนี้ แต่ละรายการจะถูกค้นหาตามลำดับทีละรายการ
• Binary Search – ช่วงเวลาการค้นหาถูกแบ่งครึ่งซ้ำๆ หากองค์ประกอบที่จะค้นหาอยู่ต่ำกว่าองค์ประกอบตรงกลางของช่วงเวลา ช่วงเวลานั้นจะถูกจำกัดให้เหลือเพียงครึ่งล่าง มิฉะนั้นจะแคบลงถึงครึ่งบน กระบวนการนี้ทำซ้ำจนกว่าจะพบค่า

อัลกอริธึมกราฟ

มีสองวิธีในการสำรวจกราฟโดยใช้ขอบ เหล่านี้คือ:

• Depth-first Traversal (DFS) – ในอัลกอริธึมนี้ กราฟจะเคลื่อนที่ในเชิงลึก เมื่อการวนซ้ำใด ๆ พบกับทางตัน สแต็กจะถูกใช้เพื่อไปยังจุดสุดยอดถัดไปและเริ่มการค้นหา DFS ถูกนำมาใช้ใน Python โดยใช้ประเภทข้อมูลที่ตั้งไว้
• Breadth-first Traversal (BFS) – ในอัลกอริธึมนี้ กราฟจะเคลื่อนที่ในแนวกว้าง เมื่อการวนซ้ำใดๆ พบกับทางตัน คิวจะใช้เพื่อไปยังจุดยอดถัดไปและเริ่มการค้นหา BFS ถูกนำมาใช้ใน Python โดยใช้โครงสร้างข้อมูลคิว

การวิเคราะห์อัลกอริทึม

• A Priori Analysis – แสดงถึงการวิเคราะห์เชิงทฤษฎีของอัลกอริทึมก่อนนำไปปฏิบัติ ประสิทธิภาพของอัลกอริธึมถูกวัดโดยสันนิษฐานว่าปัจจัยต่างๆ เช่น ความเร็วของโปรเซสเซอร์ คงที่และไม่มีผลใดๆ ต่ออัลกอริธึม
• การวิเคราะห์ภายหลัง – หมายถึงการวิเคราะห์เชิงประจักษ์ของอัลกอริทึมหลังการใช้งาน ภาษาโปรแกรมใช้ในการปรับใช้อัลกอริธึมที่เลือก ตามด้วยการใช้งานบนคอมพิวเตอร์ การวิเคราะห์นี้รวบรวมสถิติ เช่น เวลาและพื้นที่ที่จำเป็นสำหรับอัลกอริทึมในการทำงาน

บทสรุป

ไม่ว่าคุณจะเป็นผู้เชี่ยวชาญในการเขียนโปรแกรมหรือเพิ่งเริ่มใช้งาน คุณก็ไม่สามารถละเลย โครงสร้างข้อมูลและอัลกอริธึมใน Python ได้ แนวคิดเหล่านี้มีความสำคัญเมื่อคุณดำเนินการกับข้อมูล และคุณจำเป็นต้องปรับการประมวลผลข้อมูลให้เหมาะสม แม้ว่าโครงสร้างข้อมูลจะช่วยในการจัดระเบียบข้อมูล แต่อัลกอริธึมก็มีแนวทางในการแก้ปัญหาการวิเคราะห์ข้อมูล ทั้งสองวิธีนี้ช่วยให้นักวิทยาศาสตร์คอมพิวเตอร์สามารถประมวลผลข้อมูลที่กำหนดให้เป็นข้อมูลป้อนเข้าได้

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ลองดูโปรแกรม Executive PG ของ IIIT-B & upGrad ใน Data Science ซึ่งสร้างขึ้นสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1 -on-1 พร้อมที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ