Смещение/выравнивание/вращение кругового буфера до нуля на месте

Я использую круговой буфер для ввода данных в любой конец списка. После того, как я закончил, я хочу выровнять буфер так, чтобы первый элемент в списке находился в нуле нулевой позиции и может использоваться как обычный массив без каких-либо причудливых служебных указателей.

Итак, у меня есть круговой list с емкостью N, он имеет элементы N, начиная с произвольного индекса f.

Какой самый быстрый способ сдвинуть/повернуть все элементы таким образом, чтобы f = 0?

Ловушка: я хочу сделать это на месте (хотя, конечно, понадобятся некоторые регистры/временные файлы). Буфер может быть полным (n = N), [EDIT], но я также заинтересован в эффективном рассмотрении случаев, когда он почти пуст.

Ответ 1

Этот алгоритм, взятый из реализации std::rotate на cplusplus.com, довольно приятен:

template <class ForwardIterator>
  void rotate (ForwardIterator first, ForwardIterator middle,
               ForwardIterator last)
{
  ForwardIterator next = middle;
  while (first!=next)
  {
    swap (*first++,*next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

http://www.cplusplus.com/reference/algorithm/rotate/

Ответ 2

Сначала я предполагаю, что n=N. Вы можете поместить элемент f в 0, затем 0 перейдет в n-f, n-f в n-2f и т.д. После конечного числа шагов вы вернетесь к 0, благодаря теории групп. Вы перейдете ко всем пунктам не более 1 раза (за исключением, конечно, f, который является началом и концом).

Вы бы пошли на все предметы как минимум на 1? Ну, это зависит, если l=pgcd(N, f)==0. Если l==1, все готово. Если нет, вы должны выполнить ту же процедуру l-1 раз, начиная с (f+1)...(f+l-1). Эта процедура использует только одну переменную и выполняет ее на месте. Каждый цикл запускается на точных элементах n/f.

На следующем рисунке показан алгоритм с n = N = 12 и f = 3. Мы имеем l = 3, поэтому у нас есть три петли: marron, blue, green. Исходные числа находятся в черном цвете, финал окрашен.

Если n<N тот же алгоритм все еще работает, потому что пустая область до f в круговой массиве будет сообщаться в пустую область в конце линейной матрицы. См. Следующую схему для иллюстрации этого трюка. Мы имеем N=12, n=10 и f=3, поэтому 1 и 2 отсутствуют (т.е. они находятся в серой области или в кольце). l=gcd(3, 12)=3 здесь.

Для удобства кэширования вы можете инвертировать две петли. В этом случае вам понадобятся переменные l.

В псевдо-Python

from fractions import gcd
l = gcd(N, f)
niter = N//l                   # integer because l = gcd(N, f)
temp = t[f:(f+l-1)]
pos = f
for i=1 to niter
    for j=0 to l-1
        pos -= 1
        pos = (pos + N) % N    # in [0...N-1]
        swap(temp[j],  t[pos])

Ответ 3

В буфере назначения после позиции буфера поворота n получает сжатие позиции (n + f) % N. Трудная часть состоит в том, что могут произойти всевозможные последовательности замены. Это можно обработать путем прохождения этих последовательностей до тех пор, пока не произойдет первоначальное положение. Отслеживание того, сколько замен было сделано, позволяет алгоритму остановиться во времени.

Следующий метод тестирования действует на массив char, который проще всего настроить:

private char[] rotate(char[] buf, int start) {

    int len = buf.length;
    int count = 0;
    int offset = 0;

    while (count < len) {

        int index = offset;
        char tmp = buf[index];
        int index2 = (start + index) % len;

        while (index2 != offset) {

            buf[index] = buf[index2];
            count++;

            index = index2;
            index2 = (start + index) % len;
        }

        buf[index] = tmp;
        count++;

        offset++;
    }

    return buf;
}

Следующие тесты успешны:

public void testRotate() {

    assertEquals("A",       rotate("A",         0));
    assertEquals("AB",      rotate("AB",        0));
    assertEquals("AB",      rotate("BA",        1));

    assertEquals("ABCD",        rotate("DABC",      1));
    assertEquals("ABCDE",       rotate("DEABC",     2));
    assertEquals("ABCDEF",      rotate("DEFABC",    3));
    assertEquals("ABCDEF1",     rotate("DEF1ABC",   4));
    assertEquals("ABCDEF12",    rotate("DEF12ABC",  5));
    assertEquals("ABCDEF123",   rotate("DEF123ABC",     6));
}

private String rotate(String buf, int start) {

    return new String(rotate(buf.toCharArray(), start));
}

Update:

Вышеупомянутый алгоритм вращает полный буфер, чтобы оптимизировать вращающиеся буферы, которые не заполнены, вы можете выбрать быстрые выигрыши и использовать полное вращение для того, что осталось:

private char[] realign(char[] buf, int start, int items) {

    int len = buf.length;
    int offset = 0;

    if (0 == start) {

        // done

    } else if (items <= len - start) {

        // simply move to front
        while (offset < items) {
            buf[offset++] = buf[start++];
        }

    } else if (items * 2 <= len) {

        // move lead out of the way first
        int last = start;
        int end = items - len + start;

        while (0 < end) {
            buf[--last] = buf[--end];
        }

        while (offset < items && start < len) {

            buf[offset++] = buf[start++];
        }

        while (offset < items) {

            buf[offset++] = buf[last++];
        }

    } else {

        // use full rotate on the rest
        buf = rotate(buf, start);
    }

    return buf;
}

Это позаботится о большинстве ситуаций, в которых буфер, если он заполнен более чем наполовину и где он завертывается в конец буфера, полностью вращается. Достигнуты следующие тесты:

public void testRealign() {

    assertEquals("A",       realign("A",        0, 1));
    assertEquals("AB",      realign("BA",       1, 2));

    assertEquals("ABCD",        realign("DABC",     1, 4));
    assertEquals("ABCDE",       realign("DEABC",    2, 5));
    assertEquals("ABCDEF",      realign("DEF123ABC",    6, 6));

    assertEquals("0123456789",  realign("4567890123", 6, 10));

    assertEquals("ABC",         realign("ABC",  0, 3));
    assertEquals("ABC",         realign("012ABC3", 3, 3));
    assertEquals("ABC",         realign("01234ABC", 5, 3));
    assertEquals("ABCD",        realign("D1234ABC", 5, 4));
    assertEquals("ABCD",        realign("CD1234AB", 6, 4));
    assertEquals("ABCD",        realign("BCD1234A", 7, 4));
}

private String realign(String buf, int start, int items) {

    return (new String(realign(buf.toCharArray(), start, items))).substring(0,  items);
}

Ответ 4

Прежде всего, вы не должны выровнять буфер. Похоже на ненужные накладные расходы.

Напротив, способ реализовать это должен быть

1) Создайте новый массив
2) Копировать элементы (std:: copy) из n = 0 в конец массива
3) Копирование начала массива от f = 0 до n = 6
4) std:: swap массивы