(на графике по оси абсцисс логарифмическая шкала)

В ходе обсуждения анонса арендуемых серверов на базе атомов по 1500р возник вопрос, насколько атом более медленный, чем остальные платформы.

Вопрос оказался интересным. Вот результаты тестов. В качестве теста использовался sysbench (он есть во многих дистрибутивах Линукса, в т.ч. в Ubuntu и Squeeze).

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

Хорошо видно, что атомы существенно проигрывают Core/Xeon процессорам, которые в один поток оказываются в полтора-два раза быстрее, чем атом с двумя ядрами и гипертредингом.

Ещё одно интересное наблюдение — на атоме 32-битный и 64-битный режим показывают себя одинаково, на всех остальных процессорах 64-битная архитектура заметно выигрывает у 32-битной.

В качестве эталонного теста использовался вызов nice -20 sysbench --test=cpu --cpu-max-prime=40000 --num-threads=X run (X — число потоков, от 1 до 16).

Конечная цель любого стартапа — деньги. Будет ли это успешно работающий доходный бизнес или выгодная продажа более крупным игрокам рынка, зависит от каждой отдельной компании. Кто-то хочет получить свои миллионы от Гугла, кто-то и сам не прочь стать Гуглом. Конечно, важна идея, самовыражение, амбиции — не без этого. Но в итоге, если не верить, что стартап принесет миллионы, то и начинать не стоит. Поговорим о том, как же делить доли в стартапе между основателями компании.

Мы делили апельсин, много нас, а он один

В американской традиции стартапов принято брать в долю всех участников проекта, работающих с первого дня его основания. Отличный способ мотивации команды, скажу я вам. Но как делить баснословные доходы, если они таки будут? Самое первое, приходящее на ум — поделить поровну. Таким образом, если над стартапом работало пять человек, то каждому достанется по 20%. Справедливо? Не очень.

У американцев есть отличная поговорка про курицу и свинью «a chicken is involved with breakfast, but a pig is committed»: речь о яичнице с беконом на завтрак, для приготовления которого требуется некоторое усилие от курицы (снести яйцо и жить себе спокойно дальше), в то время как свинье придётся принести куда более существенную жертву. Так же и в бизнесе: некоторые участники проекта выполняют работу достаточно формально и потом наблюдают за результатами, другие же несут принципиально большие риски и вкладываются в дело сильнее.

Frank Demmler, профессор предпринимательства в бизнес-школе при Carnegie Mellon University, предложил следующий метод распределения долей в стартапе.

Очень часто фантазия человека, разрабатывающего макет сайта, не ограничивается шириной 1024px, при этом требуется, чтобы сайт выглядел достойно на всех разрешениях и соответствовал полёту мысли дизайнера.

Проблему можно представить графически так:


Задача вёрстки заключается в следующем:

• — независимо от разрешения (размера она браузера), информативная часть сайта находилась посередине;
• — справа и слева должны остаться графические блоки (уши), причём эти уши должны быть видны только при увеличенном размере экрана браузера, а при уменьшенном не уместившаяся часть должна прятаться (в идеале, чтобы ещё горизонтальной полосы прокрутки не было);;
• — страница должна быть резиновой от 680px до 1000px.

Работает для FF3, FF4, IE8 и почти для Opera.

В догонку к посту про макет бизнес модели, не менее полезный «самый короткий в мире маркетинговый план» (так его назвал автор, Келли Одел).

Можно для любой новой идеи, продукта или услуги заполнить эту табличку и сразу увидеть общую картину с перспективами.

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

Введение

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

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Добрый день, Хабрахабр. Это еще один пост в рамках моей программы по обогащению базы данных крупнейшего IT-ресурса информацией по алгоритмам и структурам данных. Как показывает практика, этой информации многим не хватает, а необходимость встречается в самых разнообразных сферах программистской жизни.
Я продолжаю преимущественно выбирать те алгоритмы/структуры, которые легко понимаются и для которых не требуется много кода — а вот практическое значение сложно недооценить. В прошлый раз это было декартово дерево. В этот раз — система непересекающихся множеств. Она же известна под названиями disjoint set union (DSU) или Union-Find.

Условие

Поставим перед собой следующую задачу. Пускай мы оперируем элементами N видов (для простоты, здесь и далее — числами от 0 до N-1). Некоторые группы чисел объединены в множества. Также мы можем добавить в структуру новый элемент, он тем самым образует множество размера 1 из самого себя. И наконец, периодически некоторые два множества нам потребуется сливать в одно.

Формализируем задачу: создать быструю структуру, которая поддерживает следующие операции:

MakeSet(X) — внести в структуру новый элемент X, создать для него множество размера 1 из самого себя.
Find(X) — возвратить идентификатор множества, которому принадлежит элемент X. В качестве идентификатора мы будем выбирать один элемент из этого множества — представителя множества. Гарантируется, что для одного и того же множества представитель будет возвращаться один и тот же, иначе невозможно будет работать со структурой: не будет корректной даже проверка принадлежности двух элементов одному множеству if (Find(X) == Find(Y)).
Unite(X, Y) — объединить два множества, в которых лежат элементы X и Y, в одно новое.

На рисунке я продемонстрирую работу такой гипотетической структуры.

Вы, вероятно, представляли ее себе как целый орган — грандиозное сооружение длиной в пару метров с сотнями и тысячами клавиш. На самом деле, большинство китайцев используют обычную клавиатуру с латинской раскладкой QWERTY. Но как с помощью нее можно набрать такое несметное количество различных иероглифов? Мы попросили рассказать об этом нашу сотрудницу Юлию Дрейзис. Ее с Китаем связывают и давняя любовь, и работа.

История вопроса: печатные машинки

За несколько тысяч лет хитроумные китайцы успели довести количество иероглифов до 50000 с хвостиком. И хотя число нужных в повседневной жизни знаков не измеряется десятками тысяч, все равно, как ни крути, стандартный набор старой типографии — 9000 литер.

Долгое время набор осуществлялся по принципу «на каждый иероглиф — отдельный печатный элемент». Поэтому работать приходилось с машинками-монстрами вроде такой:


Печатная машинка фирмы «Шуангэ», 1947 год (принцип действия придуман японцем Киота Сугимото в 1915 году).

Представьте себе Maple, Maxima или Mathematica, в которой правила работы являются энциклопедическими статьями, и, наоборот, энциклопедию, пополняя которую, вы улучшаете работу системы компьютерной алгебры. Эта идея лежит в основе Galois/Wiki (Галуа/Вики) — математической энциклопедии с интеллектуальным поиском.

Всего несколько дней назад этот процессор был анонсирован на конференции Hot Chips 2010, причем анонс прошел довольно скромно, несмотря на значимость самого продукта. Анонс нового процессора был сделан не руководством компании, а простым (ну, или не очень простым) инженером IBM по имени Брайан Карран. Он скромно заявил, что вскоре начнутся продажи самого производительного процессора в мире, тактовая частота которого составляет, сколько бы вы думали? Да, 5,2 гигагерца. Жаль конечно, но этот процессор никак нельзя встроить в потребительский ПК, или ноутбук — он предназначен для мейнфремов серии Z.

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Очень сильное колдунство

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

Вспомним-ка еще раз структуру дерамиды. В ней есть ключ x, по которому дерамида есть дерево поиска, случайный ключ y, по которому дерамида есть куча, а также, возможно, какая-то пользовательская информация с (cost). Давайте совершим невозможное и рассмотрим дерамиду… без ключей x. То есть у нас будет дерево, в котором ключа x нет вообще, а ключи y — случайные. Соответственно, зачем оно нужно — вообще непонятно :)

На самом деле расценивать такую структуру стоит как декартово дерево, в котором ключи x все так же где-то имеются, но нам их не сообщили. Однако клянутся, что для них, как полагается, выполняется условие двоичного дерева поиска. Тогда можно представить, что эти неизвестные иксы суть числа от 0 до N-1 и неявно расставить их по структуре дерева:

Получается, что в дереве будто бы не ключи в вершинах проставлены, а сами вершины пронумерованы. Причем пронумерованы в уже знакомом с прошлой части порядке in-order обхода. Дерево с четко пронумерованными вершинами можно рассматривать как массив, в котором индекс — это тот самый неявный ключ, а содержимое — пользовательская информация c. Игреки нужны только для балансировки, это внутренние детали структуры данных, ненужные пользователю. Иксов на самом деле нет в принципе, их хранить не нужно.

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

Предупреждение: Описанное в статье несколько устарело, т.к. я забросил винды в эпоху Windows 2003.

Каждый раз, когда меня знакомые спрашивают: «какой антивирус лучше?», я могу сказать только одно: «антивирус — как придворный шаман. Бывают лучше, бывают хуже, но определить, кто лучше камлает, не получится». Антивирус не гарантирует защиту от вирусов, более того, у него есть полное моральное право пропустить новую заразу и начать её детектить дня через 2-3 после «инцидента». Т.е. как основное средство защиты он годится не очень.

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

Теория

Любой уважающий себя вирус, оказавшись запущенным, тем или иным методом стремится в системе закрепиться, т.е. создаёт исполняемый файл или библиотеку, которая прописывается тем или иным образом в запуск. «Авто» запуск или в форме «дополнения» к другим исполняемым файлам (debugger, hander, плагин, и т.д.) — не важно. Важно: существует барьер под названием «запуск кода». Даже старые-добрые вирусы, дописывающие себя в исполняемые файлы, всё равно должны иметь возможность писать в файлы, которые предполагается запускать.

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

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

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

Однако, запреты и разрешения не будут иметь смысла, если не сформулировать правила, которые запретят запуск «чужаков».

Модель безопасности

Перед тем, как описать подробно конфигурацию, сформулирую теоретические принципы её организации:

1. То, куда пользователь может писать закрыто для запуска.
2. То, что пользователь может запускать, закрыто для записи.

Это двадцать шестая публикация в серии публикаций о VS 2010 и .NET 4.

Сегодняшняя публикация рассматривает некоторые полезные советы по отладке которые вы можете применять в Visual Studio. Мой друг Скот Кэйт (Scott Cate) (который опубликовал в блоге дюжину великолепных советов и трюков по VS) недавно обратил мое внимание на несколько хороших советов о которых не знает много разработчиков использующих Visual Studio (даже при том, что многие из них работают с ней уже давно с более ранних версий).

Приветствую хабраюзеров, в этой статье пойдет речь о внутреннем устройстве компилятора LLVM. О том, что LLVM вообще такое, можно прочитать здесь или на llvm.org. Как известно, LLVM (условно) состоит из трех частей — байткода, стратегии компиляции и окружения aka LLVM infrastructure. Я рассмотрю последнее.

Содержание:

• Сборка LLVM
• Привязка к Eclipse
• Архитектура окружения
• LLVM API
• Оптимизация Hello, World!

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Тема сегодняшней лекции

В прошлый раз мы с вами познакомились — скажем прямо, очень обширно познакомились — с понятием декартового дерева и основным его функционалом. Только до сих мы с вами использовали его одним-единственным образом: как «квази-сбалансированное» дерево поиска. То есть пускай нам дан массив ключей, добавим к ним случайно сгенерированные приоритеты, и получим дерево, в котором каждый ключ можно искать, добавлять и удалять за логарифмическое время и минимум усилий. Звучит неплохо, но мало.

К счастью (или к сожалению?), реальная жизнь такими пустяковыми задачами не ограничивается. О чем сегодня и пойдет речь. Первый вопрос на повестке дня — это так называемая K-я порядковая статистика, или индекс в дереве, которая плавно подведет нас к хранению пользовательской информации в вершинах, и наконец — к бесчисленному множеству манипуляций, которые с этой информацией может потребоваться выполнять. Поехали.

Ищем индекс

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

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

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

На заметку сразу скажу, что совершенно не обязательно думать про кучу исключительно как структуру, у которой родитель больше, чем его потомки. Никто не запрещает взять противоположный вариант и считать, что родитель меньше потомков — главное, выберите что-то одно для всего дерева. Для нужд этой статьи гораздо удобнее будет использовать вариант со знаком «больше».

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

Первая статья цикла

Интро

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

Приветствую!

В своей дипломной работе я проводил обзор и сравнительный анализ алгоритмов кластеризации данных. Подумал, что уже собранный и проработанный материал может оказаться кому-то интересен и полезен.
О том, что такое кластеризация, рассказал sashaeve в статье «Кластеризация: алгоритмы k-means и c-means». Я частично повторю слова Александра, частично дополню. Также в конце этой статьи интересующиеся могут почитать материалы по ссылкам в списке литературы.

Так же я постарался привести сухой «дипломный» стиль изложения к более публицистическому.