如何加快某些键可能不存在的批量多索引查找？

问：

我想知道如何对包含大量（数千及以上）元素的序列进行多索引查找，其中使用两个级别的索引，其中一个索引是元素本身，另一个索引在每次查找中都是相同的。

在我进一步解释之前，我想澄清一下，这不是家庭作业或与工作相关的，我是一个失业的编程爱好者，我之所以这么说，是因为有些人可能会认为这是家庭作业。

这些元素可以是任何可散列类型，而不仅仅是 s，例如它们可以是 s，并且它们可能不存在于查找表中，第二个索引是 a 并且每个批处理查找中都是相同的。所需的行为是，如果元素位于查找表中，则输出位于与查找表中元素关联的集合中第二个索引处的元素，否则输出元素本身。intstrint

我想知道如何扩展它，以便它可以处理巨大的输入。

我创建了一个脚本，将字符串中的基本拉丁字母旋转 n（0 <= n <= 25，n 是一个整数）来说明这一点，如果字符串中的字符是 52 个拉丁字母之一，则将其替换为位于字母表中字符的 n 个索引处的字母， 通过环绕和外壳保存，否则角色将保持原样。

该代码仅用作最小可重现示例，这不是我的目标，我已经测量了语句的执行时间并在注释中提供了时间：

import random
from typing import Mapping, Sequence
from itertools import product

LETTERS = [
    {chr(a + b): chr(a + (b + i) % 26) for a, b in product((65, 97), range(26))}
    for i in range(26)
]
# 365 µs ± 24.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

UPPER = [chr(65 + i) for i in range(26)]
# 2.43 µs ± 75.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

LOWER = [chr(97 + i) for i in range(26)]
# 2.68 µs ± 222 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

ROT = {c: case[i:] + case[:i] for case in (LOWER, UPPER) for i, c in enumerate(case)} 
# 24.9 µs ± 1.77 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

ROT_LIST = [{} for _ in range(26)]
# 1.58 µs ± 13.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

for k, v in ROT.items():
    for i, c in enumerate(v):
        ROT_LIST[i][k] = c
# 135 µs ± 5.05 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

# (2.43 + 2.68 + 24.9 + 1.58) == 31.59
# (31.59 + 135) == 166.59
# 31.59 / 365 == 0.08654794520547945
# 166.59 / 365 == 0.4564109589041096

def rot(s: str, d: int = 13) -> str:
    return "".join(LETTERS[d].get(c, c) for c in s)

def rot_v1(s: str, d: int = 13) -> str:
    return "".join(c if (r := ROT.get(c, c)) == c else r[d] for c in s)

def rot_v2(s: str, d: int = 13) -> str:
    return "".join(ROT[c][d] if c in ROT else c for c in s)

def get_size(obj: object) -> int:
    size = obj.__sizeof__()
    if isinstance(obj, Mapping):
        size += sum(get_size(k) + get_size(v) for k, v in obj.items())
    elif isinstance(obj, Sequence) and not isinstance(obj, str):
        size += sum(get_size(e) for e in obj)
    return size

# get_size(LETTERS) == 194152
# get_size(ROT) == 85352
# 85352 / 194152 == 0.439614322798632

string = random.choices(LOWER, k=4096)

LETTERS是我能想到的最直接的生成查找表的方法，但它既内存效率低下又时间效率低下。 既省时又省内存，它减少了 56.04% 的内存使用量和 91.35% 的执行时间，尽管我猜查询它可能会比 .ROTLETTERS

我还发现，生成像 from 这样的结构比直接计算它花费的时间少 54.36%。LETTERSROT

我进行了多次测试，时间差异很大，但似乎始终比 快，而 又始终比：rot_v2rotrot_v1

In [9]: %timeit rot(string)
742 µs ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [10]: %timeit rot_v1(string)
771 µs ± 8.55 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [11]: %timeit rot_v2(string)
569 µs ± 6.14 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [12]: %timeit rot_v2(string)
588 µs ± 50.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [13]: %timeit rot_v1(string)
821 µs ± 44.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [14]: %timeit rot_v2(string)
609 µs ± 53.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [15]: %timeit rot(string)
601 µs ± 50.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [16]: %timeit rot(string)
603 µs ± 48.1 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [17]: %timeit rot_v2(string)
586 µs ± 54.9 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [18]: %timeit rot_v1(string)
818 µs ± 68.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

我考虑过使用，但到目前为止，我只使用布尔值和整数作为数组索引，我不知道如何使用字符串数组作为索引。NumPy

我怎样才能加快速度？

编辑

澄清：这不是我真正想要的，它只是一个更通用的多索引查找的 MRE，其中可能缺少一些键。rot