วีลิสต์

วีลิสต์ (อังกฤษ: Vlist) เป็นโครงสร้างข้อมูลในทางวิทยาการคอมพิวเตอร์ ออกแบบโดย ฟิล แบคเวลล์ (Phil Bagwell) ซึ่งวีลิซท์เกิดจากการดัดแปลงรายการโยง (linked list) แบบโยงทางเดียว (singly-linked) โดยการนำความสามารถของแถวลำดับ (array) มาใช้ เพื่อให้การเข้าสู่ข้อมูลที่ตำแหน่งใดๆ ในเวลา O(log n)ในขนาดที่การเพิ่มหรือลดข้อมูลที่ตำแหน่งหน้าสุด (ตำแหน่งสุดท้ายในรายการ) ใช้เวลา O(1)

วีลิสต์มีประโยชน์อย่างมากในการเขียนโปรแกรมเชิงฟังก์ชัน (functional programming languages) และนำไปใช้ในการสร้างโครงสร้างข้อมูลแบบ persistent data structure

หลักการ

แทนที่จะโยงต่อกันด้วยโหนดตัวเดียวแบบในรายการแบบโยง วีลิสต์ใช้การโยงของก้อนข้อมูล (memory block) ซึ่งประกอบด้วยอาเรย์ซึ่งสามารถเก็บข้อมูลได้หลายตัวมาโยงต่อกัน โดยมีฐาน (base) เป็นตัวชี้ (pointer) ไปยังก้อนข้อมูลก่อนหน้า และมีออฟเซ็ต (offset) เป็นตัวอ้างอิงตำแหน่งปัจจุบันของข้อมูลที่เทียบจากรายการ และตำแหน่งล่าสุด (last used) ซึ่งเทียบตำแหน่งของข้อมูลจากอาเรย์ปัจจุบันที่ข้อมูลตัวนั้นอยู่ นอกจากนี้ในก้อนข้อมูลยังมีตัวแปรเก็บขนาดสูงสุดของอาเรย์ปัจจุบัน และทุกๆครั้งที่ข้อมูลเต็มก้อนข้อมูลอันเก่า เมื่อเพิ่มก้อนข้อมูลใหม่ ก้อนข้อมูลใหม่จะมีขนาดเป็น r เท่าของก้อนข้อมูลเดิม และก้อนข้อมูลก่อนๆจะมีขนาดลดลงเป็น r เท่า

การเพิ่มข้อมูล

ในการเพิ่มข้อมูลเข้าที่ตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งสุดท้ายของรายการ) จะต้องตรวจสอบว่าอาเรย์ของข้อมูลในก้อนข้อมูล (memory block) ปัจจุบันนั้นเต็มรึยัง ถ้าไม่เต็มก็เพิ่มข้อมูลลงในตำแหน่งถัดไป และเพิ่มค่าของตำแหน่งล่าสุด (last used) ในก้อนข้อมูลปัจจุบัน ถ้าอาเรย์ของข้อมูลเต็มแล้วต้องทำการสร้างก้อนข้อมูลตัวใหม่ที่มีอาเรย์เป็นขนาด r เท่าของก้อนข้อมูลตัวเดิม แทรกเข้าไปที่ตำแหน่งหน้าของก้อนข้อมูลตัวก่อน (ตำแหน่งท้ายสุดของรายการ) และให้ออฟเซ็ต (offset)ของก้อนข้อมูลตัวล่าสุดเก็บตำแหน่งสุดท้ายของรายการจากก้อนข้อมูลอันก่อน

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

การลบข้อมูล

ในการลบข้อมูลจากตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งท้ายสุดของรายการ) ทำได้โดยลบตำแหน่งล่าสุด (last used) ที่อ้างอิงอาเรย์ของข้อมูลลงหนึ่งค่า ซึ่งการลบข้อมูลด้วยวิธีนี้จะไม่คืนหน่วยความจำที่จองไว้ แต่เมื่อมีการเพิ่มข้อมูลตัวใหม่จะเขียนทับตำแหน่งเดิม เมื่อตำแหน่งอ้างอิงของอาเรย์ข้อมูลในก้อนข้อมูลปัจจุบันมีค่าติดลบ การให้ตัวชี้ชี้ไปยังก้อนข้อมูล (memory block) ถัดไป ก้อนข้อมูลที่ถูกลบนั้นจะถูกเก็บกวาดด้วยตัวเก็บขยะ (Garbage Collection)

ในการลบข้อมูลที่ตำแหน่งใดๆที่ไม่ใช่ตำแหน่งหน้าสุดต้องมีการสร้างวีลิสต์ตัวใหม่ให้ชี้ไปยังข้อมูลตำแหน่งก่อนหน้าข้อมูลที่จะทำการลบ แล้วเพิ่มข้อมูลจากวีลิสต์ตัวเก่าโดยไม่เพิ่มข้อมูลจากตำแหน่งที่ต้องการลบ

การเข้าสู่ตำแหน่งใดๆ

การเข้าสู่ตำแหน่งที่ n ใดๆของวีลิสต์ จะเริ่มด้วยการนำ n ลบกับออฟเซ็ต (offset) ของก้อนข้อมูลปัจจุบันถ้าเป็นบวก แสดงว่าตำแหน่งนั้นอยู่ที่ตำแหน่งของอาเรย์ตำแหน่งที่ n - offset ถ้า n ลบกับออฟเซ็ตเป็นลบ แสดงว่าตำแหน่งนั้นอยู่ในอาเรย์ข้อมูลของก้อนข้อมูล (memory block) ถัดๆไป ซึ่งเราสามารถหาได้โดยลบกับออฟเซ็ตของก้อนข้อมูลถัดไปๆ เรื่อยๆ จนลบแล้วได้ค่าของ n ลบกับออฟเซ็ตแล้วเป็นบวก ตำแหน่งนั้นคือตำแหน่งของอาเรย์ที่ n - offset ของก้อนข้อมูลตัวนั้น

ประสิทธิภาพในการทำงาน

• เนื้อที่ในการเก็บตัวชี้จะใช้เนื้อที่ O(log n) เพราะการโยงข้อมูลของแต่ละก้อนข้อมูลใช้ตัวชี้เพียงตัวเดียว และข้อมูลได้อยู่เป็นกลุ่มในแต่ละก้อนข้อมูลลดลงกันไปก้อนละ r เท่า
• การเพิ่มข้อมูลข้างหน้าของวีลิสต์ใช้เวลา O(1)
• การลบข้อมูลที่อยู่ข้างหน้าของวีลิสต์ใช้เวลา O(1)
• การนับจำนวนข้อมูลในวีลิสต์ใช้เวลา O(log n)
• การเข้าสู่ตำแหน่งใดๆของวีลิสต์ใช้เวลาเฉลี่ย O(1) ในกรณีที่ช้าที่สุดใช้เวลา O(log n)

เนื่องจาก 50% ของข้อมูลทั้งหมดอยู่ที่ก้อนข้อมูลอันแรกแล้ว 75% อยู่ในก้อนข้อมูลอันแรกและอันที่สองรวมกัน ซึ่งในกรณีที่ช้าที่สุดคือตำแหน่งที่ต้องการอยู่ในก้อนข้อมูลอันสุดท้าย ต้องผ่านก้อนข้อมูลไปจำนวน n/2^i เมื่อค่า r คือ 2 นั้นก็คือ log n เมื่อคิดในกรณีเฉลี่ย การเข้าสู่ตำแหน่งใดๆ จะได้ตามสมการนี้ $\sum _{i=1}^{\lceil log_{2}n\rceil }{\frac {i-1}{2^{i}}}<\sum _{i=1}^{\infty }{\frac {i-1}{2^{i}}}=1.$ นั้นคือ O(1)

ตัวอย่างการเขียน

รหัส(code) เขียนด้วยภาษาจาวา (Java) ซึ่งได้ดัดแปลงให้การนับจำนวนข้อมูลใช้เวลา O(1) และเพิ่มเมธ็อด (method) เพิ่มเติมเข้าไป

public class Vlist {
	private static class Block {
		Object[] element;
		Block base;
		int size;
		int lastUsed;
		int offSet;

		public Block(int size, Block base) {
			this.size = size;
			this.base = base;
			if (base == null)
				this.offSet = 0;
			else
				this.offSet = base.offSet + base.size;
			this.lastUsed = 0;
			element = new Object[size];
		}
	}

	Block header;
	final int r = 2;

	public Vlist() {
		header = new Block(0, null);
		header.base = new Block(2, null);
	}

	public void add(Object e) {
		if (header.base.element[header.base.lastUsed] != null
				&& header.base.lastUsed + 1 == header.base.size) {
			header.base = new Block(header.base.size * 2, header.base);
		}
		if (header.base.element[header.base.lastUsed] == null) {
			header.base.element[header.base.lastUsed] = e;
			return;
		}
		header.base.element[++header.base.lastUsed] = e;
	}

	public int size() {
		return header.base.offSet + header.base.lastUsed + 1;
	}

	public Object get(int index) {
		Block current = header.base;
		while (index - current.offSet < 0) {
			current = current.base;
		}
		return current.element[index - current.offSet];
	}

	public void removeLast() {
		if (header.base == null)
			return;
		header.base.lastUsed--;
		if (header.base.lastUsed < 0) {
			header.base = header.base.base;
		}
	}

	public void set(int index, Object e) {
		Block current = header.base;
		while (index - current.offSet < 0) {
			current = current.base;
		}
		current.element[index - current.offSet] = e;
	}

	public int indexOf(Object e) {
		Block current = header.base;
		int index = size() - 1;
		while (current != null) {
			if (current.element[index - current.offSet].equals(e))
				return index;
			index--;
			if (index < current.offSet)
				current = current.base;
		}
		return -1;
	}
}

การนำไปใช้เพื่อสร้างโครงสร้างข้อมูลแบบอื่น

วีลิสต์สามารถนำไปเพื่อสร้าง

• ตารางแฮช (Hash Table) โดยการแบ่งก้อนข้อมูลในมีส่วนของข้อมูลและส่วนของตารางแฮช โดยส่วนที่เป็นข้อมูลจะมีการโยงถึงตำแหน่งและข้อมูลก่อนหน้า เช่นเดียวกับส่วนที่เป็นตารางแฮชก็จะมีการโยงกับตารางแฮชก่อนหน้า ด้วยประสิทธิภาพของตารางแฮชทำให้การหาข้อมูลทำได้โดยเวลาคงที่
• แถวลำดับพลวัต (dynamic array)
• แถวคอยสองหน้า (Double-ended queue)

แหล่งข้อมูลอื่น

• การเขียนวีลิสต์ด้วยภาษาซีพลัสพลัส เก็บถาวร 2010-09-07 ที่ เวย์แบ็กแมชชีน
• การเขียนวีลิสต์ด้วยภาษาซีชาร์ป
• ลิงก์รายงานการทดลองของฟิล แบคแวลล์