Data Mining → Теория шести рукопожатий: еще одно подтверждение из песочницы
Однажды в студеную зимнюю пору я столкнулся с упоминанием того, что кто-то в Facebook пытается подтвердить теорию шести рукопожатий. Для тех кто не в курсе, эта теория заключается в том, что все жители земли в среднем знакомы друг с другом через цепочку из пяти друзей (т.е. шести рукопожатий). Подробнее об истории этой теории можно прочитать в википедии, там же можно узнать о том, что Майкрософт несколько лет назад пыталась подтвердить эту теорию на основе данных о контакт-листах мессенджера MSN — в результате у них получилось 6,6 рукопожатий, что вполне вписывается в теорию.
Очень мне захотелось эту теорию подтвердить самому, используя данные, которые есть под рукой — ВКонтакте. Для претворения моей странной идеи в жизнь надо было решить целый комплекс проблем:
Очень мне захотелось эту теорию подтвердить самому, используя данные, которые есть под рукой — ВКонтакте. Для претворения моей странной идеи в жизнь надо было решить целый комплекс проблем:
- На каких данных это все расчитывать.
- Где эти данные взять.
- Как эти данные сохранять.
- Каким алгоритмом воспользоваться для расчетов.
Программирование → Вычисления с фиксированной точкой. Основные принципы (ч.1) из песочницы
Введение или зачем этот топик
Читая Хабрахабр, я натолкнулся на два топика, «выводящие на чистую воду» вычисления с плавающей запятой.
В одном из них достаточно подробно и качественно дана выжимка из стандарта IEEE754 и основные проблемы при вычислениях с плавающей запятой, другой — короткий топик-заметка про то, что не все так хорошо при вычислениях на ПК. При этом даются рекомендации в случае, когда важна математическая точность результата, использовать целочисленные вычисления, «фиксировать запятую» или как минимум проверять результаты, выдаваемые платформой (компилятор + процессор).
Несмотря на то, что советы дельные, понять, как использовать целочисленные вычисления там, где до этого была плавающая запятая, не так просто, особенно без математической подготовки. Достаточно занимательна в этом смысле попытка одного из «хабровчан» разобраться с фиксированной точкой методом экспериментов.
Данный топик — краткое введение, которое должно дать представление о вычислениях с фиксированной точкой. Математика в данной статье не должна никого напугать — все очень примитивно. Сразу прошу простить: среди моих знакомых устоявшимся выражением является именно «фиксированная точка» (от англ., fixed-point), а не «запятая», поэтому я буду придерживаться именно этого термина.
Программирование → Увеличиваем скорость вычислений в Matlab из песочницы
Добрый день, уважаемые хабровчане!
Предлагаю вашему вниманию статью, на которую меня натолкнул недавний пост Matlab кластер своими руками. В свое время я столкнулся с теми же проблемами что и автор топика, однако для увеличения производительности я не стал уходить в дебри распределенных вычислений, а просто решил максимально оптимизировать свой код. Как это сделать в Matlab, прошу под кат за подробностями.
Статья является описанием жизненного опыта и вольным переводом англоязычной публикации.
Предлагаю вашему вниманию статью, на которую меня натолкнул недавний пост Matlab кластер своими руками. В свое время я столкнулся с теми же проблемами что и автор топика, однако для увеличения производительности я не стал уходить в дебри распределенных вычислений, а просто решил максимально оптимизировать свой код. Как это сделать в Matlab, прошу под кат за подробностями.
Статья является описанием жизненного опыта и вольным переводом англоязычной публикации.
Программирование → Календарь древних майя — как вычислить дату? из песочницы
Здравствуй, читатель!
Если ты помнишь, то совсем недавно календарь древних майя был у всех на слуху. Мало кто обошёл вниманием тему животрепещущего вопроса окончания летосчисления некогда великой цивилизации. Сейчас я предлагаю вникнуть в математическую суть вопроса — как вычислить дату календаря майя.
В своём повествовании я покажу как получить дату календаря майя из даты привычного нам григорианского календаря, приводя примеры алгоритмов на языке Python.
Если ты помнишь, то совсем недавно календарь древних майя был у всех на слуху. Мало кто обошёл вниманием тему животрепещущего вопроса окончания летосчисления некогда великой цивилизации. Сейчас я предлагаю вникнуть в математическую суть вопроса — как вычислить дату календаря майя.
В своём повествовании я покажу как получить дату календаря майя из даты привычного нам григорианского календаря, приводя примеры алгоритмов на языке Python.
Блог компании TrendClub → Цветовые палитры фильмов
Наверняка, многие помнят пост Стильный фон за 5 минут, где говорилось, что из любой фотографии можно сделать фон, путём нескольких простых преобразований. Картинки, которые сделали участники проекта MovieBarCode немного похожи на стильные фоны, но отличаются по назначению.
Всё дело в том, что наличие различных цветов в жизни необходимо для поддержания нервной системы человека в тонусе. Известны случаи т.н. «цветового голодания», когда при цветовой бедности окружающего пейзажа и обстановки развивались симптомы астенизации — (греч. astheneia бессилие, слабость) — снижение функциональных возможностей центральной нервной системы, проявляющееся ухудшением работоспособности, психической утомляемостью, ухудшением внимания, памяти, повышенной реактивностью с раздражительной слабостью).
При просмотре фильма вы питаетесь цветовой энергией полтора часа, а то и больше. Поэтому не стоит удивляться, что то или иное произведение искусства нравится вам, и не нравится вашему другу, быть может всё дело не в отсутствии вкуса, а в индивидуальной энергетической потребности или цветовом голодании. Прежде чем смотреть какой-либо фильм, борясь с цветовым голоданием, поищите его цветовую палитру. К примеру, на картинке выше вы видите фильм «Матрица».
Всё дело в том, что наличие различных цветов в жизни необходимо для поддержания нервной системы человека в тонусе. Известны случаи т.н. «цветового голодания», когда при цветовой бедности окружающего пейзажа и обстановки развивались симптомы астенизации — (греч. astheneia бессилие, слабость) — снижение функциональных возможностей центральной нервной системы, проявляющееся ухудшением работоспособности, психической утомляемостью, ухудшением внимания, памяти, повышенной реактивностью с раздражительной слабостью).
При просмотре фильма вы питаетесь цветовой энергией полтора часа, а то и больше. Поэтому не стоит удивляться, что то или иное произведение искусства нравится вам, и не нравится вашему другу, быть может всё дело не в отсутствии вкуса, а в индивидуальной энергетической потребности или цветовом голодании. Прежде чем смотреть какой-либо фильм, борясь с цветовым голоданием, поищите его цветовую палитру. К примеру, на картинке выше вы видите фильм «Матрица».
Алгоритмы → Моноиды и их приложения: моноидальные вычисления в деревьях
Приветствую, Хабрахабр. Сегодня я хочу, в своём обычном стиле, устроить сообществу небольшой ликбез по структурам данных. Только на этот раз он будет гораздо более всеобъемлющ, а его применения и практичность — простираться далеко в самые разнообразные области программирования. Самые красивые применения, я, конечно же, покажу и опишу непосредственно в статье.
Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.
Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.
Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.
Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+":
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так,fst(5, 2) = 5 ; fst( . Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.
Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.
И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строкаfst(e, a) = e всегда, и если a ≠ e , то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)
Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.
Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.
Моноид как концепция
Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.
Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+":
"John" ◦ "Doe" = "JohnDoe"Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так,
"foo", "bar") = "foo"Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.
И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка
"": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:
public interface IMonoid<T> {
T Zero { get; }
T Append(T a, T b);
}
Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.
Персональные блоги → Квантовая информатика для котов и людей
Это продолжение недавней статьи «Квантовая информатика с человеческим лицом».
Мы попробуем понять, вправду ли невозможные вычисления обходятся программисту задаром, узнаем, что случилось с котом Шредингера, выясним, можно ли сделать результат невозможного вычисления единственным материальным следствием прогона квантовой программы и заглянем внутрь квантового кулера.
Антропный принцип, эффект Зенона и фермент в роли машины Тьюринга
Мы попробуем понять, вправду ли невозможные вычисления обходятся программисту задаром, узнаем, что случилось с котом Шредингера, выясним, можно ли сделать результат невозможного вычисления единственным материальным следствием прогона квантовой программы и заглянем внутрь квантового кулера.
Антропный принцип, эффект Зенона и фермент в роли машины Тьюринга
Будущее здесь → Невероятный вероятностный процессор
На проходящей с 8 по 12 февраля в Сан-Франциско Международной конференции по полупроводниковым схемам (Solid-State Circuits Conference) исследователи из Rice University показали реально работающий вероятностный процессор.
Назвали его PCMOS, (probability-based complementary metal-oxide semiconductor). Собственно, новое тут — приставка P (probability-based). Так как процессор использует точно такую же комплементарную логику на транзисторах металл-оксид-полупроводник, как и существующие чипы. Однако представленный прототип, при создании которого разработчики отказались от традиционной булевой логики, заменив ее вероятностным подходом, в 7 раз быстрее нынешних чипов, и при этом в потребляет в 30 раз меньше энергии.
По мнению руководителя научной группы исследователей из Rice University Кришны Пэлема, новый процессор опровергает один из постулатов компьютерной науки — о том, что информация по определению является точной. Дело в том, что PCMOS способен отключать питание у отдельных его транзисторов, допуская в связи с этим возможность неточности выполнения некоторых вычислений. В итоге процессор работает при значительно более низком напряжении и обрабатывает ошибки вычисления и погрешности при помощи вероятностной логики.
Интересно то, что на Solid-State Circuits Conference был показан не только сам чип, но пример его экспериментального применения. Так, PCMOS использован в видеодекодере для сотовых телефонов, который «старается быть точным» только при обработке наиболее значимых элементов изображения. По словам разработчиков, участники экспериментов не находят разницы между картинкой, генерируемой PCMOS, и процессором традиционной архитектуры.
via electronista
Назвали его PCMOS, (probability-based complementary metal-oxide semiconductor). Собственно, новое тут — приставка P (probability-based). Так как процессор использует точно такую же комплементарную логику на транзисторах металл-оксид-полупроводник, как и существующие чипы. Однако представленный прототип, при создании которого разработчики отказались от традиционной булевой логики, заменив ее вероятностным подходом, в 7 раз быстрее нынешних чипов, и при этом в потребляет в 30 раз меньше энергии.
По мнению руководителя научной группы исследователей из Rice University Кришны Пэлема, новый процессор опровергает один из постулатов компьютерной науки — о том, что информация по определению является точной. Дело в том, что PCMOS способен отключать питание у отдельных его транзисторов, допуская в связи с этим возможность неточности выполнения некоторых вычислений. В итоге процессор работает при значительно более низком напряжении и обрабатывает ошибки вычисления и погрешности при помощи вероятностной логики.
Интересно то, что на Solid-State Circuits Conference был показан не только сам чип, но пример его экспериментального применения. Так, PCMOS использован в видеодекодере для сотовых телефонов, который «старается быть точным» только при обработке наиболее значимых элементов изображения. По словам разработчиков, участники экспериментов не находят разницы между картинкой, генерируемой PCMOS, и процессором традиционной архитектуры.
via electronista
Персональные блоги → О’Рейли о сохранении заманчивой прибыли в Облаках с послесловием переводчика
Вычисления в облаках – это реальность. Всё движется в Облака: и в целом, и по частям. При этом главный фокус заключается в том, что, когда на определённой стадии развития некоторой «производственной» цепочки заманчивая прибыль исчезает в одном месте из-за того, что здесь «производство» стало модульным и серийным, возможность получить такую прибыль от соответствующего продукта обычно переходит в смежное место...
Как и обещал, информирую хабраграждан, что в моей серии заметок «О’Рейли, Майкрософт и другие о вычислениях в облаках» появились две очередные.
Первая из них является заключительной частью перевода статьи О’Рейли «Web 2.0 and Cloud Computing». Главная идея этой заметке сформулирована выше.
Во второй заметке вы найдёте более расширенные соображения и замечания переводчика, как и некоторые обобщающие комментарии по обсуждению в Хабре первой части перевода статьи О’Рейли. Главным в этой заметке является попытка определения понятия «вычисления в облаках» через совокупность пяти ключевых признаков, характеризующих эту технологию: Виртуальность, Выделенность, Эластичность/Динамичность, Отчуждённость и Оплата по факту.
Итак:
Закон сохранения заманчивой прибыли в Облаках (перевод 2-й части статьи)
Послесловие переводчика с попыткой определения Облаков
Как и обещал, информирую хабраграждан, что в моей серии заметок «О’Рейли, Майкрософт и другие о вычислениях в облаках» появились две очередные.
Первая из них является заключительной частью перевода статьи О’Рейли «Web 2.0 and Cloud Computing». Главная идея этой заметке сформулирована выше.
Во второй заметке вы найдёте более расширенные соображения и замечания переводчика, как и некоторые обобщающие комментарии по обсуждению в Хабре первой части перевода статьи О’Рейли. Главным в этой заметке является попытка определения понятия «вычисления в облаках» через совокупность пяти ключевых признаков, характеризующих эту технологию: Виртуальность, Выделенность, Эластичность/Динамичность, Отчуждённость и Оплата по факту.
Итак:
Закон сохранения заманчивой прибыли в Облаках (перевод 2-й части статьи)
Послесловие переводчика с попыткой определения Облаков
Персональные блоги → О’Рейли, Майкрософт и другие о вычислениях в облаках
Похоже, что, действительно вычислениям в облаках (cloud computing) уготована судьба электрификации 21-го века. Исследователи Gartner назвали это направление вторым в списке тех, которые будут наиболее бурно развиваться в следующем году. А если учесть, что вычисления в облаках является, по сути дела, составной частью более общей концепции виртуализации, которая заняло первое место в этом списке, то и «Облака» вполне можно рассматривать как первое перспективное направление.