Распараллеливание кода без зависимостей

Введение

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

Была у меня давнишняя идея, как расширить возможности интерфейса файловых менеджеров, улучшив визуализацию разных дисков, разных типов дисков и определенных папок. И вот теперь ее удалось реализовать.

Скриншот для затравки:

Представляю сообществу простой, но полезный инструмент для управления полномочиями доступа к коду .Net сборок – Managed Sandbox. На утилиту советую обратить внимание НЕ только разработчикам, но и всем кто периодически использует .Net программы из не доверенных источников (с небольшими оговорками, но об этом ниже).



Статья состоит из 2-х частей: (1) немного философии о системе безопасности .Net-платформы, (2) описание утилиты Managed Sandbox и причин, почему нужно было ее создавать.

Динамические вызовы: что это и зачем?

Думаю, для каждого разработчика, работающим на статических языках программирования, иногда возникала необходимость прибегнуть к динамическим вызовам — вызвать метод чего-то, о чем пока еще ничего не известно. Или получить какое-то свойство у какого-то объекта, о котором будет известно только в run-time.

Это иногда используется в алгоритмах, основанных на так называемой «утиной типизации» (duck typing):

Если что-то выглядит как утка, плавает как утка и крякает как утка, то это, вероятно, утка и есть.

В данной статье я хотел бы рассмотреть основные доступные в Microsoft .NET 4.0 способы, сравнить их производительность и синтаксис.

От всей души рекомендую видео лекцию А. Степанова (человека создавшего STL): «о истории алгоритма нахождения наибольшего общего делителя», это популярная лекция оказалась бесконечно интересной, в ней рассказывается, на примере этого алгоритма о развитие алгоритмического знания всего человечества с эпистемологической точки зрения в разрезе истории с античных времен с Пифагора до наших дней до Кнута.


Посмотреть можно здесь:
часть1
video.yandex.ru/users/ya-events/view/129
часть2
video.yandex.ru/users/ya-events/view/128

Здесь приведен ряд очень простых правил, следуя которым, ваше сотрудничество с jQuery не будет омрачено скрежетом напрягшегося браузера. Конечно, не так часто случается, что скорость работы javascript’а оказывается критичной, однако такое все же может произойти, и произойти в самый неподходящий момент. Поэтому, лучше держать эти правила в голове и не пренебрегать ими.

В наше время среди СУБД самую большую распространенность получили реляционные базы данных, в которых основными объектами являются таблицы и отношения между ними. Таблицы — это очень хорошо, они позволяют решить большинство задач по хранению данных и манипуляции с ними. Но в реальном мире сущности требующие хранения не всегда представлены в табличном виде. Одним из таких очень распространенных видов структуры данных отличных от таблицы является древовидная структура, когда каждый элемент данных имеет предка и потомков. Примером такой структуры может быть структура штата предприятия, в котором во главе стоит директор (корень дерева), его заместители, отделы с начальниками, которые подчиняются определенным заместителям, сотрудники отделов, которые подчиняются начальникам.

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

Однако, разработчики СУБД MS SQL предлагают в своей новой версии MS SQL 2008 для реализации древовидной иерархии новый тип хранения данных hierarchyid.

Очередная порция экспериментов на HTML5. Автор просит не использовать их в спорах HTML5vsFlash :)

.Net используются при программировании настольных и веб-приложений, а возможно ли использовать фреймворк для управления промышленными объектами?
Разберемся в начале с тем, где возможно применение такого ПО.
Промышленные системы управления состоят из нескольких уровней:

• уровень датчиков
• уровень управления (ПЛК, компьютер)
• уровень визуализации/SCADA

Визуализация – самый неприхотливый уровень АСУ по скорости обработки информации, обычно на операторских панелях отображается информация о состоянии какого-либо агрегата всей системы (некоторые численные значения, биты состояния (вкл-выкл), графики изменения величин). Для этого уровня можно свободно использовать все возможности .NET для вывода графической информации (Win Forms, WPF, SilverLight).
Рассмотрим уровень управления. Здесь нужная скорость обработки информации зависит от объекта управления: если вы хотите просто помигать светодиодом или включить/выключить двигатель без жесткой привязки по времени, то это возможно. Если же необходимо управлять объектами с жестко-определенным временем реакции, то необходимо использовать систему реального времени.
Для систем реального времени необходима ОС реального времени. В таких ОС жёстко определено время переключения контекста задач, т.е. квант времени на обработку каждого потока с одинаковым приоритетом выделяется одинаковый.
А что может получиться при использовании «десктопной» ОС?

Приложение не отвечает?!

Многие из тех, кто программирует WPF-приложения, наверное тысячи раз писали конструкцию вида:

{Binding Items}

Если получение элементов коллекции Items выполняется в основном потоке приложения и занимает некоторое время — мы получаем «мертвый» пользовательский интерфейс. Приложение некоторое время не будет отрисовывать изменения состояния и реагировать на пользовательский ввод.

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

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

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

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

Введение

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

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

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

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

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

Любой разработчик, имеющий дело с генерацией отчётности из баз данных, регулярно сталкивается с построением громоздких запросов. Часто это бывает связано с ошибками проектирования БД, и, ещё чаще, со сложностями преобразования извлекаемых данных. К последним можно отнести применение итерационных методов вычисления, подсчёт промежуточных итогов по подгруппам, расчёты, в которых используются значения соседних строк выборки, сложное форматирование строк и подобные задачи. Такие преобразования часто выносятся с уровня БД на уровень сервера приложений или клиента, что сказывается на производительности и удобстве сопровождения кода. Для решения этих задач SQL СУБД Oracle предоставляет аналитические функции и оператор MODEL — о нём и пойдёт речь в этой статье.

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

Vinay Deolalikar разослал некоторым ученым свое доказательство, что класс сложности P ≠ NP.

Само доказательство на ~100 страницах.

Можно почитать более или менее адекватный комментарий на ycombinator.

Добавить нечего, читаем и/или ждем мнений специалистов в этой области.

P.S. На всякий случай, ссылка о том, что такое NP и P. (спасибо, SMiX)

Команда разработчиков ASP.NET готова представить новый набор инструментов с открытым исходным кодом под названием Sprite and Image Optimization Framework.

Sprite and Image Optimization Framework – это фреймворк, который содержит набор инструментов клиентской оптимизации для веб-сайтов, позволяющий сократить время доступа к страницам для пользователей. Для этого фреймворк предлагает использовать механизмы оптимизации загрузки изображений: посредством спрайтов и кодирования на основе data:uri.

Разработчикам ASP.NET предлагается использовать элемент управления для WebForms-проектов и специальный вспомогательный класс для ASP.NET MVC-проектов. Вместе с ними поставляется HTTP Module, который выполняет всю работу по оптимизации изображений и передачи их клиенту.

Загрузить Sprite and Image Optimization Framework можно по этой ссылке с сайта codeplex.com. Там можно найти исходные коды фреймворка, демонстрационные проекты, документацию.

Фонд венчурных инвестиций Softline Venture Partners объявил наш проект Hivext Platform победителем конкурса Dev Generation 2010. Чему мы очень рады.

Причин для нашей радости несколько:

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

Прелюдия

Доброго времени суток, уважаемые читатели.
Скорее всего, большинству из вас известно, что из себя представляет асимметричный алгоритм шифрования RSA. В самом деле, этому вопросу по всему рунету и на этом ресурсе в частности посвящено столько статей, что сказать о нем что то новое практически невозможно.
Ну что там, ей богу, можно еще придумать и так все давным-давно понятно. Рецепт приготовления прост:
Два простых числа P и Q.
Перемножить до получения числа N.
Выбрать произвольное E.
Найти D=E^-1(mod(P-1)(Q-1)).
Для шифрования сообщение M возводим в степень E по модулю N. Для дешифрования криптотекст C в степень D по все тому же модулю N. Все криптопримитив готов. Берем и пользуемся, так? На самом деле, не так. Дело все в том, что это и в самом деле не более чем криптопримитив и в реальном мире все самую чуточку сложнее.

Вот уже более 30 лет протокол распределения ключей Диффи-Хеллмана радует глаз простого криптомана своей простотой и надежностью. Для тех, кто эти последние 30 лет провел за занятиями более веселыми, нежели изучение криптографических протоколов, поясняю.
Протокол Диффи-Хеллмана был опубликован в 1976 году и послужил началом эры асимметричной криптографии. Суть его до гениального проста: Алиса и Боб хотят получить общий ключ для симметричной криптосистемы. Для этого они, договорившись, выбирают два больших числа g и p. Эти числа известны им обоим и держать их в секрете не имеет никакого смысла. Затем Алиса в тайне генерирует большое секретное число a, а Боб — большое число b. А далее за дело берется простая арифметика. Алиса посылает Бобу число
.
Боб в свою очередь высылает Алисе
.

Вот уже более 10 лет существуют объектно-реляционные СУБД, постоянно усложняется структура хранимой информации, стандарт SQL учитывает вопросы сопряжения с объектно-ориентированными языками программирования, но, тем не менее, функционал обеспечивающий поддержку объектной парадигмы крайне редко используются в БД. Отчасти, это объясняется консерватизмом разработчиков, отсутствием развитых методологий проектирования объектно-реляционных БД и широким распространением ORM-средств. Тем не менее, существует ряд задач, где использование объектных возможностей самих БД может повысить производительность и гибкость системы.