[ Обновленные темы · Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Типс энд трикс в программировании
eXceedДата: Суббота, 21.06.2008, 15:38 | Сообщение # 1
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
Существует море всяких интересных приемов в программировании. Но почему то студентам их не показывают. Решил исправить ситуацию.
Внимание! Правило раздела.
Автор статьи должен в конце указать музыку под которую статья писалась! Будет очень интересно узнать музыкальные пристрастия ну это дает возможность почувствовать настроение автора. Остальные пользователи вправе не указывать трек который они слушали во время написания ответа.
з.ы. Приветствуются все программисты!

1. Некоторые студенты 2го курса КЗОИ столкнулись с проблемой обратной(реверсированной сортировки) при написании курсовой по предмету МПиПА.
Я нашел довольно простое и эффективное решение с точки зрения размера байткода, размеров памяти и скорости выполнения. Суть такова: Есть массив чисел который нужно отсортировать. С прямой(от меньшего к большему) сортировкой нет проблем. Но есть проблемы с обратной(от большего к меньшему). Конечно есть классические методы решения данной задачи: Прогнать цикл от большего к меньшему и етц. Но это лишний байткод. Все вы знаете, что сортировки массивов изобилуют конструкциями if. Это не допустимо с точки зрения быстродействия. Простое и красивое решение: Перемножить все элементы массива на -1 и провести ту же прямую сортировку. Далее перемножаем на -1 снова и получаем массив отсортированный от большего к меньшему =) Дело в том, что умножения числа для процессора операция очень быстрая. Быстрее только перемещения из регистра в регистр. Поэтому мы тут теряем часть времени, но оно с лихвой компенсируется тем, что результирующий байт код меньше.
Пример реализации из моей курсовой работы на C++.

Сама функция сортировки.

Code
int CMainVectorOperations::SimpleSort()
{
  int i, j, value;

  for (i = 1; i < Ot.size(); i++)
  {
   value = Ot[i];
   for (j = i - 1; (j >= 0) && (Ot[j] > value); j--)
   {
    Ot[j + 1] = Ot[j];
   }
   Ot[j + 1] = value;
  }
  return 0;
}

Функция реверса вектора

Code
int CMainVectorOperations::VectorReverse()
{
  int i = 0;

  do  
  {
   Ot[i] = Ot[i] * -1;
   i++;
  } while(i < Ot.size());

  return 0;
}

Имея две функции пишем 3 строчки кода для обратной сортировки =)

Code
CVector.VectorReverse();
CVector.SimpleSort();
CVector.VectorReverse();

Согласитесь, что код стал проще?

Продолжаем теребить мой курсач =)

Нужны действительно псевдослучайные числа? ЛЕГКО!

Code
CMainVectorOperations::CMainVectorOperations(void)  
{
  int i;
  int iBuf;
  int RANGE_MIN = 0;
  int RANGE_MAX = 100;

  srand((unsigned)time(NULL));
  for (i = 0; i < 50; i++)
  {
   iBuf = (((double) rand() / (double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
   Ox.push_back(iBuf);
   iBuf = (((double) rand() / (double) RAND_MAX) * RANGE_MAX + RANGE_MIN);
   Oy.push_back(iBuf);
  }
}

Здесь я заполнил векторы псевдослучайными величинами опираясь на системный таймер. Советую взять на вооружение.

Циклические сдвиги влево и вправо.

Огромным недостатком языка C/C++ является отсутствие функций циклического сдвига байт. Аналог ROL и ROR функций процессора x86. На самом деле C/C++ кросс платформенный язык, а на некоторых процессорах команд ROL и ROR нет. Поэтому они не реализованы в языке.
А ведь без них не обходится вычисление CRC32, ни вычисление корректирующих кодов Рида-Соломона, ни куча других подобных алгоритмов.

Некоторые программисты используют ассемблерные вставки, прибегая к непосредственному вызову команд процессора (на x86 это ROL/ROR – циклический битовый сдвиг влево и вправо соответственно). Однако такое решение делает программу непереносимой, причем совершенно неоправданно непереносимой, поскольку циклический сдвиг элементарно реализуется стандартными средствами Си.

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

Примеры реализации:

Code
ROL(int a, int n)
{
    int t1, t2;
    n = n % (sizeof(a)*8);
    t1 = a << n;
    t2 = a >> (sizeof(a)*8 - n);
   return t1 | t2;
}

Алгоритм работы:
1. Нормализуем n
2. Двигаем а вправо на n бит, теряя старшие биты
3. Перегоняем старшие биты в младшие
4. Объединяем старшие и младшие биты

Аналогично для правого сдвига, только теряем младшие биты.

ROR(int a, int n)
{
int t1, t2;
n = n % (sizeof(a)*8);
t1 = a >> n;
t2 = a << (sizeof(a)*8 - n);
return t1 | t2;
}

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

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

Code
int x;

// ** <- фигура типа

//.. * <- «бумеранг»

union{int ou; char uo[4];} xxx; xxx.ou = 0x2A2A2A2A20;
for (x=0;x<8;x++)
{
printf("%c%c\n%c%c\n\n",xxx.uo[0],xxx.uo[3],xxx.uo[1],xxx.uo[2]);
xxx.ou=ROL(xxx.ou,8);
}

В результате получим: * -> ** -> ** -> * -> * -> ** -> ** -> * ** * * ** ** * * **

Как видно, «бумеранг» исправно вращается против часовой стрелки (или по часовой стрелке, если используется функция ROR), но стоит нам выбрать другую схему отображения, как вместо вращения мы получим зеркальное отображение. Для этого в нашей программе достаточно изменить всего одну строку:

Code
printf("%c%c\n%c%c\n\n",xxx.uo[0], xxx.uo[1], xxx.uo[2], xxx.uo[3]);

В результате получим: * -> * -> ** -> ** -> * -> * -> ** -> ** ** ** * * ** ** * *
Слегка усовершенствовав функцию циклического разворота, мы сможем трансформировать не только массивы 2x2, но и гораздо большие фигуры.
з.ы. Таким методом поворачивает матрицы видеокарта =)

Чуть позже мы продолжим. Жду ваших отзывов.
Основной трек для статьи: James Brown - Play that funky music white boy


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
vitalyuДата: Воскресенье, 22.06.2008, 01:20 | Сообщение # 2
Генерал-полковник
Группа: Гости
Сообщений: 852
Репутация: 108
Статус: Offline
Прочел smile

Quote (eXceed)
for (j = i - 1; (j >= 0) && (Ot[j] > value); j--) {Ot[j + 1] = Ot[j];

Не слишком ли много манипуляций происходит при такой конструкции .. IMHO, если использовать простое нахождение максимальной переменной от i до size и затем перестановки конкретного элемента, не будет разве работать быстрее .. Согласен, что при этом код длиннее будет на 2 строчки ..

С инверсией *-1 тоже игрался, когда курсач по МПиПА делал. Гораздо удобнее, чем обенивать через буфер m[i] = m[size-i] элементы.
У меня тогда пирамидальная сортировка была и интерполяционный поиск. Тоже забавные алгоритмы.

Quote (eXceed)
Нужны действительно псевдослучайные числа? ЛЕГКО!

18го числа сиего месяца сдавал экзамен у Берсенева по Криптологии .. Эта тема напомнила ГОСТ в режиме гаммирования. Там для создания псевдослучайной гамма-последовательности отправляется синхропакет, задающий начальное положение генератора (к примеру, то же системное время) .. Это дает уникальную степень случайности (особенно если еще с параметрами дополнительными завязать, паролем ex.)

Quote (eXceed)
эффективный разворот, отображение и другие типы трансформаций геометрических фигур

О!!! Не думал что ты эту тему затронешь smile Достаточно противная она. Если помнишь, в колледже как то у меня была идея написать свой 3D двиган .. С тобой вроде шли и болтали про сие .. Единственным вариантом была реализация через матрицу поворота, до которого я так и не дошел sad Были кривые варианты через sin,cos biggrin Но дальше парочки линий в пространстве не ушло smile

Прикольно, что эти темы поднял smile Освежил память smile


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Воскресенье, 22.06.2008, 01:50
 
eXceedДата: Воскресенье, 22.06.2008, 02:00 | Сообщение # 3
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
vitalyu
1. Манипуляций не много, я лишь задал границы цикла и гоняю в пределах одного банка памяти данные. Поэтому приемлимо по скорости.
Я вот не понимаю одного: почему студенты не могут придумать оригинальных алгоритмов? Делают все шаблонно... Это ведь не интересно =)
2. Нафига так все усложнять? Даже для защиты банковских данных достаточно генерить числа опираясь на таймер.
3. Помню. Вот тебе и эффективный разворот матрицы. Как я писал выше - можно вращать любые матрицы и даже геометрические фигуры. Матрицы поворота слишком ресурсоемкие к памяти. Ведь в двигле нужно экономить полосу пропускания памяти. Кста, можно вообще матрицы поворачивать при помощи SSE =) Правда кода больше и не факт, что будет быстрее. Просто нужно хорошо знать платформу под которую программируешь.
з.ы. И ты пиши триксы. Тебе ведь есть, что показать и рассказать!


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
vitalyuДата: Воскресенье, 22.06.2008, 02:05 | Сообщение # 4
Генерал-полковник
Группа: Гости
Сообщений: 852
Репутация: 108
Статус: Offline
Quote (eXceed)
1.

Честно, не пробовал, возможно ты прав.

Quote (eXceed)
2.

Ы. Это просто такой метод шифрования. На самом деле схема та же, что ты говорил, просто в реальной реализации smile

Quote (eXceed)
3.

Ага smile Прикольно .. эх .. где ж ты то время ..

Quote (eXceed)
з.ы. И ты пиши триксы. Тебе ведь есть, что показать и рассказать!

Да тут просто все по C smile Вот и не суюсь с Delphi, ведь я с графикой в основном .. Надо бы время найти, да написать историю создания одного интерфейса с кодом smile


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...
 
eXceedДата: Воскресенье, 22.06.2008, 02:15 | Сообщение # 5
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
vitalyu
Не гони ересь! Delphi тоже язык и дельфины тоже кодеры. Графика? Круто. Фигачь про графику. У тебя интерфейсы просто загляденье!
То, что ты делал с графикой на Delphi - тоже триксы, причем которые не всем дано понять!


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
eXceedДата: Понедельник, 23.06.2008, 00:35 | Сообщение # 6
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
Продолжим.

1. Если «тяжеловесная» функция многократно вызывается с одними и теми же аргументами, лучшим способом оптимизации будет запоминание однажды вычисленного результата и возвращение его в готовом виде в случае совпадения аргументов. В особенности это касается операций поиска в файле/базе данных. Идентичные запросы здесь — обычное дело, и базы данных давно научились кэшировать их. Так почему бы не применить этот подход и к поиску в файле?
С математическими функциями все обстоит еще интереснее. Как известно, существуют два основных подхода — вычисления на лету и предвычисленные таблицы (часто комбинируемые с различными алгоритмами интерполяции). Проблема в том, что мы наперед не знаем, какой из двух подходов окажется эффективнее. Вычисления требуют времени, предвычисленные таблицы — памяти, а обращение к памяти (особенно вытесненной на диск) — операция не из «дешевых». Однако кэширование вычислений позволяет решить эту проблему, автоматически адаптируясь под конкретную ситуацию и особенно хорошо себя проявляя в распределенных системах, где мы можем одновременно начать поиск с поиском уже вычисленного значения. А там уже кто кого опередит. Если ответ вернется раньше, чем вычисления будут закончены, прерываем их!

Даже на однопроцессорных машинах с поддержкой Hyper Threading уже наблюдается ощутимый прирост производительности! И чем больше процессоров, тем значительнее выигрыш. Единственное, о чем следует позаботиться, — чтобы 2 и более процессора не выполняли одни и те же вычисления одновременно. То есть, получив запрос на наличие уже вычисленных значений, функция не должна выполнять их сама, даже если они отсутствуют в ее кэше, поскольку их уже выполняет кто-то другой. Соответственно, если функция уже приступила к вычислениям, то одна должна вернуть сообщение: «Данных еще нет, но скоро будут», чтобы другая функция не начинала вычисления с нуля.

2. Типизация, призванная оградить программиста от совершения ошибок, хорошо работает лишь на бумаге, а в реальной жизни порождает множество проблем (особенно при низкоуровневом разборе байтов), решаемых с помощью явного преобразования типов или, другим словами, «кастинга» (от английского «casting»), например, так:

Code

int *p; char x;



x = *(((char*)p)+3); // получить байт, лежащий по смещению 3 от ячейки *p

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

Рассмотрим следующую ситуацию:

Жесткая типизация приплюснутого Си трактует попытку передачи void* вместо char* как ошибку

Code

f00(char *x); // функция, ожидающая указателя на char

void* bar(); // функция, возвращающая обобщенный указатель void

f00(bar()); // ошибка! Указатель на char не равнозначен указателю void*

Здесь функция f00 принимает указатель на char, а функция bar возвращает обобщенный указатель void*, который мы должны передать функции f00, но… мы не можем этого сделать!

Компилятор, сообщив об ошибке приведения типов, остановит трансляцию. Что здесь плохого? А то, что программиста вырабатывается устойчивый рефлекс преобразовывать типы всякий раз, когда их не может проглотить компилятор, совершенно не обращая внимания на их «совместимость», в результате чего константы сплошь и рядом преобразуются в указатели, а указатели — в константы со всеми вытекающими отсюда последствиями. Но по-другому программировать просто не получается! Различные функции различных библиотек по-разному объявляют физически идентичные типы переменных, так что от преобразования никуда не уйти, а ограничиться одной конкретной библиотекой все равно не получится. Платформа .NET выглядит обнадеживающей, но… похожая идея (объять необъятное) уже предпринималась не раз и не два и всякий раз заканчивалась если не провалом, то разводом и девичьей фамилией. Взять хотя бы MFC… и попытаться прикрутить ее к чему-нибудь еще, например, к API-функциям операционной системы. Преобразований там будет…

Но частые преобразования очень напрягают, особенно если их приходится выполнять над одним и тем же набором переменных. В этом случае можно (и нужно) использовать объединения, объявляемые ключевым словом «union» и позволяющие «легализовать» операции между разнотипными переменными.

Code
union pint2char /* декларация объединения */

{

int *pi; // указатель на int

char *pb; // указатель на char

} ppp;

int *p; char x; // объявление остальных переменных



ppp.pi = p; x = *(ppp.pb+3); // элегантный уход от кастинга

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

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

Использование анонимных объединений в приплюснутом Си избавляет нас от кастинга, но делает логику работы кода менее очевидной

Code

union /* декларация анонимного объединения */

{

void *VOID; // обобщенный указатель void*

char *CHAR; // указатель на char

};

VOID = bar(); f00(CHAR); // уход от кастинга

Анонимные объединения элегантно избавляют нас от кастинга, но, в то же самое время, затрудняют чтение листинга, поскольку из конструкции «VOID = bar(); f00(CHAR);» совершенно не очевидно, что функции f00 передается значение, возращенное bar. Не видя объединения, можно подумать, что VOID и CHAR - это две разные переменные, когда, на самом деле, это одна физическая ячейка памяти.

Музыка: Poets Of The Fall - Carnival Of Rust


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
vitalyuДата: Понедельник, 23.06.2008, 02:19 | Сообщение # 7
Генерал-полковник
Группа: Гости
Сообщений: 852
Репутация: 108
Статус: Offline
Quote (eXceed)
Poets Of The Fall

Вообще отличная группа, только мало кто ее знает. Нравится композиции "Lift" и "Fire" wink

По остальному отпишу щавтра biggrin Устал сегодня smile


Бог сумел сотворить мир всего за 6 дней только потому, что ему не нужно было решать проблемы совместимости с предыдущей версией.
...
Автомат Калашникова - это средство для превращения стэка в очередь...


Сообщение отредактировал vitalyu - Понедельник, 23.06.2008, 02:21
 
eXceedДата: Четверг, 02.04.2009, 17:12 | Сообщение # 8
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
Многие начинающие программировать на VC++ спрашивают как заставить печатать в консоли русский текст. Начинают мутить с локалями проектов, выводить текст используя преобразования типа CharToOEM. Нашел просто очень эффективный метод. В теле функции которая будет выводить текст в консоль(не обязательно в консоль. Если вывод в файл идет через stderr или stdout, то тоже метод подходит), перед выводом ставим конструкцию setlocale(LC_CTYPE, "Russian"); и выводим текст. Конечно не обязательно перед самым выводом ставить конструкцию. Можно и в начале тела функции.

Пример:

Code

#include <iostream>

using namespace std;

int main()
{
   setlocale(LC_CTYPE, "Russian");   
   cout << "Привет, мир!" << endl;
   cout << "Hello, world!" << endl;
   return 0;
}   

Текст выведется нормально.

Но некоторые используют вот это:

Code

char* ToRus(char* str)
{
    char * buf;
    buf=(char*)malloc(strlen(str)+1);
    CharToOem(str, buf);
    return buf;
}

Никогда так не делайте.


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.

Сообщение отредактировал eXceed - Четверг, 02.04.2009, 17:15
 
eXceedДата: Четверг, 23.04.2009, 13:16 | Сообщение # 9
Генералиссимус
Группа: Гости
Сообщений: 5466
Репутация: 616
Статус: Offline
Открыл снова тему, т.к. лень стало заниматься перемещением информации. Пусть будет так как есть. Новый трикс в C++. Использование директив предпроцессора для создания функций.

Вчера сидел писал прогу для курсовой и возникла необходимость левого сдвига, аналог ROL. Выпилил вот так: #define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32 - n)))

Это для 32х байтных значений. Поворот влево.

Короткие функции можно определять в директивах предпроцессора компилятора в одну строку. Из плюсов это статическая компиляция.


bda-expert.ru — это система форумов, где можно общаться быстро и свободно, где любая точка зрения имеет право на жизнь.
 
  • Страница 1 из 1
  • 1
Поиск:

close