如何在python3.7中逐步浏览一个大的有序字典？

Question

最近，我将一些bash脚本重构到python3.7中，这既是一个学习练习，也是为了在项目中实际使用。最终的实现使用了一个非常大的有序字典，比如说大约200万到300万个条目。这种方式存储数据有一些显著的优点，可以降低代码复杂度和处理时间。然而，有一项任务我没有完成：如何从一个已知的起点逐步浏览字典。你知道吗

如果我在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%肯定。你知道吗

我对我订的字典的了解

• 元音和辅音等组确实是分组的，而不是分散的。你知道吗
• 在每个组中，条目按已知的、所需的顺序排序
• 每个组的开始键

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

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

Answer 1

根据经验，像这样通过循环处理大量数据是不可能的，因为这意味着您至少要使用字典大小的2倍（根据经验，它使用的RAM是字典字节大小的两倍）。你知道吗

几点建议：

1. 研究如何将其存储到数据帧中。pandas软件包之所以被广泛采用，有一个原因：它使用后端优化（如果我错了，有人会纠正我：numpy，并扩展为pandas，使用一些C风格或实际的C编译），这胜过了基础Python所能做的一切。无论是pandas还是dask，这都是一项相当简单的任务，而且会表现得相当好。你知道吗

   # file.py
   import pandas as pd
   
   cols =  ['key', 'phonetic', 'letter', 'ascii', 'ebcedic', 'baudot', 'morse',  'hollerith', 'strokes',  'kind']
   test = pd.DataFrame(dd).transpose().reset_index()
   
   test.columns = cols
   
   def get_letters(begin, end, kind):
       return test[test['kind'] == kind].reset_index(drop=True).iloc[begin-1:end-1]
   
   output = get_letters(8,12,'cons')
   
   final = output.set_index('key').transpose().to_dict('list')
   
   # runtime >>> mean 6.82 ms, std: 93.9 us
   

2. 如果您打算使用基本的Python结构，那么理解无疑是一种方法。当您试图从另一个组Python对象创建一个新的“组”Python对象（如lists、dicts或tuples）时，理解通常比标准的“循环和附加”策略扩展得更好。if-else循环应该留给实际上没有创建新分组对象的对象。即使在创建新的分组对象之前有一些复杂的控制流和逻辑要做，我也总是选择使用理解，并且通常只是创建“helper”函数以提高可读性。我会这样做：

   def helper(dictionary, begin, end, cons):
       filtered = {k:v for k,v in dictionary.items() if v[8] == 'cons'}
   
       return [d for n, d in enumerate(filtered.values()) if n in range(begin-1, end-1)]
   
   helper(dd,8,12,'cons')
   
   # runtime >>> mean: 1.61ms, std: 58.5 us
   

注意：尽管运行时似乎显示基本Python是一种更快的机制，但我有信心地说，在更大的字典上，pandas/dask方法的性能将优于基本代码

Answer 2

对于使用Python内置的简单解决方案，您可以创建一个键列表，然后从列表中的任何一点开始，代价是使用一些内存来具体化列表。下面是一个演示这一点的互动环节。你知道吗

使用这种技术在任意范围的键上进行循环应该很容易。你知道吗

1> data = {id: (id, "a") for id in range(10)}

2> data
{0: (0, 'a'), 1: (1, 'a'), 2: (2, 'a'), 3: (3, 'a'), 4: (4, 'a'), 5: (5, 'a'), 6: (6, 'a'), 7: (7, 'a'), 8: (8, 'a'), 9: (9, 'a')}

3> data.keys()
dict_keys([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

4> data.keys()[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'dict_keys' object does not support indexing

5> keys = list(data.keys())

6> keys[5]
5

7> data[keys[5]]
(5, 'a')

• 步骤1：创建一些与您的相似的示例数据
• 第二步：演示结构
• 步骤3：获取结构的dict\ u键
• 第4步：演示您不能跳转到dict\ u keys本机表单中列表中的特定点
• 步骤5：将dict\ u键具体化为实际的列表结构
• 步骤6：演示从列表中的任何位置获取密钥
• 步骤7：使用任意键从dict中提取数据

Answer 3

有一个更简单的方案，您只需要复制另一个链表中的所有键，而不是复制整个词典。你知道吗

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', ...)
}

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

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