Деревья

Буратино был тупой... (С)

А-а-а, везде деревья. Мне они уже снятся. Идешь утром в ванную чистить зубы - видишь дерево. Когда кушаешь - видишь дерево. Я уже боюсь ходить в туалет.

Интересно, много ли существует людей, таких как я, которые подходят к окну и говорят: "Бля, и тут дерево". Они не бинарные - они зеленые.

Мне говорили, что существует болезнь излишнего использования паттерна сиглетон - называется "Синглетонизм". Видимо, мой случай назовут "массивный дендризм".

По смыслу я везде должен видеть массивы, но смотря на все через логарифмические очки ( * log(n) диоптрий) везде вижу деревья.

Интересно, пойдет ли в зачет кубка Дерево/Дом/Сын такие деревья? Хотя на огороде есть несколько моих инстансов деревьев, да и домик я требую засчитать, с сыном надо осторожнее. Это вам не 2-3-дерево.

IT-образование

Много слов ни о чем... Конечно же, все написанное - это мое личное мнение. Все что я пишу - это всегда мое личное мнение. Иначе я ставлю кавычки и указываю источник - это называется цитирование.

Прежде всего сразу же стоит отметить проблему с русским названием. В русском есть понятие "комьютерщик" (абстрактный носитель свитера), "программирование", "информатика". Кто такой программист? Даже тут куча тонкостей, на что можно убить десятки килобайт.

Что такое программирование? В английском есть две крайности: CS и ЕЕ. Программирование - это посередине. Одно - теория, другое - практика (здесь я использую слово "разработка"). Хотя в штатах есть среднее понятие CE (computer engineer), но как я понял, оно ближе к EE. В общем, где-то между CS и CE - это и есть программирование.

Кто у нас в России учит программированию? Мой рейтинг таков:

1-2) ИТМО (КТ)
1-2) МГУ мехмат (некоторые кафедры мехмата)
3) СПбГУ матмех (некоторые кафедры матмеха)
3*) АФТУ

Детализация по кафедрам нужна, ибо на том же мехмате МГУ есть какая-нибудь кафедра гидромеханики, что к программированию имеет o(1). МГУ-шники - это все дискретные - логики и теории алгоритмов, алгебры, дискретной математики. СПбГУ - тереховская, у ИТМО - я знаю только про КТ.

АФТУ идет со звездочкой, потому что они только по магистрам, и там только 1-2 группы. Даже в Питере о них знают немногие (человек с АФТУ сильно удивился, что я знаю что это такое). Направление CS там довольно hardcore-ное, ибо люди с ПОМИ.

Это не значит, что если вы не с перечисленных организаций - то ничего не знаете. Да будь у вас даже красный диплом с ММ МГУ, то это ничего не значит. Если вы не с крутого вуза, то вы можете всего добиться сами, если с крутого - то есть шанс, что кто-то на парах рассказывал что-то путное. Другой вопрос, ходили ли вы туда, и был ли эффект. А то словосочетание "прослушал курс" можно понять двояко.

Есть большие вопросы: "Чему же обучать?"

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

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

Я не против матана и тервера, оно надо, но надо в другом качестве и количестве. Вот вам рассказали про диффуры в частных производных, ТФКП/функан, хардкорный тервер... Теперь вы можете одной левой брать диффуры и жать штангу. Причем одновременно и одной рукой. Круто. Но применительно к компьютерам это абсолютно бесполезно.

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

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

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

Не призываю сжечь Жанну Д'Арк кого-либо. Арнольд лет 10-12 назад писал про французское математическое образование. Там реально все страшно. Но была такая мысль, что образование работает как фильтр - умный человек и сам всего сможет достичь, а тупых фильтруют.

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

Краткость

Тут недавно взяли на слабо. Задача почти стандартная, известная как K Problem + большая грамматика.

Далее "моя" реализация. "Моя" - потому что я заиспользовал комбинаторы.

Парсер комбинаторы - круто. Смотрим и писаем кипятком кончаем наслаждаемся.

Эта часть легко находится по подстроке "-- Carsten Schuermann: From: Monadic Parser Combinators [Hutton, Meijer]"


Тут пока некоторая магия, в которую за 5 минут не въехать. Далее должно быть понятнее.

AST - это или ссылка на ячейку, или число, или бинарный оператор из AST.
Вводим парсер для AST. Опишем стандартные арифметические операторы.

А теперь *барабанная дробь*



Собственно все, парсер (лексер + синтАнализатор) готов.
Запускаем и оно работает.



Где вы еще сможете в 3-4Кб уложится? Это вам не парсер-генератор, здесь все сделано вручную... Правда, исходя из этого - это LL. Бывает кое-что затруднительно выразить в LL, да еще и следить за левой рекурсией. LR вручную непросто реализовать, но мне местами такая грамматика больше нравится. Есть еще всякие PEG/Packrat, с не очень понятной теорией (трудно понять, выразима ли конкретная грамматика в них), и куча непрактичных но теоретических парсеров.

Далее опишем типы для "excel". Ячейка - есть строка, лист как коллекция пар из (ячейка, строковая формула) и так далее. В идеале надо бы абстрактный маппинг (словарь/функцию) из ячейки в формулу.



Простая вычислялка AST и вычислялка для строки.



Пара тривиальных вещей:



Несколько типов для вычислителя excel-я.
EvaluatedCellBuffer - это результат вычислений. Далее его как аккумулятор и будем вычислять.



Вся логика вычислений в следующем:



Далее очевидная вода:



Вычисление одной ячейки:


Тривиальный вычислитель



Пара утилитных функций



И вычисление всего листа



Примеры листов:



И примеры:


Еще можно добавить шапочку :)


В 8Кб имеет парсер, AST, вычислитель, и обход и расчет листа excel.
Несложно расширяемо на
- функции и несложную типизацию в встроенном языке
- отказаться от дву(3 ли 3.5 как в excel) мерности задачи и перейти к произвольной размерности.

У меня в текущем проекте есть нечто похожее, но это явно не 8Кб.

ЗЫ. Научиться бы здесь нормальное форматирование делать... В процессе.

Железотворительность

Подарил:
- кучку флешек, флеш-карточек
- две планки памяти
- видеокарточку
- устаревшие телефоны

Продал:
- два мертвых винта
- сломанный ЭЛТ-монитор
- потрохи от умершей машины (проц, блок, видео)

Разобрал на части:
- 3 cdrom-a

Агрегируем: все мне ненужное - дарю, все сломанное - или разбираю до винтиков, или продаю тем, кому нужны трупики.

Полтора ящика все равно забиты железным хламом. Хлам - это не мусор, его еще не выбросишь. Подарить что ль?

Идентификация

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

Всякие извраты с индийским наименованием не рассматриваем. Из серии "А знаете ли вы что...?": некто Вишванатан Ананд - это не просто имя и фамилия крутого индийского шахматиста. Оказывается, Ананд - это имя, Вишванатан - имя отца, а фамилий в нашем понимании у них (него) нет. В крайнем случае каста и город. Сошлемся на википедию.

В древней Греции, как сейчас помню, к имени добавляли город. В связи с развитием интернета, к имени сейчас добавляется логин/ник. Далее несколько замечаний о никах.

Понятно, что есть требование к уникальности (нетривиальности). Если назваться избито "Alex"... Хотя в некоторых кругах ник "Petr" - это очень круто, это реально имя собственное.

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

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

Проблема в том, что:
- почти никто не может его запомнить с точностью до знака. Только я и Артем В.
- не везде он валиден. Хотя, насколько я помню, согласно RFC email может начинаться с цифры. Но конкретную систему не убедишь что ей стоит почитать RFC. Поэтому приходится добавлять префикс, или другое.
- увы, и даже это не уникально. По крайне мере #.blogspot.com занят китайцем, еще на каком-то ruBoard-e это тоже оказалось занято.

В окружении (друзья и знакомые) есть те, кто в качестве суффикса выбрали двузначное число. 10/13/52/etc. Причем никто не может обосновать выбор. Это не возраст, не год рождения, не квартира, и не школа. Если увидите ник *239, то это скорее всего с Питера(школа), если *57 - с мск, если 30/40/41 - хоть откуда.

Поэтому я перешел на фамилию. Тут есть тоже плюсы и минусы.

+ Почти уникальность. В городе не более 10 человек, во всех соцсетях порядка одной/двух сотен.
+ По алфавиту в начале.
+ В большом неотсортированном списке в глаза бросается, ибо вторая буква.

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

ЗЫ.
Сложнее противоположному полу: есть некоторые особенности с постоянством/временностью фамилии.

Кстати, есть предложение переходить от отчества к матриархальной сущности (мочество? матринство?). Ибо если рождается девочка, то родители могут сказать что "внуки точно их будут".

Знаменитость

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

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

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

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

Избыточность воспитания

Чуть ли не половина сообщений в скайпе/жаббере у меня составляют "подтверди/получил?/не получал". Началось где-то год назад, похоже когда поменял роутер. Старый вешался довольно часто, при 20 торрентах не мог протянуть и получаса.

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

Поэтому сообщение от меня в виде "подтверди" не стоит рассматривать как признак дурного воспитания. И если я не ответил на вопрос, то тут есть вероятность что я его не получал.

ЗЫ.
И в шахматы во "вконтакте" играть невозможно, после двух ходов соперник не отвечает. Хотя, единственное что там осталось - музыка, играет без проблем. Какие-то проблемы на уровне поддержки коннекта.

низкоуровневость

c++ такой...

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

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

Выжимаю что могу, даже переписал на плюсах. На решетке (С#) пробил построение динамического суффиксного массива в 100кб/с (на первых ста килобайтах :) , дальше сказывается log^2(n)). Предыдущие алгоритмы жирноваты, там чуть ли не 3/4 времени вычисляю lcp (DRMQ). А сейчас даже lcp вычислять не обязательно, только добровольно. По константе раз 5-6 лучше.

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

Низкоуровневость и отсутствие инструментов бесит. Хотя я на это сознательно шел - это про первое. Приходится мыслить терминами "кусок памяти" и указатель. На чистый С не буду переходить, ибо у меня сплошные массивы деревья, их довольно много и объектность с виртуальностью позволяют это как-то целостно видеть. Иначе будет ад.

Дайте мне нормальную строку - мне много не надо, всего лишь: индексный доступ, возможность удаления/вставки/замены в любой позиции. Все за O(log(n)). (С) рекламный слоган. Вроде бы немного хочу, ан нету. Видимо, максимум что нужно остальным - это stringBuilder с потоковой записью в конец. А мне надо все и сразу и везде.

Год назад я "жаловался" на отсутствие простых массивов. Ну нету нигде нормальных. А нужно мне опять немого: индексный доступ, удаление/вставка/замена в любом месте и опять же за логарифм. Правда, еще нужно пару плюшек.

А везде массивы и строки - кусок памяти. Такое ощущение, что кусок чего-то такого густого и оно так на полу на кухне лежит. Даже трогать не хочется. Это блин, кусок памяти. Хочется чего-то гибкого и быстрого, а не кусок.

Конечно, воняет велосипедизмом. Но почему-то приходит осознание, что это круче велосипеда и местами на 4-5-6 и более колесах с термоядерным двигателем и крыльями - можно лишь подсматривать на другие транспортные средства.

Несколько дней избавлялся от ошибки. На маленьких строках все работает, на баааальших падает с полной фигней. Если бы в языке было понятие выхода за границы массива, или хотя бы что я не пишу в "получужую" память, то мне бы хватило и 5 минут. А так как выделение памяти для переменных/объектов есть кусок памяти, то случайный выход за границы можно уловить только через пару дней. Или я совсем не знаю ключей компиляции.

А если использовать всякие stl и прочее непонятное типа boost, то мы похоже ничего кардинального не выиграем. Ну, будет некоторая константа по скорости, но по всему остальному преимуществ уже не будет. Тогда стоит и переходить на более высокоуровневые инструменты.

Поэтому у меня всего один #include < string > , в одном не критичном месте, и никакого использования даже stl-я.