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

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

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

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

Алгоритм Кнута-Морриса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки.

Господа! Только что на сайте Imagination Technologies вышло исправленное издание бесплатного учебника на русском языке «Цифровая схемотехника и архитектура компьютера» Дэвида Харриса и Сары Харрис (кстати, они не супруги и вообще не родственники – просто так совпало). Предыдущее издание этого учебника вышло год назад, пост о нем собрал 145,000 просмотров на Хабре, количество скачиваний с британского сайта вызвало у его британских админов подозрение, что их атакуют русские хакеры, а впоследствие команду переводчиков лично благодарили за учебник преподаватели МФТИ, МВТУ им. Баумана, харьковского ХНУРЭ и других университетов.



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

Возьмите переменную и увеличьте её на 1. Звучит просто, верно? Ну… С точки зрения PHP-разработчика, наверное, да. Но так ли это на самом деле? Здесь могут возникнуть некоторые трудности. Существует несколько способов инкрементировать значения, они могут выглядеть равноценными, но под капотом PHP работают по-разному, что может привести к, так сказать, интересным результатам.

Ниже приведены основные изменения, привнесенные PHP 7.1. Для получения полного списка утвержденных и обсуждаемых на текущий момент изменений проверьте официальный PHP RFC.

• Перехват нескольких типов исключений за раз
• Поддержка Curl HTTP/2 server push
• Области видимости для констант классов
• Возвращаемый тип void
• Единое поведение строковых функций
• Поддержка строковых параметров в функции list() и новый синтаксис c []
• Выброс предупреждения при невалидных строках в арифметике
• Объявление устаревшим mcrypt() и его последующее удаление

Перехват нескольких типов исключений за раз

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

try {
    // to do something
} catch (MyException $e) {
    // Handle this exception
} catch (AnotherException $e) {
    // Handle this in the same way as MyException
} catch (Exception $e) {
    // Handle this in a different way
}

В PHP 7.1, оба исключения, обрабатываемые в примере одинаково, можно поймать одновременно:

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

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



Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.

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



Одна из первых вещей, которую слышит новоиспеченный администратор баз данных – «используй EXPLAIN». И при первой же попытке он сталкивается c непостижимым:

                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=146.63..148.65 rows=808 width=138) (actual time=55.009..55.012 rows=71 loops=1)
   Sort Key: n.nspname, p.proname, (pg_get_function_arguments(p.oid))
   Sort Method: quicksort  Memory: 43kB
   ->  Hash Join  (cost=1.14..107.61 rows=808 width=138) (actual time=42.495..54.854 rows=71 loops=1)
         Hash Cond: (p.pronamespace = n.oid)
         ->  Seq Scan on pg_proc p  (cost=0.00..89.30 rows=808 width=78) (actual time=0.052..53.465 rows=2402 loops=1)
               Filter: pg_function_is_visible(oid)
         ->  Hash  (cost=1.09..1.09 rows=4 width=68) (actual time=0.011..0.011 rows=4 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 1kB
               ->  Seq Scan on pg_namespace n  (cost=0.00..1.09 rows=4 width=68) (actual time=0.005..0.007 rows=4 loops=1)
                     Filter: ((nspname <> 'pg_catalog'::name) AND (nspname <> 'information_schema'::name))

Что бы это могло значить?

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

Оригинальное описание алгоритма

1. Сначала я задаю нужное количество комнат – к примеру, 150. Естественно, цифра произвольная, и чем она больше, тем сложнее будет подземелье.

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

Вместо равномерно распределённых случайных чисел (какие выдаёт генератор Math.random в большинстве языков), я использую нормальное распределение Парка-Миллера. В результате вероятность появления маленьких комнат превышает вероятность появления больших. Зачем это надо, объясню позже.

Кроме того я проверяю, что соотношение длины и ширины комнаты не слишком велико. Нам не нужны как идеально квадратные комнаты, так и сильно вытянутые.

3. И вот у нас есть 150 случайных комнат, расположенных на небольшом пространстве. Большинство из них наезжают друг на друга. Теперь мы осуществляем их разделение по технологии separation steering, чтобы разделить прямоугольники так, чтоб они не пересекались. В результате они не пересекаются, но находятся достаточно близко друг от друга.

4. Заполняем промежутки клетками размером 1х1. В результате у нас получается квадратная решётка из комнат различного размера.

5. И тут начинается основное веселье. Определяем, какие из клеток решётки являются комнатами – это будут любые клетки с шириной и высотой, превышающими заданные. Из-за распределения Парка-Миллера мы получим сравнительно небольшое количество комнат, между которыми есть довольно много свободного пространства. Но оставшиеся клетки нам также пригодятся.

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

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

8. Дерево получается аккуратным, но скучным – никаких вам замкнутых ходов. Поэтому мы случайным образом добавляем обратно примерно 15% ранее исключённых рёбер графа. В результате получится граф, где все комнаты гарантированно достижимы, с несколькими замкнутыми ходами.

9. Чтобы превратить его в коридоры, для каждого ребра строится серия прямых линий (в форме Г), идущих по рёбрам графа, соединяющим комнаты. Тут нам пригождаются те клетки, которые остались неиспользованными (те, что не превратились в комнаты). Все клетки, накладывающиеся на Г-образные линии, становятся коридорами. А из-за разнообразия размеров клеток стены коридоров будут неровными, что как раз хорошо для подземелья.

И вот пример результата!

Осторожно — под катом много монстров анимированных гифок!

Я пишу сайты на asp.net mvc. В этих 16 главах я хочу рассказать, как я это делаю. Это некий учебник-справочник всех тех знаний, которые я накопил в течение трех лет.

Почему именно asp.net mvc

ASP.NET MVC я люблю потому что:

• Это .net. Я знаю .net и С#.
• Это компилируемый код.
• Это не ASP.NET WebForms, я работаю с html-кодом.
• Используется MVC-паттерн.
• Visual Studio – самое популярное средство разработки, в котором есть IntelliSense.
• Отличные инструменты отладки.

Тимлид (aka ведущий разработчик, team leader) — один из таких «специалистов», обязанности которого многие видят по-разному. Думаю, что складываются различные представления примерно так: поработал кто-то в команде под руководством тимлида, который хорошо справлялся с задачами проектирования системы, и считает теперь, что это именно то, что должен делать тимлид; в другой же команде тимлид плохо справлялся с планированием спринтов, а с другими обязанностями более или менее, и стали считать сотрудники, что планирование — не то, чем должен заниматься тимлид.

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

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

«Если у вас есть сомнения, авария это или нет — то это авария!»
(с) Мудрость предков

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

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

Давайте, впрочем, вернемся к теме сегодняшней публикации. Считаю это маленьким открытием, и мне непременно нужно поделиться им с теми, кто собирается соединить некоторый отрезок своей жизни с тем, что может называться классической адвенчурой. Быть может это поможет вернуть на рынок игры, которые немного оттеснят «хипстерский пиксель» заменив его на то, что может напомнить времена лучших игр от «Westwood Studios», «Sierra» и «Lucas Arts». Предположу вскользь, что множество художников и так знают это. И, тем не менее — я не заметил публикаций на эту тему. Наша братия не спешит делиться своими секретами, сохраняя некую монополию на собственные открытия.

Я хотел приурочить эту статью к началу разработки собственной адвенчуры. Но кто знает, когда это произойдет? А вам эта информация может помочь уже сейчас. Стоит ли откладывать? Думаю, что нет. Лопаты в руки.

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

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

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

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

Думаете над развитием новой идеи? Сначала ознакомьтесь с этим подробным руководством.



«У меня есть идея Х, что мне делать дальше?»

Первым шагом в запуске успешного стартапа является создание минимально жизнеспособного продукта (Minimum Viable Product, MVP). По сути, это означает подтверждение того факта, что существует рынок, который ваша компания сможет назвать «домашним» (основным) и найти на нем платежеспособных клиентов. То есть первым делом вам нужно найти первых покупателей и понять, за что они готовы платить.

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

Если коротко, то суть статьи можно можно проиллюстрировать так:



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

Если вы регулярно используете Git, то вам могут быть полезны практические советы из этой статьи. Если вы в этом пока новичок, то для начала вам лучше ознакомиться с Git Cheat Sheet. Скажем так, данная статья предназначена для тех, у кого есть опыт использования Git от трёх месяцев. Осторожно: траффик, большие картинки!

Содержание:

1. Параметры для удобного просмотра лога
2. Вывод актуальных изменений в файл
3. Просмотр изменений в определённых строках файла
4. Просмотр ещё не влитых в родительскую ветку изменений
5. Извлечение файла из другой ветки
6. Пара слов о ребейзе
7. Сохранение структуры ветки после локального мержа
8. Исправление последнего коммита вместо создания нового
9. Три состояния в Git и переключение между ними
10. Мягкая отмена коммитов
11. Просмотр диффов для всего проекта (а не по одному файлу за раз) с помощью сторонних инструментов
12. Игнорирование пробелов
13. Добавление определённых изменений из файла
14. Поиск и удаление старых веток
15. Откладывание изменений определённых файлов
16. Хорошие примечания к коммиту
17. Автодополнения команд Git
18. Создание алиасов для часто используемых команд
19. Быстрый поиск плохого коммита