#order #problem #maintenance #approach #priorities #totally-ordered #relabeling

无 std order-maintenance

针对订单维护问题的全序优先级

2 个版本

0.1.1 2023 年 10 月 10 日
0.1.0 2023 年 9 月 15 日

2105算法

MIT 许可证

18KB
278

订单维护

Continuous integration

该软件包仍在开发中,可能包含严重的错误!

针对订单维护问题的全序优先级。

当前实现使用 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