社区
C语言 帖子详情 链表访问速度的问题 edwardliqi 2011-01-26 10:49:49 自定义了一个结构体 node 长度是 36 个字节
我申请了一个 20000（2W）长度的数组，类型是 node，然后把他们按顺序穿起来，变成一个链表，这样访问一遍的速度是TIME1
我再把里面的顺序打乱，非常乱，但是还是这个链表，首地址没有变，但是还是访问一边，速度是TIME2
为啥 TIME2 大约是 TIME1 的两倍啊？
...全文
423 27 打赏 收藏 链表访问速度的问题 自定义了一个结构体 node 长度是 36 个字节 我申请了一个 20000（2W）长度的数组，类型是 node，然后把他们按顺序穿起来，变成一个链表，这样访问一遍的速度是TIME1 我再把里面的顺序打乱，非常乱，但是还是这个链表，首地址没有变，但是还是访问一边，速度是TIME2 为啥 TIME2 大约是 TIME1 的两倍啊？ 复制链接
扫一扫 分享 转发到动态 举报 AI 作业
写回复 配置赞助广告取 消
确 定
用AI写文章 27 条回复 切换为时间正序 请发表友善的回复… 发表回复 打赏红包 需支付: 0.00 元 取 消 确 定 rushman 2011-02-07 打赏举报 回复 2W单元，不算太多。
可能是你的机器内存、缓存比较小吧，使得两者之间差异显得比较大。 henrykind 2011-02-07 打赏举报 回复 应该和CPU或者MMU cache有关吧，通常连续的逻辑地址访问要比完全随机访问快一点 莫萧恒 2011-02-02 打赏举报 回复 你是怎么打乱的啊 xzlcc 2011-01-31 打赏举报 回复 应该不会有多大区别，建议LZ多测试几次 取平均时间看看 appx 2011-01-30 打赏举报 回复 问题在于两者虽然都是链表的形式定义的，但是并不确定具体的使用方式也是相同的，因为数组形式分配的空间是可以采用数组方式处理数据的，如果这样，机器在执行指令条数上要比无任何顺序可言的链表操作要少这就好比，由于机器i++和i = i+1,两者的处理方式不同，而导致时间差别有相同的道理。 edwardliqi 2011-01-30 打赏举报 回复 [Quote=引用 21 楼 d412188290 的回复:]
不应该啊 你如果按照链表的顺数访问时间不会有太大的出入吧。
[/Quote]
不是顺序访问，是打乱之后再访问 d412188290 2011-01-28 打赏举报 回复 不应该啊 你如果按照链表的顺数访问时间不会有太大的出入吧。 abcdwell 2011-01-28 打赏举报 回复 看着有点乱，有什么序吗？
qq120848369 2011-01-28 打赏举报 回复 因为之前分配内存你是一个接一个分配的,比较整齐。
打乱了，就不是一个挨着一个了，所以就索引的慢了。 edwardliqi 2011-01-28 打赏举报 回复 页面抖动时什么意思？ lengxujun 2011-01-26 打赏举报 回复 这里有一个方法,供lz参考.
哈希: 链地址法.
buckets[N]:
buckets[0] -> node -> node -> ... -> NULL // 链表1
buckets[1] -> node -> node -> ... -> NULL // 链表2
.
.
.
buckets[N] -> node -> node -> ... -> NULL
当有一个结点要放置,根据hash函数来决定放入那一个链表;
读取的时候同样用hash函数定位.这样扫描的时间将缩短,因
为你只扫描了你所有结点的一部分,额外加上一个哈希函数调
用开销.
至于N定义多少合适,hash函数的定义,得看具体数据,多做几
次测试,权衡一下,大概达到自己的时间要求就可以了. gbb21 2011-01-26 打赏举报 回复 cache jiangtao19861107 2011-01-26 打赏举报 回复 应该和cache有关，因为你是使用数组来分配的内存空间，所以a,b,c等等的内存地址是连续的，当你访问a时，系统会把b，c的内容一起读入cache中，这样可以加快b，c的访问速度，不需要再去内存中读取。
打乱顺序之后，每次访问一个节点可能都需要先将其从内存中读入cache中，效率比较低。
欣客 2011-01-26 打赏举报 回复 链表的访问速度是比较慢的，因为不是线性的。优点是快速的插入和删除。 欣客 2011-01-26 打赏举报 回复 访问的速度是一样的， 时间差别应该是寻址上面的时间，首地址一样，但要确定所有的地址都一样。 MYMGrub 2011-01-26 打赏举报 回复 [Quote=引用 5 楼 edwardliqi 的回复:]
引用 1 楼 mymgrub 的回复:
里面被打的有多么乱呀？怎么个乱法呀
就是比如长度是5： a b c d e f a.next = b b.next = c ......
然后大乱后 : a f c e b d a.next = f f.next = c ......
反正就是由个程序，把里面的东西按照一个规则（每次运行不固定）排序，然后，遍历的时间丫的差好多
[/Quote]
照这样应该对遍历的速度没有太大的影响啊..如果是在同一台机器上测得的数据我觉得LZ可以在计算时间的方式上找找原因..或者LZ把打乱的这个过程的时间也算进去了... dengsf 2011-01-26 打赏举报 回复 cache，
链表数据720k，看看测试机器的cache多大。 edwardliqi 2011-01-26 打赏举报 回复 谁能给个解决方案啊。。。最好让time2 = time1 edwardliqi 2011-01-26 打赏举报 回复 晕 不会数数了，是长度是6.。。。。编辑的时候和回帖之后对齐竟然不一样 edwardliqi 2011-01-26 打赏举报 回复 [Quote=引用 1 楼 mymgrub 的回复:]
里面被打的有多么乱呀？怎么个乱法呀
[/Quote]
就是比如长度是5： a b c d e f a.next = b b.next = c ......
然后大乱后 : a f c e b d a.next = f f.next = c ......
反正就是由个程序，把里面的东西按照一个规则（每次运行不固定）排序，然后，遍历的时间丫的差好多 加载更多回复（7） 数据结构（高一凡）. 数组的特点是随机访问速度快，但插入和删除操作相对较慢。 链表则弥补了数组在动态扩展和删除方面的不足，通过指针连接元素，可以在任何位置插入或删除节点。链表分为单链表、双链表和循环链表等多种形式，各有优劣... 微软面试100题系列之高清完整版PDF文档[带目录+标签]by_July 数据结构是计算机科学中一个非常重要的概念，它涉及如何组织和存储数据以便高效地访问和修改。微软面试100题系列中的数据结构部分可能包含以下知识点： 1. **基本数据结构**：包括数组、链表、栈、队列等。 - **... JAVA近百种算法大全 2. 链表：动态存储结构，插入和删除高效，但访问速度慢。 3. 栈：后进先出（LIFO）的数据结构，常用于函数调用和表达式求值。 4. 队列：先进先出（FIFO）的数据结构，适用于任务调度和消息传递。 5. 树：非线性的... 链表和数组的区别 链表的访问速度较慢，因为链表访问元素需要移动指针。 区别三：添加、删减元素速度 数组的元素增删速度较慢，因为需要移动大量的元素。 链表的元素增删速度较快，因为只需要修改指针即可。 ... 哈希链表：提高链表访问效率 当数据动态生成时，此时我们无法确知其数据大小，当然也无法进行判断了，而链表则可以解决此问题。针对上题文本数据，我们给出链表的解法。 首先，我们要熟悉下链表的创建过程：往链表头部加入新节点。Node *head =...
C语言
70,025
社区成员
243,260
社区内容
发帖 与我相关 我的任务 C语言 C语言相关问题讨论 复制链接
扫一扫 分享 确定 社区描述 C语言相关问题讨论 社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告 试试用AI创作助手写篇文章吧
+ 用AI写文章