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

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

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

---

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)

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

---

Об экзаменах

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

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

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

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

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

Я придумал следующий алгоритм.
1. Экзаменуемые получают экзаменационные задания.
2. Готовятся. Пользоваться можно всем.
3. Экзаменуемые по очереди отвечают. После ответа им выставляется та оценка, которую они желают.

Этот алгоритм обладает существенным недостатком, а именно первый критерий выполняется слабо. Тяжело оценивать свой труд, когда все готовятся по литературе/конспектам.

Недавно я придумал другой, усовершенствованный алгоритм. Он отвечает первому критерию.
Сдача состоит из четырёх фаз.
1. Подготовка. Все экзаменуемые готовятся. Пользоваться дополнительными источниками знаний запрещено. Если ловят на списывании, то либо сразу выгоняют, либо запрет на фазы 3 и 4.
2. Ответ. В конце ответа экзаменуемый называет желаемую оценку. Если экзаменатор считает, что экзаменуемый на неё (или выше неё) ответил, желаемая оценка выставляется, до свидания. Если экзаменуемый ответил хуже чем хочет, переходим к фазе 3. Также тут возможно занесение оценки во внутреннюю ведомость экзаменатора, для себя (если он и учил), либо для преподавателя. Вышестоящие инстанции об этой оценке не знают.
3. Экзаменуемый идёт на дополнительную подготовку. Теперь уже можно пользоваться всем, включая головы тех кто на 3+ фазах или уже сдал (или кого выгнали).
4. Экзаменуемый отвечает ещё раз. Если и во второй раз он ответил хуже чем хочет, переходит опять к фазе 3.

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

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

А как бы экзамен провели вы, если бы вам пришлось это сделать?
Пожалуйста, ознакомьтесь с комментариями!

---

О реструктуризации

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

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

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

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

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

---

О переводе времени

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

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

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

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

---

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
Ссылки на видео приведены с промоткой до тех мест, где начинается мелодия.

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

---

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 (текущий мировой рекорд по очкам)

Комментарии

Часть А (от начала до мидбосса): по плану прохождения надо запускать транс после 4-го выстрела в 3 ряда (там есть выстрелы в 1, 2, 3, 4 ряда)
1-й спелл: оказывается лучше доджить только горизонтально, так чаще ловится
2-й спелл: всегда бомблю; почти
3-й спелл: -
Часть Б (от мидбосса до босса): по плану прохождения -- феи с тремя кусками бомб обслуживаются бомбой же, а семь фей с кусками бомб и жизней -- трансом
4-й спелл: сначала показался очень сложным, но таковым не является
5-й спелл: ого, вертикальный стриминг; там правда ещё одна такая карта есть
6-й спелл:-
7-й спелл: можно было дальше доджить, но забомбил на всякий случай, т.к. транс был по плану нужен для следующей карты
8-й спелл: протрансил
9-й спелл: трюк в том, чтобы во время выстрела человечков стоять в одном ряду с ними а потом сразу подниматься, после этого разлетающие пули будут лететь по горизонтали (почти) и доджить почти не придётся; но все равно забомбил
10-й спелл: адский спелл
11-й спелл: подумал, что забомбив можно почистить поле от лягушек, которые стреляют жёлтыми карточкми, так будет проще; и правда
12-й спелл: протупил 2 бомбы и ещё сдох в конце, в итоге на последний спелл пришёл с 0 жизней и 2 бомбами -- ААА!
13-й спелл: тут я уже особо ни на что не надеялся, а когда спелл перешёл в финальную фазу, тем более ни на что не надеялся, т.к. бомбы уже израсходовал; когда услыша низкий гул (такой издаётся перед самым подыханием босса), я очень сильно удивился, а при финальном замедлении успел подумать "так, аккуратненько, аккуратненько, чтобы не вышло MAMIZOU IS NOT GOOD GIRL AT ALL" (что это значит, ищите на я-трубе).
Таки прошёл.

Напоминаю, что Футацуива Мамидзо: второй персонаж в очках после Рикако и очередной с портативной бутылкой сакэ. Тут стало понятно, откуда в атаках человечки -- просто она упилась до чёртиков.

Изначально эти человечки и прочая вызывали ассоциацию с Конан Дойлем -- вот вам и пляшущие человечки и собака Баскервилей

Показать

пляшущие человечки

собаки баскервилей

этюд в багровых тонах

А изображение босса вызвало недоумение -- она же наркоманка с выпученными скошенными глазами! А потом я понял, что это просто очки, а не белки глаз. Успокоился.

---

О Сбербанке

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

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

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

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

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

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

---

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

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

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

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

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

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

---

Untitled [007]

Интересно, почему?

В одних интернет-магазинах чем больше стоимость заказа тем меньше стоимость доставки!
А в других интернет-магазинах чем больше стоимость заказа тем больше стоимость доставки!

Но я всегда выбираю самовывоз (-;

---

Freezing 01-12 END

Итак, я хотел посмотреть Freezing.
Можно было скачать:
1. ТВ-рип с цензурой.
2. ТВ-рип без цензуры, но всё, кроме заставок -- 4:3 (поля чёрные сбоку).
3. Три блю-рей рипа. Один 34 гига, другой 33, тетий 22 гигов.

Тяжёлый выбор. Я полёз в шару и нашёл там рип всего на 14.5 гигов. Ладно, замнём для ясности.

Интересно, но слишком Ева. Поставил мангу качаться, надо посмотреть, что там было.
Ну главная героиня, конечно, няшка -- она в очках и её озвучивает Ното Мамико...

Пара картинок

Няшечка же!

Обратите внимание на мягкую игрушку в виде кости.

Ну точно няшечка.

В детстве Бриджет на Алису Маргатроид была похожа.

FFFUUUUUUUUUUU

---

О работе

Никогда не упускайте возможности поработать забесплатно.
Никогда не упускайте возможности побездельничать за деньги.

---

Ая

Стоял я на остановке как-то и ждал автобус. Вдруг из-за угла выворачивает трактор, а спереди у него ковш, а в ковше -- велосипед. Эта картина настолько меня потрясла, что я незамедлительно решил её запечатлеть. Я молниеносно достал фотоаппарат, включил его и нацелил, но пока я всё это делал (и пока фотик включался и мееееееедленно выдвигал об'ектив), трактор уже проехал. Тогда-то я и почувствовал себя Аей из Shoot the Bullet, которая не успела зарядить фотик перед кадром. Очень сильное ощущение.

---

Голосовой спам

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

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

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

Я им ответил: "Спасибо большое за ваше предложение, но я не интересуюсь этим, до свидания". А надо-то было ответить: "Ваш звонок очень важен для меня, но я этим не увлекаюсь".

Вот если бы мне предложили стать антрепренёром, я бы ещё подумал.

И вообще, фондовые рынки мне как-то больше симпатичны. Ты покупаешь не обезличенные дезодорированные деньги, а конкретные акции (или другие бумаги) конкретных организаций.

---

TOUHOU 10 HARD

1st time clear. Реплей в картинке. А ещё в картинке оригинал картинки.

th10_25.rpy: TOUHOU10 HARD ReimuA 283015890 1CC от 2011/10/16
Напоминаю, что Touhou 10 не поддерживает юзер-реплеи.
Все экстенды получены (6), 7 миссов, 55 бомб (8 дес-бомб), 7 карт поймано (из 25).

Комментарии

Бомбфест )=. Благодаря большой мощности бомб (плевать, что у всех персонажей они почти одинаковые (по-моему, площадь немного разнится)) и их увеличенному количеству (3 после каждой смерти+неограниченно можно подбирать повер+ можно держать до 5 бомб), я пробомбил всё, что можно. В целом, далось легко. Отдельно мучил только 5-й стейдж, и то, для удовольствия. Кстати, это помогло слабо.
Стейдж 1: -
Стейдж 2: Неубиваемый мидбосс оказался простым стримингом. 1-я карта основного босса никак не ловилась, а дело в том, что надо было стоять левее (в этом ране поймана).
Стейдж 3: Ух, все нон-спеллы Нитори без бомб.
Стейдж 4: Первая смерть за ран. Тупая. Момидзи страшна. Поймал таймаут-карту.
Стейдж 5: -
Стейдж 6: Тут в начале сложилась интересная ситуация. У меня осталось 0.40 мощности, что не давало возможности забомбить. Я уворачивался как мог, закончил в левом верхнем углу, чудом не попав под последние пули. Повер 0.90, ещё два айтема! Потом вываливается повер, я уже в левом нижнем углу с трудом выдерживаю натиск, наконец он долетел до низу, я его подобрал (повер стал больше 1.00), забомбил и перешёл в центр. Но бомбой я не собрал повера на новую, поэтому когда появилась фея со специфичным паттерном, я её уже одолеть не смог и сдох. Поймал 2-я карту Канако, хотя обычно ловлю только 1-ю (а 1-ю как раз не поймал). Ласт спелл безобразен.

Вообще, тема Санаэ (стейдж 5) шикарна, вот любимое исполнение:
幽閉サテライト // 不可逆的ネクサス [yuuhei sattelite // fukagyakuteki nexus]

---

Untitled [006]

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

---

Сальвадора Дали псто

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

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

На выставке было выставлено 20-30 картин, более 50 рисунков (в основном, иллюстрации) и 20-30 фотографий. И ещё кое-что.

Интересно. Некоторые (немного) картины такие же сильные как Иконы (сильных икон я, правда, тоже мало видел). По-хорошему, на изучение многих картин (и рисунков) надо потратить минут по 15, чтобы обнаружить все детали. И при этом стоять на расстоянии вытянутой руки от полотна, а иногда приближаться на расстояние 30-10 см. А рисунки все с 30-10 см рассматривать. Но народу много. Приходилось стоять и ждать, пока впереди стоящие отойдут и можно будет стать Первым. Печально было слышать даже не слова посетителей, что им не нравится или "а вот это плохо нарисовал", а слова о том, что он сумасшедший и что "все гении немного не в себе"... По-моему, такое можно нарисовать только будучи полностью в здравом уме и твёрдой памяти.

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

По некоторым конкретным работам:

Показать

Нос Наполеона, превращенного в беременную женщину, которая гуляет как грустная тень среди древних руин. 1945

Тут кто-то рядом говорил с кем-то ещё рядом и сказал: "вот, тут надо представить себе беременную женщину... а я не могу". Господи, не надо ничего представлять, надо найти! Вот же она, в носу верхнего Наполеона!

Композиция с невидимками. 1933, холст, масло

Очень сильные ассоциации с Реем Бредбери (особенно "Марсианские хроники").

Рассвет, полдень, закат и сумерки. 1979, фанера, масло

Очень неудачно висит. Это надо смотреть чуть издалека, но рядом, перпендикулярно, висит "50 абстрактных картин" (см. далее), перед ней толпа, и невозможно смотреть издалека. Либо вплотную, либо не видно. Пришлось снять очки. Вот это -- почти Икона (ну, тут не видно, конечно).

Пятьдесят абстрактных картин,складывающихся на расстоянии два метра в три портрета Ленина в виде китайца, а с шести метров превращающихся в голову королевского тигра. Этюд
Около 1962, 1920, картон, смешанная техника

Повесил для справки относительно места расположения предыдущей. Те самые 50 картин. Насчитал 49. А главное, какое название!

Была ещё одна работа, впечатлившая, но это была иллюстрация к Дон Кихоту, в интернетах не нашёл. Найду -- повешу.

Жаль, что не привезли Самые Знаменитые Картины... и жаль, что не привезли иллюстрации к Алисе в Стране Чудес.
Дали гениален.

---

Usagi Drop 01-11 END

Сериал хороший, только не закончили. Может, 2-й сезон сделают? Конец манги известен, правда, надо почитать.

Опенинг с падающими каплями вызвал ассоциацию с пулями в Touhou, эндинг снова (как и при просмотре Мадоки) заставил вспомнить про опенинг от третьей серии GOKU SZS. Остальной саундтрек был, но не выделялся.

Дайкити очень повезло с Рин. До шести лет её воспитывал дедушка, иначе бы Дайкити бы потребовалась помощь, не думаю, что он один бы справился с новорожденным+работа. Рин удивительно логична и адекватна, не ждал такого от шести-семилетнего ребёнка. Ещё и помощь по хозяйству оказывает. Ещё и подшучивать умеет и комментарии отпускать, а это очень ценно. По виду (и только по виду!) -- Хагу-тян в молодости.
Ещё подумал, что неплохо было бы, чтобы Дайкити был вместе с мамой Ко:ки-куна.

(спойлер по манге, уже после сериала)

Правда читавшие сказали, что Дайкити эта самая мама обломала.
С самого начала Рин не считает Дайкити отцом, а кем она его считает, не говорится.
Сериал почти пастельный (хотя Аой Хана пастельнее), Рин всё время мило улыбается. Очень добрый. А в жизни что-то вроде этого.

Очень понравилась сцена в первой серии, где Рэйна бьёт по голове Дайкити плюшевым мишкой.

Картинки (мало)

Совсем не стесняются названия фирм печатать... им заплатили? Жители Москвы могут видеть рекламу этой фирмы на газетах "Метро".

Её явно напрягает поведение соседнего пассажира. Зачем так оделась-то?

Тут тоже мальчики на девочек падают.

FACEPALM

Самый страшный враг!

Бедненький...

Шутит.

Кровь.

Вот почему, наверное, кое-кто предложил перевести название сериала как "Падение Русака".

---

Обмен валют

Подумал тут, что обменивая валюту своей страны на валюту чужой, люди отдают кусочек своей страны, получая, правда, при этом, кусочек чужой взамен. Глобализация!

---

Untitled [005]

Рассказали мне вчера про один гениальный программистский трюк.
Допустим, вы программируете на Си/Си++, и вам необходимо в целочисленном выражении иметь число вида 0xFFFFFFFF. Как это проще всего записать?
Можно воспользоваться конструкцией
(~0)
Это приведёт к тому, что 0 будет приведён к типу выражения (а это -- тип максимального размера в выражении, то есть тип переменной/константы в выражении с максимальным размером), а потом побитово инвертирован, что и даст искомый 0xFFFFFFFF, причём тип выходного числа будет совпадать с типом всего выражения. Это позволяет гибко менять типы переменных не заботясь о том, чтобы подобные константы соответствовали типу выражения.