четверг, 22 ноября 2012 г.

Немного об абстракции

На самом деле дальше пойдут личные псевдофилософские рассуждения об абстракции и абстрагировании, так что многим может быть не интересно.
Вообще абстракциями мы пользуемся всегда: в разговоре, в письме и так далее. Мы описываем объекты образно, но чтобы было понятно, что эти именно. О том что это на самом деле абстракция и мы редко может описать один-единственный конкретный объект мы не задумываемся.
Другую роль абстракция играет в моделировании - абстрагирование происходит осознано и целенаправленно. Это относится как и к ООП-моделям так и математическим моделям. Чисто формально абстракция - это отношение эквивалентности, мы говорим какие объекты будем считать не отличимым - какими свойствами объектов мы пренебрегаем. При использовании ООП для написания прикладных программ обычно используется многоуровневая абстракция: на каждом уровне подробнее и подробнее, а на самом низком уровне все объекты описаны уже точно.
Однако более всего заметна абстракция при моделировании некоторых естественных (реальных) объектов или процессов. То есть это различные биологические, физически и химические задачи. Здесь от уровня абстракции зависит многое: сложность модели, вычислительная сложность и даже само понимание проблемы затрудняется.
Вот именно на примерах таких задач я заметил одно интересно свойство абстракции - не монотонность. Что я имею ввиду: при самом подробном рассмотрении объекты идентичны (состоят из некоторых элементарных объектов, например элементарных частиц - электронов, протонов и т.д.) и при самом уделённом рассмотрении объекты тоже идентичны. При этом сложность описания объектов монотонна и убывает с увеличением уровня абстракции.
Простой физический (даже физико-химический) пример я уже начал приводить: всё состоит из некоторых элементарных частиц, однако описание движения тела даже по прямой через взаимодействие этих частиц очень сложная задача. При более высоком уровне абстракции получим, что описать это движение можно одним простым уравнением.
Так же могу привести биолого-социологический пример: это моделирование некоторой социальной ситуации. Такие модели есть и они дают более-менее адекватные прогнозы (подробнее не скажу), если же моделировать эти же ситуации используя информацию о различных биологических особенностях человека (особенности обработки информации мозгом, реакцию мышц на различные размножители внешние и прочее) то  полученная модель не факт что будет решаемой вообще (по крайней мере в ближайшее время).
В заключение приложу картинки, как по моему мнению выглядят:

 Разнообразие объектов в зависимости от уровня абстракции   
Сложность задачи в зависимости от уровня абстракции

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

воскресенье, 14 октября 2012 г.

Чем можно открыть большие текстовые файлы

Последнее время пришлось повозится с большими текстовыми файлами (размером более половины гигабайта) и, как оказывается, далеко не все редакторы их легко открывают. И так небольшая статистика, для файла размером в 2.4 ГБ:
1. Notepad (Блокнот) - выдал ошибку, что файл слишком большой и попросил открыть его другим редактором.
2. MS Word, Notepad++ - тоже самое.
3. Wordpad - сожрал 1.3 ГБ оперативной памяти и завис. Пытался сожрать ещё больше, но открывали на нетбуке у которого всего 2 ГБ. Когда открывал на компе файл размерном в 643 МБ он сожрал столько же, файл всё-таки открыл, но любое действие вызывало 2-х минутное зависание.

Стандартные (и не очень) редакторы от Microsoft (ну за исключением Notepad++ - он не от них) не справились с большими файлами. А что же нам приготовил Линукс:
1. Nano - с файлом в 2.4 ГБ он не справился, а файл размерном 643 Мб открыл за две минуты, причём не глючит и не виснет.
2. Vim - файл в 2.4 ГБ открыл за 2 минуты, отлично работал и даже не намекал на зависание. С меньшим фалом справился ещё лучше.

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

вторник, 10 июля 2012 г.

Аппаратная мощность - не всё для скорости работы программы

Люди, далёкие от программирования и вычислительной техники, часто считают, что скорость работы программы полностью определяется аппаратной мощностью вычислительной системы. Не так давно я пытался доказывать, что некоторые задачи нельзя быстро решить просто по тому, что не придумали хорошего алгоритма решения этих задач (я сейчас про класс NP). Однако мне кажется, что я не был убедителен. В искупление этого записал видео, где сравниваются две разных структуры и соответствующие им алгоритмы разработки. Так что если кому-то придётся объяснять нечто подобное можете сослаться на это видео.
Исходный код используемой в видео программы.
Само видео:

Начинайте с простого

Прежде, чем лесть в интернет, искать, почему же не работает микрофон на Ubuntu и в отчаянии думать что всё, все планы сломались, проверьте - включен ли микрофон ;)

воскресенье, 8 июля 2012 г.

Где используются многомерные пространства

Почему-то в середине лета решал дать ответ на этот вопрос.
На самом деле пространства размерности выше 3 используется очень часто и очень много где, просто понятие пространства в математики не сводятся только к бытовому понятию пространства (извиняюсь за тавтологию, но надеюсь понятно). Обычно пытаются по аналогии продолжить: двухмерное это длина и ширина,  трёхмерное - длина, ширина, высота, значит и дальше сохраняется эта схема. Собственно эти рассуждения и приводят в тупик.
Теперь примеры, где используются пространства размерности выше 3:
  • Теория относительности и М-теория
 В специальной теории относительности пространство-время представляется в виде 4-х мерного пространства Минковского, в котором три компоненты пространственные и одна временная. Это пространство можно назвать "плоским" - оно однородно и изотропно (временная компонента только изотропна). В общей теории относительности используется более сложное пространство - пространство Римана. Так же 4-х мерное.Оно уже не является плоским и искривлено как только можно, физически искривление в пространство вносит масса.
В M-теории используют 11 или 12-ти мерные пространства, точно не помню. Собственно это всё, что я знаю об этом.
  • Обобщенные координаты
Это уже более привычная вещь, которую можно представить. Для примера рассмотрим человека. У человека есть лицо, спина, право, лево, верх и низ. И так же пусть он находится в помещении, в котором ввели некоторую декартову прямоугольную систему координат. Чтобы задать положение человека  в этом помещении не достаточно называть его координаты x, y, z, поскольку человек "ориантирован" надо задать ещё углы поворота вокруг этих осей: φ, ψ, θ (обозначения могут разнится, но смысл понятен). Вот уже получили 6-ти мерное пространство, если хоти описать его перемещение во времени, то получаем уже 7-ми мерное.
Обобщенные координаты могут представлять собой любые характеристики описываемого объекта, от цвета до квантового состояния.
  • Функциональный анализ и численные методы
Фактически функциональный анализ и занимается изучением многомерных пространств. Функция с такого представления объект многомерный: её можно раскладывать в ряд по базису (ряды Фурье, Лорана и Тейлора), можно менять базис и так далее. Это нужно для моделирования различных реальных процессов и решения прикладных задач. Однако решать задачи "на бумаге" не всегда удобно. Например систему из миллиона уравнений (а такие встречаются) просто так не решить. И поэтому пользуются численными методами: составляют программу на компьютере, который все эти вычисления проводит. Однако вот беда - память компьютера конечна и он не может хранить полностью вещественные числа и ряды. Вещественные числа хранятся с определённой точностью,а с рядами поступают следующим образом: выбирают проекцию функции на некоторое конечное n-мерное подпространство и работают с ними. Проще говоря - бегут какие-то n слагаемых ряда, а про остальные забывают.

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

среда, 4 июля 2012 г.

FiguresWars - source

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

Немного о начале каникул

Проекты по физике были успешно сданы, в архиве содержаться оба проекта: "Колебания и волны на струне" и "Пружинные маятники".
FiguresWars был сдан в виде курсового, и делать его дальше интерес пока пропал. Потому что следующую стадию работы надо начать с "облагораживания" кода, а то сейчас он вполне сойдёт за индусский код. Если найду какая версия кода последняя может быть даже выложу исходники.
В планах на лето, если пересилю лень и не найду полезное занятие, освоить Haskell и Java, и может быть написать небольшой физический движок. Так же хочется сделать несколько абсурдных обзоров на различные вещи. Посмотрим что из этого получится.

вторник, 26 июня 2012 г.

Haskell, WinCHCi - суперпозиция

Мучился с суперпозицией в Хаскель. Почему-то та, что указана в учебниках: через точку не работала.
sp1 x =  s2x . sx1 x
 Проект упорно не хотел компилироваться. Однако стоило вспомнить, что "Хаскель прост для записи математических формул", и тут же спасли родные скобочки: ещё один плюс функциональных языков - это использование такой логики, по крайней мере на начальной - главное чтобы это не стало проблемой в будущем. Кстати, так же не хотело компилится без явного указания типов функций. Пришлось их дописать.
Обновление: при использовании скобочек всё-таки можно не указывать явно тип функций, код становится в два раза короче :) .
Код, который я писал был чисто обучающим:
s2x x = 2 * x
sx1 x = x + 1
sp1 x = s2x (sx1 x)
sp2 x = sx1 (s2x x)

четверг, 21 июня 2012 г.

Как я познакомился с Haskell

Не так давно, захотелось мне посмотреть, что из себя представляют функциональные языки. Один из первых, на которые я наткнулся был Хаскель. Почитал, посмотрел примеры - мне понравилось.
Вот сегодня собрался, зашёл в гугл набрал "Haskell IDE", попал на http://www.haskell.org, скачал оттуда среду GHCi.
Из примеров и вики учебника я понял немного синтаксис, который достаточно простой (намного проще чем в знакомых мне Фортране и С). Решил начать с того, чем меня мучители на последней лабе - вычисление интегралов. Всё оказалось довольно просто и мило, вот метод прямоугольников для функции sin(x):
integralx h a b = sum points * h where points = map (\x->sin x) [a,a+h..b]
Вот эта строчка и есть весь код. Собственно, пока что мне нравится. Осталось только придумать, чего бы хотелось на нём написать - просто так тыкаться не интересно.

среда, 9 мая 2012 г.

FiguresWars - абсолютно серьёзный обзор.

Думаю, этим всё сказано =)

FiguresWars - близко к минимуму

За два дня я пересилил свою лень и смог много чего сделать. Плюс ещё немного было сделано на выходных.
Индексация юнитов
Теперь к юнитам можно обращаться по идентификатору - это порядковый номер юнита, как он был создан. Для каждого типа юнита и игрока своя индексация. Она начинается с нуля. Команды такого типа имеют букву n в конце, например:
moven warrior 1 1
Задаёт передвижение война с номером 1 в направление 1. Теперь к координатам можно не прибегать вообще.
Условия
Добавлены новые условия: такие как проверка hp, проверка существует ли следующая клетка в заданном направлении  , и проверка существует (или если он раньше был - то жив ли) юнит. Синтаксис каждой прописывать сейчас не буду, поскольку в ближайшее время буду составлять полный список команд.
Внешние изменения
Теперь юниты перемешаются плавно, а не скочками, как раньше. Добавил отображения древа технологий. А так же иконки технологий к юнитам: нажав на юнита можно понять - исследована технология, связанная с ним или нет.
И небольшой обзорчик
Поскольку изменения по большей части внешние, то записал видео.
 

суббота, 5 мая 2012 г.

FigureaWars - немного доработанное окно статистики

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


четверг, 3 мая 2012 г.

FiguresWars - первая победа

Первая официальная победа в FW. Ура!
Плюс комментарии по ходу, что творится на экране (чтобы было не слишком скучно смотреть).

FiguresWars - продвижение вперёд.

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

Юниты 
  • Исследовательский центр - как видно из названия в нём можно изучать новые технологии. Пока из всего три. И следовательский центр может у игрока всего один. Жизни: 20.
  • Лучники - новый юнит, который может атаковать на расстояние до трёх клеток (по прямой). Для того, чтобы его можно было производить необходимо первое исследование из ветви атаки. Жизни: 15, Атака: 5, Радиус атаки: 3.
Команды для лучника(особые):
rattack x y d r - атаковать юниту с координатами x y в направление d, на расстояние r
marcher x y - запомнить лучника с координатами x y 
marmove  d - запомненный лучник идёт в направлении d
marattck d r - запомненный лучник атакую в направлении d на расстояние r
Древо технологий
Пока древо технологий представляет из себя корень и двух потомков (названия пока что рабочие):
  • Основное исследование - добавляет 1 к атаке и 2 к жизни войнам
  • Первая технология атаки - позволяет строить лучников
  • Первая технология защиты - добавляет 1 к атаке и 5 к жизни башен
 Чтобы исследовать технологию атаки или защиты надо сперва исследовать основную технологию.
 Команды
Блоки
Введены операторы block, которые по сути своей составляют процедуры языка FW. Каждому блоку при задании присваивается номер. И затем с помощью команды callblock блок может быть вызван. Так же есть команда multi_callblock, которая вызывает указанный блок указанно число раз.
Расположение блока в программе - любое, однако два блока не могут пресекается. При этом возможно рекурсия - в блоке можно вызывать этот блок. 
Синтаксис:
block N {
...
}
callblock N
multi_callblock N M
N - номер блока, M - натуральное число, сколько раз надо вызывать блок.
Пример:
block 2 {
mbcreate 2
mwarrior 2 1
mfor 10 warrior move 1
}
callblock 2 
block 2 - это номер блока, затем идёт пробел и открывающая скобка, когда блок заканчивается идёт закрывающая скобка. Команда callblock 2 вызывает второй блок.

Условия
Условия есть двух типов if и negif. Первое - срабатывает. когда условие истинно, второе - ложно.
Синтаксис:
 if <условие> {
...
};
Аналогично negif.
Возможные условия:
  1. cellempty x y - условие истинно, если клетка с координатами x y пуста
  2. mcellempty type d - условие истинно, если клетка в направлении d от запомнено юнита типа type пуста(про типы напишу ниже)
  3. cellenemy x y - условие истинно, если на клетке с координатами x y стоит враг
  4. mcellenemy type d - условие истинно, если на клетке в направлении d от запомненного юнита типа type стоит враг.
  5. makestep x y - условие истинно, если юнит с координатами x y может сделать шаг
  6. mmakestep type - условие истинно, если запомненный юнит типа type может сделать шаг 
Используя условия и блоки можно уже сделать какую-никакую тактику, без привязке к карте, вот например:
block 1 {
mwarmove 1
negif mcellenemy warrior 1 {
callblock 1
};
}
Данный код делает следующее: запомненный войн идёт по прямой в вправлении 1, пока не встретит врага.
Циклы
Не помню - писал о них или нет, но напишу. Фактически цикл можно организовать следующими способами:  используя multi_callblock и используя рекурсию, однако до того, как их сделать я ввёл два двух оператора цикла. Они задают делают юниту действие некоторое число раз.
for n x y command
mfor n type command
Первый - говорит юниту с координатами x y выполнять команду n раз, второй - запомненому юниту типа type.
Возможные команды:
  1. move d - передвигаться в направлении d
  2. build t d - построить юнита типа t в направлении d
  3. basecreate t - если юнит в цикл - база, он производит юниты типа t
  4. attack d - атаковать в направлении d
  5. rattack d r - атаковать в направлении d на расстояние r
Пример:
for 5 3 2 move 2
mfor 10 warrior move 1
Первый цикл говорит юниту в клетке (3,2) 5 раз пойти в направлении 2, второй говорит запомненному войну пройти 10 раз в направлении 1.

Типы юнитов
В тех местах, где я указываю type нужно писать номер юнита, где t - код типа юнита, вот их список:
0 - worker - Рабочий
1 - base - База
2 - warrior - Войн
3 - tower - Башня
4 - rschcenter - Исследовательский центр
5 - archer - лучник

Графическая статистика
Отображает количество юнитов у игроков на том или ином ходе. По оси абсцисс отображается номер шага, по оси ординат - количество юнитов, график масштабируется автоматически, внизу можно включить/отключить учитываемых юнитов. Идея пришла сегодня, когда играл в Героев и пожалел, то там такого нет.

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

суббота, 28 апреля 2012 г.

Сравнение сортировок

От скуки решили посмотреть, за на сколько стандартные сортировки лучше работают. И к тому же, насколько хорошо работает случайная сортировка. Её я организовал следующим образом:
  1. Берётся два случных элемента, выбирать надо до тех пор, пока эта пара не начнёт нарушать отношение порядка.
  2. Выбранные элементы меняются местами.
  3. Массив проверяется на упорядоченность.
Первый явный недостаток - алгоритм никогда не завершится, если массив уже отсортирован. Но это легко преодолеть, если проверить заранее. Меня такие ситуации не интересуют.
Другие сортировки, "конкурирующие" со случайной: это пузырьковая, вставки и выбор.
Признаюсь честно, сам, больше всего люблю сортировку вставками, т.к. оно учитывает уже имеющийся порядок и не меняет его. Полезное свойство, особенно  если надо делать сортировку по нескольким критериями.
Весь процесс вы можете посмотреть на видео, а если в крадце, то  на 10000 элементов:
1. Вставка 0.46 с
2. Выбор 0.53 с.
3. Пузырьковая 1.23 с.
4. Случайная 139.13 с.
Исходники можете скачать по этой ссылке.

понедельник, 23 апреля 2012 г.

FiguresWars. Как я понял, что не надо ленится.

 По теме
Сегодня опять взялся за FiguresWars. Для хранения юнитов там используется специальный контейнер. Особенность в том, что мне лень(по какой-то причине) перегружать оператор [], однако не лень(видимо по той же причине) создать в классе переменную cur и функции, обрабатывающие её: переместить на начало, передвинуть на следующий, вернуть значение. Сейчас придётся переписывать это всё, потому что не удобно.
Так что я подумал и пришёл к выводу, даже если вы пишете это только для себя, особенно если так, то делайте сразу всё удобно и красиво, иначе, если вы прервётесь на насколько недель, то включится заново в работу будет труднее и придётся всё-равно переделывать.

По самому проекту
 Сейчас внедряю древо технологий(пока маленькое), затем будут писаться условные переходы, циклы и блоки команд. Как реализовывать последние я пока понятие не имею - но что-нибудь придумаем :)

суббота, 14 апреля 2012 г.

суббота, 7 апреля 2012 г.

Не доводите до абсурда. Там, где не следует применять математику.

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

пятница, 6 апреля 2012 г.

ООП

В последнее время часто натыкаюсь на критику ООП, что оно не эффективно, плохо и от него надо избавится вообще.
Лично моё мнение, что любая парадигма сама по себе не эффективна. И чтобы получить эффективную и понятную программу приходится прибегать к различным парадигмам. ООП позволяет легко описывать взаимодействия объектов внутри какой-то системы. Фактически для этого оно и было создано, и критиковать ООП за то, что оно не эффективно в других областях по крайней мере не логично, так же как и использовать его. При этом не надо путать использование парадигмы ООП и классов, которые могут быть использованы в другом смысле - просто для удобства или из-за привычки.
Идеи ООП достаточно хороши, но в описании парадигмы не сказано, где их надо применять. Для реализации мультиагентных систем они подходят. А вот для реализации вычислений бессмысленно использовать ООП. По этой причине мне не нравятся языки "чистого ООП" - они представляют в виде отдельных объектов системы то, что не должно быть объектом. А так же внешнее взаимодействие, которое должно представлять из себя нечто иное, рассматривают как объект системы.
И если кратко, то правы обе стороны. ООП - не панацея, и не всеобщее зло. Есть плюсы и минусы, поэтому когда собираетесь написать "чистую" объектно-ориентированную программу задумайтесь: а надо ли это?

Почему я не люблю vector

Многие любят использовать шаблон vector, везде, где только можно, не смотря на то, для чего он используется. Он вроде бы и как массив, и в тоже время лучше. Плюсы, несомненно, есть и я пожалуй начну с них:
  1. Всё уже сделано и проверено за программиста - пожалуй самый главный плюс, ведь преодолеть лень бывает трудно.
  2. Внешне работа с vector мало чем отличает от работы с массивом - это удобно.
  3. Это стандартная библиотека - можно назвать под разделом первого пункта, но лучше выделить.
  4. Vector - это шаблон и позволяет работать почти со всеми типами данных.
На самом деле весомых аргументов "за", кроме удобства я не нашёл. "Против" же находились в практике и, поэтому, они могу показаться слишком частными, но всё же:
  1. Не смотря на всю схожесть, vector - это не массив. Элементы vector'а хранятся в памяти не последовательно, а значит при обходе элементов последовательно, память может обходится в случайном порядке. Для небольшого количества данных это не заметно, однако чем больше - тем заметнее как уменьшается скорость работы программы.
  2. Vector реализует линейный список. Это минус скорее всего не вектора, а программистов, сильно полюбивших его, и использующих vector везде. Иногда данные представляют собой не линейную последовательность, а более сложную - некоторый граф(и, конечно, его частные случаи - сеть, дерево и т.д.) и лучше бы создать(либо найти уже готовую) свою структуру данных, которая будет подходить для задачи.
  3. Vector - шаблон. Проблемы начинаются, когда работа ведётся с векторными типами данных и классами/структурами содержащими их, ссылки на них и так далее. Справедливости ради, стоит заметить что использовании SSE-раширений всегда есть некоторые проблемы, однако незнание внутреннего устройства vector'а усугубляет их.
Вот основные минусы, которые я нашёл. Работал с vector'ом я не так много, предпочитаю писать структуры данных сам - под ситуацию, это оказывается эффективней.И небольшой вывод: в обычных случаях, когда просто требуется хранить небольшое количество данных, не обрабатывая их особым образом, vector - удобная и полезная вещь, в остальных случаях - структуру данных лучше написать самому, либо найти подходящий готовый аналог.

вторник, 3 апреля 2012 г.

По немногу, о разном

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

Теперь, пожалуй, о одной из самых трудно преодолимых проблем: внимательности. Она очень сказывается, когда программируешь на языке, где разрешено неявное объявление переменных. Например Fortran. Опечатался, а ни компилятор не выдает ошибку, ни сам сразу её не видишь. Но так не стоит забывать о переменных с похожими именами и так далее. Много где можно чего-то просто не заметить и всё будет работать, но как-то не так.

В общем, на этом "немногофилософская" минутка закончилась. По продленной работе: проект по физике, связанный с колебаниями струны на стадии завершения. FiguresWars на паузе. И другой проект по физике в планах на разработку.

среда, 21 марта 2012 г.

C++ суперпозиция функций, функторы

Недавно заинтересовал вопрос: можно ли в C++ получить суперпозицию нескольких функций, как одну, самостоятельную функцию. Ответ: можно. Для этого используются указатели на функции и функторы. Функтором в С++ является класс, экземпляры которого интерпретируются, как функции. Делается это следующим образом: создаётся некоторый класс, у которого перегружается оператор (), в классе хранятся указатели на нужные функции, затем в операторе () происходит вычисление.
Простой пример: есть две функции они принимают float и возвращают float. Тогда класс, для суперпозиции таких функций можно записать, как:
typedef float(*nw)(float);

class functest{
 public:
 functest(){
  a = 0;
  b = 0;
 }
 functest(nw a1, nw b1){
  a = a1;
  b = b1;
 }
 void setfn(nw a1, nw b1){
  a = a1;
  b = b1;
 }
 float operator ()(float t){
  return b(a(t));
 }
 private:
 nw a, b;
};
Пример использования:
float one(float x){
 return x + 1;
}

float two(float b){
 return 2*b;
}

int main(){

 functest r(one,two), r1(two, one);
 float x = r(2);
 float x1 = r1(2);
 printf("%f %f",x,x1);
 getch();

}
Результатом работы программы будет x = 6, x1 = 5.
Помоем, достаточно удобный аппарат, особенно для математических расчётов: программирование интегральных преобразований, зависящих от параметра, производных функции, расположений в ряды. В графике может использоваться, для преобразований координат. Вообще везде - для сокращения записи.
Явным минусом является то, что обращение к функции через указатель занимает достаточно время.

воскресенье, 4 марта 2012 г.

Выбор юнитов для стратегий. Теоретическая часть для реализации.

После прочтения статьи про выбор объектов в OpenGL, мне особенно понравился метод выбора, используя буфер цвета. Идея метода заключается в следующем: каждом объекту, который может быть выбран присваивается уникальный id и уникальный цвет(на самом деле достаточно только цвета), затем все эти объекты помещаются в некоторую структуры данных. При попытки выделить объект, строится двумерная проекция картинки. Строить надо лишь объекты, которые можно выделить и строить их надо без текстур, однотонные с указанным цветом. Затем считывается цвет пикселя под курсором мышки и ищется объект соответствующего цвета. Затем он и становится выделенным объектом.
За идентификатор рационально использовать сам объект, если такое возможно(например, если все объекты, которые могут быть выделены предоставляют собой потомков некоторого класса, то можно использовать механизм позднего связывания).
Явный минус такого алгоритма - он позволяет выделить только одного юнита. Если больше не надо использовать стоит именно его, если же надо выделить более одного, то алгоритм можно расширить. Я могу предложить два способа, как это сделать, они похожи, отличия у них, правда, небольшие.
Нам понадобится ещё одна структура данных, где мы будет хранить выделенных юнитов. Оба способа заключается в обходе выделанного прямоугольника, считывании пикселей, поиске фигур в буфере цвета(первая структура данных) и помещение их в буфер выделения(вторая структура данных). Отличите простое: в первом случае я предлагаю сделать обработку буфера выделения так, чтобы в нём не возникало коллизий(если юнит уже есть, то его не добавлять). Второй способ заключается в том, чтобы если юнит попадет в буфер выделения, то он удаляется из буфера цвета. Главный минус первого способа - каждый раз при добавлении в буфер выделения необходимо проверять все уже выделенные фигуры, главный минус второго способа - каждый раз при выделении необходимо заново строить буфер цвета(или "перекидывать" из буфера выделения обратно).
Следующий вопрос, не менее важный, это - как выбрать эти структуры данных. Начну с конца. Буфер выделения, выбирать лучше исходя из особенностей выделяемых объектов и самого выделения. Если выделить можно некоторое конечное количество фигур, то подойдёт ограниченный линейный список(реализованный с помощью массива, т.к. это позволяет производить прямой и обратный обход памяти, что даёт существенный выигрыш во времени), если можно выделять потенциально бесконечное множество объектов, то тут уже надо "смотреть на месте".
Для буфера цвета строить общую теорию проще, т.к. его вид его элементов и назначение сразу определенно. Буду рассматривать ситуацию, когда идентификатор включен в буфер. Назначение буфера цвета - это хранение всех объектов, которые могут быть выделены, а так же возможность поиска в нём. Из необходимости поиска и будем исходить. В статье, ссылку на которую я дал вышел, в виде буфера цвета используется статический массив и линейный поиск(просматриваются подряд все элементы массива). При небольшом количество объектов это, пожалуй лучшее решение. Причина всё та же - возможность прямого и обратного обхода памяти. Однако когда количество элементов превышает уже, где-то 256 это не очень удобно, т.к. время обхода будет компенсировать выигрыш.
Проблема в построении структуры данных для поиска, в данном случае, заключается в том, что величина, по которой мы ведём поиск - векторная, состоящая из минимум трёх компонент: (r, g, b). Однако, задачу можно очень просто свести к задачи поиска по скалярной величине. Множество значений каждой из переменных ограниченно, и можно построить отображение из множества цветов во множество натуральных чисел следующим образом:
 Пожалуй, это самый просто способ решения. Построив такое отображение, мы можем искать вместо цвета, простое чисто. В силу ограниченности отображения, у него существует обратное, которая находится достаточно легко(одна из учебных задач - разить число на части), числа в разрядах 0-2 будут означать красную составляющию цвета, 3-5 - зелёную и 6-8 - синюю. Теперь, для буфера цвета, в качестве структуры данных можно использовать бинарное дерево поиска. Поиск в такой структуре один из самых быстрых(собственно, для этого она и предназначена) и кодированние/декодированние цвета тоже занимает мало количество времени. Минус использования дерева поиска - это удаление элемента из дерева может привести к перестройке всего дерева, поэтому второй, из предложенных мной, способов реализации выделения большого числа юнитов не подходит.
В общем, это достаточный теоретический минимум, чтобы реализовать выделение юнитов. Особенно это полезно в играх-стратегиях. Однако применение возможно и в других областях, например, взаимодействие пользователя с некоторыми предметами, посредством мышки(например некоторая физическая система и её элементы можно двигать, щёлкая на них мышкой).

четверг, 1 марта 2012 г.

Проект по физике - работа идёт.

Завершил сегодня вычислительную часть и отправил её, на разработку графики и интерфейса. Пока проект насчитывает 7 частей:
  1. Колебания непрерывной струны
  2. Колебание дискретной струны
  3. Поперечные волны на непрерывной струне
  4. Поперечные волны на дискретной струне
  5. Стоячие волны на непрерывной струне
  6. Стоячие волны на дискретной струне
  7. Волны на границе раздела двух сред.
Самым сложным, для реализации вычислений, представляется второй пункт. Там решается система из k ОДУ, где k - количество грузов на струне. Решается всё методом Рунге-Кутта четвёртого порядка.
Для решение волнового уравнения из первого пункта используется Метод Фурье, позволяющий сразу получить решение в виде ряда Фурье, не прибегая к МКР или МКЭ, применяя только численно интегрирование начальных условий. Об этих пунктах я писал раньше, перейдём к остальным.
Колебания в остальных пунктах представлены в виде гармонических (в седьмом пункте ввиде суммы двух гармонических), и, теоретически, предоставляют из собой первый член разложения в ряд Фурье функций из первых двух пунктов. А фактически просто вычисляются синусы и косинусы определённых аргументов.
Ну чтож, ждём интерфейс.

среда, 22 февраля 2012 г.

FiguresWars - переход на Qt+OpenGL


Если кратко, то был добавлен интерфейс Qt и OpenGL было внедрено с помощью Qt. По смыслу игры ничего нового сделано не было. Единственное, что могу сказать Qt - удобная штука, правда надо немного помучится, чтобы его освоить.

воскресенье, 19 февраля 2012 г.

PicView - изучаем Qt

Прежде чем совмещать Qt и OpenGL, я решил изучить, хотя бы.. понемногу, того и того в отдельности. На ogl я делал "тестовую графику" для проекта по физике. На Qt  я решил сделать...да то, что получится. Очень важным элементом для меня была подгрузка картинок и их отображение, а так же понять как вообще работает Qt и так же было интересно пользоваться дизайнером окон Qt Creator.
Первое, что я сделал в новом проекте - это создал кнопку и сделал так, что при нажатии на неё, она скрывается. Абсолютно бессмысленная вещь. Однако принцип работы: как для элементов, созданных в дизайнере делать события я понял(правой кнопкой мыши на элемент и "Добавить слот"). Дальше я принялся загружать картинки(они отображались в виджитах типа label). Полез в гугл.нарыл кучу разных способов, но работал только один:
QString f;
...
QImage im;
im.load(f);
l->setPixmap(QPixmap::fromImage(im));
Где l - это указатель на наш label. образ метода был взят отсюда, спасибо автору статьи. В общем, это статья и определила тип приложения, которое я собирался сделать. А именно - небольшой просмоторщик картинок. Естественно. особый интерес представляла  загрузка файлов из папки проекта(ресурсные файлы, итд). Долго у меня не получилось, поэтом оказалась, что всё дело в странности реализации режима debug в Qt Creator,а именно: он создаёт папку, например: пусть в папке "MP" находится ваш проект с именем "Pj", при сборке debug, QtC создаёт папку, например "Pj-build-desktop-Qt_4_8_0_for_Desktop_-_MSVC2008__Qt_SDK_________" и в этой папке есть папка "debug", где находится файл Pj.exe(например). Я кидал ресурсы в папки MP/Pj и MP/.../debug. А при запуске в этом режиме QtC считает корневой папку MP/Pj-build-...
в неё и надо скидывать ресурсы. При это в release, он считай корневой ту папку, в которой находится исполняемый файл.
После того, как я понял этот странный факт, всё пошло быстро. к приложению была добавлена иконка(найденная, на просторах интернета, а точнее - на этом сайте).

Некоторые элементы интерфейса, были созданы программно, а именно опция "Открыть" в меню "Файл" и элемент label в статус-баре. С созданной опцией так же программно было связанно событие открытия файла.
Приложение работает следующим образом: с помощью опции "Открыть", в меню "Файл", выбираете картинку, а затем нажимаете "Set Image".
Вот то, что получилось, исходники прилагаются. Приложение требует библиотек QtGui4.dll и QtCore4.dll. Из-за того, что они немного увесисты(10 Мб вместе), прикладывать их не стал.

суббота, 18 февраля 2012 г.

Проект по физике - Волны на струне непрерывные и дискретные волны

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

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

Дискретная струна
Это тонкая невесомая нить, на которой закреплены грузы равной массы. через равное расстояние.  Начальное положение высчитывается так же, однако, чтобы хоть как-то облегчить задачу, "потянуть" струну можно только за груз.
Колебание такой струны описывается системой из k уравнений следующего вида:
N - сила натяжения нити, m - масса груза, Δl - расстояние между грузами, а un - искомые функции.
Метод Эйлера решить эту систему не сильно помог.
Расспараллеленный на OpenMP, метод Рунге-Кутт, при нужной погрешности очень тормозил (тестирование проводилось при k=13, m =4кг, l =20м), однако, убрав параллельные области, я избавился от тормозов.

Сейчас обе модели работают, и дают верные(точнее, похожие на верные) результаты. Итог: использование параллельного программирование не всегда даёт прирост в скорости. Иногда на создание/уничтожение потоков(или пересылку сообщений) затрачивается больше времени, чем выигрывается на ускорение вычислений. Это тоже надо учитывать.

На очереди две соединённые непрерывные струны разной плотности. После проверки выложу примерный код(или сам код), реализующий описанные мой системы.

суббота, 11 февраля 2012 г.

Figures Wars - прогресс за два дня

Если быть честным, то прогресс за один день. В течении второго ничего добиться не получилось.

Краткий обзор
Сменился графический движок (теперь он на OpenGL), добавились новые команды и название старых было изменено, добавился новый юнит и введены характеристики, добавилось возможность запомнить по одному юниту каждого типа. Теперь за ход выполняется не одна команда, а множество команд, которые могут быть выполнены и независимы. Например, рабочий может либо сходить, либо построить базу, но вместе эти действия совершить нельзя.

Юниты
Сокращения: HP - жизни, AT - атака, T - тип, M - графическое отображение
Рабочий. HP - 2, AT - 0, T - 0, M - конус, остриём вниз.
База. HP - 20, AT - 0, T - 1, M - шар.
Башня. HP - 10, AT - 1, T - 3,  M - параллелепипед. На каждом ходе башня атакует клетки во все 4 направления.

Команды
Курсивом помечаются аргументы функции. 
move x y d - юнит с координатами (x, y) перемещается в направление d
build x y t d - юнит с координатами (x, y) строить здание типа t в направление d
basecreate x y t - база с координатами (x, y) производит юнита типа t
mworker x y - запомнить рабочего с координатами (x, y)
mbase x y - запомнить базу с координатами (x, y)
mwmove d - запомненный рабочий перемещается в направлении d
mwbuild t d - запомненный рабочий строит здание t в направлении d
mbcreate t - запомненная база производит юнита типа t
| - разделитель, введён чтобы облегчить восприятие алгоритма. Отделяет команды созданные для одного шага.

Скрины

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

Благорадрность

Спасибо Антону (@MrFeod, блог) за внедрение OpenGL в проект.
  

четверг, 9 февраля 2012 г.

Figures Wars - начало

А вот и та игрушка. Она достаточно простая и, пока что, не интересная.  

Краткое описание
Есть несколько фракций (пока что от 1 до 3), которые враждую между собою. Все эти фракции представляют из себя фигуры. Каждая фигура выполняет свою роль. Круги - это базы, они создают юнитов, треугольники - это рабочие, они создаются здания. А больше пока и нет.
Задача игрока: написать последовательность действий, которая приведёт его к победе. 

 А теперь подробней
Игрокам предоставляется информация о карте: её размер, количество игроков, максимальное количество баз у одного игрока и местоположение начальных баз. Карта предоставляет из себя прямоугольное поле. Для каждой клетки задана относительная ориентация - направления, обознаются числами: 1 - вправо, 2 - вверх, 3 - влево, 4 - вниз.
Изначально у каждого игрока есть одна база и один рабочий(появляется в направлении 1, если там конец поля - в направлении 3 от базы). Далее все юниты выполняют последовательность команд, заданную игроком.

Команды
Курсивом будут указываться параметры команды.
md x y d  - перемещает юнита с координатами (x,y) в направление d(если клетка свободна)
bd x y t d - рабочий в клетке с координатами (x,y) строит здание типа t, на клетки в направлении d
bc x y t - база с координатами (x,y) строит юнит типа t. Юнит строится в свободной клетке, номер направления которой наименьший.

Юниты
Пока что есть два типа юнитов: 0 - рабочий, который может строить здания и 1 - база, которая производит другие юниты. Номера соответствуют типу юнита.


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

Первый скрин

Простая игрушка

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

четверг, 2 февраля 2012 г.

Проект по физике: ряды Фурье, метод Эйлера и параллельное программирование

В третьем семестре мы разработали проект по физики - физический маятник. Я занимался вычислениями. Если в общих чертах, то там решалось дифференциальное уравнение методом Эйлера. И функция заданная эти уравнением раскладывалась в ряд Фурье.
Подсчёт коэффициентов Фурье занимал достаточно много времени (на компах в терминалках на это уходило до двух минут), поэтому решил попробовать ускорить это всё, используя OpenMP.
Сама задача не хитрая - распараллелить цикл подсчёта интегральных сумм(метод трапеций). Однако, в силу неявного задания функции очень неудобно считать её значения в точках, т.к. высчитываются они отдельно от предыдущих. Сказано - сделано.
Теперь просто - запускаем параллельный цикл с помощью #pragma parallel for и использованием reduction и получаем уже расспареллеленую версию интегрирования.
Что меня поразило, так это ускорение: если последовательный вариант считался 26.6 с, то параллельный 3.3 с.
Приведу схематичный пример кода (на С), который был и который стал(пояснения после)
double Ssin = 0, Scos = 0;
double fp = f(x1,fimax,vl,x1,&penenq,vl,w);
double fp1,fc,fc1,fs,fs1;

while(absol(x1-l)>=h){

 fp1 = f(x1, fp, vl, x1+h,&penenq,vl,w);
 fc = fp * cos(2*n*(x1)*pi/l)*h;
 fc1 = fp1 * cos(2*n*(x1+h)*pi/l)*h;
 fs = fp * sin(2*n*(x1)*pi/l)*h;
 fs1 = fp1 * sin(2*n*(x1+h)*pi/l)*h;
 Scos += (fc+fc1)/2;
 Ssin += (fs+fs1)/2;
 x1 += h1;
 fp = fp1;

};
Scos = 2*Scos/l;
Ssin = 2*Ssin/l;
Параллельный вариант:
double Ssin = 0, Scos = 0;
double fp1,fc,fc1,fs,fs1;
int it_numb = l/h;
double *fp = new double [it_numb];
fp[0] = f(x1,fimax,vl,x1,&penenq,vl,w);
for(int i = 1; i < it_numb; i++)
 fp[i] = f(x1+i*h);
int i;

#pragma omp parallel for reduction (+:Scos) reduction (+:Ssin) private (fc,fc1,fs,fs1,i) schedule(dynamic,4)

for(i = 1; i < it_numb; i++){
 fc = fp[i-1] * cos(2*n*(x1+i*h)*pi/l)*h;
 fc1 = fp[i] * cos(2*n*(x1+(i+1)*h)*pi/l)*h;
 fs = fp[i-1] * sin(2*n*(x1+i*h)*pi/l)*h;
 fs1 = fp[i] * sin(2*n*(x1+(i+1)*h)*pi/l)*h;
 Scos += (fc+fc1)/2;
 Ssin1 += (fs+fs1)/2;
}

Scos = 2*Scos/l;
Ssin = 2*Ssin/l; 
delete fp[];
x1 - текущая точка(в последовательном варианте) или начальная точка(в параллельном), l - промежуток интегрирования (если быть более точным [0,l]), h - шаг разбиения.
Я считаю, что сами изменения кода не очень большие, а вот результат очень хороший, так что при возможности - распараллеливание вычисления. 

Небольшое вступление.

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