Search
Write a publication
Pull to refresh
7
0
Алексей @boov

User

Send message

Поиск повторений в двумерном массиве, или вычислительная сложность на примере

Reading time7 min
Views9.4K
Доброго времени суток, уважаемое хабрасообщество.

Когда я учился в институте на втором или третьем курсе (то есть, в общем, не так и давно), был у меня, помимо прочих, предмет под названием «алгоритмы и структуры данных». Рассказывали там, однако, не только про сами алгоритмы и структуры, но и о таком понятии, как «вычислительная сложность». Признаюсь, тогда это меня не очень заинтересовало.

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

Однако недавно мне пришлось сильно изменить свое мнение из-за простой, казалось бы, задачи.
Читать дальше →

Code52 — новый проект каждую неделю

Reading time1 min
Views3.3K
imageЕсли вы хотите заняться open source проектом, но не знаете с чего начать, то Code52 вам поможет. В начале года несколько программистов (Andrew Tobin, Brendan Forster и Paul Jenkins) решили создать место для легкого старта в open source мире.
Раз в неделю реализуется одна новая идея. Уже сейчас в Code52 17 проектов. Преимущественно используюется .NET платформа, но создатели не собираются себя ограничивать. Например, проект sayw.at, стартовавший вчера, будет написан на NodeJS.

Подробнее о Code52

Архитектура Android-приложений. Часть III — основные части приложения

Reading time7 min
Views70K
Итак, мы уже говорили о происхождении архитектуры ОС Android и о шаблонах, реализованных в этой архитектуре. Теперь настала пора поговорить о том, из чего состоит Android-приложение.

В этой статье будут представлены основные «персонажи» архитектуры Android-приложения.
Читать дальше →

Структура Radix Tree для сжатия данных

Reading time7 min
Views16K
Этот топик повествует об использовании Radix Tree на практическом примере. Radix Tree или дерево остатков — это структура данных, формируемая по принципу хранение значений в листовом узле. Промежуточные узлы представляют собой элемент конечного значения. Это может быть бит для чисел, символ для строк или цифра для номера, как в примере ниже. Приведенный алгоритм сжатия с использованием Radix Tree используется в реальной embeded системе, для хранения параметров телефонного файрвола.
Читать дальше →

MySQLi раскладываем все по полочкам

Reading time11 min
Views214K

Для кого это статья? Первоочередной целью написания статьи было именно «разложить все по полочкам» для тех, кто уже работал с mysqli, но не вникал глубоко, а быстренько написал свои обертки и забыл про оригинальный синтаксис. Я постарался разъяснить нюансы, с которым столкнулся сам, при переносе данных из большой и очень старой БД, спроектированной человеком, не знающим про нормализации, в новую, с сильно изменившейся структурой.

Можно ли читать эту статью людям, которые все еще используют старое расширение mysql и только думающие об перехода на PDO или MySqli? Думаю даже нужно.

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

Как я получил ключ к Diablo III Beta

Reading time6 min
Views58K
В YouTube роликах ThisIsHorosho с недавних пор стали появляться ключи к Diablo III Beta. В 7-ми минутном ролике на секунду показывается ключ, кто его первый активирует, то и выигрывает. Вот так на стоп кадре выглядит ключ:


Вы подумали о том же, о чем и я?

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

Библиотека для регистрации и отлова нажатий 'горячих' комбинация клавиш

Reading time3 min
Views6.4K
Под комбинацией клавиш понимается любое количество одновременно нажатых клавиш, нажатых в любом порядке, которое может позволить ваша клавиатура. Для конечного пользователя, однако, не стоит превышать количество более пяти в одной комбинации, т.к. игровые клавиатуры есть не у всех.

Пример использования

HotKeysManager manager = new HotKeysManager();
manager.AddHotKey(new HotKeyCombination(() => { MessageBox.Show("Привет, Хабр!"); }) { Keys.LControlKey, Keys.H });

Другой вариант добавления, где в качестве комбинации берутся текущие нажатые клавиши, удобно в случае когда пользователь назначает комбинацию сам. В демке есть пример подобной записи комбинаций.
manager.AddHotKey(new HotKeyCombination(HookManager.CurrentDownedKeys.ToArray(), () => { MessageBox.Show("Привет, Хабр!"); }));


Теперь при нажатии комбинации LeftCtrl+H (или H+LeftControl), мы увидим приветственное сообщение.
Читать дальше →

GPU нужно разогнать в 2000 раз для достижения анатомического предела

Reading time3 min
Views7.1K
На конференции для игровых разработчиков DICE Тим Суини (Tim Sweeney) из компании Epic Games представил свои расчёты, какой должна быть производительность графических карт, чтобы они обеспечили максимальное качество, воспринимаемое человеческим зрением (видеозапись выступления, 30 минут, слайды).

Тим Суини занялся математикой не просто так, а потому что в последнее время стала популярной точка зрения, якобы современное поколение игровых приставок имеет уже «достаточную» производительность — и следующее поколение может стать последним. По мнению Суини, об этом не может быть и речи. Он приводит расчёты, что для обсчёта эффектов, заметных на разрешении человеческого глаза 8000х4000, производительность GPU должна вырасти в 2000 раз до примерно 5000 терафлопс.

Тим Суини, основатель компании Epic Games и автор движка Unreal, пользуется в игровой индустрии не меньшим авторитетом, чем Джон Кармак.
Читать дальше →

Архитектура Android-приложений. Часть II — архитектурные стили и шаблоны

Reading time5 min
Views43K
В этой статье мы поговорим об архитектурных шаблонах, используемых в Android-приложениях.

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

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

Фильтр Калмана — Введение

Reading time5 min
Views269K
Фильтр Калмана — это, наверное, самый популярный алгоритм фильтрации, используемый во многих областях науки и техники. Благодаря своей простоте и эффективности его можно встретить в GPS-приемниках, обработчиках показаний датчиков, при реализации систем управления и т.д.

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

Сравнение библиотек для архивации в .Net

Reading time5 min
Views16K
Недавно для моего проекта понадобилась мне библиотека для архивирования. С полгода назад по работе я пользовался библиотекой zlibnet и впечатления остались не очень приятные, так что решил поискать альтернативу. После недолгих поисков наткнулся на обзор библиотек для архивации, которая и сподвигла меня написать этот обзор.
Читать дальше →

Наследование интерфейсов и контракты

Reading time8 min
Views7.9K
В библиотеке Code Contracts, которая любезно предоставляет возможности контрактного программирования на платформе .NET, для задания предусловий и постусловий используются вызовы статических методов класса Contract. С одной стороны – это хорошо, поскольку альтернативная реализация на основе атрибутов была бы слишком ограниченной. С другой стороны – это добавляет определенные сложности, когда дело касается контрактов интерфейсов или абстрактных методов, которые, по своей природе, не содержат никакого кода, а значит и вызывать методы просто не откуда.

Решается эта с помощью двух атрибутов: ContractClassAttribute, который вешается на интерфейс или абстрактный класс, и ContractClassForAttribute – который вешается на сам контракт.
Читать дальше →

Реализация паттерна MVC для PyQt

Reading time6 min
Views37K
Всем доброго времени суток!
В статье описывается реализация паттерна проектирования MVC для приложений использующих PyQt, на примере программы сложения двух чисел. Помимо описания реализации паттерна приводится описание процесса создания приложения.

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

Сказ о wx.Python

Reading time13 min
Views25K
Здравствуй хабрхабр!

В данной статье я хотел бы рассказать, сформулировать свои мысли по поводу такой замечательной библиотеки как wxPython. Под катом вы найдете небольшую теорию, описание форм, разбор свойств форм, различных контролов и всё что касается wxPython.
Welcome to wxPython.
Читать дальше →

Python, Модули, SWIG, Windows

Reading time4 min
Views21K
Эта статья – описание моих экспериментов по сборке модулей для Python. Мне понадобился высокоуровневый интерфейс к библиотеке LibRaw, притом в первую очередь под Windows.

Последний раз модуль для питона на C++ я писал в 2004 году. Модуль к мертворожденной (к счастью не мной) библиотеке ( я тупо продавал свои умения за зарплату). Естественно, навыки не закрепились. Помню, что SWIG сильно облегчил мне работу, поскольку нужен был объектный интерфейс, а «ручками» его писать ломало. Память у меня профессиональная – то есть избирательная и короткая, поэтому пришлось прыгать сначала.

Это статья только про настройку SWIG для Python под Windows. Писать же модули на C/C++ с использованием SWIG гораздо проще, чем всё настроить (кстати, у меня такое впечатление, что это парадигма современного программирования).

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

Альтернативная проверка предусловий в Code Contracts

Reading time4 min
Views3.9K
При попытке использования библиотеки Code Contracts в реальном проекте может возникнуть небольшая сложность: хотя сам класс Contract с методами проверки предусловий и постусловий, располагается в mscorlib начиная с 4-й версии .NET Framework, но без установки самой библиотеки Code Contracts, они не попадают в результирующую сборку.

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

Однако Code Contracts поддерживает дополнительный «режим совместимости», который позволяет «жестко зашить» проверки предусловий в результирующий код, так что они будут видны всем, не зависимо от того, установлены контракты на машине разработчика или нет.
Читать дальше →

Написание компилятора LALR(1)-парсеров. Базовая теория

Reading time7 min
Views23K

Введение, или зачем нужны синтаксические анализаторы


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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

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

Шустрый 128-битный LFSR (MMX required)

Reading time4 min
Views18K
Случайные числа — темная лошадка обеспечения механизмов безопасности в цифровой среде. Незаслуженно оставаясь в тени криптографических примитивов, они в то же время являются ключевым элементом для генерации сессионных ключей, применяются в численных методах Монте-Карло, в имитационном моделировании и даже для проверки теорий формирования циклонов!

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



Вариантов реализации генератора псевдослучайных чисел достаточно много: Yarrow, использующий традиционные криптопримитивы, такие как AES-256, SHA-1, MD5; интерфейс CryptoAPI от Microsoft; экзотичные Chaos и PRAND и другие.

Но цель этой заметки иная. Здесь я хочу рассмотреть особенность практической реализации одного весьма популярного генератора псевдослучайных чисел, широко используемого к примеру в Unix среде в псевдоустройстве /dev/random, а также в электронике и при создании потоковых шифров. Речь пойдёт об LFSR (Linear Feedback Shift Register).

Дело в том, что есть мнение, будто в случае использования плотных многочленов, состояния регистра LFSR очень медленно просчитываются. Но как мне видится, зачастую проблема не в самом алгоритме (хотя и он конечно не идеал), а в его реализации.
Читать дальше →

Что же всё-таки не так со структурой DateTime?

Reading time11 min
Views14K
Замечания:
1. В предыдущей заметке "time zone" я перевёл как «временнАя зона», поскольку речь шла о часовых поясах США, имеющих специфическое название. В данном случае корректнее использовать "часовой пояс". Здесь используется более корректный перевод.

2. Небольшая врезка из Википедии даст вам понимание что такое UTC и чем оно отличается от GMT —

Всеми́рное координи́рованное вре́мя (UTC) — стандарт, по которому общество регулирует часы и время. Отличается на целое количество секунд от атомного времени и на дробное количество секунд от всемирного времени UT1.

UTC было введено вместо устаревшего среднего времени по Гринвичу (GMT). Новая шкала времени UTC была введена, поскольку шкала GMT является неравномерной шкалой и связана с суточным вращением Земли. Шкала UTC основана на равномерной шкале атомного времени (TAI) и является более удобной для гражданского использования.

Часовые пояса вокруг земного шара выражаются как положительное и отрицательное смещение от UTC.

Следует помнить, что время по UTC не переводится ни зимой, ни летом. Поэтому для тех мест, где есть переход на летнее время, меняется смещение относительно UTC.


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

Через некоторое время после публикации твита о Noda Time, меня начали спрашивать, какой смысл в использовании Noda Time — люди верили, что поддержка дат и времени в .NET вполне хороша. Я конечно не видел их код, но подозреваю, что практически любая кодовая база, имеющая дело с датами, станет яснее, если будет использовать Noda Time, а также, вполне возможно, станет более корректной благодаря подходу, с помощью которого Noda Time заставляет вас принимать некоторые, не очевидные в .NET, решения. В этой заметке мы обсудим недостатки .NET API, обеспечивающего работу с датами и временем. Моё отношение к этой теме выглядит несколько предвзятым, но я надеюсь, что эта заметка не выглядит неуважительно по отношению к команде, работающей над BCL (Base Class Library — прим. переводчика) — поскольку, кроме всего прочего, они работают в условиях, заставляющих их принимать во внимание взаимодействие с COM и т.п.
Читать дальше →

.Net Локализованные сообщения «относительного времени»

Reading time4 min
Views1.3K
Всем привет,

На текущем проекте, от заказчика пришли требования, о том, что информация о прошедших событиях, должна показываться клиенту в виде «относительно времени» (Сообщение вида: «Событие произошло N минуту\минут\минуты назад»). Нам пришли шаблоны сообщений для разных вариантов, а также требования к внешнему виду, одним из которых было то, что сообщения должны быть локализованы.

«Что здесь сложного?», — подумали мы и отправились в гугл, на поиски готового решения. К сожалению, гугл изображал из себя партизана, предлагал несколько вариантов готовых решений для построения такого типа сообщений для английского языка, но ни одно из них не поддерживало локализации.

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

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Registered
Activity