面试题：Ruby数组与哈希复杂操作及性能优化

Question

假设有一个包含大量人员信息的数组，每个元素是一个哈希，格式为{name: '张三', age: 25, score: 80}。请编写代码实现：1. 找出年龄大于30岁且分数大于85的人员名单；2. 对所有人员按分数从高到低排序，并输出前10名的姓名；3. 分析并优化这段代码的性能，特别是在数据量很大时的情况。

Answer 1

以下以Python代码为例：

1. 找出年龄大于30岁且分数大于85的人员名单

people = [
    {'name': '张三', 'age': 25,'score': 80},
    {'name': '李四', 'age': 35,'score': 90},
    {'name': '王五', 'age': 28,'score': 88},
    {'name': '赵六', 'age': 32,'score': 86}
]
result1 = [person['name'] for person in people if person['age'] > 30 and person['score'] > 85]
print(result1)

2. 对所有人员按分数从高到低排序，并输出前10名的姓名

sorted_people = sorted(people, key=lambda x: x['score'], reverse=True)
top_10_names = [person['name'] for person in sorted_people[:10]]
print(top_10_names)

3. 性能分析与优化

• 性能分析：
  • 对于第一个需求，使用列表推导式遍历一次数组，时间复杂度为O(n)。
  • 对于第二个需求，sorted函数的时间复杂度在平均和最坏情况下为O(n log n)，其中n是数组长度。
• 优化措施：
  • 对于大数据量：
    • 第一个需求可考虑使用生成器代替列表推导式，这样可以减少内存占用，当数据量很大时，不会一次性生成整个结果列表。

    def filter_people_generator(people):
        for person in people:
            if person['age'] > 30 and person['score'] > 85:
                yield person['name']
    result1_generator = filter_people_generator(people)
    

    • 第二个需求，若数据量非常大，可考虑使用堆排序（heapq模块），heapq.nlargest可以直接获取前n个最大的元素，而无需对整个列表进行排序，其时间复杂度为O(n log k)，其中k是要获取的元素个数（这里k = 10）。

    import heapq
    top_10_heap = heapq.nlargest(10, people, key=lambda x: x['score'])
    top_10_names_heap = [person['name'] for person in top_10_heap]
    print(top_10_names_heap)
    

若使用其他语言，如JavaScript：

1. 找出年龄大于30岁且分数大于85的人员名单

const people = [
    {name: '张三', age: 25, score: 80},
    {name: '李四', age: 35, score: 90},
    {name: '王五', age: 28, score: 88},
    {name: '赵六', age: 32, score: 86}
];
const result1 = people.filter(person => person.age > 30 && person.score > 85).map(person => person.name);
console.log(result1);

2. 对所有人员按分数从高到低排序，并输出前10名的姓名

const sortedPeople = people.sort((a, b) => b.score - a.score);
const top10Names = sortedPeople.slice(0, 10).map(person => person.name);
console.log(top10Names);

3. 性能分析与优化

• 性能分析：
  • 第一个需求，filter和map方法遍历数组，时间复杂度为O(n)。
  • 第二个需求，sort方法的时间复杂度在平均情况下为O(n log n)，最坏情况下为O(n^2)。
• 优化措施：
  • 对于大数据量：
    • 第一个需求，可使用迭代器和生成器来减少内存消耗。

    function* filterPeopleGenerator(people) {
        for (const person of people) {
            if (person.age > 30 && person.score > 85) {
                yield person.name;
            }
        }
    }
    const result1Generator = filterPeopleGenerator(people);
    

    • 第二个需求，可使用PriorityQueue（需要自己实现或者使用第三方库）来实现类似堆排序的功能获取前10名，避免对整个数组进行排序，优化时间复杂度。