2 个版本
0.1.1 | 2023 年 10 月 10 日 |
---|---|
0.1.0 | 2023 年 9 月 15 日 |
2105 在 算法
18KB
278 行
订单维护
该软件包仍在开发中,可能包含严重的错误!
针对订单维护问题的全序优先级。
当前实现使用 Dietz & Sleator (1987) 的标签范围重标记方法。
支持 no_std
环境,虽然它需要 alloc
可用。
优化机会
该软件包还处于起步阶段,尚未经过彻底的测试、基准测试或优化。
以下是一些潜在的优化想法
-
使用 Bender 等人 (2002) 的列表范围重标记方法,而不是标签范围重标记;列表范围重标记比乘法和除法更倾向于位操作,因此应该更快。
-
而不是将
Arena::SIZE
设置为2^63
,只让它为2^64
,让溢出自然发生。这省略了目前使用的许多模运算。出于谨慎考虑,目前未实现(此软件包是从具有显式模运算的实现移植过来的),但在理论上是应该的。 -
在
slotmap::{SlotMap, HopSlotMap,DenseSlotMap}
、slab::Slab
、普通的Vec
(插入和删除时移动元素)、{,A}Rc
或甚至原始指针之间进行实验,使用不同的底层分配器。 -
重新调整内部使用的
RefCell
的使用,或者甚至用UnsafeCell
替换它们,以减少内存占用和动态检查。
依赖项
~280KB