Search
Write a publication
Pull to refresh
2
0

User

Send message

Обучение онлайн

Reading time1 min
Views35K
Для изучающих Ruby / Rails, будет полезно ознакомиться с подборкой бесплатных онлайн курсов, туториалов и интерактивных занятий, посвященных языку программирования Ruby и фреймворку Ruby on Rails.

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

Асинхронность: назад в будущее

Reading time22 min
Views114K

Асинхронность… Услышав это слово, у программистов начинают блестеть глаза, дыхание становится поверхностным, руки начинают трястись, голос — заикаться, мозг начинает рисовать многочисленные уровни абстракции… У менеджеров округляются глаза, звуки становятся нечленораздельными, руки сжимаются в кулаки, а голос переходит на обертона… Единственное, что их объединяет — это учащенный пульс. Только причины этого различны: программисты рвутся в бой, а менеджеры пытаются заглянуть в хрустальный шар и осознать риски, начинают судорожно придумывать причины увеличения сроков в разы… И уже потом, когда большая часть кода написана, программисты начинают осознавать и познавать всю горечь асинхронности, проводя бесконечные ночи в дебаггере, отчаянно пытаясь понять, что же все-таки происходит…

Именно такую картину рисует мое воспаленное воображение при слове “асинхронность”. Конечно, все это слишком эмоционально и не всегда правда. Ведь так?.. Возможны варианты. Некоторые скажут, что “при правильном подходе все будет работать хорошо”. Однако это можно сказать всегда и везде при всяком удобном и не удобном случае. Но лучше от этого не становится, баги не исправляются, а бессонница не проходит.

Так что же такое асинхронность? Почему она так привлекательна? А главное: что с ней не так?
Назад в будущее...

Графы для самых маленьких: Ford & Bellman или как понять, что ты попал в бесконечно далекое прошлое

Reading time3 min
Views60K
В предыдущих частях цикла мы рассмотрели алгоритмы DFS и BFS, позволяющие найти путь в графе и обладающие рядом других интересных свойств. Но в жизни очень часто оказывается, что гораздо проще выглядит модель задачи в виде графа с неодинаковыми длинами ребер. Поиском кратчайшего пути во взвешенном графе мы и займемся под катом.
Читать дальше →

Tower Defense своими руками

Reading time7 min
Views105K
Доброго времени суток!

Я бы хотел рассказать Вам о своих личных ощущениях о игрострое после года работы над собственным проектом.

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

Еще раз напомнюсь, эта статья — лишь ощущения от знакомства с игростроем, и рассказ о своем небольшом опыте.

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

Коды Грея и задачи перебора

Reading time5 min
Views82K
В данной статье будет показан математический подход к составлению алгоритмов на примере следующих вопросов и задач:
  • Двоичные коды Грея. Их существование. Перебор подмножеств данного множества в порядке минимального изменения.
  • Существование и реализация перебора подмножеств из k элементов в порядке минимального изменения.

Итак, приступим.
Читать дальше →

Lock-free структуры данных. Основы: Модель памяти

Reading time18 min
Views103K

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.
Читать дальше →

Алгоритм поиска путей в лабиринте

Reading time5 min
Views129K
Доброго времени суток, уважаемое сообщество.

Предыстория



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

Вот собственно и он:




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

Кого заинтересовал, прошу под кат

Fortuna: генератор случайных чисел для параноиков

Reading time5 min
Views46K

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

Если у вас такого устройства нет, то прошу под кат.
Читать дальше →

QtCreator: Qt кросс-компиляция из linux 64 в linux 32, win32, win64 и Mac OS X; upx, usb, dmg, etc

Reading time14 min
Views83K


Библиотека Qt позволяет делать действительно кроссплатформенные приложения. Единожды написанный код можно откомпилировать под многие операционные системы. Но проблема именно в слове «компилировать», т.к. подразумевается, что необходимо перезагрузиться под целевую систему, иметь в ней настроенную среду разработки, установленный и настроенный зоопарк библиотек. Спасает кросс-компиляция — компиляция, производящая исполняемый код для платформы, отличной от той, на которой исполняется.
Читать дальше →

Введение в анализ сложности алгоритмов (часть 3)

Reading time6 min
Views128K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2

Логарифмы


image
Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.
Читать дальше →

Введение в анализ сложности алгоритмов (часть 4)

Reading time5 min
Views101K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка


Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n2 ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

В поисках криптостойкого ГПСЧ

Reading time6 min
Views38K

Привет, %username%!

В сегодняшнем посте речь пойдет о криптостойкости генераторов псевдослучайных чисел (ГПСЧ).
Для начала определимся, что же такое криптостойкий ГПСЧ (КСГПСЧ).
КСГПСЧ должен удовлетворять «тесту на следующий бит». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 битов с вероятностью более 50 %.
Wikipedia

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

Lock-free структуры данных. Основы: Атомарность и атомарные примитивы

Reading time15 min
Views112K

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.
Читать дальше →

Tips & tricks for MySQL Developers. Работа с SQL

Reading time10 min
Views51K

Эта статья задумана мной как сборник некоторых интересных моментов по использованию и оптимизации SQL запросов в БД MySQL, на мой взгляд, плохо освещенных в интернете. Так, из статьи вы узнаете о конструкции with rollup, и о том, как переписать подзапросы in и not in на join'ы, а так же обновление и удаление данных в нескольких таблицах — одним запросом, и многое другое. Начнем по порядку.
Читать дальше →

Значимые мелочи

Reading time7 min
Views20K
Знаки препинания — неотъемлемая часть любого языка. Обычная запятая может кардинально изменить значение предложения: достаточно вспомнить историю с «Казнить нельзя помиловать». А работа переводчиков и редакторов предполагает, что они свободно ориентируются как минимум в двух пунктуационных системах.

Идея этого поста родилась, когда мы обсуждали перевод статьи. В исходном материале знак процента отделялся пробелом от числа, и это бросилось в глаза — в русском тексте в таком случае пробел не используется (хотя, всё же утверждение спорное — специалисты так и не пришли к единому мнению по этому вопросу). Тогда мы решили, что об этом нужно рассказать. Специалисты отдела многоязычной локализации опросили наших зарубежных коллег и подготовили материал, которым теперь делимся с вами. Надеемся, он окажется полезным.
Читать дальше →

Lock-free структуры данных. 1 — Начало

Reading time12 min
Views153K

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

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

Алгоритм сортировки Timsort

Reading time6 min
Views162K
Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.
Читать дальше →

Реактивный манифест

Reading time12 min
Views57K
В последние годы требования к приложениям значительно изменились. Десятки серверов, время отклика в несколько секунд, оффлайновое обслуживание, которое могло длиться часами, гигабайты данных — такими были большие приложения буквально несколько лет назад. Сегодня же приложения работают абсолютно на всём, начиная с простых мобильников и заканчивая кластерами из тысячи процессоров. Пользователи ожидают миллисекундного времени отклика и стопроцентного аптайма, в то время как данные выросли до петабайтов.

Первоначально эту нишу занимали крупные инновационные интернет-компании типа Google или Twitter, однако такие требования к приложениям начали всплывать во многих областях индустрии. Финансовые и телекоммуникационные компании первыми начали внедрять новые практики, чтобы удовлетворить новым требованиям, а теперь подтягиваются и остальные.

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

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

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

Erlang для самых маленьких. Глава 1: Типы данных, переменные, списки и кортежи

Reading time8 min
Views67K

Добрый день, дорогие хабражители.

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


Если интересно - давайте начнем...

Руководство по проектированию реляционных баз данных (7-9 часть из 15) [перевод]

Reading time6 min
Views545K
Продолжение.
Предыдущие части: 1-3, 4-6

7. Связь один-ко-многим.


Я уже показал вам как данные из разных таблиц могут быть связаны при помощи связи по внешнему ключу. Вы видели как заказы связываются с клиентами путем помещения customer_id в качестве внешнего ключа в таблице заказов.

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

(Технически лучше говорить о женщине и ее детях вместо матери и ее детях потому, что, в контексте связи один-ко-многим, мать может иметь 0, 1 или множество потомков, но мать с 0 детей не может считаться матерью. Но давайте закроем на это глаза, хорошо?)

Когда одна запись в таблице А может быть связана с 0, 1 или множеством записей в таблице B, вы имеете дело со связью один-ко-многим. В реляционной модели данных связь один-ко-многим использует две таблицы.

image
Схематическое представление связи один-ко-многим. Запись в таблице А имеет 0, 1 или множество ассоциированных ей записей в таблице B.
Читать дальше →

Information

Rating
5,201-st
Location
Россия
Registered
Activity