ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
25 сообщений из 111, страница 3 из 5
  3  все
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38681840
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
MasterZivКстати, о производительности.

auto other = y;
y = x;
x = other;

-- тут три операции. Точнее, три чтения и три записи.

в твоём 3 * 3 + 1 = 10 операций.
При этом одна из этих трёх операций ( одно чтение, XOR и одна запись )
ещё и задействует АЛУ. А при обычном swap оно может быть и без АЛУ.

Как вы умудрились насчитать десять операций???
Код: sql
1.
x ^= y ^= x ^= y;

эквивалентно
Код: sql
1.
2.
3.
x ^= y;
y ^= x; // y стало равным x-старое
x ^= y; // x стало равным y-старое

"Вычисление с присваиванием" - одна (логическая) операция.
"Физически" будет, скорее, всего, два чтения, две записи и три логические операции (в регистрах).
...
Рейтинг: 0 / 0
27.06.2014, 13:38
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38681876
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonСашок хочешь задачку подкину?
Конечно :)
...
Рейтинг: 0 / 0
27.06.2014, 14:02
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38681924
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
On 27.06.2014 14:38, Basil A. Sidorov wrote:
> Автор: Basil A. Sidorov. MasterZiv
> Кстати, о производительности.
>
> auto other = y;
> y = x;
> x = other;
>
> -- тут три операции. Точнее, три чтения и три записи.
>
> в твоём 3 * 3 + 1 = 10 операций.
> При этом одна из этих трёх операций ( одно чтение, XOR и одна запись )
> ещё и задействует АЛУ. А при обычном swap оно может быть и без АЛУ.
>
> Как вы умудрились насчитать десять операций???
>
> x^= y^= x^= y;
>
> эквивалентно


x^= y -- читать x, читать y и выполнить XOR, результат записать в x.

И так три раза. Результат предыдущего вычисления (x в данном случае)
можно , конечно, не читатЬ, тогда следующие операции -- по 3 , а не по
4. А первая -- +1 даёт.

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
27.06.2014, 14:38
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38681937
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Это всё замечательно, но применительно к реальной жизни ваш пример - ничем не лучше цепочки xor-ов.
Если компилятор предоставляет swap(x, y) - именно эта функция и должна использоваться.
А превратит ли её компилятор в две пары push/pop или в загрузку/сохранение пары регистров - забота разработчиков этого компилятора.
...
Рейтинг: 0 / 0
27.06.2014, 14:50
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38681963
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercurymaytonСашок хочешь задачку подкину?
Конечно :)
Вот тебе задача.

Есть игровой мир. В трёхмерных координатах. X,Y,Z.
Состоит из кирпичиков. Каждый кирпичик имеет координаты соотв от (0,0,0) до (1024,1024,1024).
Состояние кирпичика определяется 16-битным целым (shot). Кирпичик может быть:
- установлен/убран
- иметь повреждение от 0 до 15.
- иметь тип материала (256 типов в том числе стекло, дерево, бетон)

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

Необходима имплементация следующего интерфейса.
Код: plaintext
1.
2.
3.
4.
5.
6.
interface BrickWorld{

  void setBrick(int x,int y,int z,short value);
  short getBrick(int x,int y,int z);

}



Спецификация кирпичика
Код: plaintext
1.
2.
3.
4.
5.
struct Brick {
   unsigned short isSet: 3;    
   unsigned short Damage:4;    
   unsigned short Matherial:8;    
};


При этом надо помнить что память ограничена и по возможности не делать 3-d матриц.
Этот код должен работать на сервере где память - ограничена.

Второй частью этой разработки будут активные игроки или действия игрового мира.
...
Рейтинг: 0 / 0
27.06.2014, 15:11
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682012
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
mayton,

А почему "isSet: 3" когда всего 2 состояния "установлен/убран"?
...
Рейтинг: 0 / 0
27.06.2014, 15:42
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682029
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly Moskovsky, да верно. Поправил.

Код: plaintext
1.
2.
3.
4.
5.
struct Brick {
   unsigned short isSet: 1;    
   unsigned short Damage:4;    
   unsigned short Matherial:8;    
};
...
Рейтинг: 0 / 0
27.06.2014, 15:52
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682031
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вы хотите решить эту задачу не тратив 2^31 байт ? Я правильно понял ?
...
Рейтинг: 0 / 0
27.06.2014, 15:54
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682071
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury, да. Не создавая 3-д матрицу. Исходим из предположения
что игровой мир будет заполнен не полностью.
...
Рейтинг: 0 / 0
27.06.2014, 16:22
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682094
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Я могу хранить в одномерном, размерностью 2^31. Но это не то, как я понял. То есть мы хотим хранить элементов столько, сколько есть непустых. Где isSet true. Уже гонят спать..подумаю, мне кажется это вполне реализуемо.
Спасибо за задачу :)
Ps
Я могу применить malloc дважды к одному указателю ? " Довыделить память "
...
Рейтинг: 0 / 0
27.06.2014, 16:34
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682095
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Размерностью 2^30
...
Рейтинг: 0 / 0
27.06.2014, 16:34
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682096
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryЯ могу применить malloc дважды к одному указателю ? " Довыделить память "
realloc()
...
Рейтинг: 0 / 0
27.06.2014, 16:36
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682208
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
MasterZivOn 26.06.2014 03:14, egorych wrote:

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

Ну ладно, не так уж и редко.
Любая сортировка.
А сортировка -- основа многих алгоритмов, да и сама часто используется.
и часто ты сам сортировку пишешь? std::sort - и вуаля )))
...
Рейтинг: 0 / 0
27.06.2014, 18:10
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682247
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВот тебе задача...
Не издевайся, неподъемная задача. Он алгоритмы не изучил. Тут сортировки как минимум надо освоить.
Да и задача неполноценная, надо какую-то статистику по однотипным элементам ввести в условие, например сколько неиспользуемых элементов и т.д.
...
Рейтинг: 0 / 0
27.06.2014, 18:43
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682332
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima T,

А по мне - слишком простая (для Саши) :)
...
Рейтинг: 0 / 0
27.06.2014, 20:36
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682500
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Как работать с value понятно, тут проблем нет. Нужно решить проблему с однозначно адресуемым расширяемым массивов, либо с тем как хранить эти кирпичи чтобы однозначно адресовать по xyz. Спецификацию кирпича расширять нельзя ?
...
Рейтинг: 0 / 0
28.06.2014, 07:19
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682501
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Можно еще подумать, и возможно как то использовать коды Грея или кривую Гильберта. Но вы не подсказывайте. Я только начал думать.
...
Рейтинг: 0 / 0
28.06.2014, 07:21
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682574
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Думай. Спецификацию кирпича я расширять не планирую. Ну даже если расширять то в крайнем случае
заменить short на int. Это не влияет принципально.
...
Рейтинг: 0 / 0
28.06.2014, 13:33
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682634
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Самый простой вариант после матриц, такой(только тут проблемы с выделением памяти, уже час пытаюсь понять в чём дело, а на этом пк нет стандарта Си), но я думаю что алгоритм понятен
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
#include <stdio.h>
#include <stdlib.h>

struct Brick {
   unsigned short isSet: 3;    
   unsigned short Damage:4;    
   unsigned short Matherial:8;    
};


int* buf;
int* c_buf=buf;

void setBrick(int x,int y,int z,int value)
{
	//выделяю память на value
	c_buf=(int*)realloc(buf,sizeof(buf)+sizeof(int));
	//записываем значение value
	*c_buf++=value;
	//выделяю память на координаты 
	c_buf=(int*)realloc(buf,sizeof(buf)+sizeof(int));
	*c_buf++=x+(y<<10)+(z<<20);
}

int getBrick(int x,int y,int z)
{
	for(int i=1;i<sizeof(buf)/sizeof(int);i+=2)//иду по чётным элементам(по адресам)
	{
		if(*(buf+i)==x+(y<<10)+(z<<20))
		{
			return *(buf+i);
		}
	}
	return -1;//в случае неудачи
}


int main(int argc, char** argv)
{
	printf("%i \n",sizeof(buf));
	setBrick(0,0,0,124);
	setBrick(1023,1024,1023,5675);
	printf("%i\n",sizeof(buf));
	return 0;
}



Очевидный минус(после исправления ошибки с выделением памяти), время доступа к элементу ~O(n). И второй минус, трачу в два раза больше памяти чем элементов.
...
Рейтинг: 0 / 0
28.06.2014, 16:53
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682649
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Но это конечно не то. Нужно(и скорее всего можно) по-другому решить эту задачу
...
Рейтинг: 0 / 0
28.06.2014, 17:15
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38682723
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Ваши sizeof(buf) возвращают размер указателя. Это, как максимум, восемь байт.
Хотите выделить память для массива элементов - определяетесь с размером и выделяете "размер * sizeof(тип)" байт.
Дополнительно определяетесь со способом определения размера массива. Чтобы использовать одно и ту же логику во всех частях программы.
...
Рейтинг: 0 / 0
28.06.2014, 20:22
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38683093
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryНо это конечно не то. Нужно(и скорее всего можно) по-другому решить эту задачу
Эту задачу можно решить тысячами способов. Код твой я еще не смотрел.
Но сходу предложу использовать Stdint.h для фиксации
типов данных. А такой фокус как sizeof(int) лучше вообще не использовать. Никогда.
...
Рейтинг: 0 / 0
29.06.2014, 17:36
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38683130
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Тут как раз таки в первую очередь "никогда" - это к sizeof(buf), который типа int*. Это даже если вдруг забыть, что значение buf изначально используется не инициализированным. Да и O(n) на доступ к записям по координатам как-то слишком много.
...
Рейтинг: 0 / 0
29.06.2014, 19:16
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38683274
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Я только код исправлю. Пока что не проверяйте.

wstДа и O(n) на доступ к записям по координатам как-то слишком много.

Ну это предел сверху. Вот если бы я мог записывать в те адреса памяти что я хочу (в пределах той памяти что выделена), это было бы хорошо. Хотя что хорошего, вся программа была бы разбросана кусками. Пока что я не вижу другого варианта. Мне приходится хранить пару, значение и код координаты. И когда я хочу получить значение, очевидно что у меня происходит запрос
select value from table t where ID=' '. И потом max это количество строк
...
Рейтинг: 0 / 0
30.06.2014, 02:13
| Ответить | Цитировать | Написать  
Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
    #38683276
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
wstна доступ к записям по координатам как-то слишком много.

и не к записям, а к чтению!
...
Рейтинг: 0 / 0
30.06.2014, 02:14
| Ответить | Цитировать | Написать  
25 сообщений из 111, страница 3 из 5
  3  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Анализ программного кода. International Obfucated C Code Contest. 1984. By Mike Laman
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]