※ 引述《sudada (叽咕叽咕叽咕)》之铭言： : 各位好 : 最近遇到一个sorting的问题 : 假设我有一个List里面放我自订的class : 他必须是个排序好的状态 : 但是每次有新增或更新资料 我都必须取得那笔资料的index : 而且使用上get range的使用机率应该会比insert高一点 : 目前我有两种想法 : 第一 : 每次丢资料进去都call一次sort : 不过这样没办法直接知道我刚刚新增的那笔资料 : 到底会被丢到哪里去 : 所以sort完以後还要再抓一次index? : 这种方法我觉得完全不可行...... : 第二 : 跑回圈用自己的compare方式找到适当的位置 : 直接call insert : 这样"感觉上"快很多 : 但是问题出在用List的资料结构的话 : 每次都必须从头开始 cost应该是O(n)? : 如果要改进这里势必要改资料结构 : 用binary tree又怕会影响整体get的效能 : 想请问大家会怎麽取舍 : 谢谢 这里有个叫 TreeSet 的东西 有个 method 应该有用: NavigableSet<E> headSet(E toElement, boolean inclusive) Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement. 也就是说 用 headSet 拉出来再贴 size 就能得到 index 了 或许你可以改用 TreeSet 来做事 (它的底层是红黑树, 插入删除寻找都是对数时间) range query 也有 subSet 可以用 -- 'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.32