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

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

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

列表

覆盖

Python

区间

36 replies • 2018-09-13 14:21:23 +08:00

DCjanus

Sep 12, 2018 via Android

数据的取值区间是多少？

lanceK

Sep 12, 2018

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

C0VN

Sep 12, 2018 via Android

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

lanceK

Sep 12, 2018

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

sunnyadamm

Sep 12, 2018

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

vimiix

Sep 12, 2018

怎么两层就溢出了。

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

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

return a

这样应该不会溢出吧

ipwx

Sep 12, 2018 via iPhone

线段树

nooper

Sep 12, 2018

pandas, query. numpy apply.

nooper

Sep 12, 2018

bitmap

scriptB0y

Sep 12, 2018

我跟 @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

Sep 12, 2018

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

takeoffyoung

Sep 12, 2018

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

lanceK

Sep 12, 2018

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

lanceK

Sep 12, 2018

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

huangzhe8263

Sep 12, 2018

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

baojiweicn2

Sep 12, 2018 via iPhone

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

widewing

Sep 12, 2018 via Android

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

lanceK

Sep 12, 2018

@takeoffyoung 非常感谢大神~

DCjanus

Sep 12, 2018

如果每个区间都是确定的上下界差值 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

Sep 12, 2018

#!/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.]

DCjanus

Sep 12, 2018

由于 Python 自带的 List 默认内存拓展策略，你可能手动设定 capacity 会内存占用更少。

不过如果是我，没有其他性能需求，一般会比较懒，直接放 PostgreSQL 一把梭了。

lanceK

Sep 12, 2018

@ipwx 厉害了，多谢~

lanceK

Sep 12, 2018

@nooper 牛掰了，多谢

lanceK

Sep 12, 2018

@scriptB0y 谢谢~

lanceK

Sep 12, 2018

@huangzhe8263 谢谢~

lanceK

Sep 12, 2018

@widewing 谢谢啦~

lanceK

Sep 12, 2018

@DCjanus 好思路，多谢~

lanceK

Sep 12, 2018

@xpresslink 好的，谢谢啦~

lanceK

Sep 12, 2018

@DCjanus 哈哈嗯

vimiix

Sep 13, 2018

@DCjanus 把数据处理交给数据库是好方法。👍

sunnyadamm

Sep 13, 2018

@lanceK 我知道是两层嵌套，是你想复杂了

sunnyadamm

Sep 13, 2018 via Android

你现在的情况应该是量太大，导致爆内存了，可以参考前面楼层说的用数据库去处理

lanceK

Sep 13, 2018

@vimiix 对的~

lanceK

Sep 13, 2018

@sunnyadamm 没毛病哈哈

sunnyadamm

Sep 13, 2018 via Android

@lanceK 大量数据扔到 pc 机内存去处理肯定是不合适的，所以说你要么就放库里，要么就用服务器吧😂😂😂。我有的时候处理数据就用的单位的空转的服务器，速度杠杠的，美滋滋

lanceK

Sep 13, 2018

@sunnyadamm nice~~

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

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