รายการจัดตัวเอง
มีการแนะนำว่า บทความนี้ทั้งหมดหรือบางส่วนควรย้ายไปโครงการวิกิตำรา (อภิปราย) เนื่องจากการจัดรูปแบบเนื้อหาไม่ตรงตามนโยบายของวิกิพีเดียที่เป็นสารานุกรม และอาจเข้ากับโครงการวิกิตำรามากกว่า |
รายการจัดตัวเอง (อังกฤษ: self-organizing list) เป็นรายการที่มีการจัดการลำดับความสำคัญขององค์ประกอบภายในรายการด้วยตัวเอง โดยที่อิงจากการวิเคราะห์พฤติกรรมในการจัดตัวเองเพื่อปรับปรุงเวลาในการเข้าถึงข้อมูลโดยเฉลี่ย
ซี่งมีจุดมุ่งหมาย ของรายการจัดตัวเอง คือ ปรับปรุงประสิทธิภาพของการค้นหาเชิงเส้นด้วยการย้ายรายการที่เข้าถึงบ่อยไปอยู่ที่บริเวณหัวของรายการ
การวิเคราะห์เวลาทำงานสำหรับการเข้าถึง
Best case
กรณีที่ข้อมูลหรือโหนดที่ต้องการเข้าถึงนั้นเป็นส่วนหัวของข้อมูล ซึ้งจะทำให้มีความซับซ้อนเป็น
Worst case
กรณีที่ข้อมูลหรือโหนดที่ต้องการเข้าถึงนั้นเป็นส่วนท้ายของข้อมูล หรือไม่มีอยู่ในรายการ ซึ้งจะทำให้มีความซับซ้อนที่มีการทำงานแบบเชิงเส้นเป็น
ตัวอย่างขั้นตอนวิธี (Algorithm)
- Move to front Method (MTF)
- Count Method (Frequency counter)
- Transpose Method
Move to front Method (MTF)
หลักการทำงาน
ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นไปไว้ต้นรายการเสมอ
ข้อดี
สามารถปรับรูปแบบการเข้าถึงข้อมูลได้อย่างรวดเร็ว
ข้อเสีย
จะจัดลำดับความสำคัญของข้อมูลนั้นได้ยาก
ตัวอย่างโค้ดในภาษา Python
def move2front(array,selectNode): n = len(array) for i in range(0,n): if (selectNode == array[i]): item = array.pop(i) array.insert(0, item) return array return array
วิเคราะห์ความซับซ้อนของโค้ด
จากโค้ดในบรรทัดที่ 3 และ6 มีความซับซ้อนเป็น จึงทำให้ best case และ worst case โค้ดมีความซับซ้อน เหมือนกัน
Count Method (frequency counter)
หลักการทำงาน
ข้อมูลแต่ละตำแหน่งจะมีการเก็บค่าจำนวนครั่งในการเข้าถึงข้อมูลนั้นจากนั้นจะมีการเรียงลำดับข้อมูลใหม่ตามความถี่ที่เข้าถึงข้อมูล ซึ่งวิธีการนี้ต้องใช้พื้นที่เพิ่มเติมในการจัดเก็บข้อมูล
ข้อดี
ท้อนให้เห็นถึงรูปแบบการเข้าถึงข้อมูลที่แท้จริงให้สมจริงมากขึ้น
ข้อเสีย
ต้องมีพื้นที่เพิ่มในการเก็บจำนวนที่นับ และปรับตัวให้เข้ากับการเปลี่ยนแปลงอย่างรวดเร็วได้ค่อนข้างยาก
ตัวอย่างโค้ดในภาษา Python
def freqCount(array,user,memory): n = len(array) for i in range(0,n): if (array[i] == user ): itemL = array.pop(i) itemC = memory.pop(i) itemC += 1 for p in range(0,n): if (memory[p] <= itemC): array.insert(p, itemL) memory.insert(p, itemC) return [array, memory] return [array, memory]
วิเคราะห์ความซับซ้อนของโค้ด
จากโค้ดในบรรทัดที่ 3 และ8 มีความซับซ้อนเป็น จึงทำให้ best case โค้ดมีความซับซ้อน และ worst case โค้ดมีความซับซ้อน เพราะมี 2-nested loop
Transpose Method
หลักการทำงาน
ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นปางหน้าเสมอ
ข้อดี
ใช้งานง่ายและใช้หน่วยความจำน้อย
ข้อเสีย
ต้องเข้าถึงหลายข้อมูลเพื่อที่จะย้ายเพียงครั้งเดียว และใช้เวลามากเมื่อข้อมูลที่ต้องการมีตำแหน่งอยู่ไกล
ตัวอย่างโค้ดในภาษา Python
def transpose(array,user): n = len(array) for index in range(0, n): if (index == 0 and user == array[index]): return array elif (user == array[index]): temp = array[index-1] array[index-1] = array[index] array[index] = temp return array return array
วิเคราะห์ความซับซ้อนของโค้ด
จากโค้ดในบรรทัดที่ 2 มีความซับซ้อนเป็น จึงทำให้ best case และ worst case โค้ดมีความซับซ้อน เหมือนกัน
อ้างอิง
- Self Organization (pdf), 2004