1
DCjanus 2018-09-12 13:52:50 +08:00 via Android
数据的取值区间是多少?
|
3
xavierskip 2018-09-12 14:15:56 +08:00 via Android
内存溢出和循环关系不大吧。
既然每个区间差值都是 50,一层循环就够了。 |
4
lanceK OP @xavierskip 请问一层循环怎么统计呢?
|
5
sunnyadamm 2018-09-12 17:06:26 +08:00
for。。。
if。。。 count+=1 |
6
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 这样应该不会溢出吧 |
7
ipwx 2018-09-12 18:36:40 +08:00 via iPhone
线段树
|
8
nooper 2018-09-12 19:15:48 +08:00
pandas, query. numpy apply.
|
9
nooper 2018-09-12 19:16:06 +08:00
bitmap
|
10
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 |
11
takeoffyoung 2018-09-12 19:49:33 +08:00
1. 把区间端点映射到有限区间内
2. 差分前缀扫一遍 3. 后续操作就看需求了 |
12
takeoffyoung 2018-09-12 20:27:33 +08:00 1
|
13
lanceK OP @sunnyadamm 老铁注意看是两层 list 嵌套,真要这么简单我就不问了。。。 不过还是谢谢哈哈
|
15
huangzhe8263 2018-09-12 22:00:48 +08:00
一个求巧的方法就是不要用 python 自带的数据结构
转成用 numpy 存... |
16
baojiweicn2 2018-09-12 22:09:33 +08:00 via iPhone
首先:矩阵类运算用 numpy,其次:数据爆内存了就别放内存,db or nosql db 都是很好的选择,最后,我觉得矩阵运算一下不会爆啊?你 po 下实现代码
|
17
widewing 2018-09-12 22:19:46 +08:00 via Android
把所有数值进行排序。然后遍历,遇到是左边的数则+1,右边的数则-1 即可。复杂度 nlogn
|
18
lanceK OP @takeoffyoung 非常感谢大神~
|
19
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; ``` |
20
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.] |
21
DCjanus 2018-09-12 23:02:24 +08:00
由于 Python 自带的 List 默认内存拓展策略,你可能手动设定 capacity 会内存占用更少。
不过如果是我,没有其他性能需求,一般会比较懒,直接放 PostgreSQL 一把梭了。 |
25
lanceK OP @huangzhe8263 谢谢~
|
28
lanceK OP @xpresslink 好的,谢谢啦~
|
31
sunnyadamm 2018-09-13 12:01:41 +08:00
@lanceK 我知道是两层嵌套,是你想复杂了
|
32
sunnyadamm 2018-09-13 12:22:23 +08:00 via Android
你现在的情况应该是量太大,导致爆内存了,可以参考前面楼层说的用数据库去处理
|
34
lanceK OP @sunnyadamm 没毛病哈哈
|
35
sunnyadamm 2018-09-13 13:18:39 +08:00 via Android
@lanceK 大量数据扔到 pc 机内存去处理肯定是不合适的,所以说你要么就放库里,要么就用服务器吧😂😂😂。我有的时候处理数据就用的单位的空转的服务器,速度杠杠的,美滋滋
|
36
lanceK OP @sunnyadamm nice~~
|