Максимізація Ефективності Сортування
Вбудоване сортування
Коли виникає потреба відсортувати список, за винятком рідкісних особливих випадків, майже завжди найкраще використовувати один із двох високоефективних інструментів сортування: функцію sorted() або метод sort(). Обидва реалізовані на C та використовують Timsort — гібридний алгоритм, що поєднує злиття та вставку для підвищення ефективності.
sorted() ідеально підходить для загального сортування, коли потрібно відсортувати будь-який ітерований об'єкт без зміни вихідних даних. Натомість, sort() найкраще підходить для списків, коли допускається зміна на місці.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Обидва методи ефективні, але list.sort() може бути лише трохи швидшим для дуже великих списків, оскільки не створює новий список. Однак використовуйте sorted(), якщо потрібно зберегти початковий список незмінним.
Часткове сортування з heapq
У випадках, коли потрібно отримати лише найменші або найбільші елементи з набору даних, повне сортування не є необхідним. Модуль heapq надає ефективні методи, такі як heapq.nsmallest() та heapq.nlargest(), для отримання цих елементів без повного сортування ітерованого об'єкта, що робить процес швидшим і менш ресурсомістким.
Порівняймо продуктивність функції sorted() та функції heapq.nsmallest() для отримання 10 найменших чисел зі списку:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(10, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:10] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
Як видно з нашого прикладу, у даному випадку heapq.nsmallest() приблизно у 10 разів швидший.
Однак, якщо кількість найбільших або найменших елементів (n), які потрібно отримати, наближається до загальної кількості елементів у списку, heapq часто працює повільніше, ніж функція sorted() або метод .sort().
Наприклад, зараз отримаємо 100000 найменших елементів зі списку:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(100000, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:100000] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
У цьому випадку функція sorted() явно перевершує heapq за швидкістю.
1. Потрібно відсортувати цілий список чисел без зміни оригінального списку. Яку функцію/метод сортування слід використовувати?
2. Ви аналізуєте набір даних із 500 000 записів про продажі. Щоб визначити 20 транзакцій з найбільшим доходом, який підхід, ймовірно, буде швидшим і ефективнішим за використанням пам'яті?
Дякуємо за ваш відгук!
Запитати АІ
Запитати АІ
Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат
Can you explain why heapq is faster for small n but slower for large n?
When should I use heapq over sorted() in practice?
Are there other efficient ways to partially sort data in Python?
Awesome!
Completion rate improved to 7.69Максимізація Ефективності Сортування
Свайпніть щоб показати меню
Вбудоване сортування
Коли виникає потреба відсортувати список, за винятком рідкісних особливих випадків, майже завжди найкраще використовувати один із двох високоефективних інструментів сортування: функцію sorted() або метод sort(). Обидва реалізовані на C та використовують Timsort — гібридний алгоритм, що поєднує злиття та вставку для підвищення ефективності.
sorted() ідеально підходить для загального сортування, коли потрібно відсортувати будь-який ітерований об'єкт без зміни вихідних даних. Натомість, sort() найкраще підходить для списків, коли допускається зміна на місці.
sorted_list = sorted(some_list) # Returns a new sorted list
some_list.sort() # Sorts the list in place
Обидва методи ефективні, але list.sort() може бути лише трохи швидшим для дуже великих списків, оскільки не створює новий список. Однак використовуйте sorted(), якщо потрібно зберегти початковий список незмінним.
Часткове сортування з heapq
У випадках, коли потрібно отримати лише найменші або найбільші елементи з набору даних, повне сортування не є необхідним. Модуль heapq надає ефективні методи, такі як heapq.nsmallest() та heapq.nlargest(), для отримання цих елементів без повного сортування ітерованого об'єкта, що робить процес швидшим і менш ресурсомістким.
Порівняймо продуктивність функції sorted() та функції heapq.nsmallest() для отримання 10 найменших чисел зі списку:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(10, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:10] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
Як видно з нашого прикладу, у даному випадку heapq.nsmallest() приблизно у 10 разів швидший.
Однак, якщо кількість найбільших або найменших елементів (n), які потрібно отримати, наближається до загальної кількості елементів у списку, heapq часто працює повільніше, ніж функція sorted() або метод .sort().
Наприклад, зараз отримаємо 100000 найменших елементів зі списку:
1234567891011121314151617181920212223import heapq import os decorators = os.system('wget https://staging-content-media-cdn.codefinity.com/courses/8d21890f-d960-4129-bc88-096e24211d53/section_1/chapter_3/decorators.py 2>/dev/null') from decorators import timeit_decorator import random # Generate a large list of random integers numbers = [random.randint(1, 1000000) for _ in range(1000000)] @timeit_decorator(number=10) def partial_sort_heapq(): return heapq.nsmallest(100000, numbers) @timeit_decorator(number=10) def partial_sort_sorted(): return sorted(numbers)[:100000] # Compare performance heapq_result = partial_sort_heapq() sorted_result = partial_sort_sorted() # Ensure both methods give the same result print(heapq_result == sorted_result)
У цьому випадку функція sorted() явно перевершує heapq за швидкістю.
1. Потрібно відсортувати цілий список чисел без зміни оригінального списку. Яку функцію/метод сортування слід використовувати?
2. Ви аналізуєте набір даних із 500 000 записів про продажі. Щоб визначити 20 транзакцій з найбільшим доходом, який підхід, ймовірно, буде швидшим і ефективнішим за використанням пам'яті?
Дякуємо за ваш відгук!
