Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ซิปเปอร์ (อังกฤษ: Zipper) เป็นโครงสร้างข้อมูลชนิดหนึ่งหรืออาจเรียกว่าเป็นวิธีการที่สามารถใช้แสดงข้อมูลที่เราสนใจอยู่พร้อมกับรายการของข้อมูลอื่น ๆ ที่อยู่ภายในโครงสร้างข้อมูลเดียวกัน กล่าวคือ ในการเข้าถึงข้อมูลใด ๆ ภายในโครงสร้างข้อมูลนี้จะต้องระบุทั้งข้อมูลที่เราสนใจและที่อยู่ของข้อมูลซึ่งก็คือรายการของข้อมูลที่อยู่ในวิถีจากข้อมูลนั้นไปยังรากหรือตอนต้นของรายการและจากข้อมูลนั้นไปยังใบหรือปลายสุดของรายการ อีกทั้งเมื่อเราเข้าถึงข้อมูลที่เราสนใจได้แล้วเรายังเปลี่ยนจุดสนใจไปยังข้อมูลที่อยู่รอบ ๆ ข้อมูลที่เราสนใจได้ด้วยหรืออาจใช้คำสั่งอย่างอื่น เช่น เพิ่ม เปลี่ยน หรือลบข้อมูล โดยคำสั่งส่วนใหญ่มีประสิทธิภาพการทำงานเป็น O(1) แนวคิดนี้ถูกคิดค้นขึ้นโดย Gérard Huet เมื่อปี 1997 โดยตั้งชื่อตามการทำงานของโครงสร้างข้อมูลนี้ที่เปรียบเสมือนซิปที่เราสามารถรูดขึ้นลงได้
| ซิปเปอร์ | |
|---|---|
| ความสำคัญของลำดับ | ขึ้นอยู่กับว่านำซิปเปอร์ไปประยุกต์ใช้กับโครงสร้างข้อมูลแบบใด |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| เวลาที่ใช้ในการเข้าถึง | ฟังก์ชันที่กำหนดโดยข้อมูลที่สนใจและรายการของข้อมูลอื่น ๆ บนวิถีเดียวกันจากข้อมูลที่สนใจไปยังรากและไปยังใบ |
นอกจากนี้โครงสร้างข้อมูลชนิดนี้มักเขียนเป็นโปรแกรมด้วยการเขียนโปรแกรมเชิงฟังก์ชัน (Functional programming) และแนวคิดของซิปเปอร์สามารถนำไปประยุกต์ใช้กับโครงสร้างข้อมูลได้หลายอย่าง เช่น รายการ (List) และต้นไม้ (Tree)
ลักษณะของซิปเปอร์
จริง ๆ ซิปเปอร์เป็นเพียงเทคนิคที่ใช้สำหรับโครงสร้างข้อมูลที่ต้องการพิจารณาทั้งข้อมูลที่เราสนใจอยู่พร้อมกับข้อมูลอื่น ๆ ดังนั้นโครงสร้างของซิปเปอร์จึงไม่ตายตัว อาจจะนำมาใช้กับรายการหรือต้นไม้แบบใดก็ได้ ถ้าใช้กับต้นไม้ เวลาเข้าถึงข้อมูลที่เราสนใจก็จะต้องระบุทั้งข้อมูลนั้นพร้อมกับรายการของข้อมูลอื่น ๆ ที่อยู่บนวิถีจากข้อมูลนี้ไปยังรากและที่ไปยังใบ (สำหรับวิถีไปยังใบ อาจเรียกได้ว่าเป็นที่มีข้อมูลที่เราสนใจเป็นรากก็ได้)
ตัวอย่างการใช้งานซิปเปอร์ : ต้นไม้แบบทวิภาค
ซิปเปอร์สามารถนำไปประยุกต์ใช้กับโครงสร้างข้อมูลได้หลายอย่าง ในที่นี้จะยกตัวอย่างโดยใช้ซิปเปอร์กับต้นไม้แบบทวิภาคซึ่งจะเป็นการเขียน a*(b^c-d)+(e+f) ออกมาในรูปของต้นไม้ทวิภาคดังรูป
ในที่นี้ กำหนดให้ปมข้อมูล (node) แต่ละปมแทนด้วย
- Node(value,left,right) โดย value คือค่าในปมข้อมูล, left คือปมลูกที่อยู่ทางซ้าย, right คือปมลูกที่อยู่ทางขวา
- null ถ้าบริเวณนั้นไม่มีปมข้อมูลอยู่
กำหนดให้วิถีของแต่ละปม (path) ในต้นไม้นี้แทนด้วย
- L(path,node) เมื่อปมข้อมูลที่เรากำลังพิจารณาเป็นปมลูกซ้าย โดย path เป็นวิถีของปมพ่อ และ node คือปมพ่อ
- R(node,path) เมื่อปมข้อมูลที่เรากำลังพิจารณาเป็นปมลูกขวา โดย path เป็นวิถีของปมพ่อ และ node คือปมพ่อ
- top เมื่อปมข้อมูลนั้นเป็นปมราก
และกำหนดให้ตำแหน่งของปมข้อมูลแทนด้วย
- Pos(node,path) โดย node คือปมข้อมูลที่เราสนใจและ path คือวิถีของปมข้อมูลนี้ถึงปมราก
ดังนั้นต้นไม้ทวิภาคนี้จะสามารถเขียนเป็นฟังก์ชันได้ว่า
Node("+",Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),Node("+",Node("e",null,null),Node("f",null,null))) ดังนั้น เราสามารถที่จะระบุตำแหน่งของเครื่องหมายลบในต้นไม้ทวิภาคนี้ได้เป็น
Pos(Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),R(Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))), L(top,Node("+",Node("*",Node("a",null,null),Node("-",Node("^",Node("b",null,null),Node("c",null,null)),Node("d",null,null))),Node("+",Node("e",null,null),Node("f",null,null))))) เมื่อเราสามารถระบุตำแหน่งข้อมูลที่เราต้องการได้แล้ว เราก็สามารถใช้คำสั่งอื่น ๆ กับข้อมูลที่เราสนใจได้ เช่น เลื่อนตำแหน่งลง (goDown) เลื่อนตำแหน่งขึ้น (goUp) เลื่อนไปทางซ้าย (goLeft) เลื่อนไปทางขวา (goRight) เปลี่ยนค่าในปมข้อมูล (change) เพิ่มข้อมูล (insert) หรือแม้แต่ลบปมข้อมูลนั้น (delete) อย่างถ้าต้องการสั่งให้เลื่อนตำแหน่งลงก็ใช้คำสั่งเป็น goDown(Pos(n,p)) ได้เลย ในเมื่อเราสามารถระบุตำแหน่งปมข้อมูลที่เราต้องการและสั่งได้เช่นนี้แสดงว่าการทำงานของฟังก์ชันเหล่านี้เป็น O(1)
จุดเด่นของซิปเปอร์
จุดเด่นของซิปเปอร์คือเราสามารถแสดงข้อมูลอื่น ๆ ที่อยู่บนวิถีเดียวกันกับข้อมูลที่เราสนใจตามที่ได้กล่าวไว้ในหัวข้อลักษณะของซิปเปอร์ ทำให้แนวคิดนี้ถูกนำไปใช้กับโปรแกรมที่มีการเพ่งความสนใจข้อมูล (focus) รวมถึงสามารถย้ายตำแหน่งของจุดสนใจไปยังข้อมูลรอบ ๆ ได้ด้วย เช่น โปรแกรม Xmonad อีกทั้งประสิทธิภาพในการทำงานของคำสั่งส่วนใหญ่ที่มีประสิทธิภาพในการทำงานเป็น O(1) และจุดเด่นที่สำคัญอีกอย่างหนึ่งโครงสร้างข้อมูลชนิดนี้เขียนโดยใช้การเขียนโปรแกรมเชิงฟังก์ชัน (Functional programming) ซึ่งการเขียนโปรแกรมแบบนี้อาจเป็นเรื่องใหม่สำหรับโปรแกรมเมอร์หลาย ๆ คน
การเขียนโปรแกรมเชิงฟังก์ชัน
การเขียนโปรแกรมเชิงฟังก์ชันเป็นการเขียนโปรแกรมที่ทำงานคล้ายกับฟังก์ชันของคณิตศาสตร์ โดยมีแนวคิดสำคัญว่าให้หลีกเลี่ยงการเกี่ยวข้องกับสถานะของโปรแกรม (state) และหลีกเลี่ยงการเปลี่ยนแปลงข้อมูลต่าง ๆ โดยคำสั่งหนึ่งที่ได้รับพารามิเตอร์เหมือนกันต้องให้คำตอบเดียวกัน อย่างเช่น ในคณิตศาสตร์ ถ้าให้ f(x) = x + 4 และ x = 4 จะได้ f(4) = 8 เสมอ แสดงว่าถ้าสร้างคำสั่ง foo(Object e) ขึ้นมา จะได้ว่าคำสั่ง foo มีการทำงานเหมือนเดิมตราบที่พารามิเตอร์คือ e ยังเป็นค่าเดิม ดังนั้นจะพบว่าการเขียนโปรแกรมแบบนี้จะมีตัวแปรอยู่ในโปรแกรมน้อยเพื่อเป็นการหลีกเลี่ยงการเปลี่ยนแปลงค่าในข้อมูลและสามารถมี (Composite function) อยู่ในส่วนการทำงานของโปรแกรมได้มากมาย
บริการที่มักจะมี
- บริการที่ย้ายจุดที่สนใจไปยังรอบ ๆ ข้อมูลที่สนใจ เช่น ซ้าย ขวา บน และล่าง
- บริการเปลี่ยนค่าของข้อมูลที่จุดที่สนใจ
- บริการแทรกและลบข้อมูลที่จุดที่สนใจ
ความเร็วที่ใช้ในการทำงาน
ความเร็วในการทำงานส่วนใหญ่จะเป็น O(1) ซึ่งเป็นเพราะการเขียนโปรแกรมเชิงฟังก์ชันซึ่งเปรียบเสมือนการใส่ข้อมูลตัวนั้นและที่อยู่ของมันที่อาจเป็นในลักษณะของ (Composite function) เพื่อให้โปรแกรมทำงานตามบริการที่เราต้องการ แต่ทั้งนี้ก็ขึ้นอยู่กับการออกแบบโครงสร้างข้อมูลของโปรแกรมเมอร์แต่ละคนด้วยว่าจะวางโครงสร้างไว้อย่างไร บางคำสั่งจึงไม่จำเป็นต้องมีการทำงานเป็น O(1) เสมอไป
อ้างอิง
- Huet, Gerard. "Functional Pearl: The Zipper" Journal of Functional Programming 7 (5): 549-554, September 1997.
- Zipper (data structure)
- Functional Programming
- "Roll Your Own Window Manager: Tracking Focus with a Zipper"
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisud sipepxr xngkvs Zipper epnokhrngsrangkhxmulchnidhnunghruxxaceriykwaepnwithikarthisamarthichaesdngkhxmulthierasnicxyuphrxmkbraykarkhxngkhxmulxun thixyuphayinokhrngsrangkhxmulediywkn klawkhux inkarekhathungkhxmulid phayinokhrngsrangkhxmulnicatxngrabuthngkhxmulthierasnicaelathixyukhxngkhxmulsungkkhuxraykarkhxngkhxmulthixyuinwithicakkhxmulnnipyngrakhruxtxntnkhxngraykaraelacakkhxmulnnipyngibhruxplaysudkhxngraykar xikthngemuxeraekhathungkhxmulthierasnicidaelwerayngepliyncudsnicipyngkhxmulthixyurxb khxmulthierasniciddwyhruxxacichkhasngxyangxun echn ephim epliyn hruxlbkhxmul odykhasngswnihymiprasiththiphaphkarthanganepn O 1 aenwkhidnithukkhidkhnkhunody Gerard Huet emuxpi 1997 odytngchuxtamkarthangankhxngokhrngsrangkhxmulnithiepriybesmuxnsipthierasamarthrudkhunlngidsipepxrkhwamsakhykhxngladbkhunxyukbwanasipepxripprayuktichkbokhrngsrangkhxmulaebbidkarsaknkhxngsmachikxnuyatihsaknidewlathiichinkarekhathungfngkchnthikahndodykhxmulthisnicaelaraykarkhxngkhxmulxun bnwithiediywkncakkhxmulthisnicipyngrakaelaipyngib nxkcakniokhrngsrangkhxmulchnidnimkekhiynepnopraekrmdwykarekhiynopraekrmechingfngkchn Functional programming aelaaenwkhidkhxngsipepxrsamarthnaipprayuktichkbokhrngsrangkhxmulidhlayxyang echn raykar List aelatnim Tree lksnakhxngsipepxrcring sipepxrepnephiyngethkhnikhthiichsahrbokhrngsrangkhxmulthitxngkarphicarnathngkhxmulthierasnicxyuphrxmkbkhxmulxun dngnnokhrngsrangkhxngsipepxrcungimtaytw xaccanamaichkbraykarhruxtnimaebbidkid thaichkbtnim ewlaekhathungkhxmulthierasnickcatxngrabuthngkhxmulnnphrxmkbraykarkhxngkhxmulxun thixyubnwithicakkhxmulniipyngrakaelathiipyngib sahrbwithiipyngib xaceriykidwaepnthimikhxmulthierasnicepnrakkid twxyangkarichngansipepxr tnimaebbthwiphakhsipepxrsamarthnaipprayuktichkbokhrngsrangkhxmulidhlayxyang inthinicayktwxyangodyichsipepxrkbtnimaebbthwiphakhsungcaepnkarekhiyn a b c d e f xxkmainrupkhxngtnimthwiphakhdngrup inthini kahndihpmkhxmul node aetlapmaethndwy Node value left right ody value khuxkhainpmkhxmul left khuxpmlukthixyuthangsay right khuxpmlukthixyuthangkhwa null thabriewnnnimmipmkhxmulxyu kahndihwithikhxngaetlapm path intnimniaethndwy L path node emuxpmkhxmulthierakalngphicarnaepnpmluksay ody path epnwithikhxngpmphx aela node khuxpmphx R node path emuxpmkhxmulthierakalngphicarnaepnpmlukkhwa ody path epnwithikhxngpmphx aela node khuxpmphx top emuxpmkhxmulnnepnpmrak aelakahndihtaaehnngkhxngpmkhxmulaethndwy Pos node path ody node khuxpmkhxmulthierasnicaela path khuxwithikhxngpmkhxmulnithungpmrak dngnntnimthwiphakhnicasamarthekhiynepnfngkchnidwa Node Node Node a null null Node Node Node b null null Node c null null Node d null null Node Node e null null Node f null null dngnn erasamarththicarabutaaehnngkhxngekhruxnghmaylbintnimthwiphakhniidepn Pos Node Node Node b null null Node c null null Node d null null R Node Node a null null Node Node Node b null null Node c null null Node d null null L top Node Node Node a null null Node Node Node b null null Node c null null Node d null null Node Node e null null Node f null null emuxerasamarthrabutaaehnngkhxmulthieratxngkaridaelw eraksamarthichkhasngxun kbkhxmulthierasnicid echn eluxntaaehnnglng goDown eluxntaaehnngkhun goUp eluxnipthangsay goLeft eluxnipthangkhwa goRight epliynkhainpmkhxmul change ephimkhxmul insert hruxaemaetlbpmkhxmulnn delete xyangthatxngkarsngiheluxntaaehnnglngkichkhasngepn goDown Pos n p idely inemuxerasamarthrabutaaehnngpmkhxmulthieratxngkaraelasngidechnniaesdngwakarthangankhxngfngkchnehlaniepn O 1 cudednkhxngsipepxrcudednkhxngsipepxrkhuxerasamarthaesdngkhxmulxun thixyubnwithiediywknkbkhxmulthierasnictamthiidklawiwinhwkhxlksnakhxngsipepxr thaihaenwkhidnithuknaipichkbopraekrmthimikarephngkhwamsnickhxmul focus rwmthungsamarthyaytaaehnngkhxngcudsnicipyngkhxmulrxb iddwy echn opraekrm Xmonad xikthngprasiththiphaphinkarthangankhxngkhasngswnihythimiprasiththiphaphinkarthanganepn O 1 aelacudednthisakhyxikxyanghnungokhrngsrangkhxmulchnidniekhiynodyichkarekhiynopraekrmechingfngkchn Functional programming sungkarekhiynopraekrmaebbnixacepneruxngihmsahrbopraekrmemxrhlay khnkarekhiynopraekrmechingfngkchnkarekhiynopraekrmechingfngkchnepnkarekhiynopraekrmthithangankhlaykbfngkchnkhxngkhnitsastr odymiaenwkhidsakhywaihhlikeliyngkarekiywkhxngkbsthanakhxngopraekrm state aelahlikeliyngkarepliynaeplngkhxmultang odykhasnghnungthiidrbpharamietxrehmuxnkntxngihkhatxbediywkn xyangechn inkhnitsastr thaih f x x 4 aela x 4 caid f 4 8 esmx aesdngwathasrangkhasng foo Object e khunma caidwakhasng foo mikarthanganehmuxnedimtrabthipharamietxrkhux e yngepnkhaedim dngnncaphbwakarekhiynopraekrmaebbnicamitwaeprxyuinopraekrmnxyephuxepnkarhlikeliyngkarepliynaeplngkhainkhxmulaelasamarthmi Composite function xyuinswnkarthangankhxngopraekrmidmakmaybrikarthimkcamibrikarthiyaycudthisnicipyngrxb khxmulthisnic echn say khwa bn aelalang brikarepliynkhakhxngkhxmulthicudthisnic brikaraethrkaelalbkhxmulthicudthisnickhwamerwthiichinkarthangankhwamerwinkarthanganswnihycaepn O 1 sungepnephraakarekhiynopraekrmechingfngkchnsungepriybesmuxnkariskhxmultwnnaelathixyukhxngmnthixacepninlksnakhxng Composite function ephuxihopraekrmthangantambrikarthieratxngkar aetthngnikkhunxyukbkarxxkaebbokhrngsrangkhxmulkhxngopraekrmemxraetlakhndwywacawangokhrngsrangiwxyangir bangkhasngcungimcaepntxngmikarthanganepn O 1 esmxipxangxingHuet Gerard Functional Pearl The Zipper Journal of Functional Programming 7 5 549 554 September 1997 Zipper data structure Functional Programming Roll Your Own Window Manager Tracking Focus with a Zipper