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

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

Логарифмы

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

Первая статья цикла

Интро

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

Интро

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

В своих статьях я буду приводить примеры кода сразу на двух языках: на Java и на Haskell. Благодаря этому можно будет сравнить императивный и функциональный стили программирования и увидить плюсы и минусы того и другого.

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

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

До 28 октября я должен был принять решение, буду ли я работать в Amazon по окончанию стажировки. Оставалось совсем немного времени, но мой друг Дэниел убедил меня, что если я попробую попасть в Twitter, то как раз успею пройти все интервью. Я не смог устоять.

Сначала меня попросили решить пару вопросов с Codility, дав на все про все час времени. Вопросы попались средней интересности («является ли слово анаграммой палиндрома» и «посчитать количество седловых точек в двумерном массиве»). Я был не слишком уверен в получившихся решениях, но вскоре Джуди прислала мне письмо с приглашением на телефонное интервью в среду в 17:30.

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

Новости хаба .Net на Хабре занимают 33 страницы или 328 постов. Что говорит о том что новости появляются почти каждый день =) Посмотрим на самое интересное из них (на мой скромный взгляд). Ну и загляните под кат: до ката, конечно же, не все.

Доступен новый JIT: теперь с поддержкой SIMD
Как работает декомпиляция в .Net или Java на примере .Net
Microsoft раскрыла исходный код компилятора С#
Consulo: ~1000 коммитов, или как прошла осень
Под капотом у Stopwatch
Как тестировать код финализатора (c#). Послесловие: тест все-таки упал

В рамках моей «работы» над стандартизацией C# 5 в технической группе ECMA-334 TC49-TG2 мне посчастливилось увидеть несколько интересных способов, которыми Владимир Решетников проверял C# на прочность. В данной статье описана одна из проблем, которые он поднял. Разумеется, она, скорее всего, никак не затронет 99.999% C#-разработчиков… но разобраться все равно любопытно.

Спецификации, используемые в статье:

• Стандарт Unicode 7.0.0 – в особенности, глава 3
• C# 5 (Документ Word)
• ECMA-335 (Спецификация CLI)

Что такое строка?

Как бы вы объявили тип string (или System.String)? Я могу предположить несколько вариантов ответа на данный вопрос, от расплывчатых до довольно конкретных:

• «Какой-нибудь текст в кавычках»
• Последовательность символов
• Последовательность символов Юникода
• Последовательность 16-битных символов
• Последовательность слов UTF-16

Только последнее утверждение полностью верно. Спецификация C# 5 (раздел 1.3) гласит:

Обработка строк и символов в C# использует UTF-16. Тип char представляет слово UTF-16, а тип string – последовательность слов UTF-16.

Пока всё в порядке. Но это C#. А как насчет IL? Что используется там, и имеет ли это значение? Оказывается, что имеет… Строки должны быть объявлены в IL как константы, и природа этого способа представления важна – не только кодировка, но и интерпретация этих закодированных данных. В частности, последовательность слов UTF-16 не всегда может быть представлена в виде последовательности слов UTF-8.

Этим постом подвожу итог попытки определить лучшие игры всех времен и народов по версии Хабрахабра на 2013 год.

Отбор проводился по простым правилам:

− В этот пост каждый желающий вносил свою любимую игру,
− Каждый другой желающий голосовал за любимую игру.

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

Основные итоги

Всего в посте собралось за 5 дней больше 1 800 комментариев. Игр было указано около 400. Набрали больше 20 голосов 121 игра. При подсчете учитывались только плюсы (минусы не считал, ибо мы выбирали то, что нравится). Итак, встречайте десятку лучших:

1. Герои Меча и Магии (259)
2. Half Life (254)
3. Fallout (211)
4. Portal (182)
5. Neverhood (174)
6. DOOM (153)
7. Civilization (151)
8. StarCraft (150)
9. Космические рейнджеры (128)
10. Warcraft (127)

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

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

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

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

Мы построим свой музей компьютерных игр, Юзернейм!

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

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

— Советы из личного опыта от olyapka,
— Как правильно покупать от darbin.

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

Пару минут назад произошло знаковое событие — игра Path of Exile, идейная наследница Diablo и Diablo 2, наконец предстала на суд широкой общественности после 6 лет разработки и длительного этапа закрытого бета-теста.

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

Основная проблема любой идеи стартапа — никто не знает, нужно ли это вообще кому-нибудь или нет. Готовы ли люди изменить своё поведение, свои привычки и начать пользоваться новым продуктом? И главное — готовы ли они за него заплатить?

Десятки-сотни тысяч стартапов ежегодно запускаются, не зная ответа на этот вопрос. Это понятно — никогда нельзя быть абсолютно уверенным в успехе нового бизнеса. Тем не менее, существуют несколько методов проверки идеи — и все они с разной степенью могут предсказать будущее продукта. Один из самых эффективных методов — это разработка fake landing page.

Начнем «раскручивать» термин с конца. Landing page («посадочная страница») называют страницу сайта, на которую пользователь переходит по нажатию на рекламное сообщение. Обычно на этой странице кратко и полно описывается суть продукта, а так же размещается action button, например «Зайти», «Начать», «Узанать подробнее». Цель landing page — «взять на руку» человека, пришедшего извне по рекламе, быстро и четко объяснить, что здесь происходит, и показать один путь, куда двигаться дальше. Переход же на главную страницу сайта, как часто делают многие рекламодатели, обычно является серьезной ошибкой — большое количество информации, которая понятна уже постоянному пользователю, пугает новичка — и даже не надейтесь, что он найдет раздел «О нас» или «Что это?».

С появлением приставки fake — фальшивый, ненастоящий — проявляется сакральный смысл всей идеи проверки будущего стартапа на реальности. Мы создаем landing page для еще несуществующего продукта, «пригоняем» траффик посредством рекламного объявления и проверяем, как ведут себя наши потенциальные клиенты. Итоговым результатом является четкий ответ — сколько из всех, кто в принципе заинтересован предложенной идеей (нажали на рекламное объявление) готовы стать вашими клиентами (нажали на кнопку «Зайти» на fake landing page).

Введение (от переводчика)

Так вышло, что одна из моих самых любимых игр — Warcraft II.
Каждый раз, когда эта игра где-то упоминается, или кто-то про неё вспоминает, я обычно очень радуюсь. Перед Warcraft II, разумеется, был просто Warcraft.

И вот недавно случилось интересное — Патрик Вайат (Patrick Wyatt), один из тех людей, кто стоял у истоков Blizzard, и человек, который затеял разработку Warcraft начал цикл воспоминаний о тех временах. Первая статья, которую я вам предлагаю прочитать ниже — о начале разработки Warcraft. О том, откуда появилась идея; о том, какая сеть была организована у ребят в офисе, пока они грезили о мультиплеере; о EMS и тонкостях эстетики программирования под DOS; о команде проекта и так далее.

Я, увы, совсем не специалист в разработке под DOS, поэтому если читатели укажут мне на неточности в переводе, связанные с техническими деталями — буду рад и тут же исправлюсь.

Это касается, понятное дело, и любых других неточностей, опечаток, пунктуации и стилистики.

---

Давным давно, в начале времен, когда игры для PC писались под операционной системой DOS, я начал работать над игрой под названием Warcraft.

В результате профилирования моей софтины я сделал вывод о необходимости оптимизации функции сравнения буферов.
Т.к. CLR не предоставляет стандартного способа сравнить два куска памяти, то функция была написан на скорую руку самостоятельно (лишь бы работало).
Погуглив по фразе «Best Way to Compare Byte Arrays in .Net», я пришёл в замешательство: в абсолютном большинстве случаев люди предлагали использовать либо LINQ, либо Enumerable.SequenceEqual(), что практически одно и тоже. Даже на StackOverflow это был самый популярный ответ. Т.е. катастрофически популярно заблуждение вида:

«Compiler\run-time environment will optimize your loop so you don't need to worry about performance.» Отсюда.

Именно оно впервые навело меня на мысль написать этот пост.
Я провёл сравнительное тестирование пяти способов сравнения буферов, доступных из C#, и на основании результатов тестирования дал рекомендации в выборе способа.
Кроме того, я декомпилировал некоторые функции, и проанализировал код, генерируемый JIT-компилятором для конфигурации x86, а так же сравнил машинный код, генерируемый JIT-компилятором, с машинным кодом функции CRT аналогичного назначения.

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

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

На днях специалисты Neuroscape Lab создали 3D-визуализацию работы мозга. Видео получено следующим образом: вначале мозг добровольца сканировался на MRI, затем подключаются электроды электроэнцефалографа, и проводится мониторинг работы мозга, визуализация чего накладывается на ранее отсканированную модель мозга.

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

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

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

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

Надеюсь все знают про НПО им. С.А. Лавочкина – предприятие которое с 1965 года реализует все межпланетные миссии СССР и России. По крайней мере, наверняка все слышали об их продукции: «Луна-3», «Луна-9», «Луна-16», «Луноход», «Марс-3», «Марс-5», «Венера-7», «Венера-13», «Вега», «Фобос-Грунт», «Радиоастрон», «Электро-Л»… Как всякое предприятие космической отрасли оно находится под режимом секретности, и даже в музей можно попасть только по предварительной заявке и в составе групповой экскурсии.

Всего месяц назад я с удивлением узнал, что в НПОЛ, помимо музея, еще есть загадочное место под ироничным названием «Ангар 18».



В отличие от американского аналога, он скрывает не инопланетные корабли, а земные. Но богатство коллекции, собранной на незначительной площади, уверенно может конкурировать с ныне разгромленным павильоном «Космос» на ВДНХ. Увидев такое космическое изобилие, я поначалу был просто ошеломлен. Потом узнал, что Луноход – это ходовая модель; «Венера-7» — технологический макет, проходивший термовакуумные испытания перед полетом в 1970 году; и почти все модели содержат элементы, которые создавались для реальных аппаратов, успехами которых я вдохновлялся еще в детстве. Короче, состояние шока отпустило далеко не сразу. Но обо всем по порядку.