时间戳

首页 > 解决方案 > 如何在 Python 3.7 中单步执行大型有序字典？

python - 如何在 Python 3.7 中单步执行大型有序字典？

问题描述

最近，我一直在将一些 bash 脚本重构到 Python 3.7 中，作为学习练习和项目中的实际使用。最终的实现使用了一个非常大的有序字典，比如大约 2 到 3 百万个条目。以这种方式存储数据有一些显着的优势，可以降低代码复杂性和处理时间。但是，有一个任务让我难以理解：如何从已知的起点逐步浏览字典。

如果我在 C 中执行此操作，我会将指针指向所需的起点并遍历指针。如果Python中有类似的操作，我不知道也找不到。我发现的所有技术似乎都将部分/全部信息复制到一个新列表中，这将非常耗时并且在我的应用程序中浪费大量内存。似乎您也无法对字典进行切片，即使它们现在默认排序。

考虑这个人为的拉丁字母字典示例，其奇怪的键条目按元音和辅音分组，每个组中的条目按字母顺序排序：

dd = { #   key:  (  phonetic, letter, ascii, ebcedic, baudot, morse,  hollerith, strokes,  kind     )
    4296433290:  ( 'Alfa',     'A',    65,     193,     3,    '.-',     (12,1),     3,    'vowl'    ),
    5046716526:  ( 'Echo',     'E',    69,     197,     1,    '.',      (12,5),     4,    'vowl'    ),
    5000200584:  ( 'India',    'I',    73,     201,     6,    '..',     (12,9),     3,    'vowl'    ),
    5000971262:  ( 'Oscar',    'O',    79,     214,     24,   '---',    (11,6),     1,    'vowl'    ),
    5000921625:  ( 'Uniform',  'U',    85,     228,     7,    '..-',    (0,4),      1,    'vowl'    ),
    4297147083:  ( 'Yankee',   'Y',    89,     232,     21,   '-.--',   (0,8),      3,    'vowl'    ),
    4297256046:  ( 'Bravo',    'B',    66,     194,     25,   '-...',   (12,2),     3,    'cons'    ),
    4298140290:  ( 'Charlie',  'C',    67,     195,     14,   '-.-.',   (12,3),     1,    'cons'    ),
    5036185622:  ( 'Delta',    'D',    68,     196,     9,    '-..',    (12,4),     2,    'cons'    ),
    5036854221:  ( 'Foxtrot',  'F',    70,     198,     13,   '..-.',   (12,6),     3,    'cons'    ),
    5037458768:  ( 'Golf',     'G',    71,     199,     26,   '--.',    (12,7),     2,    'cons'    ),
    5035556903:  ( 'Hotel',    'H',    72,     200,     20,   '....',   (12,8),     3,    'cons'    ),
    5037119814:  ( 'Juliett',  'J',    74,     209,     11,   '.---',   (11,1),     2,    'cons'    ),
    5035556831:  ( 'Kilo',     'K',    75,     210,     15,   '-.-',    (11,2),     3,    'cons'    ),
    4296755665:  ( 'Lima',     'L',    76,     211,     18,   '.-..',   (11,3),     2,    'cons'    ),
    5035557110:  ( 'Mike',     'M',    77,     212,     28,   '--',     (11,4),     4,    'cons'    ),
    5037118125:  ( 'November', 'N',    78,     213,     12,   '-.',     (11,5),     3,    'cons'    ),
    5000423356:  ( 'Papa',     'P',    80,     215,     22,   '.--.',   (11,7),     2,    'cons'    ),
    5000923300:  ( 'Quebec',   'Q',    81,     216,     23,   '--.-',   (11,8),     2,    'cons'    ),
    5000969482:  ( 'Romeo',    'R',    82,     217,     10,   '.-.',    (11,9),     3,    'cons'    ),
    5035943840:  ( 'Sierra',   'S',    83,     226,     5,    '...',    (0,2),      1,    'cons'    ),
    5045251209:  ( 'Tango',    'T',    84,     227,     16,   '-',      (0,3),      2,    'cons'    ),
    5000168680:  ( 'Victor',   'V',    86,     229,     30,   '...-',   (0,5),      2,    'cons'    ),
    4296684445:  ( 'Whiskey',  'W',    87,     230,     19,   '.--',    (0,6),      4,    'cons'    ),
    5000923277:  ( 'Xray',     'X',    88,     231,     29,   '-..-',   (0,7),      2,    'cons'    ),
    4296215569:  ( 'Zulu',     'Z',    90,     233,     17,   '--..',   (0,9),      3,    'cons'    ),
}

假设我想对辅音进行一些处理。而且由于处理需要很多时间（想想几天），我想分块进行。在这种情况下，假设一次有 4 个辅音。我提前知道组开始的键，例如：

vowlbeg = 4296433290 # key of first vowel
consbeg = 4297256046 # key of first consonant

但我不知道如何利用这种预知。例如，要处理第 8 到第 11 个辅音，我能做的最好的事情是：

beg = 8 # begin processing with 8th consonant
end = 12 # end processing with 11th consonant
kind = 'cons' # desired group
i=-1
for d in dd.items():
    if d[1][-1] is not kind: continue
    i += 1
    if i < beg: continue
    if i >= end: break
    print('processing:', i, d)

这给出了期望的结果，尽管有点慢，因为我从头开始浏览整个字典，直到遇到所需的条目。

processing: 8 (5035556831, ('Kilo', 'K', 75, 210, 15, '-.-', (11, 2), 3, 'cons'))
processing: 9 (4296755665, ('Lima', 'L', 76, 211, 18, '.-..', (11, 3), 2, 'cons'))
processing: 10 (5035557110, ('Mike', 'M', 77, 212, 28, '--', (11, 4), 4, 'cons'))
processing: 11 (5037118125, ('November', 'N', 78, 213, 12, '-.', (11, 5), 3, 'cons'))

我想我可以使用列表或字典理解更紧凑地表达这个循环，但似乎会在内存中产生巨大的重复。也许上面的方法也能做到这一点，我不是 100% 确定。

我对订购词典的了解

问：有没有更好的方法来做到这一点？ 我的备用计划是咬紧牙关，保留一组重复的元组，每组一个，以便能够对其进行切片。但这基本上会使我的记忆加倍，据我所知。

注意：这个愚蠢的例子并不明显，但是能够通过单个字典中的键访问条目在我的应用程序中是一个巨大的优势。

标签： pythonpython-3.xordereddict

解决方案

与其复制整个字典，还有一个更简单的方案，您只需复制另一个链表中的所有键即可。

dd_list = LinkedList("4296433290", "5046716526", "5000200584", ... "4296215569")

在原始字典中，在每个条目中，还保留对与该键对应的链表条目的引用：

dd = { 
    4296433290:  ( <reference to the linked-list entry of 4296433290>, 'Alfa', ...),
    5046716526:  ( <reference to the linked-list entry of 5046716526>, 'Echo', ...),
    .....
    .....
    .....
    4296215569:  ( <reference to the linked-list entry of 4296215569>, 'Zulu', ...)
}

现在，如果您想在距离 5 个条目的距离处迭代 3 个条目4297256046，您只需要执行以下操作：

entry_iterator = dd['4297256046'][0]
i = 0
while i < 5:
    # Skip 5 entries
    entry_iterator = entry_iterator.next()
    i += 1

num_iterations = 0
while num_iterations < 3:
    key = entry_iterator.value
    entry = dd[key]
    process_entry(entry)
    entry_iterator = entry_iterator.next()
    num_iterations += 1

现在我提到链表的原因是，如果您想从地图中删除任何条目，您还可以及时从链表中删除相应的条目O(1)。
如果没有删除，您可以只使用常规数组，并将整数数组索引保持为<reference to the linked-list entry of ...>.

请注意，默认情况下 Python 没有任何链表数据结构。但是，您将能够在线找到大量高质量的实现。

编辑：

数组案例的示例代码：

dd_list = ["4296433290", "5046716526", "5000200584", ... "4296215569"]

dd = { 
    4296433290:  ( 0, 'Alfa', ...),
    5046716526:  ( 1, 'Echo', ...),
    .....
    .....
    .....
    4296215569:  ( 25, 'Zulu', ...)
}

entry_index = dd['4297256046'][0]
# Skip 5 entries
entry_index += 5

num_iterations = 0
while num_iterations < 3:
    key = dd_list[entry_index]
    entry = dd[key]
    process_entry(entry)
    entry_index += 1
    num_iterations += 1

推荐阅读