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

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

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

列表

覆盖

Python

区间

36 条回复 • 2018-09-13 14:21:23 +08:00

DCjanus

2018-09-12 13:52:50 +08:00 via Android

数据的取值区间是多少？

lanceK

2018-09-12 14:01:55 +08:00

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

xavierskip

2018-09-12 14:15:56 +08:00 via Android

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

lanceK

2018-09-12 14:21:54 +08:00

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

sunnyadamm

2018-09-12 17:06:26 +08:00

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

vimiix

2018-09-12 18:24:23 +08:00

怎么两层就溢出了。

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

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

return a

这样应该不会溢出吧

ipwx

2018-09-12 18:36:40 +08:00 via iPhone

线段树

nooper

2018-09-12 19:15:48 +08:00

pandas, query. numpy apply.

nooper

2018-09-12 19:16:06 +08:00

bitmap

scriptB0y

2018-09-12 19:24:23 +08:00

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

2018-09-12 19:49:33 +08:00

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

takeoffyoung

2018-09-12 20:27:33 +08:00

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

lanceK

2018-09-12 21:53:58 +08:00

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

lanceK

2018-09-12 21:55:07 +08:00

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

huangzhe8263

2018-09-12 22:00:48 +08:00

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

baojiweicn2

2018-09-12 22:09:33 +08:00 via iPhone

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

widewing

2018-09-12 22:19:46 +08:00 via Android

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

lanceK

2018-09-12 22:31:58 +08:00

@takeoffyoung 非常感谢大神~

DCjanus

2018-09-12 22:59:49 +08:00

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

2018-09-12 23:00:29 +08:00

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

2018-09-12 23:02:24 +08:00

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

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

lanceK

2018-09-12 23:15:30 +08:00

@ipwx 厉害了，多谢~

lanceK

2018-09-12 23:29:33 +08:00

@nooper 牛掰了，多谢

lanceK

2018-09-12 23:30:21 +08:00

@scriptB0y 谢谢~

lanceK

2018-09-12 23:31:36 +08:00

@huangzhe8263 谢谢~

lanceK

2018-09-12 23:32:30 +08:00

@widewing 谢谢啦~

lanceK

2018-09-12 23:33:54 +08:00

@DCjanus 好思路，多谢~

lanceK

2018-09-12 23:35:20 +08:00

@xpresslink 好的，谢谢啦~

lanceK

2018-09-12 23:35:59 +08:00

@DCjanus 哈哈嗯

vimiix

2018-09-13 10:03:13 +08:00

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

sunnyadamm

2018-09-13 12:01:41 +08:00

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

sunnyadamm

2018-09-13 12:22:23 +08:00 via Android

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

lanceK

2018-09-13 12:58:05 +08:00

@vimiix 对的~

lanceK

2018-09-13 12:58:18 +08:00

@sunnyadamm 没毛病哈哈

sunnyadamm

2018-09-13 13:18:39 +08:00 via Android

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

lanceK

2018-09-13 14:21:23 +08:00

@sunnyadamm nice~~

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

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