среда, 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]

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

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

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

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

      Удалить
    2. nit: Мне показалось, что Vasya всего лишь хотел справедливо заметить, что слово "сдвиг" в заголовке и теле поста лучше бы заменить на "циклический сдвиг".

      Удалить
  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. Этот комментарий был удален автором.

      Удалить
  6. Главное, чтобы подобные алгоритмы оставались уделом олимпиад и научных статей. В промышленном коде применять такое боже упаси. Понадобится после аффтора что-то поправить в задаче, голову сломаешь и времени убьешь черт знает сколько.

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

    ОтветитьУдалить