Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
บทความนี้ไม่มีจาก |
วีลิสต์ (อังกฤษ: Vlist) เป็นโครงสร้างข้อมูลในทางวิทยาการคอมพิวเตอร์ ออกแบบโดย ฟิล แบคเวลล์ (Phil Bagwell) ซึ่งวีลิซท์เกิดจากการดัดแปลงรายการโยง (linked list) แบบโยงทางเดียว (singly-linked) โดยการนำความสามารถของแถวลำดับ (array) มาใช้ เพื่อให้การเข้าสู่ข้อมูลที่ตำแหน่งใดๆ ในเวลา O(log n)ในขนาดที่การเพิ่มหรือลดข้อมูลที่ตำแหน่งหน้าสุด (ตำแหน่งสุดท้ายในรายการ) ใช้เวลา O(1)
วีลิสต์มีประโยชน์อย่างมากในการเขียน (functional programming languages) และนำไปใช้ในการสร้างโครงสร้างข้อมูลแบบ
หลักการ
แทนที่จะโยงต่อกันด้วยโหนดตัวเดียวแบบในรายการแบบโยง วีลิสต์ใช้การโยงของก้อนข้อมูล (memory block) ซึ่งประกอบด้วยอาเรย์ซึ่งสามารถเก็บข้อมูลได้หลายตัวมาโยงต่อกัน โดยมีฐาน (base) เป็นตัวชี้ (pointer) ไปยังก้อนข้อมูลก่อนหน้า และมีออฟเซ็ต (offset) เป็นตัวอ้างอิงตำแหน่งปัจจุบันของข้อมูลที่เทียบจากรายการ และตำแหน่งล่าสุด (last used) ซึ่งเทียบตำแหน่งของข้อมูลจากอาเรย์ปัจจุบันที่ข้อมูลตัวนั้นอยู่ นอกจากนี้ในก้อนข้อมูลยังมีตัวแปรเก็บขนาดสูงสุดของอาเรย์ปัจจุบัน และทุกๆครั้งที่ข้อมูลเต็มก้อนข้อมูลอันเก่า เมื่อเพิ่มก้อนข้อมูลใหม่ ก้อนข้อมูลใหม่จะมีขนาดเป็น r เท่าของก้อนข้อมูลเดิม และก้อนข้อมูลก่อนๆจะมีขนาดลดลงเป็น r เท่า
การเพิ่มข้อมูล
ในการเพิ่มข้อมูลเข้าที่ตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งสุดท้ายของรายการ) จะต้องตรวจสอบว่าอาเรย์ของข้อมูลในก้อนข้อมูล (memory block) ปัจจุบันนั้นเต็มรึยัง ถ้าไม่เต็มก็เพิ่มข้อมูลลงในตำแหน่งถัดไป และเพิ่มค่าของตำแหน่งล่าสุด (last used) ในก้อนข้อมูลปัจจุบัน ถ้าอาเรย์ของข้อมูลเต็มแล้วต้องทำการสร้างก้อนข้อมูลตัวใหม่ที่มีอาเรย์เป็นขนาด r เท่าของก้อนข้อมูลตัวเดิม แทรกเข้าไปที่ตำแหน่งหน้าของก้อนข้อมูลตัวก่อน (ตำแหน่งท้ายสุดของรายการ) และให้ออฟเซ็ต (offset)ของก้อนข้อมูลตัวล่าสุดเก็บตำแหน่งสุดท้ายของรายการจากก้อนข้อมูลอันก่อน
การเพิ่มข้อมูลเข้าไปสู่ตำแหน่งอื่นที่ไม่ใช่ตำแหน่งหน้าสุดของวีลิสต์ จำเป็นต้องทำการสร้างวีลิสต์ตัวใหม่ที่ชี้ไปยังตำแหน่งที่ต้องการจะเพิ่มข้อมูล เมื่อเพิ่มข้อมูลต้องเพิ่มข้อมูลที่เหลือจากวีลิสต์อันเก่าเข้าไป
การลบข้อมูล
ในการลบข้อมูลจากตำแหน่งหน้าสุดของวีลิสต์ (ตำแหน่งท้ายสุดของรายการ) ทำได้โดยลบตำแหน่งล่าสุด (last used) ที่อ้างอิงอาเรย์ของข้อมูลลงหนึ่งค่า ซึ่งการลบข้อมูลด้วยวิธีนี้จะไม่คืนหน่วยความจำที่จองไว้ แต่เมื่อมีการเพิ่มข้อมูลตัวใหม่จะเขียนทับตำแหน่งเดิม เมื่อตำแหน่งอ้างอิงของอาเรย์ข้อมูลในก้อนข้อมูลปัจจุบันมีค่าติดลบ การให้ตัวชี้ชี้ไปยังก้อนข้อมูล (memory block) ถัดไป ก้อนข้อมูลที่ถูกลบนั้นจะถูกเก็บกวาดด้วยตัวเก็บขยะ ()
ในการลบข้อมูลที่ตำแหน่งใดๆที่ไม่ใช่ตำแหน่งหน้าสุดต้องมีการสร้างวีลิสต์ตัวใหม่ให้ชี้ไปยังข้อมูลตำแหน่งก่อนหน้าข้อมูลที่จะทำการลบ แล้วเพิ่มข้อมูลจากวีลิสต์ตัวเก่าโดยไม่เพิ่มข้อมูลจากตำแหน่งที่ต้องการลบ
การเข้าสู่ตำแหน่งใดๆ
การเข้าสู่ตำแหน่งที่ 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 เมื่อคิดในกรณีเฉลี่ย การเข้าสู่ตำแหน่งใดๆ จะได้ตามสมการนี้ 
นั้นคือ 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 ที่ เวย์แบ็กแมชชีน
- การเขียนวีลิสต์ด้วยภาษาซีชาร์ป
- ลิงก์รายงานการทดลองของฟิล แบคแวลล์
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamnixactxngkartrwcsxbtnchbb indaniwyakrn rupaebbkarekhiyn kareriyberiyng khunphaph hruxkarsakd khunsamarthchwyphthnabthkhwamidbthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir wilist xngkvs Vlist epnokhrngsrangkhxmulinthangwithyakarkhxmphiwetxr xxkaebbody fil aebkhewll Phil Bagwell sungwilisthekidcakkarddaeplngraykaroyng linked list aebboyngthangediyw singly linked odykarnakhwamsamarthkhxngaethwladb array maich ephuxihkarekhasukhxmulthitaaehnngid inewla O log n inkhnadthikarephimhruxldkhxmulthitaaehnnghnasud taaehnngsudthayinraykar ichewla O 1 wilistmipraoychnxyangmakinkarekhiyn functional programming languages aelanaipichinkarsrangokhrngsrangkhxmulaebbhlkkaraethnthicaoyngtxkndwyohndtwediywaebbinraykaraebboyng wilistichkaroyngkhxngkxnkhxmul memory block sungprakxbdwyxaerysungsamarthekbkhxmulidhlaytwmaoyngtxkn odymithan base epntwchi pointer ipyngkxnkhxmulkxnhna aelamixxfest offset epntwxangxingtaaehnngpccubnkhxngkhxmulthiethiybcakraykar aelataaehnnglasud last used sungethiybtaaehnngkhxngkhxmulcakxaerypccubnthikhxmultwnnxyu nxkcakniinkxnkhxmulyngmitwaeprekbkhnadsungsudkhxngxaerypccubn aelathukkhrngthikhxmuletmkxnkhxmulxneka emuxephimkxnkhxmulihm kxnkhxmulihmcamikhnadepn r ethakhxngkxnkhxmuledim aelakxnkhxmulkxncamikhnadldlngepn r etha karephimkhxmul inkarephimkhxmulekhathitaaehnnghnasudkhxngwilist taaehnngsudthaykhxngraykar catxngtrwcsxbwaxaerykhxngkhxmulinkxnkhxmul memory block pccubnnnetmruyng thaimetmkephimkhxmullngintaaehnngthdip aelaephimkhakhxngtaaehnnglasud last used inkxnkhxmulpccubn thaxaerykhxngkhxmuletmaelwtxngthakarsrangkxnkhxmultwihmthimixaeryepnkhnad r ethakhxngkxnkhxmultwedim aethrkekhaipthitaaehnnghnakhxngkxnkhxmultwkxn taaehnngthaysudkhxngraykar aelaihxxfest offset khxngkxnkhxmultwlasudekbtaaehnngsudthaykhxngraykarcakkxnkhxmulxnkxn karephimkhxmulekhaipsutaaehnngxunthiimichtaaehnnghnasudkhxngwilist caepntxngthakarsrangwilisttwihmthichiipyngtaaehnngthitxngkarcaephimkhxmul emuxephimkhxmultxngephimkhxmulthiehluxcakwilistxnekaekhaip karlbkhxmul inkarlbkhxmulcaktaaehnnghnasudkhxngwilist taaehnngthaysudkhxngraykar thaidodylbtaaehnnglasud last used thixangxingxaerykhxngkhxmullnghnungkha sungkarlbkhxmuldwywithinicaimkhunhnwykhwamcathicxngiw aetemuxmikarephimkhxmultwihmcaekhiynthbtaaehnngedim emuxtaaehnngxangxingkhxngxaerykhxmulinkxnkhxmulpccubnmikhatidlb karihtwchichiipyngkxnkhxmul memory block thdip kxnkhxmulthithuklbnncathukekbkwaddwytwekbkhya inkarlbkhxmulthitaaehnngidthiimichtaaehnnghnasudtxngmikarsrangwilisttwihmihchiipyngkhxmultaaehnngkxnhnakhxmulthicathakarlb aelwephimkhxmulcakwilisttwekaodyimephimkhxmulcaktaaehnngthitxngkarlb karekhasutaaehnngid karekhasutaaehnngthi n idkhxngwilist caerimdwykarna n lbkbxxfest offset khxngkxnkhxmulpccubnthaepnbwk aesdngwataaehnngnnxyuthitaaehnngkhxngxaerytaaehnngthi n offset tha n lbkbxxfestepnlb aesdngwataaehnngnnxyuinxaerykhxmulkhxngkxnkhxmul memory block thdip sungerasamarthhaidodylbkbxxfestkhxngkxnkhxmulthdip eruxy cnlbaelwidkhakhxng n lbkbxxfestaelwepnbwk taaehnngnnkhuxtaaehnngkhxngxaerythi n offset khxngkxnkhxmultwnnprasiththiphaphinkarthanganenuxthiinkarekbtwchicaichenuxthi O log n ephraakaroyngkhxmulkhxngaetlakxnkhxmulichtwchiephiyngtwediyw aelakhxmulidxyuepnkluminaetlakxnkhxmulldlngknipkxnla r etha karephimkhxmulkhanghnakhxngwilistichewla O 1 karlbkhxmulthixyukhanghnakhxngwilistichewla O 1 karnbcanwnkhxmulinwilistichewla O log n karekhasutaaehnngidkhxngwilistichewlaechliy O 1 inkrnithichathisudichewla O log n enuxngcak 50 khxngkhxmulthnghmdxyuthikxnkhxmulxnaerkaelw 75 xyuinkxnkhxmulxnaerkaelaxnthisxngrwmkn sunginkrnithichathisudkhuxtaaehnngthitxngkarxyuinkxnkhxmulxnsudthay txngphankxnkhxmulipcanwn n 2 i emuxkha r khux 2 nnkkhux log n emuxkhidinkrniechliy karekhasutaaehnngid caidtamsmkarni i 1 log2n i 12i lt i 1 i 12i 1 displaystyle sum i 1 lceil log 2 n rceil frac i 1 2 i lt sum i 1 infty frac i 1 2 i 1 nnkhux O 1 twxyangkarekhiynrhs code ekhiyndwyphasacawa Java sungidddaeplngihkarnbcanwnkhxmulichewla O 1 aelaephimemthxd method ephimetimekhaip 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 amp amp 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 lt 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 lt 0 header base header base base public void set int index Object e Block current header base while index current offSet lt 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 lt current offSet current current base return 1 karnaipichephuxsrangokhrngsrangkhxmulaebbxunwilistsamarthnaipephuxsrang tarangaehch Hash Table odykaraebngkxnkhxmulinmiswnkhxngkhxmulaelaswnkhxngtarangaehch odyswnthiepnkhxmulcamikaroyngthungtaaehnngaelakhxmulkxnhna echnediywkbswnthiepntarangaehchkcamikaroyngkbtarangaehchkxnhna dwyprasiththiphaphkhxngtarangaehchthaihkarhakhxmulthaidodyewlakhngthi aethwladbphlwt dynamic array aethwkhxysxnghna Double ended queue xangxinghttp citeseer ist psu edu bagwell02fast htmlaehlngkhxmulxunkarekhiynwilistdwyphasasiphlsphls 2010 09 07 thi ewyaebkaemchchin karekhiynwilistdwyphasasicharp lingkrayngankarthdlxngkhxngfil aebkhaewll