Хабрахабр:
В продолжение вчерашнего обсуждения. В прошлый раз остановились на том, чтобы объяснить как работают алгоритмы унификации и фильтрации на конкретном примере. Сам пример был построен особым образом, чтобы проверить определенные свойства алгоритмов. Для дальнейшего обсуждения я написал небольшой unit-тест, который оперирует формулой из примера. Unit-тест нужен для того, чтобы пропустить шаг алгоритма Романова, где происходит декомпозиция исходной формулы на множество CTF. Вместо этого декомпозиция предлагается изначально автором вопроса. Unit-тест и подробный лог работы приложения я выложил здесь: gist.github.com/791064 Предлагаю по возможности ссылаться туда по номерам строк (там не совсем удобно, что нельзя дать прямую ссылку на номер строки, придется искать ее вручную; если кто-то предложит более удобный сервис, я перенесу лог туда). Как видно из лога работы, тест заканчивается ситуацией, когда на очередном шаге построения гиперструктуры базисный граф оказался пустым множеством, что согласно алгоритму означает, что формула не выполнима (пункт 2b внизу страницы 11 в тексте статьи). Чтобы не переписывать здесь еще раз статью, предлагаю в обсуждении задавать вопросы, которые требуют дополнительных разъяснений.
Сейчас поиск людей на сайтах знакомств, по эффективности сравним с работой золотоискателя на заброшенном месторождении. Может быть в этом и есть сермяжная правда ? ценится то, что достается нелегко, да и рекламных показов больше. Но вот с пользовательской точки зрения, очень нужны инструменты группировки по сходным признакам. Например: 1. Инструмент с циничным названием ?С этой девушкой выбирают также:? ?Не сложилось? Посмотрите эти анкеты:?. Берем тех парней, кто написал этой девушке и показываем других девушек, которым они писали за последние пару дней. Предполагается, что людям нравится определенный типаж. Для слишком популярных анкет вводим понижающий коэффициент, чтобы не было засилья людей с модельной внешностью. 2. Интересы и группировка по степени совпадения в процентах, как музыкальные вкусы на last.fm. Собственно здесь, могут быть те же музыкальные или киношные вкусы. Не только на сайтах знакомств, например, в ЖЖ очень не хватает такой группировки по интересам. Общая цель сводится к тому, чтобы пользователь находился в своем сегменте, в своем кругу общения, интересов и предпочтений. Как и в реальной жизни, только круг общения будет включать в себя значительно больше участников.
Попытка улучшить алгоритмы растеризации шрифтов, пользуясь исключительно общедоступной информацией. От переводчика В первый раз я столкнулся с этой статьей в 2008 году, и ещё тогда поразился изяществом алгоритма растеризации шрифтов, предложенного автором. С тех пор меня регулярно посещали мысли сделать перевод, пока ссылка на статью не всплыла на Хабре в обсуждении топика ?Сглаживание шрифтов, анти-алиасинг, и субпиксельный рендеринг?. С тех пор я несколько раз откладывал перевод, который требовал определенных знаний в области экранной типографики, но, наконец-таки, собрался его опубликовать. Читать дальше →
Наверное, все, кто сталкивался с разработкой более или менее серьезных приложений, знают, что выбор формата хранения настроек скрипта или приложения ? достаточно ответственное дело. Конфиги должны быть легко читаемыми, легко модифицируемыми, легко переносимыми, и так далее ? список можно продолжать и продолжать. Так как серверные PHP-скрипты выполняются, бывает, много раз в секунду, скорость загрузки конфигов ? достаточно важный параметр. Хотя ему, порой, уделяется не очень много внимания. Давайте сравним различные варианты хранения настроек для PHP-скриптов с точки зрения скорости их работы. Ну и коснемся вкратце их удобства. Читать дальше →
Что у каждого гика под руками? Правильно ? клавиатура На днях ingeniarius попросил заценить одно из своих творений. Чтобы я смогла полностью проникнуться приложением вручил мне вот такой девайс. Симпатичная, правда? Всю силу привычки я ощутила после первых минут работы с TypeMatrix: печатаю как обычно, но текст при этом совсем не тот, что ожидаю. Постоянно промахиваюсь. Казалось бы, 5 миллиметров (отсутствие небольшого смещения), а все годы тренировок на смарку. При этом мне мега нравится эта клава. Она меньше чем обычная, клавиши одна над другой ровными рядами, разделенные на две руки, большие бекспейсы и энтеры, приятный ход клавиш? Мечта ? а не клава. Смотрю на нее и хочется печатать, сажусь и хочется только смотреть на нее. Читать дальше →
Решив учитывать собственное время, я быстро обнаружил, что оно уходит впустую в тех случаях, когда приходится постоянно переключаться с одного вида деятельности на другой. Я не говорю здесь о переключении каждый час или два ? напротив, это повышает производительность труда. Я скорее имею в виду многократную смену деятельности в течение 15-30 минут. Действительно, представьте, что вы захотели проверить почту, но быстро переключились в браузере на ваш любимый блог, а затем и вовсе углубились в переписку с друзьями в Facebook и выполнение заданий в Mafia Wars. Вскоре вы обнаружите, что толком ничего не сделали. Вы посетили множество мест, многое узнали и многое потрогали, но потеряли кучу времени. Потери времени начинаются уже на этапе проверки почты. Вы заходите в почтовый ящик, и там лежат десятки писем. Вы скользите по ним взглядом, и видите три уведомлялки из Facebook, одну из Twitter, пять рассылок от авторов программ, которые вы когда-то скачали или сервисов, в которых зарегистрировались. Из дюжины писем хорошо если одно написано живым человеком, который ждет ответа. Мне ежедневно приходит до сотни писем ? в основном, обезличенные сообщения от пресс-служб или администраций различных сайтов. До начала учета времени я не осознавал, что каждый раз при проверке почты теряю до получаса на разгребание этих завалов. Хуже того, а не осознавал и другого: человек не может с одного просмотра вычленить одно важное сообщение из пятидесяти. Ну и, конечно, третьего ? я заходил не проверить почту, а взглянуть, нет ли личных писем от моих друзей и знакомых. Читать дальше →
Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность ? простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье. Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания. Итак, на повестке сегодняшнего дня ? моноиды и их основное применение для кеширования вычислений в деревьях. Моноид как концепция Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "?", и записывать выражения в инфиксной форме: если a и b ? элементы множества, то c = a ? b ? тоже какой-то элемент этого множества. Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "?", а в большинстве языков программирования "+": "John" ? "Doe" = "JohnDoe". Здесь множество M ? строки, а "?" выступает в качестве операции "?". Или другой пример ? функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое. Далее мы на нашу операцию "?" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "?" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "?". Более строго, для любых трёх объектов a, b и c должно иметь место: (a ? b) ? c = a ? (b ? c) Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо: fst(fst(a, b), c) = a fst(a, fst(b, c)) = a Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент. И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e ? нейтральный элемент, то для любого a из множества имеет место: a ? e = e ? a = a В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ? e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :) Каждую такую тройку <M, ?, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде: public interface IMonoid<T> { T Zero { get; } T Append(T a, T b); } Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом. Читать дальше →
Однажды кто-то сказал: ?Идея ничего не стоит?. И был, возможно, где-то прав. По крайней мере, в существовавшей на тот момент схеме взаимодействия ?стартаперов? и ?инвесторов? небыло места для человека, имеющего в багаже одну лишь только идею интернет-проекта. Множество раз мы слышали, как венчурные инвесторы говорили: ?У нас тысячи идей, но их некому реализовывать, поэтому нам нужна 'команда+идея', а лучше ? 'команда+прототип', а ещё лучше ? 'прототип, имеющий аудиторию, и приносящий хоть какую-то прибыль'?. В этом топике я хочу рассказать о новой взаимовыгодной модели взаимодействия трёх участников: ? автора идеи, ? инвестора, ? команды разработчиков ... Читать далее ...
Когда начинаешь изучать вопросы построения компиляторов, компиляции текста, оптимизации при компиляции, то всегда сначала ведешь огромные книги, кучи текста, мат выкладки, доказание теорем о равномощности языка и еще очень много чего. Это конечно хорошо, но некоторым программистам, типа меня проще понять лексические и синтаксические анализаторы на живых примера. Куда проще увидеть класс, в котором содержится токены, на которые был разбит, чем долго и мучительно перечитывать главу. Во время изучения компиляторов, я решил прогуляться по codeplex в поисках кодов, которые могут мне помочь. И кое-что нашел. Я не рассказываю тут умные слова про LL, про разрешения конфликтов LL(1) и тп. Теория компиляции изложена и в книжках не плохо. Я рассказываю именно о проектах которые я смотрел и посчитал интересными. Прошу судить. Читать дальше →
Отписаться от этой рассылки