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

Компания Gentleminds, разработчик систем машинного обучения и компьютерного зрения, совместно с FunCorp попробовали создать генератор весёлых подписей к картинкам, используя базу мемов iFunny. Поскольку приложение англоязычное и используется преимущественно в США, подписи будут на английском. Подробности под катом.

Хэш-таблицы используются везде, в каждой серьёзной С-программе. По сути, они позволяют программисту хранить значения в «массиве», индексируя его с помощью строк, в то время как в языке С допускаются только целочисленные ключи массива. В хэш-таблице строчные ключи сначала хэшируются, а затем уменьшаются до размеров таблицы. Здесь могут возникать коллизии, поэтому нужен алгоритм их разрешения. Существует несколько подобных алгоритмов, и в РНР используется стратегия связных списков (linked list).

В Сети есть немало замечательных статей, подробно освещающих устройство хэш-таблиц и их реализации. Начать можно с http://preshing.com/. Но имейте в виду, вариантов структуры хэш-таблиц — несметное множество, и ни один из них не совершенен, в каждом есть компромиссы, несмотря на оптимизацию циклов процессора, использования памяти или хорошее масштабирование потокового окружения (threaded environment). Одни варианты лучше при добавлении данных, другие — при поиске и т. д. Выбирайте реализацию в зависимости от того, что для вас важнее.

Хэш-таблицы в РНР 5 подробно рассмотрены в материале phpinternalsbook, который я написал вместе с Nikic, автором хорошей статьи про хэш-таблицы в РНР 7. Возможно, её вы тоже сочтёте интересной. Правда, она писалась до релиза, поэтому некоторые вещи в ней слегка отличаются.

Здесь же мы подробно рассмотрим, как устроены хэш-таблицы в РНР 7, как с ними можно работать с точки зрения языка С и как ими управлять средствами РНР (используя структуры, называемые массивами). Исходный код в основном доступен в zend_hash.c. Не забывайте, что хэш-таблицы мы используем везде (обычно в роли словарей), следовательно, нужно проектировать их так, чтобы они быстро обрабатывались процессором и потребляли мало памяти. Эти структуры решающе влияют на общую производительность РНР, поскольку местные массивы не единственное место, где используются хэш-таблицы.

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

Эта статья базируется на главе Zvals книги PHP Internals Book, переводом которой на русский язык я сейчас занимаюсь [¹]. Книга ориентирована в первую очередь на C-программистов, желающих писать свои расширения для PHP, но, я уверен, что она окажется полезной и для PHP-разработчиков, так как описывает внутреннюю логику работы интерпретатора. В статье я оставил только базовую теорию, которая должна быть понятна всем разработчикам (даже не знакомым с PHP или C). За более полным изложением материала обратитесь к книге.

Задачка для привлечения внимания. Каким будет результат выполнения следующего кода?

$obj1 = new StdClass();
$obj2 = new StdClass();

$obj1->value = 1;
$obj2->value = 1;

function f1($o) {
  $o = 100;
}

function f2($o) {
  $o->value = 100;
}

f1($obj1);
f2($obj2);

var_dump($obj1);
var_dump($obj2);

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

Тема SOLID-принципов и в целом чистоты кода не раз поднималась на Хабре и, возможно, уже порядком изъезженная. Но тем не менее, не так давно мне приходилось проходить собеседования в одну интересную IT-компанию, где меня попросили рассказать о принципах SOLID с примерами и ситуациями, когда я не соблюл эти принципы и к чему это привело. И в тот момент я понял, что на каком-то подсознательном уровне я понимаю эти принципы и даже могут назвать их все, но привести лаконичные и понятные примеры для меня стало проблемой. Поэтому я и решил для себя самого и для сообщества обобщить информацию по SOLID-принципам для ещё лучшего её понимания. Статья должна быть полезной, для людей только знакомящихся с SOLID-принципами, также, как и для людей «съевших собаку» на SOLID-принципах.

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

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

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

— В PHP приведение типов работает нормально, надо только включать здравый смысл.
— А чего там, просто сравниваешь и все…
— Ого, глюк какой-то в PHP, смотри, сравниваю два флоата, они должны быть одинаковые, а он мне говорит, что они не равны.
— А, ну когда число со строкой сравниваешь, перебирать надо, что сработает.

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

Буду краток, дальше будут только примерчики. А к тебе, дорогой читатель, просьба. Некоторые ответы спрятаны под спойлер. Перед тем, как заглянуть в ответ под спойлером, попробуй ответить сам. За каждый правильный ответ заслуженно прибавляй себе по баллу. В конце поста в опросе не забудь проставить свой результат. Договорились?

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

10. Нормализация баз данных

Указания для правильного проектирования реляционных баз данных изложены в реляционной модели данных. Они собраны в 5 групп, которые называются нормальными формами. Первая нормальная форма представляет самый низкий уровень нормализации баз данных. Пятый уровень представляет высший уровень нормализации.

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

Предлагаем вашему вниманию очередную подборку со ссылками на новости и материалы.

Приятного чтения!

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

Есть в американской разведке такая дисциплина, как OSINT (Open source intelligence), которая отвечает за поиск, сбор и выбор информации из общедоступных источников. К одному из крупнейших поставщиков общедоступной информации можно отнести социальные сети. Ведь практически у каждого из нас есть учетка (а у кого-то и не одна) в одной или нескольких соцсетях. Тут мы делимся своими новостями, личными фотографиями, вкусами (например, лайкая что-то или вступая в какую-либо группу), кругом своих знакомств. Причем делаем это по своей доброй воле и практически совершенно не задумываемся о возможных последствиях. На страницах журнала уже не раз рассматривали, как можно с помощью различных уловок вытаскивать из соцсетей интересные данные. Обычно для этого нужно было вручную совершить какие-то манипуляции. Но для успешной разведки логичнее воспользоваться специальными утилитами. Существует несколько open source утилит, позволяющих вытаскивать информацию о пользователях из соцсетей.

Предлагаю читателям «Хабрахабра» перевод публикации «30 Amazing PHP Libraries for Programmers and Developers». Авторы собрали несколько удивительных PHP-библиотек, которые помогут реализовать некоторые классные вещи, не прилагая много усилий. Цель обзора состоит в том, чтобы преподнести что-то новое, поэтому список не включает популярные библиотеки.

Одним из самых больших нововведений в PHP 5.5 будет поддержка генераторов и корутин (сопрограмм). Генераторы уже достаточно были освещены в документации и в нескольких других постах (например в этом или в этом). Сопрограммы же получили очень мало внимания. Это гораздо более мощный, но и более сложный для понимания и объяснения, инструмент.

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

Генераторы

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

Если вам приходилось работать с Yii2, наверняка возникала ситуация, когда нужно было сохранить связь «многие ко многим».

Когда становилось ясно, что в сети еще нет поведений для работы с этим типом связи, тогда нужный код писался на событии «after save» и с напутствием «ну работает же» отправлялся в репозиторий.

Лично меня не устраивал такой расклад событий. Я решил написать то самое волшебное поведение, которого так не хватает в официальной сборке Yii2.

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

Сегодня я решил опубликовать свои шпаргалки, на самые часто встречающиеся ошибки при работе с MySQL.

В сети гуляет довольно много решений для эмуляции многопоточности в php. Чаще всего они основываются на форках, но есть и вариации на тему с использованием curl, proc_open и т.п.

Все встреченные варианты по тем или иным причинам меня не устроили и пришлось написать свое решение.
Набор требований у меня был следующий:

• Использование форков;
• Синхронный режим с сохранением интерфейса при отсутствии необходимых расширений;
• Многократное использование дочерних процессов;
• Полноценный обмен данными между процессами. Т.е. запуск с аргументами и получение результата по завершении;
• Возможность обмена событиями между дочерним процессом-«потоком» и основным процессом во время работы;
• Работа с пулом потоков с сохранением многократного использования, передачи аргументов и получения результатов;
• Обработка ошибок выполнения;
• Таймауты на выполнение работы, ожидание работы потоком, инициализацию;
• Максимум производительности;

В результате получилась библиотека AzaThread (старое название — CThread).

Предлагаем вашему вниманию очередную подборку со ссылками на новости и материалы.

Приятного чтения!

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


*квадраты до сотни

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

Здравствуй хаброчеловек!

Так уж случилось, что с этого семестра в своем вузе я записался на спецкурс по паттернам проектирования. Курс проходит в виде семинаров, на которых ты (студент) должен рассказать чему научился за неделю (имеется ввиду, какие паттерны изучил и применил на практике).