使用带有不匹配索引的 pandas .loc 时内存爆炸+分配导致重复轴错误

Question

这是从大多数Pythonic方式将pandas单元与条件连接起来的观察\n我无法理解为什么第三个解决方案比第一个解决方案需要更多的内存。

\n

\n

• 如果我不采样第三个解决方案不会给出运行时错误，显然有些事情很奇怪

  \n
\n

• 为了模拟大型数据帧，我尝试重新采样，但没想到会遇到这种错误

  \n
\n

\n

背景

\n

非常不言自明，一行，看起来Pythonic

\n

df[\'city\'] + (df[\'city\'] == \'paris\')*(\'_\' + df[\'arr\'].astype(str))\n

\n

s = """city,arr,final_target\nparis,11,paris_11\nparis,12,paris_12\ndallas,22,dallas\nmiami,15,miami\nparis,16,paris_16"""\nimport pandas as pd\nimport io\ndf = pd.read_csv(io.StringIO(s)).sample(1000000, replace=True)\ndf\n

\n

速度

\n

s = """city,arr,final_target\nparis,11,paris_11\nparis,12,paris_12\ndallas,22,dallas\nmiami,15,miami\nparis,16,paris_16"""\nimport pandas as pd\nimport io\ndf = pd.read_csv(io.StringIO(s)).sample(1000000, replace=True)\ndf\n

\n

%%timeit\ndf[\'city\'] + (df[\'city\'] == \'paris\')*(\'_\' + df[\'arr\'].astype(str))\n# 877 ms \xc2\xb1 19.2 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n

\n

如果我不采样，则不会出现错误，并且输出也完全匹配

\n

错误（已更新）（仅当我从数据帧采样时发生）

\n

%%timeit\ndf[\'final_target\'] = np.where(df[\'city\'].eq(\'paris\'), \n                              df[\'city\'] + \'_\' + df[\'arr\'].astype(str), \n                              df[\'city\'])\n# 874 ms \xc2\xb1 19.2 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n

\n

MemoryError: Unable to allocate 892. GiB for an array with shape (119671145392,) and data type int64\n

\n

对于较小的输入（样本大小 100），我们会得到不同的错误，说明由于大小不同而出现的问题，但是内存分配和采样是怎么回事？

\n

ValueError: cannot reindex from a duplicate axis\n---------------------------------------------------------------------------\nValueError                                Traceback (most recent call last)\n<ipython-input-5-57c5b10090b2> in <module>\n      1 df[\'final_target\'] = df[\'city\']\n----> 2 df.loc[df[\'city\'] == \'paris\', \'final_target\'] +=  \'_\' + df[\'arr\'].astype(str)\n\n~/anaconda3/lib/python3.8/site-packages/pandas/core/ops/methods.py in f(self, other)\n     99             # we are updating inplace so we want to ignore is_copy\n    100             self._update_inplace(\n--> 101                 result.reindex_like(self, copy=False), verify_is_copy=False\n    102             )\n    103 \n

\n

我每次都从头开始重新运行它们

\n

更新

\n

这是我想到的一部分

\n

s = """city,arr,final_target\nparis,11,paris_11\nparis,12,paris_12\ndallas,22,dallas\nmiami,15,miami\nparis,16,paris_16"""\nimport pandas as pd\nimport io\ndf = pd.read_csv(io.StringIO(s)).sample(10, replace=True)\ndf\n

\n

    city    arr final_target\n1   paris   12  paris_12\n0   paris   11  paris_11\n2   dallas  22  dallas\n2   dallas  22  dallas\n3   miami   15  miami\n3   miami   15  miami\n2   dallas  22  dallas\n1   paris   12  paris_12\n0   paris   11  paris_11\n3   miami   15  miami\n

\n

\n

• 放回抽样时指数会重复

  \n
\n

• 因此，即使 df.arr 和 df.loc 的大小本质上不同，重置索引也可以解决问题，或者替换为df.loc[df[\'city\'] == \'paris\', \'arr\'].astype(str)可以解决问题。正如2e0byo指出的那样。

  \n
\n

• 仍然有人可以解释 .loc 是如何工作的，以及当索引中有重复项并且不匹配时内存爆炸？！

  \n
\n

\n

Answer 1

@2e0byo一针见血地表示 pandas 的算法在这种情况下“效率低下”。

就目前而言.loc，它并没有真正做出什么了不起的事情。它在这里的使用类似于使用相同形状的布尔数组来索引 numpy 数组，并添加对特定列的类似字典键的访问 - 也就是说，它df['city'] == 'paris'本身就是一个数据帧，具有相同的行数和相同的行数。索引为df，具有单列布尔值。df.loc[df['city'] == 'paris']然后给出一个数据框，仅包含正确的行df['city'] == 'paris'（在“城市”列中具有“巴黎”）。添加附加参数“final_target”则仅返回这些行的“final_target”列，而不是全部三列（并且因为它只有一列，所以从技术上讲它是一个Series对象 - 也是如此df['arr']）。

当 pandas 实际尝试添加两个系列时，就会发生内存爆炸。正如 @2e0byo 指出的，它必须重塑 Series 才能做到这一点，并且它通过调用第一个 Series 的align()方法来做到这一点。在操作期间align，函数使用三个参数pandas.core.reshape.merge.get_join_indexers()调用pandas._libs.join.full_outer_join() （第 155 行）left ： 、right和max_groups（澄清点：这些是它们在函数中的名称full_outer_join）。left和right是包含两个 Series 对象的索引（索引列中的值）的整数数组，并且是或max_groups中唯一元素的最大数量（在我们的例子中，为 5，对应于 中的五个原始行）。leftrights

full_outer_join立即转动并调用pandas._libs.algos.groupsort_indexer() （第 194 行），一次使用leftandmax_groups作为参数，一次使用rightand max_groups。groupsort_indexer返回两个数组 - 一般而言，indexerand counts（对于调用 with left，它们称为left_sorterand left_count，相应地称为 for right）。counts具有 length max_groups + 1，每个元素（第一个元素除外，未使用）包含相应索引组在输入数组中出现的次数。因此，对于我们的例子， with max_groups = 5，count数组的形状为，元素 1-5 表示 5 个唯一索引值出现在和(6,)中的次数。leftright

构造另一个数组 ，indexer以便用它索引原始输入数组返回按升序分组的所有元素 - 因此是“排序器”。left对和完成此操作后right，full_outer_join将两个分类器切碎并将它们彼此相对地串起来。full_outer_join返回两个相同大小的数组，left_idx并且right_idx- 这些数组变得非常大并抛出错误。排序器中元素的顺序决定了它们在最后两个输出数组中出现的顺序，而count数组又决定了每个元素出现的频率。由于left先行，因此它的元素保持在一起 - 在 中left_idx，中的第一个left_count[1]元素每个left_sorter重复right_count[1]一次（aaabbbccc ...）。在 中的同一位置right_idx，第一个right_count[1]元素连续重复多次left_count[1]（abcabcabc...）。（方便的是，由于0in 中的行s是'paris'一行，left_count[1]并且right_count[1]始终相等，因此您会得到x次重复次数x次开始）。然后 的下一个left_count[2]元素left_sorter会重复right_count[2]多次，依此类推...如果任何元素counts为零，则idx数组中的相应点将填充 -1，稍后将被屏蔽（如，right_count[i] = 0表示 中的元素right_idx为 -1，反之亦然 - 和 总是这种情况left_count[3]，left_count[4]因为 rows2和3ins是非'paris'）。

最后，_idx数组的元素数量等于N_elements，可以如下计算：

left_nonzero = (left_count[1:] != 0)
right_nonzero = (right_count[1:] != 0)
left_repeats = left_count[1:]*left_nonzero + np.ones(len(left_counts)-1)*(1 - left_nonzero)
right_repeats = right_count[1:]*right_nonzero + np.ones(len(right_counts)-1)*(1 - right_nonzero)
N_elements = sum(left_repeats*right_repeats)

将数组的相应元素count相乘（将所有零替换为一），然后相加得到N_elements。

您可以看到这个数字增长得很快 ( O(n^2))。对于具有 1,000,000 个采样行的原始数据帧，每个行的出现大致相等，则count数组看起来类似于：

left_count = array([0, 2e5, 2e5, 0, 0, 2e5])
right_count = array([0, 2e5, 2e5, 2e5, 2e5, 2e5])

总长度约为1.2e11. 一般来说，对于初始样本N( df = pd.read_csv(io.StringIO(s)).sample(N, replace=True))，最终大小约为0.12*N**2

一个例子

看一个小例子可能会很有帮助，看看他们在制作这些巨大的数组时会做什么full_outer_join以及groupsort_indexer正在尝试做什么。我们将从仅 10 行的小样本开始，并遵循各种数组直至最终输出，left_idx并且right_idx。我们将从定义初始数据帧开始：

df = pd.read_csv(io.StringIO(s)).sample(10, replace=True)
df['final_target'] = df['city'] # this line doesn't change much, but meh

看起来像：

     city  arr final_target
3   miami   15        miami
1   paris   11        paris
0   paris   12        paris
0   paris   12        paris
0   paris   12        paris
1   paris   11        paris
2  dallas   22       dallas
3   miami   15        miami
2  dallas   22       dallas
4   paris   16        paris

df.loc[df['city'] == 'paris', 'final_target']好像：

1    paris
0    paris
0    paris
0    paris
1    paris
4    paris

和df['arr'].astype(str)：

3    15
1    11
0    12
0    12
0    12
1    11
2    22
3    15
2    22
4    16

然后，在对 的调用中full_outer_join，我们的参数如下所示：

left = array([1,0,0,0,1,4])            # indexes of df.loc[df['city'] == 'paris', 'final_target']
right = array([3,1,0,0,0,1,2,3,2,4])   # indexes of df['arr'].astype(str)
max_groups = 5                         # the max number of unique elements in either left or right

函数调用groupsort_indexer(left, max_groups)返回以下两个数组：

left_sorter = array([1, 2, 3, 0, 4, 5])
left_count = array([0, 3, 2, 0, 0, 1])

left_count保存 中每个唯一值的出现次数left- 第一个元素未使用，但 中存在 3 个零、2 个一、0 个二、0 个三和 1 个四left。

left_sorter就是这样left[left_sorter] = array([0, 0, 0, 1, 1, 4])——一切都井井有条。

现在right：groupsort_indexer(right, max_groups)返回

right_sorter = array([2, 3, 4, 1, 5, 6, 8, 0, 7, 9])
right_count = array([0, 3, 2, 2, 2, 1])

再次right_count包含每个计数出现的次数：未使用的第一个元素，然后是 3 个零、2 个一、2 个二、2 个三和 1 个四（请注意，两个count数组的元素 1、2 和 5 是相同的） ：这些是 )s中的行'city' = 'paris'。还，right[right_sorter] = array([0, 0, 0, 1, 1, 2, 2, 3, 3, 4])

计算完两个count数组后，我们可以计算数组的大小idx（使用实际数字比使用上面的公式更简单）：

N_total = 3*3 + 2*2 + 2 + 2 + 1*1 = 18

3是两个数组的元素 1 counts，因此我们可以期待类似[1,1,1,2,2,2,3,3,3]to start left_idx，[1,2,3]sincestartsleft_sorter和[2,3,4,2,3,4,2,3,4]to start right_idx，right_sortersincebeginswith 的内容[2,3,4]。然后我们有两个，所以[0,0,4,4]forleft_idx和[1,5,1,5]for right_idx。然后left_count有两个零，并且right_count有两个二，所以接下来-1进入 4 left_idx，接下来的四个元素right_sorter进入right_idx: [6,8,0,7]。两者count都以 1 结尾，因此sorters将idx: 5forleft_idx和9for中 go 中的最后一个元素各为 1 right_idx，留下：

left_idx  = array([1, 1, 1, 2, 2, 2, 3, 3, 3, 0, 0, 4, 4,-1, -1, -1, -1, 5])
right_idx = array([2, 3, 4, 2, 3, 4, 2, 3, 4, 1, 5, 1, 5, 6,  8,  0 , 7, 9])

这确实是 18 个元素。

由于两个索引数组具有相同的形状，pandas 可以从原始数组构造两个相同形状的 Series 来执行所需的任何操作，然后它可以屏蔽这些数组以获取排序后的索引。使用一个简单的布尔过滤器来查看我们刚刚如何排序left以及right输出，我们得到：

left[left_idx[left_idx != -1]] = array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 4])
right[right_idx[right_idx != -1]] = array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4])

回溯所有函数调用和模块后，此时相加的结果为：

0    paris_12
0    paris_12
0    paris_12
0    paris_12
0    paris_12
0    paris_12
0    paris_12
0    paris_12
0    paris_12
1    paris_11
1    paris_11
1    paris_11
1    paris_11
2         NaN
2         NaN
3         NaN
3         NaN
4    paris_16

它位于（第 11066 行result）行result = op(self, other)中，其中包含和以及我们之前添加的两个系列。pandas.core.generic.NDFrame._inplace_methodop = pandas.core.series.Series.__add__selfother

因此，据我所知，pandas 基本上尝试对相同索引行的每个组合执行操作（例如，1第一个系列中具有索引的任何和所有行都应该与1其他系列中的所有行索引一起操作）。如果其中一个系列具有另一个系列没有的索引，则这些行将被屏蔽。在这种情况下，具有相同索引的每一行都是相同的。只要您不需要在适当的位置执行任何操作，它就可以工作（尽管是多余的） - 当 pandas 尝试将此结果重新索引回原始 dataframe 的形状时，小 dataframe 的麻烦就会出现df。

分割线（较小的数据帧可以通过的线，但较大的数据帧则不能）是result = op(self, other)上面的那条线。随后在同一个函数中（称为，注意，_inplace_method），程序在 处退出self._update_inplace(result.reindex_like(self, copy=False), verify_is_copy=False)。它尝试重新索引result，使其看起来像self，因此可以替换self为result(self是原始系列，添加中的第一个，df.loc[df['city'] == 'paris', 'final_target'])。这就是较小的情况失败的地方，因为显然result有一堆重复的索引，并且 pandas 不希望在删除其中一些索引时丢失任何信息。

最后一件事

可能值得一提的是，这种行为并不是此处的加法运算所特有的。每当您尝试对两个具有大量重复索引的大型数据帧进行算术运算时，都会发生这种情况 - 例如，尝试以与第一个数据帧完全相同的方式定义第二个数据帧，df2 = pd.read_csv(io.StringIO(s)).sample(1000000, replace=True)然后尝试运行df.arr*df2.arr。你会得到同样的内存错误。

有趣的是，逻辑和比较运算符具有防止这样做的保护措施 - 它们需要相同的索引，并在调用其运算符方法之前检查它。

我在 pandas 1.2.4、python 3.7.10 中完成了所有工作，但我提供了 pandas Github 的链接，目前版本为 1.3.3。据我所知，差异不会影响结果。