Одномерный массив. Циклический сдвиг вправо - C++

@TheCalligrapher · Регистрация: 18.10.2014

Сообщение от Байт

Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего.

Отнюдь!

Во-первых, авторитет классической книги мы тут оспаривать мы не будем. Задача действительно является жемчужиной.

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

Формально оптимальным решением данной задачи является "жонглирующий" алгоритм, который берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали). Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется).

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

Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма

Другие темы раздела
C++ Правило хорошо тона при Рендеринге !? http://www.cyberforum.ru/cpp-beginners/thread777792.html Появился такой вопрос, правильно ли запихивать указатель на устройство рендеринга в объект. Class Object { //.. D3DXDEVICE * pVideoCard; //.. } или схожий пример для обертки над DirectX Class Object {	C++ Build Error 1. откуда взялся? в универе простые задачки решали письменно, решила попробовать прогу создать по одной из простеньких что было. вроде все правильно,но выбило ошибку Build Error 1 . в чем причина?? #include<stdio.h> #include<stdlib.h> int main() {int i; int R; for (i=0;i>=255;i++) R=rand; for (i=0;i>=255;i++) printf("yniversal'noe mno*estvo: %d", R); http://www.cyberforum.ru/cpp-beginners/thread777785.html
C++ Чётные числа на нечётных местах Доброго времени суток, уважаемые форумчане! Уже больше 10 часов бьюсь на задачей, но почти безрезультатно. Перерыла весь интернет, и здесь искала, но того что мне нужно не нашла. Задание такое: Дано n, a. Определить количество чётных чисел, стоящих на нечётных местах. Помогите, пожалуйста, две задачи из трёх сделала, если эту не сделаю - отчисление из колледжа :( Я смогла вывести массив на...	C++ Что за входным параметром DynamicArray(long s = 10): size(s), count(0)? : size(s), count(0) объясните что это ? //конструкторы DynamicArray(long s = 10): size(s), count(0) { //<=======================что это? p = new T; if(!p) cout << "Ошибка при создании массива" << endl; }
C++ сумма ряда 1,3,5,7 http://www.cyberforum.ru/cpp-beginners/thread777752.html # include <stdio.h> # include <conio.h> #include <iomanip> int main () { setlocale(LC_ALL,"Russian"); int i,n,s=0; printf ("\n Введите количество первых нечетных чисел которые необходимо просумировать n=\n"); scanf ("%d",&n);	C++ функция для нахождения длины связного списка Помогите написать функцию для нахождения длины связного списка. реализуйте функцию итеративно и рекурсивно. getLength (NULL) должен возвращать 0. class List { public: int value; List* next; }; int getLength(List* list) подробнее

@TheCalligrapher С чаем беда... 3705 / 1980 / 516 Регистрация: 18.10.2014 Сообщений: 3,563
	05.03.2016, 00:30 Одномерный массив. Циклический сдвиг вправо
	Сообщение от Байт Задача нетривиальна только для совершенно начинающего и ничегошеньки не соображающего. Отнюдь! Во-первых, авторитет классической книги мы тут оспаривать мы не будем. Задача действительно является жемчужиной. Во-вторых, в "Жемчужинах программирования" эта задача преподносится в большей степени для иллюстрации того, как формальная эффективность алгоритма (в данном случае - оцениваемая по количеству переносов единичных элементов массива в памяти) может существенно не согласовываться с фактической производительностью реализации этого алгоритма на современных кэшированных архитектурах. Формально оптимальным решением данной задачи является "жонглирующий" алгоритм, который берет элемент массива i и сразу же перемещает его в его финальную позицию (i + K) % N (я не буду расписывать все детали). Однако фактически такой алгоритм ведет себя очень плохо с точки зрения локализации доступа к памяти и громко проигрывает как реверсивному, так и блочно-обменному алгоритму на современных кэшированных архитектурах (при достатчоном размере массива, разумеется). Вопрос поиска алгоримов и эффективных реализаций, которые хорошо себя ведут в таких ситуациях - вопрос весьма и весьма нетривиальный и, во многих случаях, неаналитический, т.е. решаемый только на чисто эмпирической основе. Кстати, ваше упоминание НОД свидетельствует именно о том, что вы изобрели какую-то вариацию того самого "жонглирующего" алгоритма