Классическая задача для собеседования в реальной жизни

Случилось странное – я столкнулся с буквально классической задачей с собеседования в реальной жизни. Задача состоит в том, что необходимо найти первый не нулевой бит в массиве. Поиск должен происходить максимально быстро, скорость поиска желательно получить приближённую к линейной. Никаких правил по распределению единиц в массиве нет. Массив не велик и должен не вылезать за пределы одной кэш-линии.
Родились 3 варианта алгоритма, одна часть которого общая во всех случаях, вторая специфическая.
Общая часть сводится к поиску первого 32 разрядного слова с хотя бы одним не нулевым битом. Дальше, в найденном 32 разрядном слове ищем первый не нулевой бит. Я не знаю как можно оптимизировать первую часть алгоритма, так что ищу простым перебором. Continue reading

Что почитать по Mac OS X для начала?

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

  1. Драйвера и системные приложения.
  2. GUI приложения для конечного пользователя.

Как начать писать приложения для Mac OS X и iOS

Итак, по пунктам, что надо сделать для начала разработки под Mac OS X или iOS:

  1. Покупка Mac или установка Хакинтош. Я бы крайне не рекомендовал начинать с работы с виртуальной машиной, они работаютнастолько тормознуто, что такой вариант подходит разве что для “одним глазком на Mac OS X взглянуть”. Поэтому наиболее дешевым и доступным вариантом будет либо Хикинтош, либо покупка Mac Mini.
  2. Бесплатно зарегистрироваться в качестве разработчика Apple. Это необходимо сделать для доступа к документации и возможности загрузить 3-й Xcode.
  3. Загрузить бесплатно 3-й Xcode или купить за $4.99 Xcode 4. С учетом стоимости Xcode 4, я думаю что его купить все же логичнее. В то же время, в Xcode 3 доступна iOS SDK 4.3 и SDK для Mac OS X 10.6, так что “на посмотреть” его хватит.

Continue reading

Управление памятью в ANSI C

Довольно занятная ситуация: чем больше я пишу кода, тем более простой код мне нравится писать. Что интересно, наиболее простой код выходит не на C++ или Objective-C и даже не на Python, а на чистом C. Хотя, оно и понятно, нет тут простора для творчества
А вот в самом C есть один основательно напрягающий меня момент: освобождение памяти. Довольно часто приходится работать со структурами, в состав которых входят массивы, строки переменной длинны или массивы структур со всей этой радостью одновременно. А раз уж от создания такой конструкции никуда не денешься, то как минимум хочется иметь возможность ее легко удалить.
Подход с использование garbage collector мне не очень нравится, все же это как из пушки по воробьям… А вот построение из выделяемой памяти подобия дерева, мне показалось куда более интересным.
Continue reading

Tasks Explorer 1.5

Ура! Я допилил его! Из нововведений: появилась возможность посмотреть стек вызовов и я решил открыть код под BSD лицензией. Из неприятных нововведений – похоже он стал немного течь. Если у кого-то есть желание поучаствовать в разработке – добро пожаловать!
Выглядит эта радость как-то так:

Ищем быстро. Очень быстро.

Незнаю кто как, но я обычно пишу код в Vim, отлаживаюсь в GDB, ищу Grep. Если первые два пункта не вызывают никаких нареканий, но вот Grep на больших объемах данных, например на проекте с 1GB исходных кодов, несколько нерасторопен.
Решение проблемы довольно простое: надо скрестить Spotlight с Grep и получить шустрый и удобный в работе механизм. Для zsh это можно сделать так:

g()

{
mdfind -onlyin . $1 -0 | xargs -0 grep -n --color=always $1
}

Коллекция Cocoa контролов

Я долгое время считал что количество дополнительных библиотек для Mac OS X и iOS очень скромное. В крайнем случае ни о каких библиотеках кроме как OmniGroup, BWToolkit и Sparkle я особо не слышал. Поэтому, сайт CocoaControls был для меня очень приятным открытием. Пусть большинство контролов и не подойдет для непосредственного использования, но вот как набор идей и подсказок сайт реально великолепен!

Как не надо писать вакансии

Обычно, вакансии C++ разработчиков выглядят довольно логично. Но иногда попадаются просто редкостные уродцы. Вот небольшой кусочек одного из них:

Вам нравится программировать и решать нетривиальные задачи? Вы читали Страуструпа и Александреску, отличаете Composite от Decorator и знаете, где в памяти размещаются статические данные? Умеете исследовать дампы и поддерживать legacy код, но при этом вам по душе применить пару-другую паттернов в новом проекте? Тогда мы с нетерпением ждем ваше резюме на позицию Software Developer C++!

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

The Architecture of Open Source Applications

Стоящих книг посвященных архитектуре приложений очень и очень мало. Поэтому с радостью узнал о выходе в свет новой книги посвященной архитектуре приложений “The Architecture of Open Source Applications”. Книга распространяется под Creative Commons Attribution 3.0 Unported лицензией и прочесть онлайн ее можно тут. Так же книга продается в бумажном виде, либо в формате PDF.
Книга, действительно, очень интересная и полезная. Рекомендую!