无需持久存储列表，判断输入整数是否超列表指定百分比元素的技术问询

问题描述 #

我需要处理固定长度的列表，循环输入整数x时判断x是否大于列表中指定百分比的元素，随后删除列表首个元素并将x追加到末尾。当前实现直接遍历列表统计符合条件的元素数量，但面对数千个30万元素的数组时内存占用过高。希望通过数学/高效数据结构方案，在循环前计算相关数值后释放原列表内存，后续迭代仍能得到相同结果。

原实现代码 #

needed_percent = .9975
arr = [x for x in range(1, 10_000+1)]

while True:
    x = int(input('Enter number: '))
    count_less_than_x = 0
    for n in arr:
        if x > n:
            count_less_than_x += 1
    percent = count_less_than_x / len(arr)

    if percent >= needed_percent:
        print(f'Yes! Input number={x} bigger than {needed_percent*100}% elements in list')
    else:
        print(f'No. Input number={x} less than {needed_percent*100}% elements in list')

    del arr[0]
    arr.append(x)

测试示例 #

Enter number: 1000
No. Input number=1000 less than 99.75% elements in list
Enter number: 9990
Yes! Input number=9990 bigger than 99.75% elements in list
Enter number: 9975
No. Input number=9975 less than 99.75% elements in list
Enter number: 9976
No. Input number=9976 less than 99.75% elements in list
Enter number: 9977
Yes! Input number=9977 bigger than 99.75% elements in list
Enter number: 9977
No. Input number=9977 less than 99.75% elements in list
Enter number:  

优化方案 #

方案可行性：完全可行 #

无需维护原始大列表，通过维护有序数据结构结合二分查找，就能在O(logN)时间内完成统计、插入和删除操作，同时大幅降低内存开销。

具体实现思路 #

1. 初始化阶段：

   • 将原始列表排序，转换为有序列表（用Python标准库bisect模块维护）。
   • 维护一个队列记录元素加入顺序，用于后续删除最旧元素。
   • 直接删除原始大列表释放内存。

2. 循环处理阶段：

   • 用bisect.bisect_left快速找到有序列表中第一个≥x的位置，该位置即为小于x的元素数量。
   • 判断占比是否达标，输出对应结果。
   • 从有序列表中删除队列头部的最旧元素，再将x插入有序列表的正确位置，并加入队列。

优化后代码 #

import bisect

needed_percent = .9975
N = 10_000
# 初始化并排序原始数组
initial_arr = [x for x in range(1, N+1)]
initial_arr.sort()
# 维护有序列表和顺序队列
sorted_list = initial_arr.copy()
order_queue = initial_arr.copy()
# 释放原始数组内存
del initial_arr

while True:
    try:
        x = int(input('Enter number: '))
    except ValueError:
        break  # 输入非整数时退出
    
    # 快速统计小于x的元素数量
    count_less_than_x = bisect.bisect_left(sorted_list, x)
    percent = count_less_than_x / N

    if percent >= needed_percent:
        print(f'Yes! Input number={x} bigger than {needed_percent*100}% elements in list')
    else:
        print(f'No. Input number={x} less than {needed_percent*100}% elements in list')

    # 删除最旧的元素
    oldest = order_queue.pop(0)
    idx = bisect.bisect_left(sorted_list, oldest)
    if idx < len(sorted_list) and sorted_list[idx] == oldest:
        del sorted_list[idx]
    
    # 插入新元素
    bisect.insort(sorted_list, x)
    order_queue.append(x)

优势说明 #

• 内存优化：仅需维护有序列表和队列，内存占用与原始列表相当；若原始列表存在大量重复元素，还可通过collections.Counter结合有序键列表进一步压缩内存。
• 时间效率：原代码每次统计需O(N)时间，优化后每次操作仅需O(logN)时间，处理30万元素时速度提升显著。

内容的提问来源于stack exchange，提问作者555Russich