Некоторое время назад я решил посвятить себя решению экзотической задачи — нарисовать волну wave-файла, как это делают аудио- и видеоредакторы, используя для этого Питон. В результате у меня получился небольшой скрипт, который вполне с этим справляется. Так, картинка выше сгенерирована им из песни «Under Pressure» группы Queen. Для сравнения — вид волны в аудиоредакторе:

Для разбора звука я использовал библиотеку numpy, а для построения графика — matplotlib. Под катом я изложу основы работы с wav-файлами и алгоритм скрипта.

Здравствуй, Хабрахабр. Сейчас я хочу рассказать о такой структуре данных как дерево Фенвика. Впервые описанной Питером Фенвиком в 1994 году. Данная структура похожа на дерево отрезков, но проще в реализации.

Что это?

Дерево Фенвика — это структура данных, дерево на массиве, которая обладает следующими свойствами:
• позволяет вычислять значение некоторой обратимой операции F на любом отрезке [L; R] за логарифмическое время;
• позволяет изменять значение любого элемента за O(log N);
• требует памяти O(N);

Думаю, многие знакомы с весьма необычной игрой Minecraft (справа — пример сгенерированной в ней карты), в которой игрок находится на (практически) бесконечной поверхности Земли и может исследовать окружающий мир с минимальными ограничениями.

Как же автору игры, Notch'у, удалось добиться подобного сходства его случайных «миров» с земными просторами? В этом топике я как раз и рассмотрю один из способов построить искусственный ландшафт такого рода (и вскользь упомяну пару других способов), а также расскажу о моем небольшом усовершенствовании этого алгоритма, позволяющем значительно увеличивать размеры ландшафта без заметных потерь в производительности.

Внутри вас ждет несколько схем и красивых картинок, довольно много букв и ссылка на пример реализации алгоритма.

Приветствую, хабровчане!

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

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

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

Добрый день. Хотелось бы поделиться с Вами очень интересным вариантом ненормального прграммирования — составлением нормальных алгоритмов Маркова. Этот вариант программирования может служить великолепным умственным отдыхом от привычных языков и сред программирования.
Студенты, которых я имею возможность учить, кричат криком, что это сложно, но только до первого собственными руками сделанного рабочего алгоритма, потом это перетекает в очень интересные алгоритмические задачки.
Собственно, к теме этого поста: наша задача написать нормальный алгоритм Маркова для деления двух целых чисел с точностью 4 знака после запятой(для задания чисел пользуемся унарной системой исчисления). Например, вход: |/||||, выход: 0.25.
При этом у нас есть только одна операция — замена одной подстроки в исходной строке на другую. Кому интересно что это такое и как это работает — добро пожаловать под кат.

Предположим, что у нас есть 100 млн. долларов, которые нужно вложить в несколько возможных инвестиций. Каждое из этих вложений имеет различную стоимость и различный ожидаемый доход. Мы должны решить, как потратить деньги, чтобы получить максимальную прибыль.
Задачи такого типа называются задачами формирования портфеля. У нас есть несколько позиций (инвестиций), которые должны поместиться в портфель фиксированного размера (100 млн. долларов). Каждая позиция имеет свою прибыльность. Необходимо найти набор позиций, которые помещаются в портфель и дают максимальную прибыль.
Многие из вас скажут, что никакие эвристики тут не нужны, и что вполне можно обойтись полным перебором. Другие заявят, что и полный перебор не нужен, ведь существует метод ветвей и границ. Но как быть, если количество возможных инвестиций 65? Полное дерево решений содержит более 7*10^19 узлов. Предположим, что метод ветвей и границ перебирает десятую часть процента этих узлов, а компьютер проверяет миллион узлов в секунду. В этих условиях для решения задачи потребовалось бы более 2 млн. лет. Именно для таких сложных задач и используются эвристики. Если вам интересно, милости прошу под кат.

Мне очень понравился топик про распределение нагрузки от прерываний сетевого адаптера по процессорам, поэтому я решил описать как это делается в Windows.

Disclaimer: судя по некоторым комментариям в предыдущих постах, мне стоит повторить то, с чего я начал первый пост: я не даю (и не могу давать) общеприменимых рецептов. Особенно это касается производительности, где мельчайшая неучтенная деталь может катастрофически повлиять на результат. Вернее рекомендацию то я даю: ТЕСТИРОВАНИЕ И АНАЛИЗ. Смысл моей писанины в том, чтобы дать людям как можно больше информации для анализа, ведь, чем больше понимаешь в том, как что либо работает, тем легче находить пути устранения боттлнеков.

Итак, масштабируемость пропускной способности сети. Потребуется Windows Server 2003 SP2+. Сетевая карта, поддерживающая Receive Side Scaling (можно с достаточной долей уверенности сказать, что подойдет любая серверная сетевая карта, выпущенная в последние 5 лет или любая вообще 1Gb+ NIC, хотя частенько можно увидеть RSS и на 100Mb). Устанавливаем Windows Server и драйвера на карту…

Сегодня мы публикуем выдержки из отчета Econsultancy, посвященного оптимизации конверсии. Это исследование основано на опросе 700 американских компаний и digital агентств, проведенном в августе и сентябре 2010 года. Под катом немного интересной статистики по конкретным инструментам, которые используются для повышения конверсии сайтов. Эти знания вряд ли помогут повысить конверсию вашего проекта прямо сейчас, но вполне могут развеять сомнения – каким методом воспользоваться (а это важно, особенно если бюджет не такой большой, чтобы попробовать всё).

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



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

В продолжение статьи Евгения Ческидова «Яндекс. Директ. Анализируем конкурентное окружение» я хочу показать, как при помощи не очень сложных расчетов и API Яндекса вытащить из Директа буквально всю информацию о рекламных кампаниях конкурентов. Сразу скажу, что идея на практике еще не проверялась, сам факт наличия всей информации и, соответственно, возможности этого расчета был показан Ческидовым только вчера, а алгоритм родился буквально сейчас. Но математически вроде бы всё сходится. Осторожно, под катом много формул.

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

В ходе обсуждения анонса арендуемых серверов на базе атомов по 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, в одно новое.

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