logo标签列表

如何在Python 3.7中遍历一个大型有序字典？

pythonpython-3.xordereddict
4
最近，我将一些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'))

我认为可以使用列表或者字典推导式更简洁地表达这个循环，但是似乎会在内存中创建大量重复的数据。也许上面的方法也是如此，我不确定。

关于我的有序字典，我知道以下几点：

  • 组，例如元音和辅音，确实被分组而不是散布。
  • 在每个组内，条目按已知的期望顺序排序。
  • 每个组的开始键

Q：有更好的方法吗？我的备选方案是坚持并保留一组重复的元组，每组一个，以便能够对其进行切片。但是，就我所知，这将使我的内存翻倍。

注意：从这个简单的例子中不能看出来，但是能够在单个字典中通过键访问条目是我的应用程序的巨大优势。

1
字典是用于键查找的。您正在尝试通过（部分）值进行查找。您应该实现一个索引字典，将要查找的值映射到它们所在的一系列键序列。 - Klaus D.
1
你是否曾通过键访问数据？如果没有，请保留“有序”部分并将其作为列表。即使是这样，您也可以将键映射到它们在顺序中的索引，以便具有两种访问模式而不重复。 - Davis Herring
我确实通过键访问数据，事实上，这种用法是算法的主要核心。按顺序遍历列表的需求只是一个次要的行政任务。 - TheStumbler
4个回答
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', ...)
}

如果您想从4297256046开始，每隔5个元素遍历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)时间内从链表中删除相应的条目。
如果不需要删除操作，你可以使用普通的数组，并将整数数组索引作为“<参考链表项...>”。

请注意，默认情况下，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
我不确定我是否理解你的示例代码，但是你的概念是正确的。我可以在一个单独的列表中复制这些键。在我的应用程序中，我看不到使用链表的理由，因为字典基本上是常量。 - TheStumbler
那段代码只是伪代码，因为Python中没有内置的链表。如果它是常量，那么你可以简单地使用数组代替链表。我会为数组情况编辑代码。 - Anmol Singh Jaggi
检查修改。我还改进了旧代码。有一个错误。 - Anmol Singh Jaggi
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：创建类似于你的一些示例数据
  • 步骤2：展示结构
  • 步骤3：获取结构的字典键
  • 步骤4：展示在字典键的本机形式中无法跳转到列表中的特定点
  • 步骤5：将字典键实现为实际列表结构
  • 步骤6：演示从列表中任何位置获取键
  • 步骤7：使用任意键从字典中获取数据
最初的回答： 这是一个关于如何使用Python中的字典键获取数据的指南。首先，我们需要创建一些类似于您的示例数据，然后展示其结构并获取其字典键。尽管字典键的本机形式无法直接跳转到列表的特定点，但可以将其实现为实际列表结构，然后演示从列表的任何位置获取键，并使用任意键从字典中获取数据。
1

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

以下是一些建议：

  1. Look into storing this into a dataframe. There's a reason why the pandas package is widely adopted: it uses backend optimizations (someone correct me if I'm wrong: numpy, and by extension pandas, uses some C-style or actual C compilations) that trumps whatever base Python can do. This would be a fairly easy task with either pandas or dask and would perform reasonably well.

    # 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. If you're intent on using base Python structures, comprehensions is definitely the way to go. When you're trying to create a new "group" Python object (like lists, dicts or tuples) from another group Python object, comprehensions often scale way better than the standard "loop and append" tactic. the if-else loops should be left to things where you actually aren't creating new grouped objects. Even when you have some complicated control flow and logic to do before creating the new grouped object, i always elect to use comprehensions, and often just create "helper" functions for readability. I'd do it this way:

    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方法将优于基础代码。
0

如果您想尝试使用 dask 实现此操作，这里有两种可能的方法：

导入

import numpy as np
import pandas as pd
import dask.dataframe as ddd
from dask import delayed, compute
from dask.diagnostics import ProgressBar
import time

定义列名列表

h = [
    'phonetic',
    'letter',
    'ascii',
    'ebcedic',
    'baudot',
    'morse',
    'hollerith',
    'strokes',
    'kind'
    ]

使用（参见此SO帖子）从字典dd创建Dask DataFrame

def make_df(d):
    return pd.DataFrame.from_dict(d, orient='index')

dpd = [delayed(make_df)(dd)]
ddf = ddd.from_delayed(dpd)
ddf.columns = h
ddf.head()
           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

获取 DataFrame 中的分区数

print(ddf.npartitions)
1
  • 以下的2个Dask方法仅适用于DataFrame的一个分区。

Dask方法1 - 使用.map_partitions

  • 在这里，您定义了一个帮助函数来执行对kind列的切片，
%time
def slicer(df, kind):
    return df[df['kind']==kind]

ddf2 = ddf.map_partitions(slicer, 'cons', meta=ddf.head(1))
with ProgressBar():
    print(ddf2.reset_index().loc[slice(8-1,12-2)].compute().head())

CPU times: user 3 µs, sys: 1 µs, total: 4 µs
Wall time: 8.82 µs
[########################################] | 100% Completed |  0.1s
         index  phonetic letter  ascii  ebcedic  baudot morse hollerith  strokes  kind
7   5035556831      Kilo      K     75      210      15   -.-   (11, 2)        3  cons
8   4296755665      Lima      L     76      211      18  .-..   (11, 3)        2  cons
9   5035557110      Mike      M     77      212      28    --   (11, 4)        4  cons
10  5037118125  November      N     78      213      12    -.   (11, 5)        3  cons

Dask方法2 - 使用.loc

%time
with ProgressBar():
    print(ddf[ddf['kind'] == 'cons'].reset_index().loc[8-1:12-2].compute().head())

CPU times: user 4 µs, sys: 1 µs, total: 5 µs
Wall time: 9.06 µs
[########################################] | 100% Completed |  0.1s
         index  phonetic letter  ascii  ebcedic  baudot morse hollerith  strokes  kind
7   5035556831      Kilo      K     75      210      15   -.-   (11, 2)        3  cons
8   4296755665      Lima      L     76      211      18  .-..   (11, 3)        2  cons
9   5035557110      Mike      M     77      212      28    --   (11, 4)        4  cons
10  5037118125  November      N     78      213      12    -.   (11, 5)        3  cons

熊猫

%time
df = pd.DataFrame.from_dict(dd, orient='index', columns=h)
print(df[df['kind']=='cons'].reset_index().loc[slice(8-1,12-2)].head())

CPU times: user 3 µs, sys: 1 µs, total: 4 µs
Wall time: 8.82 µs
         index  phonetic letter  ascii  ebcedic  baudot morse hollerith  strokes  kind
7   5035556831      Kilo      K     75      210      15   -.-   (11, 2)        3  cons
8   4296755665      Lima      L     76      211      18  .-..   (11, 3)        2  cons
9   5035557110      Mike      M     77      212      28    --   (11, 4)        4  cons
10  5037118125  November      N     78      213      12    -.   (11, 5)        3  cons

编辑

当我运行@zero在他的回答中的方法时，我得到

%time
print(helper(dd,8,12,'cons'))
Wall time: 8.82 µs
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接