среда, 4 июля 2018 г.

Сдвиг массива влево на N элементов

Есть ряд способов сдвинуть массив влево на N элементов. Можно взять и сделать N сдвигов по одному элементу, получив квадратичную сложность. Можно создать целевой массив по размеру исходного и вычислить положение каждого элемента после сдвига. Хорошо, но скорость линейна, затраты по памяти - тоже.
Если чутка подумать, то можно придумать реализацию, которая мутирует массив и дает линейную скорость и константные затраты по памяти. Но есть один очень элегантный способ – из 3-х строк на основе чудо Span of T из System.Memory:
public static void RotateLeft(int[] input, int direction)
{
    input.AsSpan(0, direction).Reverse();
    input.AsSpan(direction).Reverse();
    input.AsSpan().Reverse();
}
Идея такая: чтобы сдвинуть массив из K элементов на N элементов влево, нужно перевернуть первые N элементов в массиве, затем последние K - N -1 элементов, а затем перевернуть весь массив:
// direction == 2, input.Length == 7
input.AsSpan(0, direction).Reverse();
// [2][1][3][4][5][6][7]
input.AsSpan(direction).Reverse();
// [2][1][7][6][5][4][3]
input.AsSpan().Reverse();// [3][4][5][6][7][1][2]

Получается два прохода по массиву, но зато с читабельностью решения все очень ОК.

14 комментариев:

  1. Справедливости ради, хочу отметить, что это циклический сдвиг влево.

    ОтветитьУдалить
    Ответы
    1. Не совсем понял мысль. Да, это одна из реализаций циклического сдвига влево. Просто, ИМХО, одна из самых кратких и выразительных.

      Удалить
  2. В своё время этот фокус произвёл на меня большое впечатление... минут 20 рисовал на листике пытаясь понять как этот трюк работает :)

    Он же, но чуть с большим wow-эффектом (IMHO) используется в задачке Reverse Words: когда необходимое переставить слова в предложении в обратном порядке. Например: "Michael Jordan" => "Jordan Michael". Необходимо сделать "реверс" каждого слова и потом реверс всей строки целиком, что в конечном итоге даёт практически линейную сложность.

    ОтветитьУдалить
    Ответы
    1. О! Отличный трюк.
      З.Ы. Сложность-то линейная, просто коэффициент равен 2.

      Удалить
  3. Фокус интересный. Но по поводу читабельности - не соглашусь. Оно же крайне не очевидно. Но элегантный, да

    ОтветитьУдалить
    Ответы
    1. Ну такое... по этой теории каждый второй алгоритм можно зафукать :)))

      Удалить
    2. Так гораздо понятнее, чем циклический сдвиг врукопашную.

      http://codelib.ru/task/cycle_shift/

      Удалить
    3. Мне кажется, что без комментария с небольшим примером решение неочевидно. Но оно читаемо, поскольку состоит из 3 строк. После же того, как прогнан в голове/дебагере один пример, то решение садится в голове прочно.

      Удалить
  4. Почему "затем последние K - N -1 элементов", если необходимо перевернуть K - N последних элементов?

    ОтветитьУдалить
  5. В "Жемчужинах программирования" читал что-то подобное... я уже не помню, но там с помощью реверса решалась задача. Интуитивно восстановил алгоритм: Сложность 4N, дополнительной памяти не требуется.

    Пример:
    исходный массив: 1234567 сдвиг вправо на 3

    преобразования:
    1234765
    4321765
    5671234
    5674321

    ОтветитьУдалить
    Ответы
    1. Этот комментарий был удален автором.

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. Я ошибся. Сложность 3N-k (где k - кол-во элементов, на которое сдвигается массив).

      Да и сдвинул я не вправо на 3, а влево на 4 :)

      Удалить