• MapReduce или подсчеты за пределами возможностей памяти и процессора (попробую без зауми)

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

      Сразу скажу — топик — для тех, кто не разобрался что такое MapReduce. Для тех, кто разобрался — полезного тут ничего не будет.

      Начнем с того как собственно родилась лично у меня идея MapReduce (хотя я и не знал, что он так называется, и, разумеется, пришла она мне куда позже чем Гугловсцам).

      Сначала опишу как она рождалась (подход был неправильный), а потом как надо правильно делать.

      Как посчитать все слова в Википедии (неправильный подход)


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

      В самом простом случае мы можем завести хеш (dict, map, hash, ассоциативный массив, array() в PHP) и считать в нем слова.

      $dict['word1'] += 1

      Но что делать когда память под хеш кончится, а мы посчитали только одну сотую всех слов?

      Читать дальше →
    • Lock-free структуры данных. Основы: Атомарность и атомарные примитивы


        Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

        Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

        А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
        Атомарность — это первый круг ада низкий уровень из двух.
        Читать дальше →
      • Lock-free структуры данных. 1 — Начало


          Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

          Читать дальше →
        • Владелец Tesla Model S оштрафован властями Сингапура за превышение нормы по выбросам СО2

            Илон Маск уже обсудил случившееся с премьер-министром страны


            В США и некоторых других странах покупатель электромобиля получает налоговые льготы от федерального правительства в размере $7500. В Сингапуре эти льготы повыше — целых $10800. Джо Нгаен (Joe Nguyen), гражданин Сингапура, выложил около $51000 за Tesla Model S, купив электромобиль в Гонконге. Затем электромобиль был перевезен в Сингапур, где новый владелец подал документы на получение налоговых льгот.

            Также потребовалось время на легализацию автомобиля в Сингапуре, на это ушло около двух месяцев. Два месяца ждать пришлось потому, что ранее регуляторы Сингапура не проводили оценку и тестирование автомобилей Tesla. По завершению этого процесса Нгаен вместо налоговых льгот получил штраф в размере $11000. Причина — превышение нормы вредных выбросов, а именно — СО2. И это не ошибка, поскольку в Сингапуре учитывают не только выбросы непосредственно из выхлопной трубы, но и побочные факторы. В данном случае были учтены выбросы CO2 в атмосферу во время производства необходимого для электромобиля количества энергии.
            Читать дальше →
          • Блок-схема для выбора STL-алгоритма



            Третьего дня, во время сортировки старых закладок, попалась мне на глаза блок-схема с алгоритмом выбора STL-контейнера. «Почему же для контейнеров есть, а для стандартных алгоритмов нет? — подумал я. — Это необходимо исправить». Подумано — сделано. Сперва планировалось за пару часов нарисовать нечто простенькое, но в дальнейшем обнаружилось, что алгоритмы никак не хотят умещаться в простенькую схему. Я слегка увлекся, и спустя два вечера схема вобрала в себя 84 алгоритма, а также немного дополнительной информации. Под катом можно увидеть, что получилось в итоге.
            Долой велосипеды!
          • Big Data от А до Я. Часть 1: Принципы работы с большими данными, парадигма MapReduce

            • Tutorial

            Привет, Хабр! Этой статьёй я открываю цикл материалов, посвящённых работе с большими данными. Зачем? Хочется сохранить накопленный опыт, свой и команды, так скажем, в энциклопедическом формате – наверняка кому-то он будет полезен.



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



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


            Читать дальше →
          • Три особенности JavaScript, о которых полезно знать каждому Java/C-разработчику

            • Перевод


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

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

            • DOM, который многие ошибочно считают эквивалентом самого языка JavaScript, обладает очень неудачным API.
            • Когда переходишь на JavaScript с языков С и Java, то попадаешь в ловушку синтаксиса, который устроен не так, как в императивных языках. Это очень часто приводит к багам и сильно раздражает.

            В результате JavaScript обрёл довольно плохую репутацию, которой он, в общем-то, не заслуживает. И чаще всего это связано с тем, что многие разработчики переносят на JavaScript свой опыт работы на Java или С/С++. Здесь разобраны три наиболее трудных случая, демонстрирующих разницу в подходах между Java и JavaScript.
            Читать дальше →
          • От математики к обобщенному программированию

              Здравствуйте!
              Всего месяц назад в издательстве Addison-Wesley вышла книга Александра Степанова — русско-американского учёного в области IT — «From Mathematics to Generic Programming».

              image

              Наверняка многие знакомы с его работой «Начала программирования», выходившей в 2011 году в «Вильямсе».
              Читать дальше →
            • Несколько недорогих способов улучшить свой цифровой быт*

                *слоган одной очень известной торговой онлайн-площадки: Smarter Shopping, Better Living!

                Нашалившего ребёнка родители теперь ставят в тот угол, где нет WiFi — из эфира одной популярной радиостанции

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

                DISCLAIMER: автор выражает благодарность советской спичечной промышленности за эталон 5см (плюс-минус 1мм по ГОСТ 1820-2001), но никак не аффилирован с торговой маркой «Балабановские Спички»; все появления означенной марки в кадрах непреднамеренны.
                Чтобы поднять читателю настроение, автор придумал каждому изделию шуточное название и perk на манер популярной компьютерной игры Fallout, специально для Geektimes.

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

                Итак, сколько плохих кабелей micro USB вы выбросили за последние пару лет? Лично я уже штук пять. А как понять качество кабеля, если заряд идёт, видимых повреждений нет, да и разъёмчик хорошо сидит? Как комфортнее электрифицировать гаджеты в автомобиле, в самолёте, в лесной глуши и на горной вершине?
                Читать дальше →
              • Фотографии NASA, которые должен увидеть каждый

                  Привет, читатель Geektimes. Я знаю, все мы тут собрались из-за интересных новостей из мира технологий и науки. Но сегодня, в пятницу, я предлагаю тебе, читатель, расслаблено сесть в своем кресле и притронуться к прекрасному, потому что лично я получил огромное удовольствие в процессе подготовки этого материала.

                  Под катом много фото и изображений взятых из аккаунта NASA Goddard Space Flight Center на Фликере, все кликабельны, а так же даны ссылки на скачивание в максимально возможных разрешениях. Некоторые из оригиналов огромны и годятся для фотообоев, серьезно, так что будьте аккуратны с трафиком.

                  А теперь наслаждайтесь.

                  image

                  Large (2048 x 2048) Original (4096 x 4096)
                  100-миллионный кадр, сделанный в SDO (Solar Dynamics Observatory) NASA. Для создания кадра использовалось параллельно четыре телескопа, которые по очереди фотографировали солнце в десяти различных волновых диапазонах каждые 12 секунд.
                  Посмотреть все фото
                • Пополняем шпаргалки по C++: неявно-генерируемые перемещающий конструктор и оператор присваивания

                  • Tutorial
                  Когда не так часто, как хотелось бы, приходится работать с языком, некоторые аспекты забываются. А некоторые никогда и не откладываются в голове. Поэтому, когда возникают вопросы, приходится отвлекаться и лезть в документацию.

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

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

                  Читать дальше →
                • Ref-qualified member functions

                    В этом посте я расскажу о новой и (как мне кажется) относительно малоизвестной фиче C++ - reference-qualified member functions. Расскажу о правилах перегрузки таких функций, а также, в качестве примера использования, расскажу, как с помощью ref-qualified функций можно попытаться улучшить схему управления ресурсами, реализуемую с помощью другой идиомы С++ — RAII.
                    Читать дальше →
                  • Преобразование Фурье в действии: точное определение частоты сигнала и выделение нот

                    последняя редакция статьи доступна на сайте makeloft.xyz

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

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

                    image

                    Читать дальше →
                  • Эстония позволит получить электронное гражданство за 50 евро

                      E-estonian это не пародия на эстонский акцент, а вполне реальная возможность пользоваться привилегиями электронного гражданства европейской страны для иностранцев: вчера в Эстонии был единогласно принят закон, вводящий статус «электронного резидента» (e-residence), позволяющий любому иностранцу открыть счёт в эстонском банке, зарегистрировать компанию и воспользоваться электронной подписью, чтобы подписывать документы из любой точки мира.


                      Эстонский президент Тоомас Хендрик Ильвес (фото РИА)
                      Читать дальше →
                    • Брюс Шнайер: Иллюзия безопасности

                        image
                        Брюс Шнайер не нуждается в представлениях. На Хабрахабре можно найти много статей, касающихся деятельности этого «гуру криптографии». Под катом — текстовая расшифровка видеолекции Брюса Шнайера «The security mirage» («Иллюзия безопасности»).
                        Эта лекция доступна на YouTube, на Amara её можно посмотреть с субтитрами на 28-ми языках (включая русский). Что же заставило меня отнимать твоё время, хабрачитатель?
                        Ну и что же там?
                      • Youtube

                          Приходится ждать загрузки видео >360p по несколько секунд, обрывы на середине просмотра стало уже обыденным делом и это с достаточно широким каналом.

                          image

                          Причина в занижении провайдерами скорости к серверам кеширующим видео, всё что нужно сделать это заблокировать доступ к ним.

                          Для того чтобы запрос шел мимо cdn серверов ютуба надо заблокировать диапазон ip адресов (в роутере или на компьютере).

                          173.194.55.0/24 и 206.111.0.0/16
                          Читать дальше →
                        • Будущее WinRT или Going Native 2.0

                          • Перевод
                          Alexandre Mutel — создатель самой быстрой и самой полной .NET обертки для DirectX, единственной, поддерживающей Windows 8 Metro, работает R&D разработчиком игрового движка в SiliconStudio, участник французской демо-группы FRequency.

                          В последнее время мы слышим много шума о возвращении идеи «Going Native» после эры управляемых языков, таких как Java и .NET. В прошлом году, когда WinRT был только представлен, начали появляться недалекие комментарии, которые утверждали, что что .NET умер, а С++ возвращается во всей своей красе — истинный и единственно верный способ для разработки приложений, в то время, как JIT начинает все чаще появляться в мире скриптовых языков (JavaScript активнее всех использует преимущества JIT). Любой код так или иначе станет нативным перед выполнением — разница лишь в длине пути, по которому он пройдет, чтобы стать нативным, и насколько оптимизированным он будет. Значение слова «native» немного изменилось и стало неразрывно связано со словом «производительность». Даже будучи сильным пропагандистом управляемого языка [C#], его производительность на самом деле ниже хорошо написанного С++ приложения. Получается, мы должны просто принять этот факт и вернуться к C++, когда такие штуки как WinRT будут для нас основой межязыкового взаимодействия? По правде говоря, я бы хотел, чтобы .NET умер, и этот пост о том, почему и зачем.
                          Читать дальше →
                        • Готовимся к ядерной войне

                            image

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

                            Вырыть бункер, установить туда системы очистки воздуха, запастись едой и водой…
                            Но дьявол, как известно, в мелочах.
                            Читать дальше →
                          • Обзор Synology DiskStation 211j

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

                              Этот системник — мой домашний сервер. Я храню там домашнюю коллекцию фото и видео, важные бэкапы, веду веб-разработку (это типа домашний дев-сервер) и хосчу веб-интерфейс для просмотра фотографий, чтобы показывать их родителям, которые живут в другом городе. К тому же он стримит музыку и видео на все мои сеттопбоксы, айпады, айфоны и андроиды дома.

                              Работает это всё под управлением Убунту 11.10

                              Надо сказать, что эта штука занимает много места и издаёт много шума, а обошлась мне в ~ 20 000 р. три года назад.

                              Недавно мне на тестирование дали конкурирующее с ним устройство Synology DiskStation 211j.