суббота, 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 на паузе. И другой проект по физике в планах на разработку.