รายการจัดตัวเอง

รายการจัดตัวเอง () เป็นรายการที่มีการจัดการลำดับความสำคัญขององค์ประกอบภายในรายการด้วยตัวเอง โดยที่อิงจากการวิเคราะห์พฤติกรรมในการจัดตัวเองเพื่อปรับปรุงเวลาในการเข้าถึงข้อมูลโดยเฉลี่ย

ซี่งมีจุดมุ่งหมาย ของรายการจัดตัวเอง คือ ปรับปรุงประสิทธิภาพของการค้นหาเชิงเส้นด้วยการย้ายรายการที่เข้าถึงบ่อยไปอยู่ที่บริเวณหัวของรายการ

 การวิเคราะห์เวลาทำงานสำหรับการเข้าถึง 

 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

หมวดหมู่:รายการโยง