面试题：Python列表添加元素在多线程及数据结构优化场景下的应用

设计思路

线程安全：为了确保多线程环境下对共享列表的操作是线程安全的，可以使用Python的threading.Lock。在每个线程对列表进行添加元素操作前，获取锁，操作完成后释放锁，这样就可以避免数据竞争问题。
数据结构优化：
- 查找优化：如果经常需要查找元素，可以考虑使用set数据结构。set在查找元素时具有O(1)的平均时间复杂度，相比列表的O(n)查找效率更高。但set是无序的，如果需要保持元素顺序，可以使用collections.OrderedDict或者collections.deque。不过对于简单的查找需求，set是一个不错的选择。
- 排序优化：为了提高排序效率，可以在添加元素时尽量保持列表的有序性。可以使用二分插入算法（如bisect模块中的函数），这样在添加元素时，平均时间复杂度为O(log n)，相比直接添加元素后再进行全列表排序（O(n log n)），后续排序的工作量会减少。

代码示例

import threading
import random
import bisect


class ThreadSafeList:
    def __init__(self):
        self.lock = threading.Lock()
        self.data = []

    def add_element(self, num):
        with self.lock:
            bisect.insort(self.data, num)


def worker(thread_safe_list):
    num = random.randint(1, 100)
    thread_safe_list.add_element(num)


if __name__ == "__main__":
    thread_safe_list = ThreadSafeList()
    num_threads = 5
    threads = []
    for _ in range(num_threads):
        t = threading.Thread(target=worker, args=(thread_safe_list,))
        threads.append(t)
        t.start()
    for t in threads:
        t.join()
    print("Final sorted list:", thread_safe_list.data)

代码说明

线程安全部分：
- ThreadSafeList类包含一个锁self.lock和一个列表self.data。
- add_element方法使用with self.lock语句，在进入代码块时自动获取锁，离开代码块时自动释放锁，从而确保对self.data的添加操作是线程安全的。
数据结构优化部分：
- 使用bisect.insort函数在添加元素时保持列表的有序性。bisect.insort会使用二分查找找到插入位置，并将元素插入到合适的位置，这样在后续进行排序操作时，如果需要，工作量会减少。
多线程控制部分：
- 创建ThreadSafeList实例thread_safe_list。
- 创建多个线程，每个线程调用worker函数，worker函数会随机生成一个整数并调用thread_safe_list的add_element方法添加元素。
- 启动所有线程并等待它们完成，最后打印出最终的有序列表。

星途面试题库

面试题：Python列表添加元素在多线程及数据结构优化场景下的应用

知识考点

面试题答案

设计思路

代码示例

代码说明