Не помню

Ой, где был я вчера
(с) Володя

Дочитал книжку, начал тыкать на планшете, чтобы выбрать слудующую из коллекции. У меня там местами шлак всякий, худ. лит, тех. лит, статьи какие-то. Тыкнул и смотрю "Efficiently four-coloring planar-graphs". Хоть убейте, не помню как она туда попала. Я только 2 недели назад о ней писал, а она оказывается чуть ли не год (не помню, может и 2 недели) как валяется в iBooks.

В общем, да, раскраска в 3 цвета для планарных - NP-hard, в 5 цветов - линейна, в 4 - тут как-то строят за квадрат. Мне еще почему-то интуитивно кажется, что если хроматическое = 4, то есть подграф стягиваемый к K_4 (?). Черт, и не понятно. То ли это какая-то тривиальщина, то ли вообще неправда. И непонятно, причем тут планарность.

А еще помню, когда не помню. Был где-то классе в 7-ом (может 8-ой), спал что-то днем. Позвонили на домашний, сотовых тогда не было. Спросонья ответил. Минуты через 2 еще звонок. Я уже немного рассерженный в трубку "Ну что еще, мам". А там мне тренер по шахматам, Маргарита Капитоновна: "Я еще вот что хотела спросить...". Как-то сразу проснулся.

И еще два случая помню, когда не помню. По работе приходилось в жизни 3 раза ночевать на работе. Ладно бы сторожем работал, програмистом 32 часа непрерывно что-то колбасить это жестоко. Тьфу^3, давно было.

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

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

Все остальное я помню, что помню. Заметьте, что это сильнее чем "не помню как нажрался" (лучше "помню что не нажрался").

Если что, то к алкоголю я негативно отношусь. Годовое потребление можно перечислить пальцами одной человеческой руки. В крайнем случае, одной человеческой + 2 пальца.

ЗЫ. Не кидаю ни в кого кирпичом, но фраза "Я запомнила... *пауза* на 10 минут" действительно со второй частью смешна.

Прогрессия

В начальных классах у меня был почти "Компаньон", оно называлось иначе, имело 48Кб оперативной памяти и читало программы с магнитофона. Первый "полноценный" компьютер у появился только в 11-ом классе. Он был с монитором в 17" (1024х768), 64Мб оперативы, 10Гб диска, 500МГц процессора, очевидно в одно ядро и в прочих характеристиках. Хотя почему был... до сих пор работает.

Так вот, я обновил телефон. Там 4 ядра по 1.5 ГГц, 1280х768, 16Гб карточка и 2Гб оперативы. Весит оно 130 с чем-то грамм. Ну, в общем, вы поняли...

В принцице, сейчас выбор между iPhone и не_iPhone. Но так даже в последней модели там нет NFC, то выбор для меня был очевиден. Я в принципе нейтрально-позитивно отношусь к Apple, считая что их планшет пока и сейчас даже очень ничего.

Я вот трачу на телефонную связь сотню рублей месяца на 4, в основном использую как будильник и совсем в редких случаях как карты городов. Поэтому мне в принципе пофиг. Еще я видел девушку в продуктовом магазине с iPhone-ом из последних. Я не настолько крут. А она - крутая. И продает там фрукты/овощи.

Так и не понял, можно ли где-то у нас в стране использовать NFC как платежный инструмент. Московское метро уже года три собирается, я попробовал, но как лошара с выключенным телефоном - оно очевидно не сработало. Аэроэкспресс говорит про скидку, но пока возможности не было. GoogleWallet в России не работает, не выросли мы еще со своим уровнем коррупции. А использовать только как читалку билетов на метро - как-то глупо и малоэффективно. Верим что настанут лучшие времена.

В предыдущем телефоне был аппаратный компас, и когда ты стоя ловил GPS, то было понятно направление куда смотришь. Сейчас GPS ловится практически мгновенно, но надо немного подвигаться чтобы понять направление.

В стране опять официально можно купить в Связном за 20 тыс. рублей, но почему-то заказать с google + посреднику 70$ за пересылку оказывается в полтора раза дешевле. Очевидно, воспользовался вторым вариантом. Конечно, есть риски. И даже посредник сейчас в новостях уведомляет, что более он именно эту марку не пересылает в Россию, так как участились кражи во время доставки.

С "Компаньоном" я в 5-7 классе писал несложные программки для простой геометрии в 3d, как оказалось к 5-му курсу у нас большинство хуже умело программировать, чем я тогда. Ностальгия... А с телефонами скучно, ну купил зеркальце, там даже кнопок нет.

Два бояна и кое-что о числах

Мужики уже умеют искать поток за O(n m). Некоторые говорят, что это боян, но я увидел только пару недель назад. Оригинальная работа вышла в августе 2012. До этого было что-то близкое по сложности, со страшными логарифмами.

Мужики умеют искать раскраску в 4 цвета для планарных графов за квадрат. Честно говоря, ВНЕЗАПНО. С какого-то 199? года. Там (с хроматическими числами) чуть ли не половина задач NP-трудные/сложные. Да и как планарность за линию делают - в моей интуиции это не укладывается. Жаль, что времени на это выделить я полноценно не смогу.

Обнаружил замечательный факт по числам Мерсенна. Пока его нигде не видел. Напомню, что тест Люкаса-Лемьера состоит в 

s_0 = 4

s_n = s_{n-1}^2 - 2 mod M_p

Если s_{p - 2} = 0, то все хорошо. 

Я все брежу, чтобы идти с конца. Корни же не всегда извлекаются. 

То есть надо идти с нуля, применяя следующую операцию, \x -> sqrt(x + 2), что дает 2 числа, либо облом.

Так вот, для Мерсенновых получается идеальное бинарное дерево. Начиная с 2 (0 + 2) получаем два числа, затем 4 числа, и так далее. На последнем шаге получаем красоту, пока необъяснимую. Никаких циклов, все числа использованы, из последнего слоя уже корни квадратные не извлекаются. Думал, что извлекаемость корней есть полный беспорядок, а тут идеальная структура. Уже недели две хожу с упоротыми глазами.

А те, которые неМерсенновы, получаем облом на втором шаге. Корень из двух очевидно равен 2^{(p + 1) / 2}. А извлечь корень из 2^{(p + 1) / 2} + 2 быстро не могу. Для неМерсенновых там облом идет. Знаний пока мало, маленький еще. Чтобы решить x^2 = a mod M_p можно просто x = a^{2^{p-2}}. То есть возведениями "в_квадрат" все равно O(p) шагов, что тот же Люкаса-Лемьера ничем не лучше. Фенечка на первом шагу для 2 заключается в том, что 2 порождает хорошую группу размером в p. Поэтому все быстро. Но стоит отойти на шаг в сторону, и размер группы будет несколько великоват, во что и утыкаюсь.

Еще пытаюсь что-то извлечь из x^3 = 1 mod M_p. Так как 2^p - 2 очевидно делится на 3, то у нас есть подгруппа размера 3. Первый корень тривиален. Тут внезапно работает теорема Виетта, та которая про сумму и произведение корней и первый/последний член полинома. Другие два корня тривиально находятся, если найти x^2 = -3 mod M_p. Что эффективнее чем Люкас я пока не вижу как. Утык.

Где бухают теоретики-числовики и прочие алгеброиды? Как в стране, так и в мире... И чтобы дети, моего уровня, смогли приобщиться. Всякие http://math.stackexchange.com/ понятно, но хочется очные.

Техническое. Мимоходом.

Если у вас в проекте oracle && .net && куча данных для сохранения, то следующий абзац (два и более, как получится), возможно, будет вам интересен.

Там получилось, что нам надо сохранять довольно много ячеек, порядка одного/двух миллионов. Естественно, хочется быстрее. Ячейки из собственного OLAP, по измерениям отличаются, разных типов штук 10-15, то есть раскидать по таблицам на каждый тип.

В итоге мы плюем на нормализуемость таблиц, тут производительность важнее. Хранится ключ по разрезам, понятно отдельно Id, а потом идет пару сотен столбцов/показателей. У себя внутри мы это называем "развернутые таблицы".

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

Ранее все хранилось как у всех обычных людей, для каждой ячейки отдельная запись. Философски это правильно. А как развернули, база с десятка Гб ужалась в 1Гб, со всеми индексами.

Теперь собственно про запись. Рекомендуется посмотреть на ODP.net (Oracle Data Provider). Там есть фишечки и тюнинг. В нем же есть ArrayBinding, это когда вместо сохранения большого массива записей вы кидаете один запрос, а все параметры биндите на массивы, где каждый массив представляет один параметр. Хоть это и круто, но пока это не все.

Очень важно, чтобы запрос был все время одинаковым. Иначе oracle будет все время его компилять/парсить, как следствие - потери. Для нашего случая мы определяем наиболее общий набор показателей (столбцов) для сохранения. То есть сохранение в просто "развернутой" таблице - это что попало из прямоугольной матрицы, а становится - объединение набора столбцов. Да, это немного лишнее, получается что мы заново сохраняем некоторые ячейки которые уже есть в базе. Но зато так sql-запрос становится универсальным для всей таблицы (конкретного набора для сохранения). А сейчас если воткнуть arrayBinding из предыдущего абзаца, то скорость сохранения увеличится на десятичный порядок.

То есть у нас было несколько итераций.
1) Просто таблица
1.1) Просто таблица + arrayBinding
2) Развернутая таблица, сохраняем одним запросом кучу ячеек.
3) Развернутая таблица, объединеный запрос на все сохранение, биндим параметры на каждый ключ отдельно
4) Развернутая таблица, объединенный запрос, биндим массивы как параметры.

Переход от 3 к 4 - это реально десятикатный прирост. От 1 к 1.1, от 1 к 2 и от 2 к 3 - где-то от полутора до трех раз (в зависимости от данных и направления солнечного ветра).

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

Еще важно, чтобы запрос был как можно проще. У нас в итоге после последнего рефкторинга самая медленная таблица оказалась единственная с nullable полем в ключе. И запрос был с NVL/decode. Естественно, решили проверить. И да, бинго. Разнесли данные, и оно относительно себя ускорилось в 2 раза, относительно всех остальных не стало выделяться.

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