python高阶数据结构与算法优化

from collections importdeque# 1. 机器人任务队列（FIFO：先进先出）task_queue = deque()# 添加任务（尾部插入）task_queue.append("导航到充电桩")task_queue.append("执行障碍物检测")task_queue.append("返回起点")print("初始任务队列：", task_queue)  # deque(['导航到充电桩', '执行障碍物检测', '返回起点'])# 执行任务（头部删除）while task_queue:    current_task = task_queue.popleft()    print(f"正在执行任务：{current_task}")# 2. 机器人历史任务栈（LIFO：后进先出）history_stack = deque()history_stack.append("导航到充电桩")history_stack.append("执行障碍物检测")# 查看最近任务（尾部查看）print("最近执行任务：", history_stack[-1])  # 执行障碍物检测# 撤销最近任务（尾部删除）history_stack.pop()print("撤销后历史任务：", history_stack)  # deque(['导航到充电桩'])# 3. 限制队列长度（超出部分自动删除头部元素，适配缓存场景）cache_queue = deque(maxlen=3)for i in range(5):    cache_queue.append(f"缓存数据{i}")print("有限长度缓存队列：", cache_queue)  # deque(['缓存数据2', '缓存数据3', '缓存数据4'])

from collections import defaultdict# 1. 深度学习数据按类别分组（默认值为list）data = [    ("cat", "图像1.jpg"),    ("dog", "图像2.jpg"),    ("cat", "图像3.jpg"),    ("bird", "图像4.jpg"),    ("dog", "图像5.jpg")]# 定义defaultdict，默认值为listdata_group = defaultdict(list)for category, img_path in data:    data_group[category].append(img_path)  # 无需判断key是否存在，直接appendprint("按类别分组的数据：")for category, imgs in data_group.items():    print(f"{category}: {imgs}")# 输出：# cat: ['图像1.jpg', '图像3.jpg']# dog: ['图像2.jpg', '图像5.jpg']# bird: ['图像4.jpg']# 2. 测试用例结果统计（默认值为int，实现计数）test_results = ["通过", "失败", "通过", "通过", "失败", "跳过", "通过"]result_count = defaultdict(int)for result in test_results:    result_count[result] += 1  # 不存在的key自动初始化为0print("测试用例结果统计：", dict(result_count))# 输出：{'通过': 4, '失败': 2, '跳过': 1}

一个“天生用来计数”的工具，给它一个列表/字符串，它能秒出每个元素的出现次数，还支持most_common(n)找前N个高频元素。语法简洁，适合频率统计场景（如文本词频、传感器数据频次）。

代码实例：文本词频统计、传感器数据频次分析

importarrayimport sys# 1. 创建array数组（类型码'i'表示int，'f'表示float）# 存储机器人IMU传感器的加速度数据（10000个int值）imu_accel = array.array('i', [i*2for i in range(10000)])# 对比list与array的内存占用list_accel = [i*2for i in range(10000)]print(f"list内存占用：{sys.getsizeof(list_accel)} 字节") # 85176 字节print(f"array内存占用：{sys.getsizeof(imu_accel)} 字节")  # 40080 字节（节省一半内存）# 2.array核心操作（与list类似，但更高效）print("前5个加速度值：", imu_accel[:5])  # array('i', [0, 2, 4, 6, 8])# 追加数据imu_accel.append(20000)# 插入数据（指定索引）imu_accel.insert(0, -2)# 遍历数据for accel in imu_accel[:3]:    print(f"加速度值：{accel}")# 3. 保存到文件（适合大规模数据持久化）with open("imu_accel.bin", "wb") as f:    imu_accel.tofile(f)# 从文件读取new_accel = array.array('i')with open("imu_accel.bin", "rb") as f:    new_accel.fromfile(f, 10001)  # 读取10001个元素print("读取后的数据长度：", len(new_accel))  # 10001

import heapq# 1. 机器人任务优先级调度（优先级数值越小，优先级越高）# 任务格式：(优先级, 任务名称)tasks = [    (3, "执行环境检测"),    (1, "紧急避障"),    (2, "导航到目标点"),    (4, "采集传感器数据")]# 构建最小堆（默认）heapq.heapify(tasks)print("构建堆后的任务：", tasks)  # [(1, '紧急避障'), (3, '执行环境检测'), (2, '导航到目标点'), (4, '采集传感器数据')]# 优先执行高优先级任务（弹出最小值）print("任务执行顺序：")while tasks:    priority, task = heapq.heappop(tasks)    print(f"优先级{priority}：{task}")# 输出：# 优先级1：紧急避障# 优先级2：导航到目标点# 优先级3：执行环境检测# 优先级4：采集传感器数据# 2. 实现最大堆（通过插入负数实现）nums = [5, 2, 8, 1, 9, 3]max_heap = []for num in nums:    heapq.heappush(max_heap, -num)  # 插入负数print("最大堆（存储负数）：", max_heap)  # [-9, -5, -8, -1, -2, -3]# 获取最大值（弹出负数后取反）print("最大值：", -heapq.heappop(max_heap))  # 9# 3. 获取Top3最大元素top3 = heapq.nlargest(3, nums)print("Top3最大元素：", top3)  # [9, 8, 5]# 4. 获取Top2最小元素top2_min = heapq.nsmallest(2, nums)print("Top2最小元素：", top2_min)  # [1, 2]

import randomimport timefrom collections import namedtuple# 1. 快速排序（O(nlogn)，不稳定排序，适合大规模数据）def quick_sort(arr):    iflen(arr) <= 1:        return arr    # 选择基准（优化：随机选择基准，避免最坏情况O(n²)）    pivot = random.choice(arr)    left = [x for x in arr if x < pivot]    middle = [x for x in arr if x == pivot]    right = [x for x in arr if x > pivot]    return quick_sort(left) + middle + quick_sort(right)# 2. 对比基础排序（冒泡）与优化排序（快速排序、sorted）# 生成10000个随机整数（大规模数据）large_arr = [random.randint(0, 200000) for _ in range(20000)]# 冒泡排序（O(n²)，效率极低）def bubble_sort(arr):    arr_copy = arr.copy()    n = len(arr_copy)    for i in range(n):        for j in range(0, n-i-1):            if arr_copy[j] > arr_copy[j+1]:                arr_copy[j], arr_copy[j+1] = arr_copy[j+1], arr_copy[j]    return arr_copy# 测试耗时start = time.time()bubble_sort(large_arr)print(f"冒泡排序耗时：{time.time() - start:.2f} 秒")start = time.time()quick_sort(large_arr)print(f"快速排序耗时：{time.time() - start:.2f} 秒")start = time.time()sorted(large_arr)print(f"内置sorted排序耗时：{time.time() - start:.2f} 秒")# 3. 自定义排序（按对象属性排序，适配业务场景）# 机器人任务排序（按优先级升序，优先级相同按创建时间升序）Task = namedtuple("Task", ["name", "priority", "create_time"])tasks = [    Task("导航", 2, 100),    Task("避障", 1, 105),    Task("充电", 2, 98),    Task("检测", 3, 102)]# 按优先级升序，再按创建时间升序sorted_tasks = sorted(tasks, key=lambda x: (x.priority, x.create_time))print("自定义排序后的任务：")for task in sorted_tasks:    print(f"{task.name}（优先级：{task.priority}，创建时间：{task.create_time}）")# 输出：# 避障（优先级：1，创建时间：105）# 充电（优先级：2，创建时间：98）# 导航（优先级：2，创建时间：100）# 检测（优先级：3，创建时间：102）

# 1. 二分查找（迭代实现，推荐：避免递归栈溢出）def binary_search(arr, target):    left, right = 0, len(arr) - 1    while left <= right:        mid = (left + right) // 2  # 中间索引（避免溢出：可改为left + (right-left)//2）        if arr[mid] == target:            return mid  # 返回目标索引        elif arr[mid] < target:            left = mid + 1  # 目标在右半部分        else:            right = mid - 1  # 目标在左半部分    return-1  # 目标不存在# 2. 二分查找（递归实现）def binary_search_recursive(arr, target, left, right):    if left > right:        return-1    mid = (left + right) // 2    if arr[mid] == target:        return mid    elif arr[mid] < target:        return binary_search_recursive(arr, target, mid + 1, right)    else:        return binary_search_recursive(arr, target, left, mid - 1)# 测试sorted_arr = [1, 3, 5, 7, 9, 11, 13, 15]target = 7print(f"迭代查找{target}的索引：", binary_search(sorted_arr, target))  # 3print(f"递归查找{target}的索引：", binary_search_recursive(sorted_arr, target, 0, len(sorted_arr)-1))  # 3# 3. 实际场景：机器人路径点查询（有序路径点ID查询）path_points = [101, 102, 103, 105, 107, 109, 110]  # 有序路径点IDtarget_point = 105point_index = binary_search(path_points, target_point)if point_index != -1:    print(f"找到路径点{target_point}，索引：{point_index}")else:    print(f"未找到路径点{target_point}")# 4. 内置bisect模块（二分查找工具，更简洁）import bisect# 查找插入位置（保持数组有序）insert_pos = bisect.bisect_left(sorted_arr, 8)print(f"8应插入的位置：{insert_pos}")  # 4（插入后数组仍有序）# 检查元素是否存在if bisect.bisect_left(sorted_arr, target) != len(sorted_arr) and sorted_arr[bisect.bisect_left(sorted_arr, target)] == target:    print(f"{target}存在于数组中")

# 1. 机器人零钱兑换（贪心算法：优先选面额大的硬币，适合硬币面额为倍数关系）def coin_change_greedy(coins, amount):    """    coins: 硬币面额（降序排列）    amount: 需要兑换的金额    return: 最少硬币数    """    coins.sort(reverse=True)  # 按面额降序排序    count = 0    for coin in coins:        if amount <= 0:            break        # 尽可能多用当前面额        num = amount // coin        count += num        amount -= num * coin    return count if amount == 0else-1  # 无法兑换返回-1# 测试coins = [25, 10, 5, 1]  # 美元硬币（面额为倍数关系，贪心有效）amount = 37print(f"兑换{amount}需要最少硬币数：", coin_change_greedy(coins, amount))  # 4（25+10+1+1）# 2. 机器人活动安排问题（选择最多不重叠的活动，最大化任务数量）# 活动格式：(开始时间, 结束时间)activities = [    (1, 3), (2, 4), (3, 5), (4, 6), (5, 7)]def activity_selection(activities):    # 按结束时间升序排序（贪心核心：选择结束最早的活动）    activities.sort(key=lambda x: x[1])    selected = [activities[0]]  # 选择第一个活动    last_end = activities[0][1]    for act in activities[1:]:        start, end = act        if start >= last_end:  # 不与上一个活动重叠            selected.append(act)            last_end = end    return selectedselected_acts = activity_selection(activities)print("最多可选择的不重叠活动：", selected_acts)  # [(1, 3), (3, 5), (5, 7)]