Как отсортировать строку в Python при минимальной памяти?

Как отсортировать строку в Python при минимальной памяти?

Задача: сортировка строк с минимальным использованием памяти — важно для работы с большими текстовыми файлами, когда данные не помещаются в RAM. Есть несколько подходов в зависимости от контекста задачи.

Контекст 1: Отсортировать символы в строке

Если нужно отсортировать символы внутри одной строки:

# Задача: отсортировать символы "hello" -> "ehllo"

s = "hello"

# ✅ Вариант 1: встроенная функция sorted() - просто и эффективно
sorted_str = ''.join(sorted(s))
print(sorted_str)  # "ehllo"

# ✅ Вариант 2: использовать sorted() с key функцией для кастомной логики
sorted_str = ''.join(sorted(s, key=lambda x: (x.lower(), x)))  # case-sensitive sort

# ❌ Вариант 3: преобразовать в список, отсортировать, объединить (неэффективно)
char_list = list(s)
char_list.sort()
sorted_str = ''.join(char_list)  # больше операций

Анализ памяти:

• sorted() создает новый список в памяти: O(n) дополнительной памяти
• Это необходимо для любого сортирования в Python

Контекст 2: Отсортировать большой файл (по строкам)

Проблема: если файл большой (ГБ), то загрузить всё в память нельзя.

Решение 1: External Merge Sort (внешняя сортировка)

Сортируем файл по частям, сохраняем на диск, потом объединяем:

import heapq
import os
from pathlib import Path

def external_merge_sort(input_file, output_file, chunk_size=1_000_000):
    """
    Сортировка большого файла с минимальной памятью.
    chunk_size: количество строк, которые помещаются в RAM
    """
    
    # Шаг 1: Разбить на отсортированные части
    temp_files = []
    
    with open(input_file, 'r', encoding='utf-8') as f:
        chunk = []
        for line_num, line in enumerate(f):
            chunk.append(line.strip())
            
            # Когда chunk достаточно большой, отсортировать и сохранить
            if (line_num + 1) % chunk_size == 0:
                chunk.sort()
                temp_file = f'temp_chunk_{len(temp_files)}.txt'
                temp_files.append(temp_file)
                
                with open(temp_file, 'w') as tmp:
                    for item in chunk:
                        tmp.write(item + '\n')
                
                chunk = []
        
        # Сохранить оставшиеся элементы
        if chunk:
            chunk.sort()
            temp_file = f'temp_chunk_{len(temp_files)}.txt'
            temp_files.append(temp_file)
            
            with open(temp_file, 'w') as tmp:
                for item in chunk:
                    tmp.write(item + '\n')
    
    # Шаг 2: Объединить отсортированные части (merge)
    def merge_files(file_list, output_file):
        # Используем heap для эффективного объединения
        file_handles = [open(f, 'r') as h for f in file_list]
        
        with open(output_file, 'w') as out:
            # Heap содержит (значение, файл_индекс, строка)
            heap = []
            
            # Добавить первую строку из каждого файла
            for i, fh in enumerate(file_handles):
                line = fh.readline().strip()
                if line:
                    heapq.heappush(heap, (line, i))
            
            # Основной loop слияния
            while heap:
                min_line, file_idx = heapq.heappop(heap)
                out.write(min_line + '\n')
                
                # Добавить следующую строку из того же файла
                next_line = file_handles[file_idx].readline().strip()
                if next_line:
                    heapq.heappush(heap, (next_line, file_idx))
        
        # Закрыть файлы
        for fh in file_handles:
            fh.close()
    
    merge_files(temp_files, output_file)
    
    # Очистить временные файлы
    for temp_file in temp_files:
        os.remove(temp_file)

# Использование
external_merge_sort('large_file.txt', 'sorted_file.txt', chunk_size=100_000)
print("Сортировка завершена!")

Анализ:

• Память: O(chunk_size) — только chunk в памяти одновременно
• Диск: дополнительный вспомогательный диск для временных файлов
• Время: O(n log n) как обычная сортировка

Решение 2: Streaming (построчная обработка)

Если не нужна полная сортировка, а нужны top-k элементов:

import heapq
from pathlib import Path

def find_top_k_lines(input_file, k=10):
    """
    Найти k наибольших строк (лексикографически)
    Памяти: O(k) вместо O(n)
    """
    min_heap = []
    
    with open(input_file, 'r', encoding='utf-8') as f:
        for line in f:
            line = line.strip()
            
            if len(min_heap) < k:
                heapq.heappush(min_heap, line)
            elif line > min_heap[0]:  # Если больше минимума в heap
                heapq.heapreplace(min_heap, line)
    
    # Результат в обратном порядке
    return sorted(min_heap, reverse=True)

# Использование
top_10 = find_top_k_lines('large_file.txt', k=10)
for line in top_10:
    print(line)

Преимущество: O(k) памяти вместо O(n)!

Контекст 3: Сортировать с ограничением памяти (numpy/pandas)

Для большого DataFrame:

import pandas as pd
import numpy as np

# ❌ Неэффективно: загружает всё в память
df = pd.read_csv('large_file.csv')
df = df.sort_values('column')
df.to_csv('sorted.csv')

# ✅ Эффективнее: обрабатывать по chunks
def sort_csv_by_chunks(input_file, output_file, chunk_size=10_000):
    chunks = []
    
    for chunk in pd.read_csv(input_file, chunksize=chunk_size):
        chunks.append(chunk)
    
    # Конкатенировать все chunks и отсортировать
    df = pd.concat(chunks, ignore_index=True)
    df = df.sort_values('column')
    df.to_csv(output_file, index=False)

# ✅ Самое эффективное: использовать External Sort через Dask
import dask.dataframe as dd

# Dask автоматически управляет памятью
ddf = dd.read_csv('large_file.csv')
ddf = ddf.sort_values('column')
ddf.to_csv('sorted_*.csv')  # Сохранит в несколько файлов

Контекст 4: Сортировка в памяти-ограниченной среде

Counting Sort для специальных случаев (например, числа в диапазоне):

def counting_sort(arr, max_val):
    """
    Для массива с ограниченным диапазоном значений.
    Время: O(n + k), Память: O(k)
    где k - диапазон значений
    """
    count = [0] * (max_val + 1)
    
    # Считаем частотность
    for num in arr:
        count[num] += 1
    
    # Восстанавливаем отсортированный массив
    result = []
    for num in range(max_val + 1):
        result.extend([num] * count[num])
    
    return result

# Использование
arr = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_arr = counting_sort(arr, max(arr))
print(sorted_arr)  # [1, 1, 2, 3, 4, 5, 6, 9]

Анализ:

• Время: O(n + k) вместо O(n log n)
• Память: O(k) для counting array
• Когда использовать: числа в диапазоне 0...10000

Сравнение подходов

Практическая рекомендация

# Для Data Scientist-a:

# 1. Малые данные (< 1 ГБ)
result = sorted(data)

# 2. Большой CSV
import dask.dataframe as dd
df = dd.read_csv('file.csv')
df = df.sort_values('column')

# 3. Гигантский файл, нужна сортировка
# Используй external_merge_sort() из примера выше

# 4. Нужны только top-k
import heapq
top_k = heapq.nlargest(k, iterator)

Главное правило: не загружайте всё в память, если это не необходимо!