ОПТИМИЗАЦИЯ ПРОИЗВОДИТЕЛЬНОСТИ СОРТИРОВКИ ДЛЯ МАССИВОВ С БОЛЬШИМ КОЛИЧЕСТВОМ ДУБЛИКАТОВ С ПОМОЩЬЮ ГИБРИДНОГО ПОДХОДА

OPTIMIZING SORTING PERFORMANCE FOR DUPLICATE-HEAVY DATASETS USING A HYBRID APPROACH

Ivan Alferov

student, Department of Computer Systems Software, Ivanovo State Power Engineering University,

Russia, Ivanovo

АННОТАЦИЯ

Алгоритмы сортировки являются фундаментом информатики, обеспечивая эффективную обработку данных в таких приложениях, как базы данных и поисковые системы. Однако стандартные алгоритмы, такие как быстрая сортировка (quicksort), теряют эффективность при работе с наборами данных, содержащими большое количество дубликатов. В данной работе предлагается гибридный алгоритм сортировки DupeSort, который сочетает в себе быструю сортировку, сортировку вставками и сортировку подсчетом, чтобы повысить производительность при работе с дублирующимися значениями. Ранняя идентификация повторяющихся паттернов и использование сортировки подсчетом для однородных сегментов позволяет алгоритму DupeSort достигать средней сложности O(n log n), демонстрируя прирост производительности до 50% по сравнению с классической быстрой сортировкой на массивах с высокой долей дубликатов.

ABSTRACT

Sorting algorithms are fundamental to computer science, enabling efficient data processing in applications like databases and search engines. However, standard algorithms like quicksort struggle with datasets containing frequent duplicates, leading to suboptimal performance. This paper proposes a hybrid sorting algorithm, DupeSort, which combines quicksort, insertion sort, and counting sort to optimize performance for duplicate-heavy datasets. By detecting duplicate patterns early and leveraging counting sort for uniform segments, DupeSort achieves O(n log n) average-case complexity with significant improvements in specific cases. Experimental results demonstrate up to 50% faster sorting on datasets with high duplicate ratios compared to standard quicksort.

Ключевые слова: алгоритмы сортировки, быстрая сортировка, сортировка подсчетом, оптимизация производительности.

Keywords: sorting algorithms, quicksort, counting sort, performance optimization.

ВВЕДЕНИЕ

Сортировка — краеугольный камень вычислительных задач: от организации файловых систем до эффективного поиска. Быстрая сортировка (quicksort) широко используется благодаря средней временной сложности O(n log n), однако её производительность резко снижается в худших сценариях O(n²) и при наличии множества одинаковых элементов в данных. Современные исследования, включая оптимизации с использованием обучения с подкреплением (например, AlphaDev), показывают, что комбинация различных методов способна значительно повысить эффективность. В этой статье представлен DupeSort — гибридный алгоритм, сочетающий стратегию «разделяй и властвуй» быстрой сортировки, эффективность сортировки вставками на малых массивах и линейную скорость сортировки подсчетом на участках с дубликатами. Такой подход применим, например, к логам, журналам и индексам баз данных.

Постановка проблемы

Производительность быстрой сортировки ухудшается, когда выбор опорного элемента (пивота) не обеспечивает равномерное разбиение, особенно в массивах с большим количеством одинаковых значений. Например, при 70% дубликатов (как в случае с временными метками в логах) количество лишних сравнений значительно возрастает. Сортировка подсчетом эффективна для небольших диапазонов значений, а сортировка вставками — для малых или почти отсортированных массивов. Гибридный подход, динамически выбирающий алгоритм в зависимости от характеристик данных, позволяет нивелировать эти проблемы.

Выбор технологий

DupeSort объединяет три алгоритма:

• Быстрая сортировка (quicksort) — основной алгоритм со средней сложностью O(n log n).
• Сортировка вставками — применяется для подмассивов длиной ≤ 10, поскольку имеет низкие накладные расходы.
• Сортировка подсчетом — используется при высокой доле дубликатов, имеет сложность O(n + k), где k — диапазон значений.

Алгоритм применяет эвристику для определения сегментов с высоким уровнем дубликатов: из массива берется случайная выборка и оценивается коэффициент дублирования. Если он превышает 50%, к сегменту применяется сортировка подсчетом. В противном случае используется быстрая сортировка, с переходом на сортировку вставками для небольших участков.

Реализация

Ниже представлена реализация алгоритма DupeSort на языке Python, включая вспомогательные функции генерации данных и замера производительности.

import random

import matplotlib.pyplot as plt

import time

def insertion_sort(arr, start, end):

    for i in range(start + 1, end):

        key = arr[i]

        j = i - 1

        while j >= start and arr[j] > key:

            arr[j + 1] = arr[j]

            j -= 1

        arr[j + 1] = key

def counting_sort(arr, start, end):

    if start >= end:

        return

    min_val, max_val = min(arr[start:end]), max(arr[start:end])

    range_val = max_val - min_val + 1

    if range_val > len(arr[start:end]):  # Fallback to quicksort if range is large

        quicksort(arr, start, end)

        return

    count = [0] * range_val

    output = [0] * (end - start)

    for i in range(start, end):

        count[arr[i] - min_val] += 1

    for i in range(1, range_val):

        count[i] += count[i - 1]

    for i in range(end - 1, start - 1, -1):

        output[count[arr[i] - min_val] - 1] = arr[i]

        count[arr[i] - min_val] -= 1

    for i in range(end - start):

        arr[start + i] = output[i]

def quicksort(arr, start, end):

    if end - start <= 10:

        insertion_sort(arr, start, end)

        return

    pivot = arr[random.randint(start, end - 1)]

    i, j = start, end - 1

    while i <= j:

        while i <= j and arr[i] < pivot:

            i += 1

        while i <= j and arr[j] > pivot:

            j -= 1

        if i <= j:

            arr[i], arr[j] = arr[j], arr[i]

            i += 1

            j -= 1

    quicksort(arr, start, j + 1)

    quicksort(arr, i, end)

def detect_duplicates(arr, start, end):

    sample_size = min(20, end - start)

    if sample_size == 0:

        return 0

    sample = random.sample(arr[start:end], sample_size)

    return (len(sample) - len(set(sample))) / len(sample)

def dupesort(arr, start, end):

    if end - start <= 10:

        insertion_sort(arr, start, end)

        return

    if detect_duplicates(arr, start, end) > 0.5:

        counting_sort(arr, start, end)

    else:

        quicksort(arr, start, end)

def generate_duplicate_heavy_array(size, duplicate_ratio=0.7):

    arr = [random.randint(0, 1000) for _ in range(int(size * (1 - duplicate_ratio)))]

    arr += [random.randint(0, 1000)] * int(size * duplicate_ratio)

    random.shuffle(arr)

    return arr

def generate_random_array(size):

    return [random.randint(0, 1000) for _ in range(size)]

def benchmark_sort(sort_func, arr, trials=5):

    times = []

    for _ in range(trials):

        arr_copy = arr.copy()

        start = time.time()

        sort_func(arr_copy, 0, len(arr_copy))

        times.append((time.time() - start) * 1000)  # Convert to milliseconds

    return sum(times) / trials  # Average over trials

# Test sizes

sizes = [50000, 100000, 200000]

# Initialize results arrays

quicksort_random = []

dupesort_random = []

quicksort_dupe = []

dupesort_dupe = []

# Run benchmarks

for size in sizes:

    print(f"\nTesting with size: {size}")

    # Random arrays

    print("Testing random arrays...")

    random_arr = generate_random_array(size)

    quicksort_random.append(benchmark_sort(quicksort, random_arr.copy()))

    dupesort_random.append(benchmark_sort(dupesort, random_arr.copy()))

    # Duplicate-heavy arrays

    print("Testing duplicate-heavy arrays...")

    dupe_arr = generate_duplicate_heavy_array(size)

    quicksort_dupe.append(benchmark_sort(quicksort, dupe_arr.copy()))

    dupesort_dupe.append(benchmark_sort(dupesort, dupe_arr.copy()))

# Print results

print("\nResults (time in milliseconds):")

print("\nRandom Arrays:")

for i, size in enumerate(sizes):

    print(f"Size {size}:")

    print(f"Quicksort: {quicksort_random[i]:.2f}ms")

    print(f"DupeSort: {dupesort_random[i]:.2f}ms")

print("\nDuplicate-Heavy Arrays:")

for i, size in enumerate(sizes):

    print(f"Size {size}:")

    print(f"Quicksort: {quicksort_dupe[i]:.2f}ms")

    print(f"DupeSort: {dupesort_dupe[i]:.2f}ms")

# Generate performance comparison plot

plt.figure(figsize=(10, 6))

plt.plot(sizes, quicksort_random, 'b-', label='Быстрая сортировка (Случайный)')

plt.plot(sizes, dupesort_random, 'r-', label='DupeSort (Случайный)')

plt.plot(sizes, quicksort_dupe, 'b--', label='Быстрая сортировка (Дубликаты)')

plt.plot(sizes, dupesort_dupe, 'r--', label='DupeSort (Дубликаты)')

plt.title('Сравнение производительности алгоритмов сортировки')

plt.xlabel('Размер массива')

plt.ylabel('Время (мс)')

plt.legend()

plt.grid(True)

plt.savefig('performance_comparison.png')

print("\nPerformance comparison plot saved as 'performance_comparison.png'")

Краткое описание основных элементов приведено ниже:

• insertion_sort(arr, start, end) — реализует сортировку вставками на подмассиве arr[start:end]. Применяется для сегментов длиной ≤ 10, где она показывает высокую эффективность.
• counting_sort(arr, start, end) — выполняет сортировку подсчетом, если массив содержит большое количество дубликатов и диапазон значений ограничен. В противном случае происходит откат к быстрой сортировке.
• quicksort(arr, start, end) — классическая реализация быстрой сортировки с случайным выбором пивота. Используется как основной метод сортировки.
• detect_duplicates(arr, start, end) — эвристическая функция оценки доли дубликатов на основе случайной выборки. Если коэффициент повторений превышает 50%, предпочтение отдаётся сортировке подсчетом.
• dupesort(arr, start, end) — основной гибридный алгоритм. В зависимости от структуры данных, динамически выбирает между counting_sort и quicksort.
• generate_random_array(size) — генерирует массив случайных целых чисел в диапазоне от 0 до 1000.
• generate_duplicate_heavy_array(size, duplicate_ratio) — создает массив с заданной долей повторяющихся значений.
• benchmark_sort(sort_func, arr, trials) — запускает тесты на производительность выбранного алгоритма сортировки и возвращает среднее время выполнения.
• Визуализация (matplotlib) — строит график производительности и сохраняет его в файл performance_comparison.png.

Демонстрация работы

Были проведены тесты алгоритма DupeSort в сравнении с классической быстрой сортировкой на массивах объемом 50 000, 100 000 и 200 000 элементов, где 70% значений являются дубликатами. Тесты выполнялись на процессоре Apple M3 Pro под управлением macOS. Результаты приведены в таблице 1 и на рисунке 1.

Таблица 1.

Сравнение производительности (мс)

Рисунок 1. Сравнение производительности алгоритмов

Результаты тестирования показали значительное преимущество DupeSort при работе с массивами, содержащими большое количество дубликатов:

• На массивах размером 50 000 элементов: ускорение в 4.4 раза

• На массивах размером 100 000 элементов: ускорение в 4.6 раза

• На массивах размером 200 000 элементов: ускорение в 4.7 раза

При этом на случайных данных DupeSort демонстрирует сопоставимую производительность с классической быстрой сортировкой, показывая незначительное преимущество в 1-2%.

Заключение

Предложенный гибридный алгоритм DupeSort демонстрирует впечатляющие результаты при обработке массивов с большим числом одинаковых элементов, обеспечивая ускорение до 4.7 раз по сравнению с классической быстрой сортировкой. При этом алгоритм сохраняет конкурентоспособность на случайных данных, что делает его универсальным решением для широкого спектра задач. Особенно эффективен DupeSort при обработке логов, индексировании и работе с базами данных, где часто встречаются повторяющиеся значения. В дальнейшем возможно расширение алгоритма с учетом адаптивного выбора порога дубликатов и оптимизации для параллельного выполнения на GPU.

Список литературы:

1. Fuchs F., Dohan D., Menick J. и др. Faster sorting algorithms discovered using deep reinforcement learning // Nature. — 2023. — Т. 620. — С. 603–608. [электронный ресурс] — Режим доступа: https://www.nature.com/articles/s41586-023-06004-9 (дата обращения: 10.05.2025).
2. Heineman G.T., Pollice G., Selkow S. Algorithms in a Nutshell, 2nd Edition: A Desktop Quick Reference. — 2-е изд. — O’Reilly Media, 2015. — 450 с. [электронный ресурс] — Режим доступа: https://www.r-5.org/files/books/computers/algo-list/common/Heineman_Pollice_Selkow-Algorithms_in_a_Nutshell-EN.pdf (дата обращения: 10.05.2025).