V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
lanceK
V2EX  ›  Python

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

  •  
  •   lanceK · 2018-09-12 11:24:54 +08:00 · 3546 次点击
    这是一个创建于 2249 天前的主题,其中的信息可能已经有所发展或是发生改变。
    具体比如:
    [[15, 65], [30, 80], [36, 86], [45, 95], [45, 95]]  一个大列表中嵌套了好多小列表,如何统计区间内的每个点被覆盖了几次呢? 比如如果只看 [15, 65], [30, 80]这两个,30-65 这些点就被覆盖了两次

    注:因为数据量大,所以当我用两层循环来做的时候内存溢出。。。无奈不知道怎么搞,还请各位大神帮忙,先行谢过!
    36 条回复    2018-09-13 14:21:23 +08:00
    DCjanus
        1
    DCjanus  
       2018-09-12 13:52:50 +08:00 via Android
    数据的取值区间是多少?
    lanceK
        2
    lanceK  
    OP
       2018-09-12 14:01:55 +08:00
    @DCjanus 你好,每一条区间都是 50,最小点是 15, 最大点是 249238172
    xavierskip
        3
    xavierskip  
       2018-09-12 14:15:56 +08:00 via Android
    内存溢出和循环关系不大吧。
    既然每个区间差值都是 50,一层循环就够了。
    lanceK
        4
    lanceK  
    OP
       2018-09-12 14:21:54 +08:00
    @xavierskip 请问一层循环怎么统计呢?
    sunnyadamm
        5
    sunnyadamm  
       2018-09-12 17:06:26 +08:00
    for。。。
    if。。。
    count+=1
    vimiix
        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

    这样应该不会溢出吧
    ipwx
        7
    ipwx  
       2018-09-12 18:36:40 +08:00 via iPhone
    线段树
    nooper
        8
    nooper  
       2018-09-12 19:15:48 +08:00
    pandas, query. numpy apply.
    nooper
        9
    nooper  
       2018-09-12 19:16:06 +08:00
    bitmap
    scriptB0y
        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
    takeoffyoung
        11
    takeoffyoung  
       2018-09-12 19:49:33 +08:00
    1. 把区间端点映射到有限区间内
    2. 差分前缀扫一遍
    3. 后续操作就看需求了
    takeoffyoung
        12
    takeoffyoung  
       2018-09-12 20:27:33 +08:00   ❤️ 1
    lanceK
        13
    lanceK  
    OP
       2018-09-12 21:53:58 +08:00
    @sunnyadamm 老铁注意看是两层 list 嵌套,真要这么简单我就不问了。。。 不过还是谢谢哈哈
    lanceK
        14
    lanceK  
    OP
       2018-09-12 21:55:07 +08:00
    @vimiix 我一开始就是这么做的,电脑也是这么崩的 (手动笑哭)
    huangzhe8263
        15
    huangzhe8263  
       2018-09-12 22:00:48 +08:00
    一个求巧的方法就是不要用 python 自带的数据结构
    转成用 numpy 存...
    baojiweicn2
        16
    baojiweicn2  
       2018-09-12 22:09:33 +08:00 via iPhone
    首先:矩阵类运算用 numpy,其次:数据爆内存了就别放内存,db or nosql db 都是很好的选择,最后,我觉得矩阵运算一下不会爆啊?你 po 下实现代码
    widewing
        17
    widewing  
       2018-09-12 22:19:46 +08:00 via Android
    把所有数值进行排序。然后遍历,遇到是左边的数则+1,右边的数则-1 即可。复杂度 nlogn
    lanceK
        18
    lanceK  
    OP
       2018-09-12 22:31:58 +08:00
    @takeoffyoung 非常感谢大神~
    DCjanus
        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;
    ```
    xpresslink
        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.]
    DCjanus
        21
    DCjanus  
       2018-09-12 23:02:24 +08:00
    由于 Python 自带的 List 默认内存拓展策略,你可能手动设定 capacity 会内存占用更少。

    不过如果是我,没有其他性能需求,一般会比较懒,直接放 PostgreSQL 一把梭了。
    lanceK
        22
    lanceK  
    OP
       2018-09-12 23:15:30 +08:00
    @ipwx 厉害了,多谢~
    lanceK
        23
    lanceK  
    OP
       2018-09-12 23:29:33 +08:00
    @nooper 牛掰了,多谢
    lanceK
        24
    lanceK  
    OP
       2018-09-12 23:30:21 +08:00
    @scriptB0y 谢谢~
    lanceK
        25
    lanceK  
    OP
       2018-09-12 23:31:36 +08:00
    @huangzhe8263 谢谢~
    lanceK
        26
    lanceK  
    OP
       2018-09-12 23:32:30 +08:00
    @widewing 谢谢啦~
    lanceK
        27
    lanceK  
    OP
       2018-09-12 23:33:54 +08:00
    @DCjanus 好思路,多谢~
    lanceK
        28
    lanceK  
    OP
       2018-09-12 23:35:20 +08:00
    @xpresslink 好的,谢谢啦~
    lanceK
        29
    lanceK  
    OP
       2018-09-12 23:35:59 +08:00
    @DCjanus 哈哈嗯
    vimiix
        30
    vimiix  
       2018-09-13 10:03:13 +08:00
    @DCjanus 把数据处理交给数据库是好方法。👍
    sunnyadamm
        31
    sunnyadamm  
       2018-09-13 12:01:41 +08:00
    @lanceK 我知道是两层嵌套,是你想复杂了
    sunnyadamm
        32
    sunnyadamm  
       2018-09-13 12:22:23 +08:00 via Android
    你现在的情况应该是量太大,导致爆内存了,可以参考前面楼层说的用数据库去处理
    lanceK
        33
    lanceK  
    OP
       2018-09-13 12:58:05 +08:00
    @vimiix 对的~
    lanceK
        34
    lanceK  
    OP
       2018-09-13 12:58:18 +08:00
    @sunnyadamm 没毛病哈哈
    sunnyadamm
        35
    sunnyadamm  
       2018-09-13 13:18:39 +08:00 via Android
    @lanceK 大量数据扔到 pc 机内存去处理肯定是不合适的,所以说你要么就放库里,要么就用服务器吧😂😂😂。我有的时候处理数据就用的单位的空转的服务器,速度杠杠的,美滋滋
    lanceK
        36
    lanceK  
    OP
       2018-09-13 14:21:23 +08:00
    @sunnyadamm nice~~
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2812 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 02:04 · PVG 10:04 · LAX 18:04 · JFK 21:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.