Untitled — @дневники: асоциальная сеть

12:31 CEdit 3d-look / Трёхмерный CEdit

How to make 3D-look for dynamically created CEdit?
Как сделать трёхмерный CEdit, когда он создаётся динамически?

Read in English a little below.
В соответствии с тем, что я писал несколько постов назад, стараюсь донести до других частичку своего опыта. То, на что я убил несколько часов. Ввиду особой важности (куча народа ищет ответ по интернетам), привожу опыт сразу на двух языках. Сначала на английском.

EN:
(read in English)
Before you begin reading, you need to know, that every control in Windows is a window.

I was using MFC (waratte mo ii yo) and I had to make some CEdit edit-fields at runtime, create it dynamically. I wrote:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

where:
ix -- loop variable;
dlg_data[ix] -- structure with some data;
dlg_data[ix].m_edtField -- pointer to CEdit control;
bVis -- boolean, true if CEdit must be created visible;
rRect -- calculated coordinates of control in CRect;
this -- pointer to class-variable, derieved from CWnd;
dlg_data[ix].m_nedtFieldID -- ID for control, generated at runtime.

This sentence, as I thought, created CEdit for me, but it was without border, like this:

I read some documentation and decided to use WS_BORDER, so I modified sentense:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_BORDER,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

The border appeared, but it was plain, like this:

I wanted 3D-looking border. I read a little more, and understood, that I need to set the so-called "extended window style". The value must be WS_EX_CLIENTEDGE. I replaced WS_BORDER with this:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_EX_CLIENTEDGE,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

This had no effect. It was really stupid decision, as I figured out later. I continued to read. I switched to Google and forums.

I learned, that extended window style can be set only in special parameter by using CerateEx(...), not usual Create(...). So I wrote:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"WCLASS_EDIT1",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

This obviously won't work, because I didn't register WCLASS_EDIT1 windows class. I tried to register it, then I tried NULL and then I tried the standard "edit" class (I must begin with it =( ):

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

The result was the same: window creation failed. GetLastError returned 0x00000579 (0x0579, 0x579, 1041): "Invalid menu handle". Why? I have no menu in this dialog!

Then I thought that control's parent window is not my dialog and tried to set the parent window explicitly (using SetParent(...)). But I was wrong, the parent window was correct.

I gave up with CreateEx, and returned to usual Create, because I learned the great function ModifyStyleEx. This function modifies extended style on-the-fly! I decided to use it. So I wrote:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);
dlg_data[ix].m_edtField->ModifyStyleEx(0,WS_EX_CLIENTEDGE);

This compiled and ran normally, but the control has no border. Why? I explicitly set the border. I continued to read.

I learned, that border style cannot be modified with ModifyStyleEx. It can be set only on creation. The reason is unknown.

So I MUST use CreateEx(...). But windows creation fails. Why? I read forums a little more and thank godness! I found the reason. Only in one place this was described.

CreateEx need explicitly set window style WS_CHILD. The reason is unknown.
Notice, that usual Create can be successfully called without WS_CHILD. So, the final version was:

dlg_data[ix].m_edtField->CreateEx(
WS_EX_CLIENTEDGE,
"edit",
"PREFIX_EDIT1",
(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_CHILD,
rRect,
this,
dlg_data[ix].m_nedtFieldID);

This works:

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

Вы будете смеяться, но мне приходится использовать MFC (2011 год на дворе!). Задача была в том, чтобы создать на лету несколько CEdit. Я написал:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

где:
ix -- переменная цикла;
dlg_data[ix] -- структура с данными динамических контролов;
dlg_data[ix].m_edtField -- указатель на CEdit;
bVis -- флаг видимости CEdit, если истина, создаём видимым;
rRect -- расчитанные координаты контрола, запиханные в CRect;
this -- указатель на переменную-класс, класс наследник CWnd;
dlg_data[ix].m_nedtFieldID -- ID контрола, сгенерированный специально для этого.

Как я и думал, эта строчка вывела CEdit, но без рамки, вот так:

Я почитал документацию и решил использовать WS_BORDER, получилось вот что:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_BORDER,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Рамка появилась, но была плоской, вот такой:

Я же хотел обычную трёхмерную. Я почитал ещё немного и понял, что мне нужно установить так называемый "расширенный стиль окна" ("extended window style"). Установить его надо в WS_EX_CLIENTEDGE. Я заменил WS_BORDER:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_EX_CLIENTEDGE,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

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

Я узнал, что расширенный стиль окна может быть установлен, но не в том же параметре, где обычный стиль, а в другом, специальном и использовать надо CerateEx(...), а не обычный Create(...). Так что я написал:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"WCLASS_EDIT1",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Очевидно, это не заработало, ведь я не зарегистрировал класс окна WCLASS_EDIT1. Я попробовал его зарегистрировать, потом написать NULL, а потом я попробовал стандартный класс окна "edit" (с этого надо было начинать =( ):

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Результат был тот же: окно не создавалось. GetLastError вовзращал 0x00000579 (0x0579, 0x579, 1041): "Неверный дескриптор меню" ("Invalid menu handle"). С какого хрена? У меня в диалоге нет меню!

Потом я подумал, может быть родительское окно у контрола установлено неверно? Я попробовал назначить его явно с помощью SetParent(...). Я ошибался, родительское окно было установлено верно.

Я плюнул на CreateEx, и вернулся к обычному Create, ведь я узнал о замечательной функции ModifyStyleEx. Она позволяет менять расширенный стиль прямо на лету! Я решил использовать её. Я написал:

dlg_data[ix].m_edtField->Create(
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);
dlg_data[ix].m_edtField->ModifyStyleEx(0,WS_EX_CLIENTEDGE);

Это компилировалось и работало без ошибок, однако у контрола рамки по-прежнему не было. Почему? Я же явно указал стиль рамки. Я продолжил чтение.

Я выяснил, что стиль рамки по неизвестной причине не может быть изменён на лету с помощью ModifyStyleEx. Его можно установить только при создании с помощью CreateEx.

Таким образом, мне ПРИДЁТСЯ использовать CreateEx(...). Но создать окно не удаётся. Почему? Я ещё немного почитал форумы и слава богам выяснил причину. Правда написано это было только в одном месте.

CreateEx трубует явного указания обычного стиля как WS_CHILD. Почему -- неизвестно.
Заметьте, что обычный Create может быть успешно вызван и без WS_CHILD. Итак, финальная версия:

dlg_data[ix].m_edtField->CreateEx(
	WS_EX_CLIENTEDGE,
	"edit",
	"PREFIX_EDIT1",
	(bVis?WS_VISIBLE:0)|ES_NUMBER|ES_RIGHT|WS_CHILD,
	rRect,
	this,
	dlg_data[ix].m_nedtFieldID);

Это работает:

@темы: Программирование, Борьба с техникой, Статьи

URL

Комментарии (2)

01:31 Untitled [010]

Если вам не спится, займитесь рефлексией.
Снимаю с себя ответственность за последствия следования моему совету.

@темы: Мысли

URL

Комментировать

19:12 Квадратная дата

В этот день джва года назад я получил водительское удостоверение.
Да, я получил его в пятницу, 13-е.

@темы: Автомобили

URL

Комментировать

23:47 Untitled [009]

Вытаскивая звуковой усилитель из розетки, поймал себя на мысли, что я его не извлёк перед этим безопасно (Safely Remove Hardware).

@темы: Наблюдения

URL

Комментировать

08:36 Робот-зазнайка

Honda обновила своего знаменитого робота: ASIMO научился открывать пиво...

@темы: Другое

URL

Комментировать

18:05 Класс-самоубийца и Павлик Морозов

Есть такой антипаттерн -- Паблик Морозов.
Заключается он в том, что вокруг класса с закрытыми членами делается обёртка-наследник, выдающая данные закрытых членов. Юмор в данном случае понятен -- согласно известной истории, Павлик Морозов заложил своего отца. И класс-наследник закладывает своего наследодателя.

А сегодня я имел честь видеть класс-самоубийцу (все названия изменены):


class jisatsu
	{
		private:
			float* m_fData; // тут будет храниться массив с данными
		//...
		public:
			float* GetData() { return m_fData; }
		//...
	};

Автор: А.

@темы: Программирование, Говнокод

URL

Комментарии (2)

01:41 Негр и They need more money

Перевод английских реплик появится позже.

Ехал я домой. А мне для того чтобы домой попасть подходят две станции. Ехать надо было с пересадкой и я выбрал некоторую из них. Выхожу на станции (время -- 22:30), чувствую, меня кто-то хватает за рукав и что-то говорит.
Я думаю... кто там... МИЛИЦИЯ?!
Оборачиваюсь -- там стоит НЕГР.
(читать дальше)

@темы: Случай из жизни

URL

Комментарии (1)

17:26 О стратегии именования абстрактных об'ектов

Описаны методики и приёмы именования абстрактных объектов на примере файлов.

Когда нам приходится работать с большим числом более-менее однородных об'ектов, неизбежно возникает необходимость как-то ориентироваться во всём этом барахле. На помощь приходит именование. Это очень древняя система. В современном обществе имя есть практически у каждого человека (в отличие от фамилии -- у членов японской императорской семьи, например, фамилии нет, только имя). Тут следует сделать замечание, что есть две совершенно разные категории именования -- именование различных об'ектов и именование различных версий одного об'екта. Поскольку то, о чём я напишу ниже, работает для любых типов об'ектов, без ограничения общности будем считать, что речь идёт про файлы. С одной стороны, они являются более-менее однородными об'ектами (файлами (= ), с другой стороны, их содержимое может быть совершенно различным как по структуре (форматы), так и по смыслу, в случае одинаковой структуры. А ещё у всех файлов есть имя. Также речь пойдёт только о ситуациях, когда именовать вы имеете право. Если имена даны свыше (или другими существами), вы ничего с этим сделать не можете, это неинтересно.
Ниже я опишу основные способы именования, которыми я или не я пользовался или пользуюсь по сей день.
(читать далее)
Пожалуйста, ознакомьтесь с комментариями!

@темы: Тухлые идеи, Мысли, Статьи

URL

Комментарии (5)

07:45 Titled

Поздравляю всех с Днём Великой Октябрьской Социалистической Революции!

@темы: Другое

URL

Комментировать

17:39 Boku wa Tomodachi ga Sukunai 01-05

Только бы 26, только бы 26...

>>

@темы: Аниме

URL

Комментировать

03:47 Untitled [008]

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

@темы: Мысли

URL

Комментировать

21:13 О поиске, часть 1

Полчаса потратил на поиски листочка, потому что он был сложен не в четыре раза, как ожидалось, а в два.

Тяжело искать чёрную кошку в тёмной комнате, особенно если её там нет.
>>

@темы: Другое

URL

Комментировать

23:19 XOR-связный список

Описано создание XOR-связного списка и его принципы работы. Описаны принципы работы динамических структур данных -- списков и деревьев (на примере двоичных деревьев).

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

(читать дальше)

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

Обязательными полями для элемента двоичного дерева являются две ссылки на нижележащие элементы (будем называть их "левый" и "правый", хотя как называния, так и способ применения (см. ниже) не принципиальны, главное применять единообразно), а также так называемый "счётчик", на случай, если у нас будут несколько одинаковых элементов. Также необходимо придумать метод сравнения элементов, который должен отвечать следующим требованиям:
1. Если взять два произвольных элемента, один из них будет либо больше другого, либо меньше, либо равен.
2. Если два элемента по этому методу равны, то элементы являются полностью эквивалентными друг другу.
Другими словами, сравнение двух элементов "по размеру" не подходит, так как могут быть несколько элементов не эквивалентных друг другу, но имеющих одинаковый размер. Гораздо лучше сравнение по какому-либо хэшу (например, md5), но у элементов и хэши могут совпасть! (хотя это уже вряд ли). Тут уже надо кропотливо думать. Сравнивать числа и строки, правда, очень просто.
Признак, по которому мы сравниваем два элемента иногда называют "ключом" элемента.
Есть другой метод. Можно ввести только операцию "меньше", тогда элементы с повторным ключом будут неотличимы от элементов, которые больше. Это необходимо, если возможны различные элементы с одинаковыми ключами. Если такое невозможно (т.к. ключи всегда различны для различных элементов), то у нас будет потенциальное дублирование данных.

1.2.1.1 Заполнение дерева
Итак, в месте использования мы храним ровно один указатель на элемент, называемый "корнем дерева". Этот элемент либо есть, либо его нет. Если его нет, дерево пустое. Если мы добавляем элемент в пустое дерево, он становится корнем. Хотим добавить ещё один элемент и тут понимаем, что непонятно, как это следует сделать. Поскольку дерево двоичное, каждый элемент имеет по ДВА указателя на следующие элементы. Куда пихать? А если сделать так? Если новый элемент БОЛЬШЕ корневого, будем сохранять указатель на него СПРАВА (новый > старого, галочка смотрит вправо), а если МЕНЬШЕ -- СЛЕВА, а? Если место с этой стороны уже занято, перейдём по указателю и повторим процедуру с элементом ниже по уровню, пока не найдём пустое место. Если наткнёмся на элемент, который равен текущему, то останется только увеличить счётчик вхождений такого элемента на единицу.
Приведу пример заполнения.

Пример 1.
Итак, есть числа 7, 4, 9, 5, 2, 4, 3.


1. 7 -- идёт в корень.
Уровень 0.          7
2. 4<7. Кладём слева.
Уровень 0.          7
                   /
Уровень 1.        4
3. 9>7. Кладём справа.
Уровень 0.          7
                   / \
Уровень 1.        4   9
4. 5<7, но то место уже занято! Спускаемся к 4. 5>4 -- кладём справа от 4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                  \
Уровень 2.         5
5. 2<7, 2<4.
Уровень 0.         7
                  / \
Уровень 1.       4   9
                / \
Уровень 2.     2   5
5. 4<7, 4=4. Увеличиваем ссылку
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
6. 3<7, 3<4, 3>2.
Уровень 0.         7
                  / \
Уровень 1.       4(2)9
                / \
Уровень 2.     2   5
                \
Уровень 3.       3

Как заполнять дерево, вроде понятно. А как удалять?
1.2.1.2 Удаление элемента из дерева
а) если счётчик больше 1, просто уменьшаем его
б) Если мы хотим удалить элемент, у которого нет ссылок на более нижние уровни, всё понятно -- данные удаляются, ссылка, которая ссылалась на него, устанавливается в значение "пусто".
в) Если только с одной стороны есть более нижние уровни, элемент удаляем, единственный из двух возможных более нижних элементов, прицепляем вместо удалённого, чтобы верхний ссылался на него.
г) Если есть оба более нижних элемента, всё становится печально. Надо найти им новый родительский элемент, при этом следует учесть, что нельзя нарушить порядка больше-меньше, иначе дерево потеряет смысл (о смысле см. далее). Кто же подойдёт на эту роль? Элемент должен быть меньше любого элемента справа, но больше любого элемента слева! Найдём самый левый элемент правого поддерева. Это -- его наименьший элемент. Если его удалить по вышеописанному алгоритму (тут понятно, что один из пунктов "б","в" сработает, ибо "г" бы означал, что это не самый левый элемент, про пункт "а" см. далее)), спрятав данные у себя, то он станет меньше любого элемента в правом поддерева. А то, что он больше любого элемента левого поддерева и так понятно, ведь иначе бы он в нём и находился! Следует учесть, что забирать данные надо вместе со счётчиком а удалять надо все экземпляры (поэтому удаление по пункту "а" никогда не будет), ибо если перенести только один экземлпяр, у нас будет несколько равных элементов в разных местах, этого быть не должно. Данные удаляемого элемента удаляем, а спрятанные пишем вместо них. Вуаля.
Пример 2.


Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7
Хотим удалить корень дерева.
1. Придётся работать по пункту "г". В правом поддереве самый левый элемент это 6, копируем к себе (6) и удаляем (работает пункт "в").
Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
2. Удаляем данные корня, вместо них пишем то, что было в загашнике.
Уровень 0.         6
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         7   9
Как видно, порядок больше-меньше не нарушился.

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

Пример 3.
Допустим, в дереве из предыдущего примера (до удаления) хотим найти 7.


Уровень 0.         5
                  / \
Уровень 1.       3   8
                    / \
Уровень 2.         6   9
                    \
Уровень 3.           7

1. 7>5, перешли вправо.
2. 7<8, перешли влево.
3. 7>6, перешли вправо. Вот оно! Конец.
Разумеется, в нашем примере такой поиск бессмысленен и беспощаден, поскольку наши данные и есть ключ. Если же к нашему числу прилеплено ещё пять мегабайт фигни, смысл очень большой:
1. Мы сравниваем данные только по ключам, а не целиком.
2. Мы просматриваем только часть данных (3 проверки при 6 элементах).
Если надо пробежать по всем элементам, делается это следующим образом.
1. Сначала обрабатываем всё, что слева, потом себя, потом всё, что справа.
2. Спустившись на уровень ниже, повторяем пункт 1.
Понятно, что мы имеем дело с рекурсией и понятно, что мы обработаем данные в порядке возрастания. Аналогично можно придумать обработку и в порядке убывания.
Менее кустарно об этом можно прочитать тут.

К достоинствам дерева можно отнести авто-упорядочивание и быстрый поиск.
К недостаткам относится наличие рекурсии (вы заметили? (: ), что ведёт к неконтролируемому использованию стека.
К потенциальным недостаткам можно отнести следующую ситуацию. При добавлении уже упорядоченных данных, они будут добавляться всё время с одной и той же стороны дерева, превращая её В СПИСОК (см. далее)! Это называется "разбалансировка", лечится "балансировкой". Короче, надо следить, чтобы дерево было сбалансированным, т.е. слева и справа примерно одинаковое число элементов.

1.2.2 Списки
Список -- это проще чем дерево. (: В списке все элементы хранятся последовательно, при этом в каждом есть одна или две ссылки на другие элементы.
По направленности списки делятся на:
-- однонаправленные;
-- двунаправленные.
По цикличности списки делятся на
-- циклические (циклические);
-- ациклические (= (линейные).
В однонаправленных ссылка одна и перемещаться можно только вперёд. Как акула. В месте использования надо хранить указатель на один из элементов, желательно первый (а если список ациклический, то обязательно на первый!).
В двунаправленных ссылки две -- на предыдущий и на следующий элемент.
В циклических списках последний элемент ссылается на первый, в ациклических у последнего в ссылке на следующий стоит "пусто" и у первого в ссылке на предыдущий (если она есть) стоит "пусто". Необходимость использования того или иного типа списка определяется формулировкой задачи.
Добавление элемента в список (в конец или в середину) заключается в следующем:
1. Указатель "следующий" старого-предыдущего (если он есть) элемента начинает указывать на новый;
2. Указатель "предыдущий" (если он есть) старого-следующего элемента (если он есть) начинает указывать на новый;
3. Указатели "следующий" и "предыдущий" (если они есть) нового начинают указывать на старый-следующий и старый-предыдущий соответственно.
Если следующего/предыдущего элемента нет, в соответствующие указатели нового элемента устанавливается "пусто".
Удаление происходит следующим образом.
1. Указатель "следующий" предыдущего элемента начинают указывать на следующий после удаляемого элемент (если он есть; иначе -- "пусто");
2. Указатель "предыдущий" (если он есть) следующего элемента (если он есть) начинает указывать на предыдущий перед удаляемым элемент (если он есть; иначе -- "пусто");
3. Удаляемый элемент удаляется и идёт лесом.
Перемещение по списку превращается в детскую забаву -- знай себе, переходи по указателю.
А поиск только последовательным просмотром. Такие дела.
2 XOR-связный список
2.1 Что такое XOR и с чем его едят
С давних времён в программировании и дискретной математике применяются логические (в том числе побитовые) операции. XOR ("исключающее или", "сложение по модулю два", "строгая дизъюнкция" -- одна из них, причём она обладает некоторыми интересным свойствами. Таблица истинности для неё выглядит следующим образом:


+-------+-------+-------+
| x1\x2 |Истина |Ложь   |
+-------+-------+-------+
|Истина |Ложь   |Истина |
+-------+-------+-------+
|Ложь   |Истина |Ложь   |
+-------+-------+-------+

Другими словами, для двух логических значений x1 и x2 на выходе "истина", если истенен только один из операндов. Если оба истинны или оба ложны, получается ложь.
2.2 Что такое побитовая операция
Операция с двумя операндами называется побитовой, если она проводится над соответствующими битами обоих операндов и записывается в бит с тем же самым номером на выход, при этом соседние биты не затрагиваются.
Пример 4.
Вычислим побитовое XOR двух двоичных чисел (8-битных байт):


01110010
11010001
-------
10100011

2.3 Области применения XOR
Ну, во первых, это несложное шифрование. Пусть есть сообщение A и ключ шифрования K такой же длины (в битах). Проведём XOR:
A XOR K =A1.
Очевидно, что если ключ ненулевой, то на выходе будет не то же, что на входе, т.е. данные изменились. Как их достать обратно? Проведём XOR тем же ключом ещё раз!
((A XOR K) XOR K) = A XOR (K XOR K) = A XOR 0 = A.
Получили исходное значение.
K XOR K = 0, поскольку одинаковые биты первого и второго операнда зануляются (таблица истинности, см. 2.1), а они все одинаковые, значит на выходе 0.
A XOR 0 = A, поскольку XOR и истины и лжи с ложью равен исходному значению по таблице истинности, а второе значение состоит целиком и лжи (нолики).
Пример 5.


01110010 -- сообщение
11010001 -- ключ
-------
10100011 -- зашифрованное сообщение
----------------------------------------------
10100011 -- зашифрованное сообщение
11010001 -- ключ
--------
01110010 -- исходное сообщение

Вторая область применения -- это зануление. Дело в том, что операция переноса данных в процессоре гораздо медленнее, чем логическая. Сделать же регистр равным нулю -- довольно распространённая задача. Если решать в лоб, то надо делать так:

MOV AX, 0

Если подумать, то быстрее делать так:

XOR AX, AX

Что исключающее или числа самого с собой равно нулю, мы выяснили выше.
Некоторые процессоры, однако, имеют встроенную команду зануления регистра.
Может быть можно ещё что-нибудь интересное придумать с XOR?
2.4 Применимость XOR к двунаправленным спискам.
Давайте возьмём случай с шифрованием, и рассмотрим один интересный момент:
если сделать XOR между исходным сообщением и зашифрованным, получается ключ! Смотрите:
A XOR A1= A XOR (A XOR K)= (A XOR A) XOR K = 0 XOR K = K.
Теперь давайте вместо A, A1, K писать C1, C2, U (соответственно). Получим:
C1 XOR C2 = U
U XOR C1 = C2
U XOR C2 = C1
Что же получается-то? Если у нас есть два абстрактных числа, то зная их XOR и одно из чисел, можно найти второе.

Если у нас есть двусвязный список, в нём хранятся адреса следующего и предыдущего элементов. Если хранить их XOR, то зная адрес следующего элемента, можно вычислить адрес предыдущего и наоборот. В дальнейшем XOR-псевдоадрес будем называть "ёж".

Итак, пусть у нас есть пять элементов, при этом их адреса будем обозначать A_i, а ежи -- U_i.
Жирным обозначено, когда связь переходит через конец списка, палочки обозначают XOR чего и чего в еже. Кружочки -- сами элементы.


     A1   A2   A3   A4   A5
   \ O / \O / \O / \O / \O /
     U1   U2   U3   U4   U5

Во избежание проблем будем считать список циклически. Тогда:
U1 = A5 XOR A2
U2 = A1 XOR A3
U3 = A2 XOR A4
U4 = A3 XOR A5
U5 = A4 XOR A1

Пусть нам известны адреса 3 и 4 элемента. Мы хотим узнать, что было до и после них.
До: берём ёж третьего элемента и делаем исключающее или с адресом четвёртого:
U3 XOR A4 = (A3 XOR A4) XOR A4 = A3 XOR (A4 XOR A4) = A3.
После: берём ёж четвёртого элемента и делаем исключающее или с адресом третьего:
U4 XOR A3 = (A3 XOR A5) XOR A3 = A5 XOR (A3 XOR A3) = A5.
Оно работает!
А как добавить элемент?
Хотим добавить элемент X после A2.
Ёж нового элемента -- это просто исключающее или его новых соседей. А вот их ежи придётся пересчитать:
UX= A2 XOR A3
U2'=A1 XOR AX
U3'=AX XOR A4


     A1   A2   AX   A3   A4   A5
   \ O / \O / \O / \O / \O / \O /
     U1   U2'  UX   U3'  U4   U5

Ещё тонкий момент -- удаление элемента. Удалим A2. Необходимо пересчитать ежи.
U1'=U5 XOR AX
UX'= U1 XOR A3


    A1   AX   A3   A4   A5
  \ O / \O / \O / \O / \O /
    U1'  UX'  U3'  U4   U5

Разумеется в программе всё чуть сложнее.

2.5 Ежиная арифметика
Адрес XOR Адрес = Ёж
Ёж XOR Адрес = Адрес
Адрес XOR Ёж = Адрес
Ёж XOR Ёж =? Не имеет смысла

2.6 Особенности XOR-связного списка
1. Поскольку надо знать сразу два элемента (последовательных), вместо одного указателя на текущий элемент списка, придётся хранить ещё указатель на следующий (предыдущий).
2. Усложнённая арифметика: навигация по списку становится дольше.
3. В каждом элементе хранится только один ёж, а не два адреса, поэтому можно экономить память. Нужна ли такая экономия -- зависит от формулировки задачи.

2.7 Реализация алгоритма
Проще всего организовать класс, который будет всем этим заниматься. Пример реализации такого класса вместе с демонстрационной программой представлен в Приложении 1.

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

Приложение 1. Пример реализации класса XOR-связного списка на C++
pastebin (cpp)
mediafire (exe)

Статья написана по просьбе того, кто знает (:.

@темы: Программы, Программирование, Тухлые идеи, Статьи

URL

Комментировать

22:45 Об экзаменах

Описана придуманная мной методика проведения абстрактного экзамена.

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

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

@темы: Тухлые идеи, Статьи

URL

Комментарии (9)

23:06 О реструктуризации

О, это страшное слово "реструктуризация".

Реструктуризация, от основ к специфике, в восемь пунктов!

1. Реструктуризация -- изменение структуры. Связи, связывавшие раньше части системы частично или полностью разрушаются, устанавливаются новые. Части системы также могут быть удалены, добавлены, переразбиты.
2. Можно ли считать добавление в систему новых сущностей реструктуризацией -- мне неизвестно. Скорее всего, да.
3. Реструктуризация может быть проведена проведена над большим числом систем (скорее всего, над любой системой) -- это правительства, организации, комплексы оборудования (связанные единой задачей), программы в конце концов (обычно для программ называют "рефакторинг").
4. Реструктуризация бывает внутренней и внешней. После внутренней внешнее поведение системы не изменяется. После внешней у системы могут появиться, например, новые возможности (или пропасть старые).
5. Да, это не всегда возможно, но реструктурировать систему надо как можно раньше. Чем дольше работает система, тем сложнее это будет сделать. Желательно проектировать её так, чтобы реструктуризация не понадобилась. Либо реструктуризацию проводить ещё на бумаге, когда ещё нечему функционировать (что входит в проектирование). Однако если вы руководите/поддерживаете систему довольно долго, рано или поздно ситуация изменится и придётся что-то переделывать.
6. Самое главное, задуматься над вопросом целесообразности реструктуризации. После неё всё может стать хуже.
7. Грамотно спланированная реструктуризация может быть почти безболезненной, но на время её проведения всё равно наблюдается ухудшение функционирования системы, вплоть до полной парализации.
8. Под реструктуризацию часто дают дополнительное финансирование. Бывает, что на реструктуризацию уходят не все деньги. Куда деваются остальные -- сложный вопрос.

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

P.S. Я конечно всё так круто написал, но лично проводил только рефакторинг кода. Остальное по наблюдениям.

@темы: Мысли, Автомобили, Очевидное-невероятное

URL

Комментировать

12:43 О переводе времени

Я смотрю, у многих устройства и компьютеры не в курсе нововведений и перевели часы куда не надо. Согласно некоторым сведениям, это породило кучу опозданий и так далее. Меня даже спрашивали (в похожей формулировке) "Сколько сейчас времени, чёрт возьми?".

А я с троллфейсом говорил сколько времени. Я знал.

Потому что у меня на компьютере уже несколько лет работает шара (EN), которой для работы необходимо токийское время. И на компьютере тоже токийское время. Японии время не переводит. Да, переводила, С 1946 по 1952 год. Но тогда ещё не было устройств, которые бы делали это автоматически.

Другими словами, мне это только удобнее, не надо перевод токийского времени в московское в моём мозгу переключать. Хотя зимнее время с точки зрения перевода в мозгу было удобнее, т.к. разница составляла 6 часов, а 6 часов прибавлять/вычитать проще, чем 5.

@темы: Другое

URL

Комментировать

23:56 Eric Satie // Gymnopédie №1

Оригинал
Про композитора
Произведение является представителем изобретённой композитором "«меблировочной музыки», которую не надо специально слушать, ненавязчивой мелодии, звучащей в магазине или на выставке."(С). Правда в нынешних магазинах такого не пускают. На выставке Дали тоже на фоне была какая-то муть, а в магазинах обычно пускают радио.

Как ни странно, в аниме очень популярна эта мелодия. Почему, мне неизвестно. Возможно, её слышали и вы. Нашёл уже четыре места, где она есть:
1) Tooi Sekai Макото Синкая Video of this (LQ)
2) 15-й эпизод Colorful Video of this
3) Трейлер "Исчезновения Харухи Судзумии" Video of this
4) 12-й эпизод Love Hina Video of this
Ссылки на видео приведены с промоткой до тех мест, где начинается мелодия.

Ждём новые поступления в коллекцию.

@темы: Аниме, Музыка

URL

Комментировать

23:42 TOUHOU 13 EXTRA

1st time clear. Реплей в картинке.

th13_udzh11.rpy: TOUHOU13 EXTRA Reimu 129820760 1CC от 2011/10/28
2 экстенда, 4 бомб-экстенда, 4 мисса, 12 бомб (2 дес-бомбы), 5 карт из 13 поймано. 2 бомбы профукал.
Это моя первая полностью самостоятельно разобранная экстра, в остальных случаях я видел реплеи до прохождения. Из "обычных" данмаку-игр я ещё не видел экстру 12-й, 2-4-5-9-10-11, к сожалению, видел уже, так что самостоятельно смогу разобрать только ещё 12-ю.
Кстати, можно получить 3 экстенда, но надо очень постараться Replay of this (текущий мировой рекорд по очкам)
Комментарии

@темы: Touhou

URL

Комментировать

11:46 О Сбербанке

Всегда любил Сбербанк. Хороший он. Зелёный. С очередями встречался редко (потому что не в то время прихожу). Обслуживание всегда было адекватное. Возможно, мне просто везло?

И была касса в доме напротив, в пяти минутах ходьбы. И был у неё чудо-банкомат -- в помещении отдельном со входом по карточке. То есть не на улицу банкомат смотрит, как обычно, а дверь с кард-ридером, суёшь карточку, дверь открывается. Внутри помещение, где банкомат и больше ничего. Это гораздо безопаснее, чем банкомат на улице.

А потом кассу вместе с банкоматом закрыли на ремонт. Следующая ближайшая касса расположена уже в 20-30 минутах ходьбы или 15 минутах езды (ещё одна, другая). Стало очень неудобно. Ремонтировали 4-5 месяцев. В процессе ремонта замуровали дверь отдельного банкомата. Ну всё, думаю, сделают как обычно, уличный банкомат. Когда открыли, оказлось, что уличный банкомат так и не сделали. Зашёл в саму кассу посмотреть. Внутри самой кассы стоял 1 банкомат (все операции) и 1 терминал (без выдачи наличных). Меня спросили, что я хочу? Я ответил -- ничего. Мне сказали, что это хорошо! Я сказал, что просто посмотреть пришёл, как тут сделали и покинул помещение.

А оказалось, что помещение с банкоматом отдельное таки есть, его перенесли туда, где раньше был отдел обслуживания юридических лиц. Принцип тот же, только внутри не 1 банкомат, как раньше, а 2 банкомата полноценных и 2 терминала. Это и лучше и хуже, т.к. больше клиентов можно одновременно обслуживать, хотя с приватностью проблемы. На банкоматах почти везде уже стоит новое ПО, которое уже год отлаживается -- глюков всё меньше и меньше. Из положительных моментов хотелось бы отметить контекстные услуги, напирмер, снимаешь деньги, а он пишет "оставить заявку на получение кредитной карты", или платишь за интернет/телефон, а он пишет "подключить автоплатежи". А ещё они стали запоминать телефоны, на которые я деньги клал и теперь можно одним кликом повторно класть на те же номера. Причём запоминание номеров сделали раньше, чем список телефонов, то есть когда список появился, он уже знал номера, на которые я клал деньги.

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

И про ребрендеринг Сбербанка -- это, наверное, самый дорогой Pan & Zoom в графическом редакторе, который я видел.

@темы: Сбербанк, Наблюдения

URL

Комментировать

23:57 О местах для инвалидов-колясочников в автобусах

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

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

Разработчики автобусов решили добавить возможность выбора. На местах для инвалидов сделали откидные сиденья. По два на каждое. То есть +2-4 места на автобус. Сомнительно, ну и чёрт с ним.

Просто это ещё не всё. Некоторые гении мысли сделали доп. откидные места в виде лавочки сбоку. Откидываются сиденья по одному, всего их три. Я подумал -- о, как прикольно, решил проехаться. Откинул и сел. Если коротко -- очень неудобно. Ограничителей по бокам у сидений нет (и быть не может, они же откидные!), поэтому любое ускорение-торможение, если вы сидите на крайних местах приводит к риску сползаний с сидения (а автобусы дёргаются сильнее, чем метропоезда, где сиденья сбоку все, да ещё и с ограничителями). До поручня лететь ещё около метра. Спинка на три сидения общая и опереться на неё можно только частью спины в диапазоне от 10 до 40 сантиметров от основания шеи.

И я уже видел два подобных автобуса. Сурово.

@темы: Общественный транспорт

URL

Комментировать