验证列表与集合、字典的计算效率 ·构建分别包含一千条、一万和十万条数据的数据源:电话本(由姓名 和电话号构成) 编写程序,分别查找其中任意名字或标识符的电话号码
时间: 2024-09-09 11:14:26 浏览: 23
在Python中,我们通常会使用不同的数据结构来存储和查询大量数据,比如列表、集合和字典。这里我们将分析它们在处理电话本数据时的查询效率。
1. 列表(List): 如果用列表表示电话本,每个元素是一个元组,如`(姓名, 电话号码)`。查找特定名字或电话号码的时间复杂度通常是O(n),因为需要遍历整个列表才能找到目标。
```python
phone_book_list = [('Alice', '12345678'), ('Bob', '98765432'), ...]
def find_phone_by_name(name):
for entry in phone_book_list:
if entry[0] == name:
return entry[1]
```
2. 集合(Set): 集合的主要优点在于去重和快速查找,但它不存储键值对,所以不能直接通过名字查找电话号码。如果你将名字作为唯一的键,并将电话号码转换成元组放入集合,那么查找特定名字的时间复杂度也是O(n)。
```python
name_to_number_set = {('Alice', '12345678'), ('Bob', '98765432'), ...}
def find_phone_by_name(name):
if (name, None) in name_to_number_set:
return 'Phone not found'
else:
for number_tuple in name_to_number_set:
if number_tuple[0] == name:
return number_tuple[1]
```
3. 字典(Dictionary): 字典是键值对的集合,如果将名字作为键,电话号码作为值,可以实现O(1)的平均查找时间。不过要注意,如果名字不是唯一的,可能需要额外处理。
```python
phone_book_dict = {'Alice': '12345678', 'Bob': '98765432', ...}
def find_phone_by_name(name):
if name in phone_book_dict:
return phone_book_dict[name]
else:
return 'Phone not found'
```
总的来说,在电话簿较大时(例如一万个或更多记录),字典的查找效率最高。然而,具体选择哪种数据结构取决于实际需求,如是否需要频繁插入和删除等操作。