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

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

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

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

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

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

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

# Move to front Method (MTF)
# Count Method (Frequency counter)
# Transpose Method

### Move to front Method (MTF)

#### หลักการทำงาน
  ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นไปไว้ต้นรายการเสมอ
thumb|430x430px|ขั้นตอนวิธีจัดโหนดภายในรายการแบบ MTF

#### ข้อดี
  สามารถปรับรูปแบบการเข้าถึงข้อมูลได้อย่างรวดเร็ว

#### ข้อเสีย
  จะจัดลำดับความสำคัญของข้อมูลนั้นได้ยาก

#### ตัวอย่างโค้ดในภาษา Python

```python3
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)

#### หลักการทำงาน
  ข้อมูลแต่ละตำแหน่งจะมีการเก็บค่าจำนวนครั่งในการเข้าถึงข้อมูลนั้นจากนั้นจะมีการเรียงลำดับข้อมูลใหม่ตามความถี่ที่เข้าถึงข้อมูล ซึ่งวิธีการนี้ต้องใช้พื้นที่เพิ่มเติมในการจัดเก็บข้อมูล
thumb|430x430px|ขั้นตอนวิธีจัดโหนดภายในรายการแบบ Count Method (frequency counter)

#### ข้อดี
  ท้อนให้เห็นถึงรูปแบบการเข้าถึงข้อมูลที่แท้จริงให้สมจริงมากขึ้น

#### ข้อเสีย
  ต้องมีพื้นที่เพิ่มในการเก็บจำนวนที่นับ และปรับตัวให้เข้ากับการเปลี่ยนแปลงอย่างรวดเร็วได้ค่อนข้างยาก

#### ตัวอย่างโค้ดในภาษา Python

```python3
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

#### หลักการทำงาน
  ไม่ว่าจะทำการเข้าถึงข้อมูลที่ตำแหน่งใดใด ก็จะทำการย้ายข้อมูลนั้นปางหน้าเสมอ
thumb|430x430px|ขั้นตอนวิธีจัดโหนดภายในรายการแบบ Transpose Method

#### ข้อดี
  ใช้งานง่ายและใช้หน่วยความจำน้อย

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

#### ตัวอย่างโค้ดในภาษา Python

```python3
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) เหมือนกัน

## อ้างอิง

# Self Organization  (pdf), 2004

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