Python 如何统计大数据量的 嵌套列表的区间中各点的覆盖次数？

[lanceK]

具体比如：
[[15, 65], [30, 80], [36, 86], [45, 95], [45, 95]]  一个大列表中嵌套了好多小列表，如何统计区间内的每个点被覆盖了几次呢？ 比如如果只看 [15, 65], [30, 80]这两个，30-65 这些点就被覆盖了两次

注：因为数据量大，所以当我用两层循环来做的时候内存溢出。。。无奈不知道怎么搞，还请各位大神帮忙，先行谢过！

[DCjanus]

数据的取值区间是多少？

[lanceK]

@DCjanus 你好，每一条区间都是 50，最小点是 15， 最大点是 249238172

[xavierskip]

内存溢出和循环关系不大吧。
既然每个区间差值都是 50，一层循环就够了。

[lanceK]

@xavierskip 请问一层循环怎么统计呢？

[sunnyadamm]

for。。。
if。。。
count+=1

[vimiix]

怎么两层就溢出了。

# 造一个结果集
res = [1] * 50

# 然后一层循环, 往上面盖被子
for item in iter(big_list):
for i in range(item[0], item[1]+1):
a[i] += 1

return a

这样应该不会溢出吧

[ipwx]

线段树

[nooper]

pandas, query. numpy apply.

[nooper]

bitmap

[scriptB0y]

我跟 @sunnyadamm 想法一样。

In [3]: count = [0] * 249238172

In [4]: import sys

In [5]: sys.getsizeof(count)
Out[5]: 1993905440

In [6]: 1993905440 / 1024 / 1024
Out[6]: 1901.5364074707031

如果没算错的话需要 2G

[takeoffyoung]

1. 把区间端点映射到有限区间内
2. 差分前缀扫一遍
3. 后续操作就看需求了

[takeoffyoung]

https://paste.ubuntu.com/p/9GfrKmckvQ/

[lanceK]

@sunnyadamm 老铁注意看是两层 list 嵌套，真要这么简单我就不问了。。。 不过还是谢谢哈哈

[lanceK]

@vimiix 我一开始就是这么做的，电脑也是这么崩的 （手动笑哭）

[huangzhe8263]

一个求巧的方法就是不要用 python 自带的数据结构
转成用 numpy 存...

[baojiweicn2]

首先：矩阵类运算用 numpy，其次：数据爆内存了就别放内存，db or nosql db 都是很好的选择，最后，我觉得矩阵运算一下不会爆啊？你 po 下实现代码

[widewing]

把所有数值进行排序。然后遍历，遇到是左边的数则+1，右边的数则-1 即可。复杂度 nlogn

[lanceK]

@takeoffyoung 非常感谢大神~

[DCjanus]

如果每个区间都是确定的上下界差值 50，也就意味着每段的中点就可以表示这个区间。

那么[10, 60]就可以表示为 35，把所有 [x, y] 都转换为 ((x+y)/2) <即单个数字> 并对其按从小到大做排序，这样排出来的集合称为 L。

统计某个点，如 z 被覆盖的次数，就是在 L 中找到大于等于 z-25 且小于等于 z+25 的数字的个数。

数据量能在内存里放得下的话，就直接内存里排序好了，内存里放不下就放进数据库，查询起来也很简单，比如查询 40 被覆盖的数量：

```SQL
select count(*) from numbers where numbers.value<=65 and numbers.value>=15;
```

[xpresslink]

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np

MAX = 100

counter_array = np.zeros(MAX)

print(counter_array)

source_list = [[15, 65], [30, 80], [36, 86], [45, 95], [45, 95]]

for index_range in source_list: counter_array[np.arange(*index_range)] += 1

print(counter_array)

[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.
0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
[ 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1.
1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 2. 2. 2. 2. 2. 2.
3. 3. 3. 3. 3. 3. 3. 3. 3. 5. 5. 5. 5. 5. 5. 5. 5. 5.
5. 5. 5. 5. 5. 5. 5. 5. 5. 5. 5. 4. 4. 4. 4. 4. 4. 4.
4. 4. 4. 4. 4. 4. 4. 4. 3. 3. 3. 3. 3. 3. 2. 2. 2. 2.
2. 2. 2. 2. 2. 0. 0. 0. 0. 0.]