С++: сдвиг в динамическом массиве

[Кот]

На 1 двигается идеально, но если ввести 2, то все равно на 1 двигается. Будто бы К не на что не влияет

как не влияет? там же есть счетчик.
или там сдвигается только на 1 при любом К?.. если да, то в этом и заключалась идея. т е двигать по 1.
двигать первый элемент и переставлять все на места предыдущих.
может вы не обнуляли... хотя, вроде есть при задаче...

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

 

[sami]

Ты прав. Предложи свой вариант решения, академически правильный. :angry:

Смысл такой:
Запоминаем первый элемент массива, ставим на его место тот элемент, который должен стоять на его месте.
А на место того - тот, который будет стоять на том месте. И так передвигаем элементы пока не уткнемся в место первого. На место последнего ставим запомненный элемент. Повторяем обмен начиная со следующего индекса массива пока не произведем число перестановок, соответствующее длине массива.

void shift(int* pdata, int n, int k)
{
int xchangeCount = 0;
for (int start = 0; xchangeCount < n; start++)
{
int tmp = pdata[start];
int current = start;
while(true)
{
int next = (current + n - k) % n;
if (next == start)
{
pdata[current] = tmp;
xchangeCount++;
break;
}
pdata[current] = pdata[next];
xchangeCount++;
current = next;
}
}
}

Дополнительная память - только под стек (который не растет, т.к. нет рекурсии), число шагов - O(N).

 

[Touareg]

Смысл такой:

Рационально и скучно, вариант fusion с указателями мне понравился больше. :angry:
Чуть расточительно по памяти, зато экстремально быстро и без перемещения данных.

 

[sami]

Рационально и скучно, вариант fusion с указателями мне понравился больше. :angry:

Но он требует трехкратного объема памяти. И зависит от способности аллокатора тереть память. Красивым его не назовешь. Твой с копированиями лучше.

Чуть расточительно по памяти, зато экстремально быстро и без перемещения данных.

Без перемещения?
Данные нужно скопировать трижды!
Ответ во временном массиве не принимается, т.к. неизвестно кто и как его должен освобождать.

 

[Touareg]

Но он требует трехкратного объема памяти. И зависит от способности аллокатора тереть память. Красивым его не назовешь. Твой с копированиями лучше.


Без перемещения?
Данные нужно скопировать трижды!
Ответ во временном массиве не принимается, т.к. неизвестно кто и как его должен освобождать.

Ну подход красивый согласись))
Именно с академической точки зрения я считаю такой образ мышления надо поощрять.

И кстати насчет тройного копирования ты не прав, если задача именно такая как в первом сообщении темы, можно при введении пользователем размера массива N создать массив 2*N и затем ничего никуда не копировать, только указатели аккуратно двигать. Или нет? Вроде да) Тогда и без массива B можно обойтись, а значит и по памяти проигрыша нет.
Конечно только один раз сдвиг сработает, но это уже второй вопрос.

 

[sami]

Ну подход красивый согласись))
Именно с академической точки зрения я считаю такой образ мышления надо поощрять.

Нестандартно - да. Поощрять - не думаю.
а красивше было бы сделать

for(int i = 0; i < n; i++)
dst[(i+n-k)% n] = src[i];

Но вот за это

вопрос в том освободится ли А не затерев содержимое массива.

можно смело ставить пару по предмету, или как минимум снижать оценку.

И кстати насчет тройного копирования ты не прав, если задача именно такая как в первом сообщении темы, можно при введении пользователем размера массива N создать массив 2*N и затем ничего никуда не копировать, только указатели аккуратно двигать. Или нет? Вроде да)

Задача сформулирована - получить массив длиной N и сделать сдвиг.
Если будет массив длиной 2N, то это будет решение другой задачи, хоть пользователь может быть удовлетворен решением.

На месте преподавателя я бы желал видеть функцию, сдвигающую массив. А за лапшу в одном методе main отстреливал бы.

 

[Touareg]

Ну да, во время ввода массива пользователем (когда дороговизна копирования неактуальна) заполнять массив 2*N сразу сдвоенными значениями в 0, N+1; 1, N+2 и т.д., а затем когда вводится на сколько сдвигать K перемещать указатель. Круто))))

Задача сформулирована - получить массив длиной N и сделать сдвиг.
Если будет массив длиной 2N, то это будет решение другой задачи, хоть пользователь может быть удовлетворен решением.

На месте преподавателя я бы желал видеть функцию, сдвигающую массив. А за лапшу в одном методе main отстреливал бы.

Да понятно что универсально приемлемый алгоритм примерно описан здесь, а в случае острой ограниченности ресурсов по памяти актуален твой вариант, дурачусь просто. :angry:

 

[sami]

Да понятно что универсально приемлемый алгоритм примерно описан здесь, а в случае острой ограниченности ресурсов по памяти актуален твой вариант, дурачусь просто. :angry:

Мой вариант актуален еще тем, что его можно обобщить. Выполнять им не только циклический сдвиг, а любую трансформацию массива по взаимно-однозначному закону преобразования индексов. Для этого стоит лишь параметризовать метод сдвига функцией, получающей старый индекс элемента по новому (можно немножко вывернуть алгоритм наизнанку и параметризовывать функцией получения нового индекса по старому).
Тогда этим методом можно будет выворачивать массив наизнанку, транспонировать линейно развернутую в массив матрицу, и т.п.

Но это преимущество алгоритма, но не преимущество решения данной задачи.

 

[Touareg]

Задача сформулирована - получить массив длиной N и сделать сдвиг.
Если будет массив длиной 2N, то это будет решение другой задачи, хоть пользователь может быть удовлетворен решением.

То что мы сразу при вводе данных вместо массива N создаем массив 2N (взамен не создавая результирующий массив) это детали реализации, таким образом если на каждый ввод данных требуется однократный сдвиг вправо на K меньшее N (а по условиям задачи все именно так), то решение с указателем является наилучшим как по использованию памяти, так и по времени исполнения. Можно сказать что это пример агрессивной оптимизации, совершенно не универсальный, компактный, элегантный и быстрый. :angry:

Мой вариант актуален еще тем, что его можно обобщить. Выполнять им не только циклический сдвиг, а любую трансформацию массива по взаимно-однозначному закону преобразования индексов. Для этого стоит лишь параметризовать метод сдвига функцией, получающей старый индекс элемента по новому (можно немножко вывернуть алгоритм наизнанку и параметризовывать функцией получения нового индекса по старому).
Тогда этим методом можно будет выворачивать массив наизнанку, транспонировать линейно развернутую в массив матрицу, и т.п.

Но это преимущество алгоритма, но не преимущество решения данной задачи.

Абсолютно согласен)

Кстати а вариант SCTRWD с академической точки зрения хорош активным использованием стандартных библиотечных функций, с точки зрения препода такой подход я бы тоже оценил. Правда интуиция подсказывает что код там не рабочий и память жрет как белаз соляру, но опять же с академической точки зрения это пофиг. :lol:

 

[Touareg]

а красивше было бы сделать

for(int i = 0; i < n; i++)
dst[(i+n-k)% n] = src[i];

А вот такой код я недолюбливаю и красивым не считаю, он мне моск форматирует и без комментария нечитабелен. :angry: :lol:

Вот такую ассоциацию подобный код у меня вызывает)
Посмотреть вложение 123627

 

[gLm]

Кстати а вариант SCTRWD с академической точки зрения хорош активным использованием стандартных библиотечных функций, с точки зрения препода такой подход я бы тоже оценил. Правда интуиция подсказывает что код там не рабочий и память жрет как белаз соляру, но опять же с академической точки зрения это пофиг. :angry:

Вполне рабочий.

 

[Touareg]

Вполне рабочий.

Точно с краёв там всё ровно?

 

[gLm]

Точно с краёв там всё ровно?

Да
Посмотреть вложение 123628

 

[Touareg]

Да

Каюсь. :angry: :lol:

 

[sami]

То что мы сразу при вводе данных вместо массива N создаем массив 2N (взамен не создавая результирующий массив) это детали реализации, таким образом если на каждый ввод данных требуется однократный сдвиг вправо на K меньшее N (а по условиям задачи все именно так), то решение с указателем является наилучшим как по использованию памяти, так и по времени исполнения. Можно сказать что это пример агрессивной оптимизации, совершенно не универсальный, компактный, элегантный и быстрый. :angry:

Время исполнения будет страдать по сравнению с твоим вариантом в случае когда K будет соразмерен с кэшем процессора либо больше его. Решение элегантно для сдвига массива при пользовательском вводе, но не годится в качестве библиотечного.

Абсолютно согласен)

А зря! С обобщением я перегнул Потребуется более серьезная модификация с тем чтобы отслеживать непройденные цепочки преобразований. Потребуется дополнительная память в общем случае O(N)

А вот такой код я недолюбливаю и красивым не считаю, он мне моск форматирует и без комментария нечитабелен. :lol:

Вот такую ассоциацию подобный код у меня вызывает)
Посмотреть вложение 123627

for(int i = 0; i < n; i++)
dst[newindex(i)] = src[i];

Может так лучше? Только тут без лексических замыканий не обойтись, а это уже не школьная программа и не C++, скорее D. Пусть меня поправит кто-нибудь.

 

[Touareg]

Лишь бы Стёпчегу на пользу пошло я считаю, потому что резюмируя тему могу сказать - подходы бывают разные, правильных решений обычно больше чем одно, и даже если код компилируется и работает это еще не значит что он достаточно хорош.

 

[gLm]

Ну еще переворотами можно попробовать

void Reverse(int *M, int n)
{
int *tM = M + n - 1;
for(n = n/2; n; n--)
{
*M ^= *tM;
*tM ^= *M;
*M++ ^= *tM--;
}
}

void Shift(int *M, int n, int k)
{
if (k < n && k>0) 
{
Reverse(M,n);
Reverse(M,k);
Reverse(M+k,n-k);
}
}

 

[sami]

Ну еще переворотами можно попробовать

void Reverse(int *M, int n)
{
int *tM = M + n - 1;
for(n = n/2; n; n--)
{
*M ^= *tM;
*tM ^= *M;
*M++ ^= *tM--;
}
}

void Shift(int *M, int n, int k)
{
if (k < n && k>0) 
{
Reverse(M,n);
Reverse(M,k);
Reverse(M+k,n-k);
}
}

Элегантно тем что без дополнительной памяти, но вот за swap через xor я бы не похвалил. Классический swap с временной переменной гораздо более нагляден (узнаваем в коде) и легко обобщим для любого типа с конструктором копирования (не считая того что работает быстрее чем xor-ы).

На мой взгляд самая красивая реализация будет с использованием высокоуровневых методов:

shiftList k xs =
let a = take d xs
b = drop d xs
in  b ++ a
where 
d = (length xs) - k

Читается легко: взять первые (n-k) элементов последовательности (a), взять оставшиеся k элементов angry:, и приклеить первую ко второй (b++a)

 

[fusion]

Но вот за это

вопрос в том освободится ли А не затерев содержимое массива.

можно смело ставить пару по предмету, или как минимум снижать оценку.

А что очевидно, что при освобождении указателя методом free физически затирается память?
Тогда можно А=NULL.

 

[sami]

А что очевидно, что при освобождении указателя методом free физически затирается память?

Нет, это не очевидно. Однако в общем случае ничто не гарантирует неизменность содержимого памяти после ее освобождения. Указатель в момент освобождения становится диким и дальнейшее обращение к области памяти считается серьезной ошибкой (http://en.wikipedia.org/wiki/Malloc#Use_after_free).

Тогда можно А=NULL.

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