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

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

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

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

Best case

กรณีที่ข้อมูลหรือโหนดที่ต้องการเข้าถึงนั้นเป็นส่วนหัวของข้อมูล ซึ้งจะทำให้มีความซับซ้อนเป็น $O(1)$

Worst case

กรณีที่ข้อมูลหรือโหนดที่ต้องการเข้าถึงนั้นเป็นส่วนท้ายของข้อมูล หรือไม่มีอยู่ในรายการ ซึ้งจะทำให้มีความซับซ้อนที่มีการทำงานแบบเชิงเส้นเป็น $O(n)$

ตัวอย่างขั้นตอนวิธี (Algorithm)

1. Move to front Method (MTF)
2. Count Method (Frequency counter)
3. Transpose Method

Move to front Method (MTF)

หลักการทำงาน

  ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นไปไว้ต้นรายการเสมอ

ขั้นตอนวิธีจัดโหนดภายในรายการแบบ 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 มีความซับซ้อนเป็น $O(n)$ จึงทำให้ best case และ worst case โค้ดมีความซับซ้อน $O(n)$ เหมือนกัน

Count Method (frequency counter)

หลักการทำงาน

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

ขั้นตอนวิธีจัดโหนดภายในรายการแบบ 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 มีความซับซ้อนเป็น $O(n)$ จึงทำให้ best case โค้ดมีความซับซ้อน $O(n)$ และ worst case โค้ดมีความซับซ้อน $O(n^{2})$เพราะมี 2-nested loop

Transpose Method

หลักการทำงาน

  ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นปางหน้าเสมอ

ขั้นตอนวิธีจัดโหนดภายในรายการแบบ 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 มีความซับซ้อนเป็น $O(n)$ จึงทำให้ best case และ worst case โค้ดมีความซับซ้อน $O(n)$ เหมือนกัน

อ้างอิง

1. Self Organization เก็บถาวร 2012-04-14 ที่ เวย์แบ็กแมชชีน (pdf), 2004