今日看点

有关数据结构的论文

发表于话题:第七次人口普查数据结构
发布时间:2021-05-12

《Concurrent Data Structures》(并发数据结构)一文是Mark Moir和Nir Shavit所撰写的一篇有关并发数据结构的综述性文章。这篇文章从多核处理器基础开始,理清了并发数据结构的基础设计理念和技巧,介绍了数据结构算法相关的正确性证明,并列举了栈,链表,队列,树等常用并发数据结构的设计思路。

为了促进大家对并发数据结构基础概念的了解,并发编程网组织译者翻译该论文。由于时间仓促,如有不到位的地方,还请各位指出。

感谢下列译者:董明鑫,俞升兵,Noodles,张军,huavben,iDestiny,郭振斌

论文目录

1.2 共享计数器和Fetch-and-φ结构

1.3 栈和队列

并发数据结构基础概念和原则

并发数据结构即允许多线程同时访问(读和写)的数据结构。

并发数据结构中的算法的设计原则主要分两大类,liveness(活性)和safety(安全性),这两个概念最初来源于分布式系统设计。其中liveness特性保证算法可以执行,而safety保证算法最终得到想要的结果。举一个例子:

问题描述:

对一段序列进行排序,得到降序序列

safety特性:

当算法结束时,得到的序列为输入序列的降序序列。

liveness特性:

最终算法可以运行结束,并返回一段序列。

更加详细的概念和原则介绍可以参考wiki。,

标签组:[大数据] [数据结构

本文来源:https://www.kandian5.com/articles/13496.html

相关阅读

曹无伤左司马职务解析:汉朝中央官制中的重要角色

在中国古代历史的长河中,汉朝以其完备的官制和繁荣的文化著称于世。其中,左司马这一职务在汉朝中央官制中占据着重要的地位。而曹无伤,作为秦汉之际刘邦麾下的一位将领,就曾担任过左司马这一职务。 一、汉朝中...

2025-04-03

汉明帝刘庄并未被杀:一位英明君主的传奇一生

在中国历史上,汉明帝刘庄是一位备受赞誉的君主。然而,关于“汉明帝刘庄为什么被杀”的疑问,实际上是一个基于误解的问题。根据真实的历史资料,汉明帝刘庄并未被杀,他是一位在位期间政治清明、经济繁荣、文化昌盛...

2025-04-03

三国第一毒士之争:李儒与贾诩的较量

在三国时期,谋士辈出,他们以其卓越的智谋和深邃的算计,在历史的舞台上留下了浓墨重彩的一笔。其中,李儒与贾诩两位谋士,因其毒辣的手段和深沉的心机,被后人并称为“三国第一毒士”。然而,关于这一称号究竟应归...

2025-04-03

孙恩与孙权:血缘关系的探寻

在中国历史上,孙恩与孙权都是极具影响力的人物。他们分别活跃在不同的历史时期,各自在各自的时代留下了深刻的印记。然而,近年来,关于孙恩是否是孙权后代的问题,引起了人们的广泛关注和讨论。 一、孙恩与孙权...

2025-04-03

澶渊惊雷:寇准力挽狂澜的孤勇与智慧

公元1004年的深秋,北风裹挟着辽军铁蹄的震颤,黄河岸边的澶州城笼罩在战争的阴云之下。北宋朝廷内,主和派大臣们如惊弓之鸟,或主张南迁金陵,或建议西逃蜀地。在这历史抉择的十字路口,一位目光如炬的政治家挺...

2025-04-03

杜甫的代表作:千年传颂的文学瑰宝

在中国古代文学的璀璨星河中,杜甫无疑是最耀眼的星辰之一。作为唐代伟大的现实主义诗人,杜甫以其深沉的情感、卓越的艺术成就和广泛的社会关怀,被后世尊称为“诗圣”。他的代表作不仅在当时广为流传,历经千年仍被...

2025-04-03

寒门诗魂:鲍照诗歌的刚健风骨与形式突围

在南朝绮靡文风中,鲍照如同一把淬火而出的利剑,以寒门之躯劈开时代的脂粉气。他的诗歌既是对门阀制度的血性呐喊,更是中国古典诗歌美学的一次惊险飞跃。这位被杜甫赞为"俊逸鲍参军"的诗人,用充满棱角的文字构建...

2025-04-03

盛彦师之死:李渊的权谋棋局与功臣末路

在唐朝开国功臣的星空中,盛彦师的名字曾如流星般划过,留下短暂而耀眼的光芒。他斩李密、平王世充、拒降徐圆朗,以骁勇善战著称,最终却落得被唐高祖李渊赐死的结局。这场看似悖理的历史悲剧,实则暗含李渊巩固皇权...

2025-04-03

唐朝统一战争:十年烽火铸就大一统伟业

唐朝,作为中国历史上最为辉煌灿烂的王朝之一,其统一之路却并非一帆风顺。在隋末天下大乱、群雄并起的背景下,唐高祖李渊于公元618年建立唐朝,但此时的新王朝仅占据关中、河东一隅,天下仍处于四分五裂之中。为...

2025-04-03

刘唐:梁山泊中的赤发鬼杰

在《水浒传》这部描绘北宋末年农民起义的鸿篇巨制中,刘唐以其独特的形象和鲜明的性格,成为了梁山泊一百零八将中不可忽视的一员。他绰号“赤发鬼”,紫黑阔脸,鬓边一搭朱砂记,上生一片黑黄毛,形象威猛而独特。那...

2025-04-03