日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當(dāng)前位置:首頁 > 科技  > 軟件

Figma 在協(xié)同編輯中使用的順序一致性算法: Fractional indexing

來源: 責(zé)編: 時(shí)間:2024-03-27 09:26:22 170觀看
導(dǎo)讀大家好,我是前端西瓜哥。Figma 支持多人協(xié)同,那它是如何做到順序一致性的呢?在多人同時(shí)操作同層級的多個(gè)圖形的順序時(shí),需要保證用戶的意圖能保留,不會(huì)被其他用戶的操作覆蓋丟棄,且所有用戶最終的順序是一致的。為解決這個(gè)問

zZL28資訊網(wǎng)——每日最新資訊28at.com

大家好,我是前端西瓜哥。zZL28資訊網(wǎng)——每日最新資訊28at.com

Figma 支持多人協(xié)同,那它是如何做到順序一致性的呢?zZL28資訊網(wǎng)——每日最新資訊28at.com

在多人同時(shí)操作同層級的多個(gè)圖形的順序時(shí),需要保證用戶的意圖能保留,不會(huì)被其他用戶的操作覆蓋丟棄,且所有用戶最終的順序是一致的。zZL28資訊網(wǎng)——每日最新資訊28at.com

為解決這個(gè)問題,F(xiàn)igma 使用了一種名為 Fractional Indexing 的簡單算法。zZL28資訊網(wǎng)——每日最新資訊28at.com

Fractional indexing 的原理

Fractional Indexing,直譯的話,是小數(shù)索引。zZL28資訊網(wǎng)——每日最新資訊28at.com

該算法的原理并不復(fù)雜。zZL28資訊網(wǎng)——每日最新資訊28at.com

圖形對象會(huì)使用 index 屬性表示順序,記錄自己在同級圖形中的位置。zZL28資訊網(wǎng)——每日最新資訊28at.com

index 的值為 0 到 1 之間的 64 位浮點(diǎn)數(shù),不包括 0 和 1。zZL28資訊網(wǎng)——每日最新資訊28at.com

出于減少體積的考慮,figma 會(huì)丟掉前面的 0.,并把剩余的小數(shù)部分?jǐn)?shù)字轉(zhuǎn)換成 ASCII 中的可打印字符(共 95個(gè),表達(dá)為 95 進(jìn)制數(shù))。zZL28資訊網(wǎng)——每日最新資訊28at.com

不能為 0 和 1, 是因?yàn)槿绻o某個(gè)圖形設(shè)置了 0 或 1,這個(gè)圖形的左側(cè)或右側(cè)添加的圖形的 index 就會(huì)超出了 0 到 1 的范圍。zZL28資訊網(wǎng)——每日最新資訊28at.com

zZL28資訊網(wǎng)——每日最新資訊28at.com

當(dāng)往兩個(gè)圖形之間插入新的節(jié)點(diǎn)時(shí),我們會(huì)取這兩個(gè)圖形 index 的中點(diǎn)。zZL28資訊網(wǎng)——每日最新資訊28at.com

比如我們要在索引值分別為 0.3 和 0.4 的圖形插入圖形,這個(gè)圖形的索引值會(huì)取中間值 0.35。zZL28資訊網(wǎng)——每日最新資訊28at.com

zZL28資訊網(wǎng)——每日最新資訊28at.com

移動(dòng)圖形同理。zZL28資訊網(wǎng)——每日最新資訊28at.com

但在實(shí)現(xiàn)這個(gè)算法的時(shí)候,你需要注意兩個(gè)問題。zZL28資訊網(wǎng)——每日最新資訊28at.com

精度問題

首先是精度問題。zZL28資訊網(wǎng)——每日最新資訊28at.com

說到取中間值,容易聯(lián)想到二分查找。zZL28資訊網(wǎng)——每日最新資訊28at.com

二分查找效率很高,時(shí)間復(fù)雜度是 O(logn),是因?yàn)椴还軘?shù)據(jù)規(guī)模多大,它 每一次查找都會(huì)直接將數(shù)據(jù)量減半,給你打骨折。zZL28資訊網(wǎng)——每日最新資訊28at.com

zZL28資訊網(wǎng)——每日最新資訊28at.com

index 使用的雙浮點(diǎn)數(shù),能表示的二進(jìn)制小數(shù)部分位數(shù)為 52 位,每次二分就是進(jìn)行 位右移操作,會(huì)用掉一個(gè)精度。zZL28資訊網(wǎng)——每日最新資訊28at.com

假設(shè)我們不斷地往 0.3 到 0.4 的區(qū)間靠近 0.3 的那邊插入新圖形,我們會(huì)看到 index 非常快地接近 0.3,最后因?yàn)榫扔猛辏僖矡o法二分。zZL28資訊網(wǎng)——每日最新資訊28at.com

const getMid = (a, b) => (a + b) / 2;const left = 0.3let right = 0.4for (let i = 0; i <= 50; i++) {  right = getMid(left, right);  console.log(right);}

上面的代碼在 50 次左右就將精度耗盡了。zZL28資訊網(wǎng)——每日最新資訊28at.com

zZL28資訊網(wǎng)——每日最新資訊28at.com

這種是很極端的場景,一般正常的用戶操作不會(huì)出現(xiàn),F(xiàn)igma 并不打算處理這種情況的。zZL28資訊網(wǎng)——每日最新資訊28at.com

字符串表示法

當(dāng)然精度問題是有辦法解決的,那就是用無限精度的數(shù)據(jù)類型:字符串。zZL28資訊網(wǎng)——每日最新資訊28at.com

該算法使用 "0" 到 "9" 的字符串表示索引,并通過字典序作為排序依據(jù)。zZL28資訊網(wǎng)——每日最新資訊28at.com

空字符表示最小值,null 表示最大值。zZL28資訊網(wǎng)——每日最新資訊28at.com

  • 計(jì)算中點(diǎn)會(huì)做舍入,盡量不占用更多的位數(shù)。

比如 "3" 和 "6" 的中點(diǎn)是 "5",而不是 "45"。但 "3" 和 “4” 因?yàn)樘拷荒艿玫?"35"。zZL28資訊網(wǎng)——每日最新資訊28at.com

  • 如果是空字符,會(huì)等價(jià)于 "0",如果是 null,等價(jià)于 "10"(會(huì)比 "9" 大)。
  • 如果有前綴相同部分,取后面不同部分計(jì)算中點(diǎn),再拼回去。

假如兩個(gè)相鄰圖形的 index 分別是  "123" 和 "1234"。zZL28資訊網(wǎng)——每日最新資訊28at.com

我們會(huì)取后面不同的部分 ""(表示 0) 和 "4",取中點(diǎn) "2",然后添加回相同前綴 "123",得到我們需要的新索引 "1232"。zZL28資訊網(wǎng)——每日最新資訊28at.com

另外,對比 "123" 和 "123004" 時(shí),"123" 要補(bǔ)全后綴零為 "12300"。zZL28資訊網(wǎng)——每日最新資訊28at.com

我們來看看效果。zZL28資訊網(wǎng)——每日最新資訊28at.com

使用這種方式,對 "3" 和 "4" 進(jìn)行 1000 次的二分,因?yàn)橥黄屏司认拗疲覀儠?huì)得到非常非常長的字符串。zZL28資訊網(wǎng)——每日最新資訊28at.com

zZL28資訊網(wǎng)——每日最新資訊28at.com

很長,通常通過編碼處理精簡,這里就不過多介紹了。zZL28資訊網(wǎng)——每日最新資訊28at.com

沖突問題

最后是沖突問題。zZL28資訊網(wǎng)——每日最新資訊28at.com

如果耿直地計(jì)算中點(diǎn),那當(dāng)多個(gè)客戶的都同時(shí)往兩個(gè)節(jié)點(diǎn)之間插入圖形,同步后就會(huì)出現(xiàn)多個(gè)圖形的 index 相同的場景。zZL28資訊網(wǎng)——每日最新資訊28at.com

對此,我們會(huì) 在中間值的基礎(chǔ)上,加上一個(gè)隨機(jī)的偏移值,這樣多個(gè)客戶端之間的沖突概率就非常的低。zZL28資訊網(wǎng)——每日最新資訊28at.com

但非常極端的情況下,沖突還是可能發(fā)生的,這種情況下就需要作為 中心權(quán)威的服務(wù)端去做修正 了,進(jìn)行微小偏移,且和其他索引值不沖突。zZL28資訊網(wǎng)——每日最新資訊28at.com

結(jié)尾

Fractional Indexing 的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單,不需要 CRDT 那種墓碑機(jī)制,要保留大量無用的元數(shù)據(jù)。zZL28資訊網(wǎng)——每日最新資訊28at.com

缺點(diǎn)是極端場景 index 的長度很長,有精度不夠?qū)е露质〉倪吘増鼍埃捎米址鉀Q),以及對圖形編輯器并無大礙的交錯(cuò)問題(兩用戶分別輸入 "123" 和 "ABC",同步后可能會(huì)得到 "1A2B3C",而不是 "123ABC")。zZL28資訊網(wǎng)——每日最新資訊28at.com

本文鏈接:http://www.www897cc.com/showinfo-26-79607-0.htmlFigma 在協(xié)同編輯中使用的順序一致性算法: Fractional indexing

聲明:本網(wǎng)頁內(nèi)容旨在傳播知識(shí),若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系,我們將在第一時(shí)間刪除處理。郵件:2376512515@qq.com

上一篇: 詳解SpringBoot錯(cuò)誤處理

下一篇: 完美世界控股集團(tuán)入選新一批國家文化產(chǎn)業(yè)示范基地名單

標(biāo)簽:
  • 熱門焦點(diǎn)
  • 直屏旗艦來了 iQOO 12和K70 Pro同臺(tái)競技

    旗艦機(jī)基本上使用的都是雙曲面屏幕,這就讓很多喜歡直屏的愛好者在苦等一款直屏旗艦,這次,你們等到了。據(jù)博主數(shù)碼閑聊站帶來的最新爆料稱,Redmi下代旗艦K70 Pro和iQOO 12兩款手
  • 影音體驗(yàn)是真的強(qiáng) 簡單聊聊iQOO Pad

    大公司的好處就是產(chǎn)品線豐富,非常細(xì)分化的東西也能給你做出來,例如早先我們看到了新的vivo Pad2,之后我們又在iQOO Neo8 Pro的發(fā)布會(huì)上看到了iQOO的首款平板產(chǎn)品iQOO Pad。雖
  • 小米降噪藍(lán)牙耳機(jī)Necklace分享:聽一首歌 讀懂一個(gè)故事

    在今天下午的小米Civi 2新品發(fā)布會(huì)上,小米還帶來了一款新的降噪藍(lán)牙耳機(jī)Necklace,我們也在發(fā)布結(jié)束的第一時(shí)間給大家?guī)磉@款耳機(jī)的簡單分享。現(xiàn)在大家能見到最多的藍(lán)牙耳機(jī)
  • Redmi Buds 4開箱簡評:才199還有降噪 可以無腦入

    在上個(gè)月舉辦的Redmi Note11T Pro系列新機(jī)發(fā)布會(huì)上,除了兩款手機(jī)新品之外,Redmi還帶來了兩款TWS真無線藍(lán)牙耳機(jī)產(chǎn)品,Redmi Buds 4和Redmi Buds 4 Pro,此前我們在Redmi Note11T
  • 7月安卓手機(jī)性價(jià)比榜:努比亞+紅魔兩款新機(jī)入榜

    7月登場的新機(jī)有努比亞Z50S Pro和紅魔8S Pro,除了三星之外目前唯二的兩款搭載超頻版驍龍8Gen2處理器的產(chǎn)品,而且努比亞和紅魔也一貫有著不錯(cuò)的性價(jià)比,所以在本次的性價(jià)比榜單
  • Temu起訴SHEIN,跨境電商戰(zhàn)事升級

    來源 | 伯虎財(cái)經(jīng)(bohuFN)作者 | 陳平安日前據(jù)外媒報(bào)道,拼多多旗下跨境電商平臺(tái)Temu正對競爭對手SHEIN提起新訴訟,訴狀稱Shein&ldquo;利用市場支配力量強(qiáng)迫服裝廠商與之簽訂獨(dú)家
  • 自律,給不了Keep自由!

    來源 | 互聯(lián)網(wǎng)品牌官作者 | 李大為編排 | 又耳 審核 | 谷曉輝自律能不能給用戶自由暫時(shí)不好說,但大概率不能給Keep自由。近日,全球最大的在線健身平臺(tái)Keep正式登陸港交所,努力
  • 馮提莫簽約抖音公會(huì) 前“斗魚一姐”消失在直播間

    來源:直播觀察提起&ldquo;馮提莫&rdquo;這個(gè)名字,很多網(wǎng)友或許聽過,但應(yīng)該不記得她是哪位主播了。其實(shí),作為曾經(jīng)的&ldquo;斗魚一姐&rdquo;,馮提莫在游戲直播的年代影響力不輸于現(xiàn)
  • 支持aptX Lossless無損傳輸 iQOO TWS 1賽道版發(fā)布限時(shí)優(yōu)惠價(jià)369元

    2023年7月4日,“無損音質(zhì),聲動(dòng)人心”iQOO TWS 1正式發(fā)布,支持aptX Lossless無損傳輸,限時(shí)優(yōu)惠價(jià)369元。iQOO TWS 1耳機(jī)率先支持端到端aptX Lossless無
Top 主站蜘蛛池模板: 石棉县| 南汇区| 安吉县| 英超| 彭山县| 辽宁省| 乌鲁木齐县| 兴仁县| 红原县| 湘潭县| 通化市| 农安县| 高陵县| 宿州市| 宁城县| 沐川县| 鹰潭市| 阳山县| 清河县| 萍乡市| 天等县| 温宿县| 宁安市| 衡南县| 百色市| 内江市| 北碚区| 长武县| 治县。| 浦北县| 太湖县| 高碑店市| 湾仔区| 稻城县| 阳谷县| 松原市| 山东省| 和顺县| 罗田县| 正镶白旗| 汤阴县|