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

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

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

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

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

รายการโยง