1
geelaw 2023-10-04 21:37:57 +08:00
只有反复修改的情况下才需要考虑数组/链表等数据结构。
>我需要将用户手机的全部图片、视频按时间倒序添加到一个 List 里。基于 Android 的 API 限制,图片和视频的查询是分开的,故有大量的中间插入需求。 这个很简单,你可以先把所有的图片和视频都弄到一个巨大的 ArrayList 里,然后再排序。我没做过 Android 开发,猜测 API 提供按时间顺序分别获取图片、视频的功能,那么你可以先准备好两个 ArrayList ,分别得到正确顺序的图片、视频,然后做一轮归并即可。 |
2
Ericcccccccc 2023-10-04 22:01:38 +08:00
就说一点吧, 这玩意的作者都说他从来没用过 LinkedList, 也没见别人用过.
|
3
kingbill 2023-10-04 22:06:00 +08:00
LinkedList 有顺序,别的场景没用过
|
4
hairoy 2023-10-04 22:11:52 +08:00
2&3. 我的想法是,单线程 TreeMap ,多线程 ConcurrentSkipListMap ,时间戳可以放在 key 或 value 里,使用自定义排序器
|
5
Leviathann 2023-10-04 22:46:27 +08:00
需要插入到排序的某个位置? treemap 咯
不然怎么利用顺序信息? |
6
9c04C5dO01Sw5DNL 2023-10-04 23:03:46 +08:00
因为很少有场景只是 append 、遍历,而没有随机插入、访问
|
7
9c04C5dO01Sw5DNL 2023-10-04 23:06:37 +08:00
@giiiiiithub 修正:因为很少有场景只是增删改 、遍历,而没有随机访问
|
8
xiaofan305 2023-10-04 23:21:47 +08:00 via Android
@giiiiiithub 现在做着的项目就有这种。我是用 LinkedList
|
9
xloger OP @geelaw 嗯,你这种是一种很科学的方式。我最开始为啥没用这种是我考虑到我的实际需求还有一部分是:每获取到一部分图片、视频就要展示给用户看(因此有并发场景),那这个巨大的 ArrayList 是需要多次排序的有浪费。
但我刚刚突然想到了,这其实是每次排序了一部分,剩下的数据也是增量排序(把新数据放末尾就不会 UI 显示不对),实际上是没多少浪费的计算的。 然后我提问的困惑之一是:假如我在这种情况下硬要 ArrayList 、LinkedList 里二选一,ArrayList 在存在后移操作的情况下性能还是更好么? 然后我思考了一下您的想法,这样理解对不对:在有大量中间插入需求的时候,ArrayList 、LinkedList 的性能其实都很差。所以我们更应该做的是通过其他的方式(比如先插入再统一排序、或者 TreeMap 之类的方式)来规避这个问题,而不是强行比哪个差的方案更好一点。 |
10
xloger OP @hairoy
@Leviathann 谢谢回复,一开始我确实是苦恼于 List 怎么没有 TreeMap 这样的根据比较器插入的数据结构。然后网上搜索一下之后无果后放弃了这个方向。 但是现在一想,我实际上还是应该把 TreeMap 来当 List 用,因为这可能是最理想的方式(在插入时确定好顺序,且 Map 有良好的索引规避了 ArrayList 的后移、LinkedList 的查询)。 虽然它可能会带来一些额外的小问题(比如时间戳一致的资源会不会导致覆盖),但这种我自己想办法规避一下就行。 |
11
SoloCompany 2023-10-05 15:34:19 +08:00
除了 ArrayList 以外还有 ArrayDeque, LinkedList 应该是 never use
|
12
ohwind 2023-10-06 13:46:55 +08:00
@Ericcccccccc 为什么不看完别人的贴子就急于发表自己的拙见?
|
13
Ericcccccccc 2023-10-06 13:56:32 +08:00
@ohwind java 的作者表示自己从来没用过 linkedlist 是他自己说的.
|
14
sl450282169 2023-10-08 10:26:43 +08:00 1
@xloger #9 ArrayList 在中间随机插入数据时,只有扩容和移动元素位置之后的那部分元素的操作比较重,由于数组每次扩容 1.5 倍,在数组越大的情况下,扩容次数反而越少,因此在后续操作中,可以理想的看待为之需要插入元素(o(1))并移动元素位置后的那些元素(n-i)个.而 LinkedList 在中间插入元素时,需要持有当前数组的迭代器,然后遍历到指定位置(o(n)),因此数组越大,linkedlist 的插入耗时越多.
|
15
sl450282169 2023-10-08 10:29:03 +08:00 1
以目前的 java 来讲,仅有从头插入,linkedlist 速度比 arraylist 理想,但是在这种情况下,更推荐使用 Deque 拥有更优秀的方法设计.其他场景无脑选 arraylist
|
16
sl450282169 2023-10-08 10:33:46 +08:00
@xloger #9 单纯从此场景来看,你可以试试使用 ConcurrentSkipListSet,可以使插入的元素有序
|
17
Aresxue 2023-10-08 11:09:03 +08:00
@sl450282169 正解
|
18
ohwind 2023-11-20 17:01:00 +08:00
@Ericcccccccc 所以你看完 OP 的帖子了吗
|
19
Ericcccccccc 2023-11-20 17:24:44 +08:00
@ohwind 看了啊, 没有必要用 linkedlist
|
20
ohwind 2023-11-20 17:29:54 +08:00
@Ericcccccccc 我的意思是,OP 已经提到了作者自己都不用,并且不认为这一点值得讨论。所以他是知道这一点的,而您的评论的只是在重复他说过的话
|
21
Ericcccccccc 2023-11-20 17:34:35 +08:00
@ohwind 如果认真要讨论. 几万个数据没必要用 linkedlist.
|
22
txzh007 322 天前
写撤销和回退撤销的时候用过链表,不过这种场景比较少. 需要高频次对数组长度进行修改还是 linkedlist,当然现在可以预先申请很大容量的 arraylist.
|