Почему моя реализация Shaker Sort-а такая медленная?

Question

[Timur]

namespace Algorithms.Main.Sorting;

public class ShakerSort : SortAlgorithmBase<int>
{
    public override void Sort()
    {
        if (Items.Count <= 1)
            return;

        var maxIndex = Items.Count - 1;
        var left = 0;
        var right = maxIndex;

        while (left < right)
        {
            for (int i = left; i < right; i++)
            {
                var a = Items[i];
                var b = Items[i + 1];

                if (a.CompareTo(b) == 1)
                {
                    Swap(i, i + 1);
                }
            }

            right--;

            for (int i = right; i > left; i--)
            {
                var a = Items[i];
                var b = Items[i - 1];

                if (a.CompareTo(b) == -1)
                {
                    Swap(i, i - 1);
                }
            }

            left++;
        }
    }
}

Проверил скорость сделав тест:

[Test]
    public void ShakerSortTest()
    { 
       var algorithm = new ShakerSort();
        algorithm.Items = GetList();
        algorithm.Sort();
        Assert.That(isSorted);
    }
    [SetUp]
    public void SetUp()
    {
        var random = new Random();

        for (int i = 0; i < 1000; i++)
            _list.Add(random.Next(0, 10000));
    }

    private List<int> GetList() => [.._list];
    private readonly List<int> _list = [];

Использовал Stopwatch, он показывает то же время что и тесты.
Обычно время где то 120-180 мс, даже у Buble Sort от которого он пошел результат в раз 4-5 меньше.

Comments

[VoidVolker]

Дизассемблируете код и смотрите во что превратил ваш код оптимизатор. Ещё имеет смысл переписать код на си и сравнить с ним - как скорость так и результат работы оптимизатора в разных режимах оптимизации.

Answer 1

[Wataru]

Возможно, копирование данных во временные переменные a и b - медленно. Сравнивайте просто item[i] и item[i+1].

Потом, попробуйте закоментировать второй цикл, который идет с конца в начало. Сортировка первратится в bubbleSort. Я думаю, что это здорово ускорит ее. Тут дело в железе: самое медленное в современных процессорах - это обращение к памяти. И оно всякими костылями и подпорками ускореяется. Один из таких костелей - перефетчинг: когда вы читаете данные из какого-то места, процессор заранее читает сразу блок побольше, вдруг пригодится. Начиная с этого адреса и вперед.
И когда цикл идет i++, то эта оптимизация срабатывает. Данные для следующей итерации уже оказываются в кеше и работа с ними быстрая. С i-- этот фокус никак не помогает, поэтому циклы задом-на-перед гораздо медленнее циклов идущих по возрастанию индексов, даже если там ровно такие же операции. Потому что там команда чтения данных занимает гораздо больше тактов процессора.

Comments

[Timur]

public override void Sort()
    {
        if (Items.Count <= 1)
            return;

        var maxIndex = Items.Count - 1;
        var left = 0;
        var right = maxIndex;

        while (left < right)
        {
            for (int i = left; i < right; i++)
            {
                if (Items[i].CompareTo(Items[i + 1]) == 1)
                {
                    Swap(i, i + 1);
                }
            }
            right--;
        }
    }

Убрал временные переменные и 2-й цикл как вы и сказали. 1000 элементов от 0 до 1000 теперь Buble Sort сортирует за 25-40ms, а Shaker Sort за 220-300 ms.
То есть стало медленнее, забавно конечно)