qwerty: Задачка

(Добавить комментарий)

	(Анонимно) 2010-01-25 05:22 (ссылка)
	for (int i=0; i<a; i++) x[b+i] = x[i]; for (int j=0; j<b; j++) x[j] = x[a+c+j]; (Ответить) (Ветвь дискуссии)

	qwerty 2010-01-25 12:22 (ссылка)
	Вы, извините, неявно предполагаете, что a &le b && b &le c. (Ответить) (Уровень выше)

	phantom 2010-01-25 13:18 (ссылка)
	Можно в цикле записывать поверх мусора. Каждый раз ненужная область перемещается на источник (если он не принадлежит концу). Чтений-записей будет ровно a+b. (Ответить) (Ветвь дискуссии)

	qwerty 2010-01-25 13:51 (ссылка)
	Ну вот, допустим, a=3, b=2, c=1. Берем карандашик, аккуратно рисуем клеточки, внимательно смотрим на ненужную область... (Ответить) (Уровень выше) (Ветвь дискуссии)

	phantom 2010-01-25 14:06 (ссылка)
	Да, не вышло. (Ответить) (Уровень выше)

	kouzdra 2010-01-25 13:38 (ссылка)
	Ну как - развернуть задом наперед, потом каждый из массивов развернуть еще раз. (Ответить) (Ветвь дискуссии)

	qwerty 2010-01-25 13:43 (ссылка)
	Чтений и записей при этом получается ровно вдвое больше. (Ответить) (Уровень выше)

	qwerty 2010-01-25 13:53 (ссылка)
	Т.е. в лучшем случае вдвое больше, а если в лоб, то еще плюс к этому чтение и запись всего мусора. (Ответить) (Уровень выше) (Ветвь дискуссии)

	kouzdra 2010-01-25 14:00 (ссылка)
	Зато красиво :) (Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-25 14:23 (ссылка)

Ну, на самом деле, если просто свопами записать, там еще и результат не совсем правильный - дыра не в конце, а посредине, - но это лечится. После этого, правда, красоты остается совсем мало - все свопы разные.

(Ответить) (Уровень выше)

kouzdra
2010-01-25 14:03 (ссылка)

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

	qwerty 2010-01-25 14:29 (ссылка)
	Стучит в сердце "Занимательная математика" Перельмана переливанием воды из пустого в порожнее :) (Ответить) (Уровень выше)

	crazyhome.livejournal.com 2010-01-25 14:58 (ссылка)
	x[b+1]=x[1]; x[1]=x[a+c+1]; x[b+2]=x[2]; x[2]=x[a+c+2]; ... (Ответить) (Ветвь дискуссии)

qwerty
2010-01-25 15:10 (ссылка)

Все бы ничего, но ведь вы пишите в тот же массив, из которого читаете. И в том месте, куда вы пишите, не обязательно лежит мусор. А зависит это от соотношений между a, b и c.

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

crazyhome.livejournal.com
2010-01-25 16:59 (ссылка)

Хотел кратко, но, видимо, надо пояснить.
У меня идут пары присваивания. В какой-то момент пары прекращаются и остается только одно из двух (какое из двух - в зависимости от того, что больше - а или b). Первое из пары - это перемещение массива А на свое место и освобождение места под В; второе из пары - это перемещение массива B на свое место (там, где был только что элемент из А).
В том месте, куда я пишу, лежит или мусор (первое присваивание из пары), или "уже мусор" (второе присваивание из пары; это элемент массива А или B, который уже перемещен на свое место в первом присваивании из пары, и свое старое место освободил для другого элемента массива).
В общем, суть в том, что массивы перемещаются не "по очереди" (сначала весь один массив, а потом весь другой), а "параллельно" (одни элемент из А, один элемент их B, одни элемент из А, один элемент их B и т.д.).

(Ответить) (Уровень выше)

	crazyhome.livejournal.com 2010-01-25 17:02 (ссылка)
	Посмотрел коммент ниже и понял, что мой способ работает только при c>0. А при с=0, по-моему, вообще нельзя, если посторонняя память не используется. (Ответить) (Уровень выше)

	crazyhome.livejournal.com 2010-01-25 17:47 (ссылка)
	А, понял... Немного недодумал ;) ppkk - додумал ;) (Ответить) (Уровень выше) (Ветвь дискуссии)

ppkk
2010-01-25 20:27 (ссылка)

Но я неправильно написал: поторопился, не проверил. В моём понимании условий либо этот алгоритм работал, либо невозможно (причём я подразумевал наличие нескольких целочисленных переменных).

http://lj.rossia.org/users/qwerty/132388.html?thread=503332#t503332 — для этого не работает.

Похоже, что какие-то недомолвки имеются, какие-то вольности с арифметическими действиями или посторонней памятью. Пока я деталей не пойму, как идёт учёт действий при a=1, c=0 и b=1, исправлять ошибку свою не берусь.

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-26 00:04 (ссылка)

Ну, давайте считать, что у нас имеется абстрактный вычислитель load-store архитектуры с 8 или 16 регистрами общего назначения, некоторым набором 2-адресных инструкций, оперативной памятью ровно в размер упомянутого массива и памятью и достаточным количеством памяти для хранения инструкций программы, с которой больше ничего делать нельзя. К вычислителю Дед Мороз приложил простой компилятор с Ц-подобного языка, который все локальные переменные отводит в регистрах, а если не может этого сделать, то ломается.

(Ответить) (Уровень выше)

А в чём трудность-то ?

tristes_tigres
2010-01-25 15:34 (ссылка)

for (k = 0; k < min(a, b); k++) {
  x[b + k] = x[k];
  x[k] = x[b + c + k];
 }

if(a >= b) {
  for (k = b; k < a; k++) {
    x[b + k] = x[k];
  }
 } else {
   for (k = a; k < b; k++) {
    x[k] = x[b + c + k];
  }
 }

Ну, подразумевается, что с > 0

(Ответить) (Ветвь дискуссии)

	Re: А в чём трудность-то ? qwerty 2010-01-25 16:33 (ссылка)
	Берем a=2, b=1, c=1 и убеждаемся, что забава таки присутствует. Ну и, кроме того, c может быть нулевым. (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А в чём трудность-то ?

tristes_tigres
2010-01-25 19:15 (ссылка)

За исключением (очевидной) опечатки
x[k] = x[b + c + k];
должно быть
x[k] = x[a + c + k]
, не вижу никакой забавы.

Если с=0, то нужно либо разрешить внешнюю память для одного значения - т.е., ещё переменную кроме k, - либо увеличить разрешенное число операций. Иначе никак.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А в чём трудность-то ?

qwerty
2010-01-26 00:10 (ссылка)

Первое же присваивание первого же цикла невозвратимо затирает последний элемент массива A.

Насчет же места хранения значений a, b, c, переменных цикла, временных значений при вычислении выражений, локалов и проч, если настолько хочется зангудства, то вот.

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: А в чём трудность-то ?

tristes_tigres
2010-01-27 10:43 (ссылка)

Ну тогда

void
swap(int a, int b, int c, int x[])
{
  int k, m;
  int d;
  int v, w;
  int indx, key;
  
  d = gcd(a + b + c, b);
  
  for(k = 0; k < d; k++) {
    v = x[k];
    key = 1;
    for(m = 1; m <= (a + b + c)/d; m++) {
      indx = (k + m*b)%(a + b + c);
      if( (indx < a) || (indx >= a + c)) {
	w = x[indx];
      } 
      if (key == 1) {
	x[indx] = v;
      }
      v = w;
      if( (indx < a) || (indx >= a + c)) {
	key = 1;
      } else {
	key = 0;
      }
    }
  }

}

int 
gcd(int a, int b)
{
  int t;
  
  if (b > a) {
    t = b;
    b = a;
    a = t;
  }
  while (b != 0) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}

(Ответить) (Уровень выше)

ppkk
2010-01-25 17:20 (ссылка)

Видимо, если a или b равно нулю, то c>0? Ну и на пару переменных место не "категорически отсутствует".

Ставим на место a+1 то, что полагается (если a+1<=a+b), запоминаем, откуда взяли. Ставим на то место что полагается, если оно под номером <=a+b и т.д. Потом переходим к a+2 и т.д.

(Ответить) (Ветвь дискуссии)

phantom
2010-01-25 19:53 (ссылка)

Здесь тот же контрпример подходит, что и к моему решению.

>Ну и на пару переменных место не "категорически отсутствует".

Есть приём перестановки значений переменных без использования дополнительной переменной.

(Ответить) (Уровень выше) (Ветвь дискуссии)

ppkk
2010-01-25 20:39 (ссылка)

Да, слажал я.

Про "хитрые" перестановки: в итоге (в общем случае) может быть, что должно измениться каждое число (из примера: для 1 2 3 0 4 5 — 4 5 1 2 3 ?). Значит (хотя бы в некоторых ситуациях) каждая запись придаёт окончательное значение числу в ячейке, кроме того, каждая ячейка массивов A и B должна быть прочитана хотя бы по разу, а значит и не более раза.

Так что целочисленные хитрости вряд ли годятся (либо я неправильно понимаю условие, а у нас на самом деле есть возможность совершать арифметические действия со значениями ячеек, якобы "не читая" и "не записывая"). Если происходит: M[x] := M[y] + M[z] или M[x] := M[x] + M[y], то я считаю, что происходит два чтения и одна запись. Обмен значениями M[x] и M[y] — два чтения, две записи и две ячейки памяти.

Указание http://lj.rossia.org/users/qwerty/132388.html?thread=505892#t505892 , что: "Ну и, кроме того, c может быть нулевым,"— заставляют меня упереться в случай a=b=1, c=0 без понимания того, как результат достигается.

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

phantom
2010-01-25 21:11 (ссылка)

>каждая запись придаёт окончательное значение числу в ячейке, кроме того,
>каждая ячейка массивов A и B должна быть прочитана хотя бы по разу, а значит и не
>более раза.

Да, вроде того.

>Обмен значениями M[x] и M[y] — два чтения, две записи и две ячейки памяти.

Две записи и 4 чтения вроде.

(Ответить) (Уровень выше) (Ветвь дискуссии)

ppkk
2010-01-25 21:22 (ссылка)

Две записи и 4 чтения вроде.
Не знаю, как ты это насчитал, но случай a=b=1, c=0 определённо нуждается в пояснениях.

В этом обсуждении деталей явно меньше, чем в вопросе http://bytes.com/topic/algorithms/answers/875234-remapping-elements-array (позабавили комментарии)

(Ответить) (Уровень выше) (Ветвь дискуссии)

	phantom 2010-01-25 22:57 (ссылка)
	Я имел в виду классическую (хм) задачу: x = x + y; y = x - y; x = x - y; Ой, ошибся там. 6 чтений, 3 записи. (Ответить) (Уровень выше) (Ветвь дискуссии)

ppkk
2010-01-25 23:30 (ссылка)

Ответ: x=y=0?:)

Как задачу это не встречал, вероятно и потому, что так обожали менять значения в программах-примерах: составителям, в отличие от меня, это нравилось.

При таких раскладах (особенно если вопят об отсутствии памяти) кажется единственной возможной операция по записи числа на "пустое" мето. Я торопился, так что предположил, что c=0 не бывает, рассмотрел c=1, там всё однозначно (и, как я не удосужился проверить, не работает), а дальше однозначно обобщил на c>1. Так как "задачка" оказалась из жанра "угадай условие", буду ждать, когда

qwerty@lj самоудовлетворённо напишет, что все идиоты, а он Д'Артаньян: видимо, узнаю и условия, и решение, алгоритм по-любому должен быть интересным.

(Ответить) (Уровень выше) (Ветвь дискуссии)

phantom
2010-01-26 11:51 (ссылка)

>Как задачу это не встречал, вероятно и потому, что так обожали менять значения в
>программах-примерах: составителям, в отличие от меня, это нравилось.

В книге Шеня идёт как задача, правда, сразу с решением.

>видимо, узнаю и условия, и решение, алгоритм по-любому должен быть интересным.

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

(Ответить) (Уровень выше) (Ветвь дискуссии)

ppkk
2010-01-26 17:33 (ссылка)

скорее для разминки мозга, нежели несущие какую-либо практическую ценность
Зависит от работы.
Я устроился программистом (криптография-криптоанализ) — "эти задачи" были актуальны, но тянуло к переписыванию на ассемблере с SSE и прочей жутью. А сейчас просто тупо программирую то, в чём редко надо умничать. Но задачи типа упрощённого движка шаблонов или операций со списками, которые должны быть эффективными, порой встречаются: многие их решают неправильно. Или с базами данных бывает над чем подумать.

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

(Ответить) (Уровень выше)

ppkk
2010-01-25 23:38 (ссылка)

Тут и сложение, и вычитание, и неизвестно, где хранятся значения аргументов во время вычисления.

Так можно предположить, например, что для всевозможных перестановок τ l<=10-и элементов есть операция τ(x1,…,x_l), которая переставляет в массиве элементы с заданными индексами согласно τ, причём засчитывается за l чтений и l записей, не требуя дополнительной памяти:)

Кроме того, если это "математические" целые числа, то мы можем за один проход по важным числам неизвестно где (если к циклам не придирались, то в счётчике?) закодировать их все, после чего в один проход раскодировать куда надо.

Жду автора на белом коне, в общем…

(Ответить) (Уровень выше) (Ветвь дискуссии)

	qwerty 2010-01-26 00:10 (ссылка)
	http://lj.rossia.org/users/qwerty/132388.html?thread=509988#t509988 (Ответить) (Уровень выше)

phantom
2010-01-26 11:56 (ссылка)

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

Кстати, у меня один знакомый был, который программируя на одном чипе, утверждал, что он считает ДПФ по стандартной формуле быстрее, чем БПФ, благодаря операции умножения с накоплением.

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-26 13:19 (ссылка)

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

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

В части ограничения памяти задача вполне практическая, а сугубые
ограничения на число чтений и записей, конечно, для забавы. Из практически приемлемых самое красивое в худшем случае делает 3a+2b+c чтений и записей с хорошей локальностью.

(Ответить) (Уровень выше) (Ветвь дискуссии)

phantom
2010-01-26 13:29 (ссылка)

А вот нехорошо давать задачи, которые не имеют решения. Или надо оговаривать, что проблема открытая. Также стоило сказать, что это практическая задача - это в корне меняет подход.

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-26 13:51 (ссылка)

Эээ... Чего это вдруг она не имеет решения? От того, что вы вдруг обнаружили, что где-то нужно хранить локальные переменные?

В указанных ограничениях эта задача практической не является.

(Ответить) (Уровень выше) (Ветвь дискуссии)

phantom
2010-01-26 15:06 (ссылка)

Может быть, она и решаемая. Но по способу подачи некоторым показалось, что это задание по типу олимпиадного. Обычно автор знает ответ в этом случае (вот лично я бы не стал тратить время на размышления, зная, что автор решения не знает).

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-26 15:39 (ссылка)

У автора имеется решение, удовлетворяющее всем критериям, кроме субъективного эстетического.

Ниже

blue_slonopotam@lj предлагает свое решение. Я пока не проверил, верное ли оно. Оно меня эстетически тоже не особенно вдохновляет вычислением Н.О.Д., но это-то наверняка поправимо.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	blue_slonopotam 2010-01-27 01:42 (ссылка)
	Ты тоже не забудь показать, мне интересно. (Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-27 01:55 (ссылка)

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

Собственно, GCD классически считается вычитаниями:

unsigned gcd(unsigned a, unsigned b) {
  if (a == 0) {
    return b;
  }
  while (b) {
    if (a > b) {
      a -= b;
    } else {
      b -= a;
    }
  }
  return a;
}

(Ответить) (Уровень выше) (Ветвь дискуссии)

blue_slonopotam
2010-01-27 02:43 (ссылка)

"У автора имеется решение"

Я не про НОД, а про всю программу. Я почти уверен, что она работает так же, как и моя, но выглядит совершенно иначе.

про НОД - зачем на каждом проходе цикла выяснять, кто больше, когда первый проход может сделать именно это, а дальше оно чередуется ? у тебя на процессоре деления с остатком нет ?

(Ответить) (Уровень выше) (Ветвь дискуссии)

qwerty
2010-01-27 03:10 (ссылка)

Ну, все-таки, ты пока не предъявил программы, выполняющей не более a+b чтений и записей. Условия завершения пока разные, про мусор сказать еще ничего нельзя.

У меня нет вычисления НОД. Но подозреваю, что попутно производимые действия со сложениями и вычитаниями ему эквивалентны.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	blue_slonopotam 2010-01-27 03:13 (ссылка)
	Мы с тобой быдлокодеры. Джаниторз митинг, не иначе. (Ответить) (Уровень выше) (Ветвь дискуссии)

	qwerty 2010-01-27 03:17 (ссылка)
	Почему же сразу быдлокодеры? Просто в голове много заезженных паттернов застряло, они оттуда чуть что лезут. Но до TCHAR я пока не докатился, нет :) (Ответить) (Уровень выше)

	tristes_tigres 2010-01-28 14:17 (ссылка)
	выполняющей не более a+b чтений и записей. См (Ответить) (Уровень выше)

ppkk
2010-01-27 18:33 (ссылка)

Я рассматривал способы расстановки с начала цепочками их по местам (то есть: обработать позиции 1…(a+b)):
1. Проверить, что это следует делать (ниже).
2. Сохранить значение с первого места, записать туда то (с места X), что полагается, посмотреть, куда надо записать то, что стояло на первом месте, если надо — сохранить и продолжать, если не надо — записать. На начальную позицию повторно не пишем, если до неё дошли.
3. Если не доходили до начальной позиции, то заполняем в обратном направлении, если требуется (писать на место X и т.п.).

Проверка, что это следует делать: идём по цепочкам, только проверяя индексы, не выполняя операций load/store. Если встретился индекс меньше исходного, то делать не надо.

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

Требуемой красоты определённо не наблюдается: случаи разных соотношений a, b и c заметно отличаются. В случае c=0 формулы, например, могут быть проще (там будут циклы). Или в случае a=b, c=ka. В "олимпиадной задече" по

phantom-у, видимо, должны были бы стоять и "красивые" соотношения a, b и c…

(Ответить) (Уровень выше)

	Perl gregory_777 2010-01-25 17:52 (ссылка)
	$A = join(splice($A, 0, $a), splice($A, $a+$c)); (Ответить) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-25 17:53 (ссылка)
	то есть наоборот, $A = join(splice($A, $a+$c), splice($A, 0, $a)); (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl qwerty 2010-01-26 00:11 (ссылка)
	Если для решения задачи выбран язык, на котором невозможно записать некоторые из ее условий, не задача в том виновата. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-26 03:06 (ссылка)
	А программист, который не знает языка. Зачем использовать нативную алгоритмику, когда она вся давно реализована как подмножество? (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl qwerty 2010-01-26 03:22 (ссылка)
	Спасибо, посмеялся. В условиях задачи сказано про отсутствие дополнительной памяти и количество чтений и записей в массив. Вне этих ограничений задача тривиальна. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-26 03:44 (ссылка)
	$i = $a + $c; while($i++) { push @a, @b[$i]; break if($i == $a); $i = 0 if($i == count(@b)); $i++; } Ну ок. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl qwerty 2010-01-26 03:47 (ссылка)
	Как вы думаете, куда оно его пихает? Не в отсутствующий стек ли? (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-26 04:09 (ссылка)
	while($i<$a+c) { if ($i < $a) { push(@a, shift (@a)); } else { shift(@a); } } (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-26 04:13 (ссылка)
	$i=0; while($i++<$a+$c) { if ($i < $a) { push(@a, shift (@a)); } else { shift(@a); } } (Ответить) (Уровень выше)

	Re: Perl gregory_777 2010-01-26 04:13 (ссылка)
	Простите, укурен. (Ответить) (Уровень выше)

	Re: Perl gregory_777 2010-01-26 04:14 (ссылка)
	На С такие вещи делаются на указателях, ясен пень. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl qwerty 2010-01-26 04:29 (ссылка)
	Проблема тут совсем не в этом. (Ответить) (Уровень выше)

	Re: Perl qwerty 2010-01-26 04:28 (ссылка)
	Чем дальше, тем смешнее: push, shift. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-26 17:02 (ссылка)
	push и shift - это просто названия операций работы с указателями. остальные условия выполнены: используется только массив A, к-во итераций a+c. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl qwerty 2010-01-26 20:06 (ссылка)
	Какую траву курите? :) (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: Perl gregory_777 2010-01-27 02:46 (ссылка)
	А ведь и правда... (Ответить) (Уровень выше)

ХЗ как тут форматировать

blue_slonopotam
2010-01-26 01:42 (ссылка)

Тут кабы a+b+c. И я надеюсь, что у твоего процессора нет кэша, потому что ему настанет жопа.
"Сдвиг по шеллу" :)

Можно и без с, но тогда нескрасиво.

int nod( int a, int b )
{
int tmp = a % b;
if ( !tmp )
return b;
return nod( b, tmp );
}

int *M = 0;

void swapAB( int a, int c, int b )
{
int bOfs = a+c, bLen = b;
int totalSize = a+b+c;

if ( bOfs && bLen )
{
int cycleCount = nod(bLen, bOfs);
for( int i = 1; i <= cycleCount; i++ )
{
int iStart = bOfs+bLen-i;

int pass = M[iStart];
for( int dest = iStart-bOfs; dest != iStart; dest = (dest-bOfs+totalSize)%totalSize )
{
int tmp = M[dest];
M[dest] = pass;
pass = tmp;
}
M[iStart] = pass;
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
for( int a = 0; a < 100; a++ )
for( int c = 0; c < 100; c++ )
for( int b = 0; b < 100; b++ )
{
M = new int[a+c+b];

for( int i = 0; i < a; i++ )
M[i] = b+i;
for( int i = 0; i < b; i++ )
M[a+c+i] = i;

swapAB( a, c, b );

for( int i = 0; i < a+b; i++ )
if ( M[i] != i )
puts( "Vsye propalo!" );

delete []M;
}
}

(Ответить) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать blue_slonopotam 2010-01-26 01:43 (ссылка)
	Это как бы с юнитестом. А то люди не поймают сигналы. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-26 02:07 (ссылка)
	Нехорошо GCD считать рекурсивно за неимением стека, а так надо бы заставить себя по существу проверить. (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

blue_slonopotam
2010-01-26 02:26 (ссылка)

Нехорошо придираться.

int nod( int a, int b )
{
int tmp;
while( tmp = a % b )
{
a = b;
b = tmp;
}
return b;
}

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

tmain уже проверила по существу. Думай так, ты хочешь сдвиг влево на a+c.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-26 03:25 (ссылка)
	Ну, оно же выглядит [чудовищно]. Я, конечно, приведу его в удобочитаемый вид, но не сразу. А для подавления форматирования есть <pre>...</pre>. (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

blue_slonopotam
2010-01-26 03:54 (ссылка)

void swapAB( int a, int c, int b )
{
    int bOfs = a+c, bLen = b;
    int totalSize = a+b+c;

    if ( bOfs && bLen )
    {
        int cycleCount = nod(bLen, bOfs);
        for( int i = 1; i <= cycleCount; i++ )
        {
          int iStart = bOfs+bLen-i;

          int pass = M[iStart];
          for( int dest = iStart-bOfs; dest != iStart; dest = (dest-bOfs+totalSize)%totalSize )
          { 
            int tmp = M[dest];
            M[dest] = pass;
            pass = tmp;
          }
          M[iStart] = pass;
        }
    }
}

(Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-26 20:24 (ссылка)
	А не читаешь и не пишешь ли ты тут мусор, случайно? (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать blue_slonopotam 2010-01-26 22:23 (ссылка)
	YES!!!!! >теперь надо сказать, что поскольку перескок через мусор во внутреннем цикле не сделан, то незачёт. Перескочить просто, но некрасиво. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-26 23:37 (ссылка)
	Вряд ли там просто перескок. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать blue_slonopotam 2010-01-27 00:07 (ссылка)
	Именно перескок. Через пару дней покажу. А сейчас обратно в за п бой. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-27 00:18 (ссылка)
	Не забудь показать. (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

blue_slonopotam
2010-01-30 14:18 (ссылка)

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


int *M = 0;

int reads = 0, writes = 0;

void writeMem( int i, int val )
{
    M[i] = val;
    ++writes;
}

int readMem( int i )
{
    reads++;
    return M[i];
}

void swapAB( int a, int c, int b )
{
    int bOfs = a+c, bLen = b;
    int totalSize = a+b+c;

    if ( bOfs && bLen )
    {
        int cycleCount = nod(bLen, bOfs);
        for( int i = 1; i <= cycleCount; i++ )
        {
          int iStart = bOfs+bLen-i;

          bool holdsShit = false;
          int pass = readMem(iStart);
          for( int dest = iStart-bOfs; dest != iStart; dest = (dest-bOfs+totalSize)%totalSize )
          { 
            int tmpShit = dest >= a && dest < bOfs;
            int tmp = tmpShit ? 0 : readMem(dest);

            if ( !holdsShit )
                writeMem(dest,pass);

            pass = tmp;
            holdsShit = tmpShit;
          }
          if ( !holdsShit )
            writeMem(iStart,pass);
        }

        if ( reads != a+b || writes != a+b )
            puts( "Uzhas!" );
        writes = reads = 0;                 
    }
}

    M = new int[300];
	for( int a = 0; a < 100; a++ )
	    for( int c = 0; c < 100; c++ )
	        for( int b = 0; b < 100; b++ )
	        {
	            memset( M, -1, 300 * sizeof(int) );
	            for( int i = 0; i < a; i++ )
	                M[i] = b+i;
	            for( int i = 0; i < b; i++ )
	                M[a+c+i] = i;
	                
	            swapAB( a, c, b );
	            
	            for( int i = 0; i < a+b; i++ )
	                if ( M[i] != i )
	                    puts( "Vsye propalo!" );
	            
	        }
    delete []M;

Думать как-то по-другому совсем уже лень. Давайте сюда своё решение, пожалуйста.

(Ответить) (Уровень выше)

Re: ХЗ как тут форматировать

blue_slonopotam
2010-01-26 03:56 (ссылка)

int nod( int a, int b )
{
    int tmp;
    while( tmp = a % b )
    {
        a = b;
        b = tmp;
    }
    return b;
}

	for( int a = 0; a < 100; a++ )
	    for( int c = 0; c < 100; c++ )
	        for( int b = 0; b < 100; b++ )
	        {
	            memset( M, -1, 300 * sizeof(int) );
	            for( int i = 0; i < a; i++ )
	                M[i] = b+i;
	            for( int i = 0; i < b; i++ )
	                M[a+c+i] = i;
	                
	            swapAB( a, c, b );
	            
	            for( int i = 0; i < a+b; i++ )
	                if ( M[i] != i )
	                    puts( "Vsye propalo!" );
	            
	        }

(Ответить) (Уровень выше)

	Re: ХЗ как тут форматировать blue_slonopotam 2010-01-26 03:57 (ссылка)
	Хочешь я тебя устрою веб-дизайнером ? Будешь нашим королём. (Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-26 04:03 (ссылка)
	Спасибо, может, в следующей жизни. (Ответить) (Уровень выше)

Re: ХЗ как тут форматировать

faceted-jacinth.livejournal.com
2010-01-26 17:52 (ссылка)

Я вспомнил, где это видел.
http://www.stepanovpapers.com/notes.pdf, Lecture 19, Rotate (pg. 154)
Там три способа, последний на вид такой. С развёрнтьым объяснением и ещё одной реализацией которая делает луп фьюжен и меньше убивает кэш.

Вообще кстати офигенный курс!

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

qwerty
2010-01-26 20:35 (ссылка)

Что - "это"? Если б не требовалось произвести не более a+b чтений и записей, именно так бы оно красиво в три свопа и делалось, плюс пересылка в конце. В общем-то, никакой новости в том нет. В обсуждении оно тут не раз уже упоминалось.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать faceted-jacinth.livejournal.com 2010-01-26 23:59 (ссылка)
	Там три с половиной алгоритма. Третий оптимален по свопам для c == 0, для других c его кажется несложно допилить, но мне влом. Третий-с-половиной ещё и кэш не так убивает. (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

blue_slonopotam
2010-01-27 00:15 (ссылка)

не готов долго думать, но

моя запись иллюстрирует не доказательство, но некоторый ход мысли - НОД может быть 1 и a+c может быть больше размера линии кэша, из чего следует, что кэшу несдобровать в любом случае.

Я сомневаюсь в существовании "Третий-с-половиной ещё и ~~сына~~ кэш не так убивает".

(Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

faceted-jacinth.livejournal.com
2010-01-27 01:06 (ссылка)

А, я не прав был. То есть он говорит, что в 60% случаев там вообще получится один цикл (прыгающий как безумный по всему массиву), и в остальных случаях локальность будет только на первой итерации обычно, но "It [loop fusion] is, nevertheless, an important technique that is worth demonstrating" =) Типа, его прёт, что её можно сделать достаточно генерик и без залезания в нутро компилятора, и она будет работать быстро!

(Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать blue_slonopotam 2010-01-27 01:37 (ссылка)
	Изучение алгебры полезно для душевного здоровья, видимо, и автору этой книжки тоже. (Ответить) (Уровень выше)

	Re: ХЗ как тут форматировать qwerty 2010-01-27 00:17 (ссылка)
	В каком смысле оптимален? Там N+gcd. При a==b получаем 2(a+b). (Ответить) (Уровень выше) (Ветвь дискуссии)

Re: ХЗ как тут форматировать

faceted-jacinth.livejournal.com
2010-01-27 00:59 (ссылка)

Это потому что он считает в том числе и moves to/from the temporary variable.

Посмотри внимательно на первые шесть строк кода на 194 странице. Это весь алгортм, в оставшихся строках он вычисляет новое положение границы между a и b. Ну, плюс do_cycle имплементирован ранее - он тупо сдвигает циклически фигню используя особый итератор. Ну, берём первый элемент, он должен попасть куда-то там, но там уже есть элемент, он тоже в результате должен попасть куда-нибудь, и так далее, формулка и имплементация этого итератора -- на 163 странице. Ну и вот, вся магия (которую я не до конца понимаю) состоит в утверждении, что первые GCD(m - f, l - m) элементов обязательно принадлежат разным циклам и больше циклов у нас нет, то есть если мы вызовем do_cycle для них по очереди, то всё окажется на своих местах и каждый элемент будет считан/записан ровно один раз.

У него в оценке времени появляется GCD потому что do_cycle для цикла длины n производит дополнительно n-1 чтений-записей во временную переменную, ну и вот он утверждает, что если циклов -- GCD(a, b), то этих дополнительных moves будет как раз a + b - GCD(a, b) если я ничего не путаю, но вообще нам это совершенно неважно.

(Ответить) (Уровень выше) (Ветвь дискуссии)

	Re: ХЗ как тут форматировать qwerty 2010-01-27 01:10 (ссылка)
	А слабо обобщить на случай с != 0? (Ответить) (Уровень выше)