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
going
V2EX  ›  Python

Python 高性能小算法

  •  
  •   going · 2021-03-23 17:55:09 +08:00 · 2357 次点击
    这是一个创建于 1180 天前的主题,其中的信息可能已经有所发展或是发生改变。

    如何高性能计算出一个列表相近 3 个数据的最大值和最小值?

    举例:如下列表临近 3 个数据的最大值和最小值 [1,2,3,4,5,7,8,9,10] 输出 最大值为:27 最小值为:6

    15 条回复    2021-04-21 17:26:16 +08:00
    hongch
        1
    hongch  
       2021-03-23 18:11:42 +08:00
    题目应该指明是无序数组吧?
    hehe12980
        2
    hehe12980  
       2021-03-23 18:14:45 +08:00
    随便给你写了一个
    def arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]
    if (arr.size() < 3) {
    return
    }
    int min = arr[0] + arr[1] + arr[2]
    int max = arr[0] + arr[1] + arr[2]
    int prefix = 0
    for (int i = 3; i < arr.size(); i++) {
    int sum = arr[i] + max - arr[prefix++]
    max = Math.max(max, sum)
    min = Math.min(max, min)
    }
    println(min)
    println(max)
    hehe12980
        3
    hehe12980  
       2021-03-23 18:16:53 +08:00
    @hehe12980

    上面好像写的不太对

    def arr = [1, 2, 3, 4, 5, 7, 8, 9, 10]
    if (arr.size() < 3) {
    return
    }
    int min = arr[0] + arr[1] + arr[2]
    int max = arr[0] + arr[1] + arr[2]
    int prefix = 0
    for (int i = 3; i < arr.size(); i++) {
    int sum = arr[i] + max - arr[prefix++]
    max = Math.max(max, sum)
    min = Math.min(min, sum)
    }
    println(min)
    println(max)
    ClutchBear
        4
    ClutchBear  
       2021-03-23 18:18:39 +08:00   ❤️ 1
    单纯的 o(n)啊
    计算每个元素和后面两个元素的和.
    然后比较
    ClutchBear
        5
    ClutchBear  
       2021-03-23 18:19:12 +08:00
    data = [1, 2, 3, 4, 5, 7, 8, 9, 10]
    max_sum = data[0] + data[1] + data[2]
    min_sum = max_sum
    temp_list = []
    data_length = len(data)

    for index, item in enumerate(data):
    if data_length == index + 2:
    break
    temp_list = [item, data[index + 1], data[index + 2]]
    temp_list_sum = sum(temp_list)

    if temp_list_sum > max_sum:
    max_sum = temp_list_sum
    if temp_list_sum < min_sum:
    min_sum = temp_list_sum
    print(max_sum, min_sum)
    BBrother
        6
    BBrother  
       2021-03-23 18:30:40 +08:00   ❤️ 1
    数组顺序不能改的话用滑动窗口
    zyb201314
        7
    zyb201314  
       2021-03-23 18:36:01 +08:00 via Android
    #这咋样?
    import heapq
    s=[9,2,3,6,10,5,7,1,8]
    print(sum(heapq.nsmallest(3,s)))
    print(sum(heapq.nlargest(3,s)))
    Vegetable
        8
    Vegetable  
       2021-03-23 18:40:20 +08:00
    这和遍历一遍找出极值没什么区别吧
    going
        9
    going  
    OP
       2021-03-23 19:04:44 +08:00
    @hongch 是的
    going
        10
    going  
    OP
       2021-03-23 19:15:08 +08:00
    @zyb201314 你这个是排序的结果了,数组是无序的
    todd7zhang
        11
    todd7zhang  
       2021-03-24 09:29:43 +08:00
    老老实实遍历就完事,O(n)
    princelai
        12
    princelai  
       2021-03-24 10:38:34 +08:00
    高性能用 numpy 啊,你要是刷题没法引入外部包那就没办法了

    ```
    import numpy as np

    w=3
    arr = np.array([1,2,3,4,5,7,8,9,10])

    x,y = np.ogrid[:arr.shape[0]-w+1,:w]
    rolling_sum = arr[x+y].sum(axis=1)
    # 上两步替代方法
    # np.lib.stride_tricks.sliding_window_view(arr,w).sum(axis=1)

    print(f"最小值:{rolling_sum.min()}\t 最大值{rolling_sum.max()}")
    ```
    Pagliacii
        13
    Pagliacii  
       2021-03-24 10:46:27 +08:00
    livrth
        14
    livrth  
       2021-03-24 11:07:59 +08:00 via Android
    单调队列 滑动窗口 O ( N )
    adocder
        15
    adocder  
       2021-04-21 17:26:16 +08:00
    应该是考察排序吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1059 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 23:13 · PVG 07:13 · LAX 16:13 · JFK 19:13
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.