Введение

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

В первую очередь, это связано с тем, что реляционные базы не приспособлены к хранению иерархических структур (как, например, XML-файлы), структура реляционных таблиц представляет из себя простые списки. Иерархические же данные имеют связь «родитель-наследники», которая не реализована в реляционной структуре.

Тем не менее, задача «хранить деревья в базе данных» рано или поздно возникает перед любым разработчиком.

Ниже мы подробно рассмотрим, какие существуют подходы в организации хранения деревьев в реляционных БД, а также рассмотрим инструментарий, который нам предоставляет ORM Doctrine для работы с такими структурами.

Столкнулся с проблемой реализации древовидных комментариев на одном проекте, в этой заметке выкладываю своё решение.

Описание задачи

• Хранение иерархических данных (древовидных комментариев) в реляционной БД MySQL
• Простое добавление узлов/ветвей
• Выборка всего дерева одним запросом, с отсортированными в нужном порядке ветвями

В принципе, задача классическая, и сначала я её решил с помощью объединения Adjacency List и Materialized Path. Другими словами, в таблице добавлены колонки

id INT(11)
parentid INT(11)
mpath VARCHAR(255)

В mpath хранился полный путь ветки в дереве, например /1/3/4/5/8/9, где через знак "/" перечислялись ID комментария.

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

SELECT *
FROM messages
WHERE postid=$postid
ORDER BY mpath ASC

Проблема возникла при росте числа комментариев.

Здравствуй, Хабр!

Мы сделали видео-уроки по языку Swift на основе бесплатной книги The Swift Programming Language от Эппл.



Все 32 урока доступны на нашем сайте. Несколько уроков – под катом.

Синоптики предсказывают, что к 2016 году наступит второй ледниковый период трафик в беспроводных сетях на 10% превзойдёт трафик в проводном Ethernet. При этом от года в год частных точек доступа становится примерно на 20% больше.

При таком тренде не может не радовать то, что 80% владельцев сетей не меняют пароли доступа по умолчанию. В их число входят и сети компаний.

Этим циклом статей я хочу собрать воедино описания существующих технологии защит, их проблемы и способы обхода, таким образом, что в конце читатель сам сможет сказать, как сделать свою сеть непробиваемой, и даже наглядно продемонстрировать проблемы на примере незадачливого соседа (do not try this at home, kids). Практическая сторона взлома будет освещена с помощью Kali Linux (бывший Backtrack 5) в следующих частях.

Статья по мере написания выросла с 5 страниц до 40, поэтому я решил разбить её на части. Этот цикл — не просто инструкция, как нужно и не нужно делать, а подробное объяснение причин для этого. Ну, а кто хочет инструкций — они такие:

Используйте WPA2-PSK-CCMP с паролем от 12 символов a-z (2000+ лет перебора на ATI-кластере). Измените имя сети по умолчанию на нечто уникальное (защита от rainbow-таблиц). Отключите WPS (достаточно перебрать 10000 комбинаций PIN). Не полагайтесь на MAC-фильтрацию и скрытие SSID.

Оглавление:
1) Матчасть
2) Kali. Скрытие SSID. MAC-фильтрация. WPS
3) WPA. OpenCL/CUDA. Статистика подбора

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

Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

Я работаю в Яндексе, у Яндекса есть карты, а у карт есть API. API – вещь, которая позволяет встроить карты Яндекса на свой сайт. С версии 2.0 наш API умеет кластеризовать метки на клиенте. Вот как выглядят метки до и после кластеризации:



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

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

Я уже писал про обучение детей программированию на основе Лого. Однако возможен и другой, ещё более “симпатичный” подход – это визуальное программирование, в котором вообще не надо писать текст. Причём визуальное – это не обязательно рисование блок-схем! Например, можно исходить из понятия объекта, который находится в разных состояниях и реагирует на внешние события.

В Майкрософт также задумываются над проблемами обучения детей, в частности, уже писалось про проект Kodu Game Lab. Kodu – это интерактивная среда создания трехмерных игр, доступная одновременно на Xbox 360 и на ПК. Я решил написать о ней подробнее, поскольку начиная с сегодняшнего для любой желающий может скачать и попробовать версию для ПК.

10 сентября Компания «Крок» проводила конференцию, на которой докладчиком был Кевин Митник.
Для меня этот человек — кумир и легенда (я диплом писал отчасти по его книгам), поэтому попасть на его выступление было для меня делом чести.
Узнал я о конференции за 3 дня до ее начала и официально попасть мне на конференцию не удалось.
Что ж, у Митника я многому научился, и поэтому, пустив в ход социальную инженерию, я осуществил физический доступ (проникновение на охраняемый периметр).
Под катом краткий конспект выступления

В рамках федеральной программы, инициированной указом президента РФ №597 от 7 мая 2012 г., ведётся разработка новых профессиональных стандартов в области ИТ. На днях опубликованы черновики профстандартов админа БД, программиста, руководителя проектов в области информационных технологий, руководителя разработки программного обеспечения и т.д.

11-13 сентября 2013 года пройдут открытые вебинары с подробным обсуждением первой версии каждого из разрабатываемых профессиональных стандартов.

Я собираюсь написать несколько статей про новую методологию гибкой разработки Канбан (Kanban Development) в целях подготовки к Scandinavian Agile Conference 2009, где я буду делать один из докладов (кстати, заодно приглашаю всех на конференцию).
Сегодня публикую первую из статей.
Основная задача первой статьи — это как можно проще описать основы Канбан: что это такое, в чем отличие от других гибких методологий и зачем это нужно.
Также я хотел бы собрать как можно больше вопросов и сомнений в комментариях, чтобы ответить на них в следующих статьях, так что пишите всё, что вам непонятно, или что ещё вы хотели бы узнать про Канбан.
Я не то, чтобы большой специалист по этой новой методологии, но мы внутри команды пришли к Канбану самостоятельно и последовательно прошли все этапы мутации от SCRUM до Канбан, так что практический опыт есть.

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

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

Хранение запасов стоит денег. Предположим, что на хлебозаводе есть шесть 50-тонных силосов для хранения муки. Это значит, что в среднем каждый день в них находится около 150 тонн муки. По сегодняшним ценам это 73000$ мёртвого капитала.

Есть и другие издержки, например порча. Мука может храниться месяцами, но готовые булочки начинают терять в цене как только выйдут из печи; через 24 часа они не стоят почти ничего.

Зачем тогда вообще хранить запасы? Затем что есть ещё и расходы связанные с их нехваткой. Если на заказ новой партии булочек с кунжутом уходит два дня, то, если они вдруг закончатся в вашей закусочной, ваш бизнес по продаже гамбургеров остановится на двое суток. Запасы — это буфер, который предотвращает непредвиденные остановки. Сейчас придумано множество алогоритмов для вычисления оптимального объёма этих буферов (для начала: бережливое производство, теория ограничений).

Зачем я вам всё это рассказываю? Затем, что в производстве ПО тоже существуют места, где накапливаются «производственные запасы». И хранение этих запасов может стоить кучу времени и денег.

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

Есть очень неплохая книжка о специфике работы русских вообще. Она называется «Русская модель управления». Ее написал А.П.Прохоров (другой, не олигарх). Не буду ее пересказывать. Основная идея в том, что русские по своей природе могут работать только в двух модах. В нестабильном состоянии они могут свернуть горы. В это время мотивация очень высокая. В стабильном расслабленном состоянии — когда никто не пинает — русские вроде как работают плохо и не сильно утруждаются.

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

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

Я буду приводить влияние разных факторов в порядке их важности и силы влияния. Чем выше — тем сложнее это изменить и тем больший эффект это оказывает.

Ранним утром программист спросил великого мастера:
— Я готов писать модульные тесты. К какому покрытию кода я должен стремиться?
Великий мастер ответил:
— Не переживай о покрытии, просто пиши хорошие тесты.
Программист улыбнулся, поклонился и ушел.

Немного времени спустя другой программист задала этот же вопрос. Великий мастер указал на котел с кипящей водой и сказал:
— Сколько зерен риса я должен положить в этот котел?
Программист с озадаченным видом ответила:
— Как я могу ответить наверняка? Все зависит от того, сколько людей вам надо накормить, насколько они голодны, какие еще блюда вы подаете, сколько риса у вас есть и от многого другого.
— Совершенно верно. — сказал великий мастер.
Второй программист улыбнулась, поклонилась и ушла.

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

Стадия первая. Рождение

«Я программист. Я олимпиадник. Я знаю что такое «о»-маленькое. Я знаю, что такое «О»-большое. Я понимаю, чем отличается «эн-квадрат» от «эн-факториала» и почему они оба стыдливо прячутся при виде «эн-логарифм-эн». Сейчас я приду на проект и перепишу эту тормозную кашу из кода так, что она будет работать в много раз быстрее! Смотрите, я знаю алгоритм Кнута-Морриса-Пратта! А здесь можно сэкономить одно сравнение строчек на равность! А если эту рекурсию развернуть в цикл, то за счет экономии вызовов методов и выделения памяти в стэке… Что, программа тормозит? Сейчас я посмотрю код… Вот! Смотрите, здесь вместо двух вложенных циклов можно написать один и использовать бинарный поиск вместо внутреннего!»

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

Предисловие

Цель данного поста — с одной стороны поделиться своим успешным опытом старта разработки приложений на платформе Android и с другой стороны поспособствовать развитию рынка софта для этой замечательной и бурно растущей платформы за счёт (без ложной скромности скажу) возможно Вас, прочитавших данный пост. В сети, конечно, можно найти материалы на тему разработки приложения «чуть сложнее, чем helloworld», но как правило они разрозненные и в них не описываются различные мелкие подводные камешки. В данном посте мы рассмотрим полный цикл разработки приложения, начиная с чистого компьютера до готового apk-файла. Под катом скрины.

Сегодня я хочу поделиться с вами моим вольным переводом статьи, написанной Сергеем Повзнером (Sergey Povzner). Сергей ведёт блог bongizmo.com и занимается разработкой туристических гидов под общим названием Citybot.

В то время как Android продолжает свой невероятный рост, всё больше и больше программистов начинают разрабатывать приложения на этой платформе. Если ты начинаешь свой путь сегодня, то ты определенно — счастливчик. За последние годы Android значительно повзрослел и избавился от множества детских болезней. Информации по платформе более чем достаточно. Я же расскажу о самых важных ресурсах.

Статья будет полезна как новичкам, так и опытным разработчикам. Это гид по миру Android-разработки.

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

Кубик будет в 3D и его можно будет вращать мышкой, а переворачивать грани можно, кликая мышкой по стрелкам. При том стрелки появляются у ближайшей к зрителю грани.

Бесконечны лишь Вселенная и глупость человеческая. Хотя насчет первой у меня имеются сомнения. (с) Альберт Эйнштейн

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

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



Что делать, если вы попали в такую ситуацию? Вариант «уволиться» рассматривать не будем, хотя часто это единственный простой и правильный вариант.

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

Поводом к написанию данной статьи стал комментарий хабраюзера Kapustos в статье Сотрудники Symantec потеряли 50 мобильников. Не находили?. Он просил посоветовать софт, функционал которого схож с описанным в статье. Подробности под хабракатом.