LexoRank Python工具库

lexorank-py是用于分数索引的lexorank算法的轻量级、无依赖性的Python实现，实现了高效的拖放排序、动态列表重新排序和插入任何位置的操作，而无需完全重新平衡列表。 非常适合构建可排序的任务列表、看板、脚本编辑器或任何需要持久、稳定排序键的UI。

目录结构

py-lexorank/
├── src/py_lexorank/              # Python import 包：py_lexorank
│   ├── __init__.py
│   ├── lexorank_key.py           # 业务层 API（推荐使用）
│   └── lexorank/                 # LexoRank 核心实现（算法层）
│       ├── __init__.py
│       ├── lexo_decimal.py
│       ├── lexo_integer.py
│       ├── lexo_rank.py
│       ├── lexo_rank_bucket.py
│       └── numeral_systems.py
├── examples/                     # 示例/造排序数据脚本（不随 pip 包发布）
│   └── demo.py
├── tests/                        # 单元测试
│   └── test_lexorank.py
├── pyproject.toml
└── README.md

项目概述

LexoRank 是一种排序算法，允许在列表中任意位置插入新元素而无需重新排列整个列表。它通过在两个已存在的排序键之间生成新的排序键来实现这一点。

核心概念

• 排序键（Rank Key）：用于数据库排序的字符串，按字典序排序即可得到正确的顺序
• 分数索引（Fractional Indexing）：在两个排序键之间生成新键的技术
• 分桶（Bucket）：用于隔离不同分组的排序空间，避免 rank 过度变长
• 进制系统：使用 base36 进制系统进行数值表示

使用方法

基础安装和使用

安装

使用 pip 安装：

pip install py-lexorank

或使用 uv (更快的包管理器)：

uv pip install py-lexorank

推荐直接导入 LexoRankKey 类即可开始使用：

from py_lexorank import LexoRankKey

# 初始化空列表的第一条记录
first_rank = LexoRankKey.init_for_empty_list()

# 在两条记录之间插入
second_rank = LexoRankKey.insert_after(first_rank)
middle_rank = LexoRankKey.insert_between(first_rank, second_rank)

# 插入到最前面
before_first = LexoRankKey.insert_before(first_rank)

# 通用插入接口
new_rank = LexoRankKey.insert(prev_rank, next_rank)

常见使用场景

1. 空列表插入第一条记录

# 当列表为空时，插入第一条记录
first_rank = LexoRankKey.init_for_empty_list()

2. 追加到列表末尾

# 在现有列表末尾追加新记录
new_rank = LexoRankKey.insert_after(last_rank)

3. 在两条记录之间插入

# 在两个已知记录之间插入新记录（常用：拖拽排序）
new_rank = LexoRankKey.insert_between(left_rank, right_rank)

4. 插入到列表开头

# 在列表开头插入新记录
new_rank = LexoRankKey.insert_before(first_rank)

5. 通用插入接口

# 最灵活的插入方式，适用于所有场景
new_rank = LexoRankKey.insert(prev_rank, next_rank)

查看 API 文档（命令行）

本项目不发布任何 CLI（避免与业务 API 混淆）。你可以用命令行查看 API 文档：

# 查看模块文档（包含 LexoRankKey 的说明和方法注释）
python -m pydoc py_lexorank.lexorank_key

# 或在交互式环境查看类帮助
python -c "from py_lexorank import LexoRankKey; help(LexoRankKey)"

演示脚本

运行演示脚本来查看各种使用场景：

1. 直接运行（默认空列表自动插入第一条）

PYTHONPATH=src python examples/demo.py

2. 指定批量生成数量（默认空列表自动插入第一条，根据生成的第一条一次生成 X 个递增 rank）

PYTHONPATH=src python examples/demo.py --count 20

3. 指定起始 rank（从某个已有 rank 后面开始批量生成X 个递增 rank） 注意：rank 里有 |，在 zsh 里必须用引号包起来

PYTHONPATH=src python examples/demo.py --start '0|hzzzzz:' --count 10

测试

在仓库根目录运行：

PYTHONPATH=src python -m unittest discover -s tests -v

文件详细说明

源码位于 src/py_lexorank/：

• src/py_lexorank/lexorank_key.py：业务层 API（字符串进出，推荐）
• src/py_lexorank/lexorank/：LexoRank 算法核心实现与 CLI
• examples/demo.py：示例/造排序数据脚本（repo-only）
• tests/test_lexorank.py：单元测试

业务场景应用

1. 任务列表排序

在项目管理应用中，用户经常需要调整任务的顺序。使用 LexoRank 可以避免每次重排都更新整个列表：

from py_lexorank.lexorank_key import LexoRankKey

# 创建新任务并插入到列表中
def add_task_after(task_list, target_task_id):
    target_task = get_task(target_task_id)
    next_task = get_next_task(target_task_id)
    
    new_rank = LexoRankKey.insert_between(target_task.rank, next_task.rank)
    create_task(rank=new_rank)

2. 菜单项排序

在菜单编辑器中，用户可以通过拖拽调整菜单项的顺序：

from lexorank_key import LexoRankKey

# 拖拽排序：将项目从 old_pos 移动到 new_pos
def move_menu_item(item_id, old_pos, new_pos):
    if new_pos == 0:  # 移到开头
        new_rank = LexoRankKey.insert_before(get_first_item().rank)
    elif new_pos == get_last_position():  # 移到末尾
        new_rank = LexoRankKey.insert_after(get_last_item().rank)
    else:  # 移到中间
        prev_item = get_previous_item(new_pos)
        next_item = get_next_item(new_pos)
        new_rank = LexoRankKey.insert_between(prev_item.rank, next_item.rank)
    
    update_item_rank(item_id, new_rank)

3. 场景排序

在视频制作应用中，用户可以对场景进行排序：

from lexorank_key import LexoRankKey

def reorder_scenes(scene_ids, new_order):
    """根据新顺序重新排列场景"""
    ordered_scenes = []
    for i, scene_id in enumerate(new_order):
        if i == 0:
            # 第一个场景使用初始 rank 或者基于第一个现有场景的 rank
            if len(ordered_scenes) > 0:
                rank = LexoRankKey.insert_before(ordered_scenes[0].rank)
            else:
                rank = LexoRankKey.init_for_empty_list()
        else:
            # 后续场景插入到前一个场景之后
            rank = LexoRankKey.insert_after(ordered_scenes[-1].rank)
        
        ordered_scenes.append(Scene(id=scene_id, rank=rank))
    
    # 批量更新所有场景的 rank
    bulk_update_scene_ranks(ordered_scenes)

注意事项

并发安全

当多个请求并发向同一缝隙插入时，可能会生成重复的 rank。建议：

1. 在数据库中设置唯一约束
2. 在业务层添加适当的锁或重试机制
3. 处理插入冲突的情况

性能考虑

• LexoRank 字符串会随着频繁的插入操作逐渐变长
• 当 rank 字符串变得过长时，可能需要执行重新编号操作
• 对于大量数据的排序，定期进行碎片整理是有益的

测试

运行单元测试验证功能：

python -m lexorank.test_lexorank

或直接运行测试文件：

python lexorank/test_lexorank.py

许可证

本项目遵循 MIT 许可证。