Search
Write a publication
Pull to refresh
120
0.2
Send message

Методы, как first class citizens в C++

Reading time5 min
Views4.5K
На днях, гуляя по багтрекеру gcc наткнулся на интересный баг, в нем используется сразу несколько возможностей C++11:


Анализируя этот баг, я подумал, что теперь можно удобно реализовать методы как first class citizens
Читать дальше →

Немного о красоте T-фракталов

Reading time2 min
Views9.3K

В 1977 году Бенуа Мандельброт написал книгу «Фрактальная геометрия природы». В ней он подробно описал, как, руководствуясь простыми правилами, нарисовать сложный и красивый самоподобный узор. И до Мандельброта, и после, и по сей день фрактальные узоры привлекают к себе внимание математиков, программистов, художников и прочих любителей красоты.

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

Посмотреть на фракталы

Рандомизированные деревья поиска

Reading time8 min
Views58K

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.
Читать дальше →

Структуры данных: бинарные деревья. Часть 1

Reading time6 min
Views382K

Интро



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

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

Декартово дерево: Часть 1. Описание, операции, применения

Reading time15 min
Views158K

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


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

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

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

Введение


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

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


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

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

WebGl-2d.js: Реализация Canvas 2D API на WebGL

Reading time2 min
Views12K
WebGL-2d — весьма интересная javascript библиотека, реализующая стандартные методы для работы с 2d контекстом Canvas на WebGL контексте.

Ни для кого не секрет, что сегодня Canvas не может похвастаться хорошей производительностью и отрисовка сложных сцен в реальном времени может стать проблемой. С WebGL ситуация с производительностью существенно лучше, но этот стандарт поддерживают не все популярные браузеры, в частности Microsoft даже не планирует внедрять его поддержку в IE (сторонние разработчики по этой причине уже начали делать плагин).

Подключив WebGL-2d и добавив всего пару строчек, мы можем существенно ускорить отрисовку графики, реализованную с средствами Canvas 2d API в браузерах, поддерживающих WebGL и обеспечить fallback к обычному 2d контексту.

Читать дальше →

Построение минимальных выпуклых оболочек

Reading time7 min
Views143K

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

Полезные мелочи в работе веб-разработчика или «Как я мог без этого жить»

Reading time4 min
Views8.5K
Злой троянец увел у меня аккаунт на хабр, после чего под моим аккаунтом начали публиковаться какие-то тупые мультики. К сожалению узнал я об этом только когда НЛО перевело меня в read-only, а рейтинг ушел в отрицательное значение. Не беда: повод наконец написать пост, который давно собирался.

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

Yet another cool story about bash prompt

Reading time10 min
Views38K
Я программист. По крайней мере так написано в трудовой книжке. Почти всё своё рабочее время я провожу в консоли и текстовом редакторе. Мне очень нравится bash. Почти год я жил в zsh, прислушавшись к советам своих многочисленных коллег и знакомых, но в итоге я вернулся в bash и ни капельки об этом не жалею.



Zsh красив, приятен, чертовски функционален, но, признаюсь честно, я не смог совладать со всеми его многочисленными настройками. Я хочу работать, а не бороться со своим рабочим окружением. Простой пример: пару раз из-за автодополнения zsh я удалял все директории и файлы в текущей директории — zsh просто ставил пробел между автодополненной директорией и введённой мною звёзочкой (я хотел удалить всё в выбранной папке). Помните тот эпичный баг с пробелом и удалении директории /usr? У меня было то же самое. Спасибо гиту, выручил в который раз.

Впрочем, дело не в zsh — будь я чуточку умнее, я бы с ним обязательно справился бы, и всё было бы хорошо, но мы, суровые программисты, будем использовать bash и vim, а гламурные zsh и textmate оставим хипстерам и прочим модникам ;)

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

Нейросети для чайников. Часть 2 — Перцептрон

Reading time5 min
Views260K
image

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

Язык программирования, на этот раз — C#.
Заинтересовавшихся прошу под кат.
Читать дальше →

Моноиды и их приложения: моноидальные вычисления в деревьях

Reading time20 min
Views24K
Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.

Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция


Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = ab — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John""Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(ab) ⊗ c = a ⊗ (bc)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
ae = ea = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если ae, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Читать дальше →

Ropes — быстрые строки

Reading time5 min
Views26K
Здравствуй, Хабр.
Большинство из нас так или иначе работает со строками. Этого не избежать — если ты пишешь код, ты обречен каждый день складывать строки, разбивать их на составные части и обращаться к отдельным символам по индексу. Мы давно привыкли что строки — это массивы символов фиксированной длины, а это влечет за собой соответствующие ограничения в работе с ними.
Так, мы не можем быстро объединить две строки — для этого нам потребуется сначала выделить необходимое количество памяти, а потом скопировать туда данные из конкатенируемых строк. Очевидно, что такая операция имеет сложность порядка О(n), где n — суммарная длина строк.
Именно поэтому код

string s = "";
for (int i = 0; i < 100000; i++) s += "a";

работает так медленно.

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

Хватит это терпеть!

Единственный способ

Reading time4 min
Views71K
Ральф вошел в помещение ангара №1 в 8:30 утра, как делал это ежедневно уже несколько лет. Его взгляд сразу же устремился к центру зала, где на постаменте, окруженный множеством приборов и паутиной кабелей, находился смысл его работы. Собственно говоря, не только его — миллионов людей по всему миру. Первый инопланетный корабль. Полтора десятилетия назад он совершил аварийную посадку и был частично поврежден, оставив, однако, весьма много материала для изучения. Настоящим чудом стало то, что политики и учёные после этого события не переругались, а смогли организовать эффективное изучение свалившегося с небес подарка. На реверс-инжиниринг корабля были брошены лучшие умы планеты. Ральф, возглавляющий группу изучения приборов связи, стоял в ангаре и в который раз любовался стремительной, похожей на стрелу в полёте, формой корабля. Он вспоминал всё, что случилось за последние годы.
Читать дальше →

Qt/Objective-C++11 или сборка Qt-проекта с помощью GCC-4.7 и Clang

Reading time6 min
Views12K
Всем доброго хабрадня!

Сегодня я расскажу уважаемым хабражителям об очередном извращении — о сборке проекта, написанного на Qt, под Mac OS X компилятором GCC-4.7.0 с примесью Clang'а (про шланг — в конце статьи, там станет понятно, зачем ещё и его приплетать будем).

Для чего нам GCC 4.7? Ну, например, чтобы использовать все те крутые фичи из стандарта C++11. Разве этого мало? Кроме поддержки нового стандарта, в нём очень много улучшений по сравнению с идущим в комплекте с Xcode GCC 4.2 (хотя он и оказывается на поверку i686-apple-darwin11-llvm-g++-4.2), так что смысл в переходе на 4.7 явно имеется. Но и проблемы присутствуют, о чём ниже.

Мы можем предположить, что нам потребуются некие фичи из Cocoa, а значит, нам потребуется компилятор Objcetive-C, а ещё лучше — Objective-C++, чтобы, например, интегрировать наше Qt-приложение в окружение Mac OS X.
Начнем!

Django своими руками часть 1: Собираем шаблоны для jinja2

Reading time3 min
Views15K

Введение


В этом посте хотелось бы описать создание небольшого фреймворка с системой плагинов как django. Только с использованием внешних компонентов. Jinja2 для шаблонов, bottle для получения переменых среды, вместо ORM будет использоваться pymongo, а сессиями будет заниматься beaker.
В первой части хочу рассказать как удобно подсоединить Jinja2 чтоб шаблоны можно было собирать из разных папок (читай плагинов) и кешировать их.
Также в следующей части хотелось бы рассказать как подключить к шаблонам gettext и автоматизировать их перевод.

Читать дальше →

QScintilla: подсвечиваем синтаксис в приложении

Reading time3 min
Views12K
Привет, $username!

UPD: вторая и третья часть цикла о QScintilla.

Сегодня я хочу рассказать вам про отличный проект — QScintilla, который подсвечивает синтаксис кода в Qt-приложениях. Нередко возникает необходимось что-то подсвечивать. Например: C++, Bash, PHP, Diff… Этот список можно продолжать и продолжать. Но вот решение: порт Scintilla на Qt: QScintilla.

В этом посте я расскажу как установить и пользоваться QScintilla в своих приложениях на примере Ubuntu Linux.
Читать дальше →

Неврология в видеоиграх: Deus Ex: Human Revolution

Reading time5 min
Views8K
Существует любознательная штуковина, занимающая пространство между нашими ушами. Это пространство с несколькими фунтами серого вещества обеспечивает невероятную степень пластичности, учитывает полный спектр личностей, эмоций и мыслей, но все это в ограниченном физическом пространстве. При изучении неврологии, трудно пройти мимо красоты и эффективности человеческого мозга. Но каковы пределы биологического субстрата, как мозг, и как мы можем расширить свои возможности с его помощью?

Отчаянные поиски улучшения нашей естественной биологии, по иронии судьбы, являются неизбежным результатом той же собственной биологии. Кроме того, идея, что миллиарды лет эволюции заключаются в механизме, может вызвать замешательство тех из нас, кто привык к идее постоянного технологического совершенствования и развития, например как наша нынешняя модель мироздания эволюционировала, чтобы справиться с устоем Древнего мира. Существует актуальный вопрос: «Где (и что это) Человеческий мозг 2.0?» Этот вопрос раскрывается в некоторых потенциально пророческих фантастических играх, таких как Deus Ex: Human Revolution, в которых неврология встречается с синтетическими улучшениями в увлекательной и ужасающей форме.

image

Читать дальше →

Вещи, о которых следует помнить, программируя на Python

Reading time5 min
Views64K

Дзэн Питона



Изучение культуры, которая окружает язык, приближает вас на шаг к лучшим программистам. Если вы всё еще не прочли «Zen of Python», то откройте интерпретатор Python и введите import this. Для каждого элемента в списке вы найдете пример здесь

Однажды моё внимание привлекло:
Читать дальше →

Logging — библиотека для удобного ведения логов в Python

Reading time2 min
Views108K
В любой разработке приходится рано или поздно вести логи, ведь не отдашь же заказчику программу где отладочные сообщения выводятся с помощью print, да и в дальнейшем если у заказчика что то пойдет не так то можно просто попросит показать лог и понять в чем проблема(в большинстве случаев), так вот в питоне есть очень мощная и удобная библиотека и дальше я попробую про нее рассказать.
Читать дальше →

CanvGauge — измерительный прибор с помощью canvas для HTML5

Reading time1 min
Views7.5K
HTML5 Canvas GaugeДобрый день, хабровчане!

Сегодня я хочу поделиться своей небольшой разработкой, которую я делал для одного из своих проектов. На самом деле, в сети множество реализаций gauge, как платных, так и бесплатных. Но найти хоть одно решение с использованием именно canvas мне не удалось, поэтому было принято решение написать свое.
Читать дальше →

Information

Rating
4,168-th
Location
Магнитогорск, Челябинская обл., Россия
Registered
Activity