Джед Шмидт, Томас Фухс и Дастин Диаз — достаточно известные в JavaScript-коммьюнити ребята в последнее время нашли себе новую развлекуху — писать полезные штуки размером не больше одного твита, то есть 140 байт. Даже домен зарегали — 140byt.es, куда приглашаются все желающие попробовать свои силы в написании супер-компактных функций.

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

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

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

Все знают Wolfram|Alpha, и наверняка слышали о Wolfram Mathematica. К сожалению, поиск показал отсутствие постов об этой замечательной среде на хабре, и данной статьей хотелось бы открыть серию публикаций посвященных программированию на Mathematica. Для начала стоит сказать о возможностях и особенностях этой системы, которых ой как много, так что запаситесь терпением. Если хабражителей заинтересует этот математический пакет, то обязательно последуют другие статьи, более конкретные, обучающие работе со средой и внутренним языком.

JavaScript 1.8 предоставляет огромное количество вкусного синтаксического сахара, в основном любителями функциональщины. Но очень мало разработчиков знает об этой красоте. Конечно, к сожалению, все эти вкусности не поддерживает даже Chrome (что уж говорить об IE?), а только Firefox 3+, но JavaScript-разработчик просто обязан знать обо всех этих новинках.

Наиболее полную информацию можно найти в статьях на MDN:

• New in JavaScript 1.7
• New in JavaScript 1.8

А я перевела небольшую, но интересную статью Джона Ресига (автора jQuery), который раскрывает в ней некоторые из новых фич: Expression Closures, Generator Expressions, __iterator__, Array Reduce и кое-что ещё:

// Останавливаем выполнение события по-умолчанию
document.addEventListener("click", function() false, true);
// Выводим три сообщения
for ( let i in 3 ) alert( i );
// Создаем массив из 100 элементов, заполненный нулями
[ 0 for ( i in 100 ) ];
// Создаем единичную матрицу 10*10
[[ i == j ? 1 : 0 for ( i in 10 ) ] for ( j in 10 )];

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

>+>+>+>+>++<[>[<+++>-
 >>>>>
 >+>+>+>+>++<[>[<+++>-
   >>>>>
   >+>+>+>+>++<[>[<+++>-
     >>>>>
     >+>+>+>+>++<[>[<+++>-
       >>>>>
       +++[->+++++<]>[-]<
       <<<<<
     ]<<]>[-]
     <<<<<
   ]<<]>[-]
   <<<<<
 ]<<]>[-]
 <<<<<
]<<]>.

Дождались конца выполнения? Согласитесь, что это было не так быстро, как могло показаться сразу. Что ж, давайте посмотрим, как сделать интерпретатор, который будет выполнять данный код не больше чем за несколько секунд.

Любая достаточно сложная технология неотличима от магии
Артур Кларк

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

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

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

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Знаете ли вы что такое рейтрейсер? Это программа которая рисует трёхмерную сцену на экране так, как её бы увидели вы. Конечно, не совсем так, но некоторые рейтрейсеры умеют рисовать очень правдоподобные картинки, например как в "Аватаре".

Идея рейтрейсера очень простая и в этой статье я раcскажу как устроен этот алгоритм и даже напишу его на JavaScript. Картинки и пример прилагаются.

В октябре прошлого года в социальной сети «В контакте» произошел локальный скандал, связанный с неофициальной группой компании «Nokia». К тому моменту группа, созданная в 2007 году, насчитывала уже более миллиона членов и обладала «красивым» доменным именем «nokia.vkontakte.ru». В результате переговоров представителей компании с персоналом социальной сети домен этот перешел под контроль «Нокии», и сейчас там находится уже «официальная» группа. В группе на тот момент было более миллиона членов, и что они все подумали о «Нокии», легко можно себе представить. Вообще, такие непродуманные действия скорее навредили имиджу компании.

Хромая аналогия «Конкуренция» между товарным знаком и доменным именем ведет свое начало еще с тех времен, когда домены не были предусмотрены в российском законодательстве. Однако, практика требовала – и суды начали выносить решения по таким спорам, творя прецеденты в буквальном смысле этого слова, хотя право у нас и не прецедентное. Тем не менее, аналогия между доменом и ТЗ при ближайшем рассмотрении начинает выглядеть ущербной. Для того, чтобы понять, почему это происходит, нужно уяснить себе природу того и другого. Товарный знак представляет собой обозначение, задача которого – идентифицировать определенный товар или услугу. С этим связаны некоторые особенности его использования.

В далекие времена, для IT-индустрии это 70-е годы прошлого века, ученые-математики (так раньше назывались программисты) сражались как Дон-Кихоты в неравном бою с компьютерами, которые тогда были размером с маленькие ветряные мельницы. Задачи ставились серьезные: поиск вражеских подлодок в океане по снимкам с орбиты, расчет баллистики ракет дальнего действия, и прочее. Для их решения компьютер должен оперировать действительными числами, которых, как известно, континуум, тогда как память конечна. Поэтому приходится отображать этот континуум на конечное множество нулей и единиц. В поисках компромисса между скоростью, размером и точностью представления ученые предложили числа с плавающей запятой (или плавающей точкой, если по-буржуйски).

Арифметика с плавающей запятой почему-то считается экзотической областью компьютерных наук, учитывая, что соответствующие типы данных присутствуют в каждом языке программирования. Я сам, если честно, никогда не придавал особого значения компьютерной арифметике, пока решая одну и ту же задачу на CPU и GPU получил разный результат. Оказалось, что в потайных углах этой области скрываются очень любопытные и странные явления: некоммутативность и неассоциативность арифметических операций, ноль со знаком, разность неравных чисел дает ноль, и прочее. Корни этого айсберга уходят глубоко в математику, а я под катом постараюсь обрисовать лишь то, что лежит на поверхности.

После праздником мозги сильно отдохнули и теперь неплохо было бы их размять.
Есть достаточно популярная головоломка: написать программу, которая выводит свой собственный исходный код на произвольном языке программирования. Это развлечение называется куайном.
Что за язык такой этот brainfuck все знают, я думаю.

Предлагаю устроить конкурс куайнов на bf. Я нагуглил 3 варианта + написал свой собственный (чем выиграл бутылку самбуки).
В качестве интерпретатора я использовал http://brainfuck.progopedia.ru.
мой вариант куайна на bf'е под катом

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

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

Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов 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 в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

Больше примеров моноидов, а также где мы их, собственно, применять будем, лежит под катом.

Так собственно выглядит рабочая область:


Можно указать количество точек(от 2 до 13), и перетаскивать любую опорную точку наблюдая в реальном времени как меняется кривая.
Сделано для себя, с целью разобраться с кривыми разного порядка.
Базовые знания почерпнуты отсюда:

Многочлен_Бернштейна
Биномиальный_коэффициент

Можно также почитать про кривую Безье, которая является частным случаем многочлена Бернштейна.

Исходники прилагаются, в архиве также скомпиленный(Win_X86) exe'шник.

Архив с исходниками и exe'шником.
Зеркало
Доработка от Vordigont

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

В данной статье я хочу рассмотреть FileSystem API и File API, разобраться с его методами и показать пару полезных штук. Эта статья является компиляцией материалов с html5rocks (1, 2, 3). Все представленные ниже демки можно посмотреть по первым двум ссылкам. Третья ссылка так же предлагает ряд интересных демо. Ну а теперь займемся изучением материала.

Здравствуйте!

Мы все привыкли пользоваться социальными сетями. Одной из их основ является установление социально значимых связей между пользователями. Как правило, эти связи — дружба или поклонники (последователи).

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

Попробуем пофантазировать на тему социального графа и написать немного Rails кода.

И снова здравствуйте! Сегодня я поведаю о фильтре Блума — структуре данных гениальной в своей простоте. По сути, этот фильтр реализует вероятностное множество всего с двумя операциями: добавление элемента к множеству и проверка принадлежности элемента множеству. Множество вероятностное потому, что последняя операция на вопрос «принадлежит ли этот элемент множеству?» даёт ответ не в форме «да/нет», а в форме «возможно/нет».

Доброго времени суток, хабралюди. Перед Вами самадиогностика безнадёжного BrainFuck больного.
Те, кто всё понял из названия и не хотят читать весь пост целиком могут скачать игру и BFDev и сразу перейти под кат в конец поста к разделу «Как играть». В посте рассказано как я заболел BrainFuck`ом, а также описан процесс создания игры «Морской бой» на этом замечательном языке.

Введение
Как-то стояла задача отсортировать уникальный массив строк с использованием GPU с минимум кода и максимально возможной скоростью…
В данном посте опишу основную идею ее решения. В качестве элементов массива сортировки в данном посте выступают числа.
Случай с уникальными элементами небольшого массива
В качестве платформы была выбрана CUDA по причинам, которые можно считать брэндовыми или индвидуальными. По факту, здесь много примеров именно на CUDA, и она на данный момент получила большее развитие в GPU-вычислениях, чем аналогичные платформы от ATI и OpenCL.
Поиск в сети по алгоритмам сортировки на CUDA дал разные результаты. Вот наиболее интересный. Там есть рисунок

, из которого видно, что наилучший результат дал алгоритм QSORT, который дает сложность порядка от O(NlogN) до O(N^2). И хотя распараллеливание на GPU дало лучший в статье результат, закралось сомнение, что QSORT — не лучший способ использовать ресурсы видеокарты для данной задачи (особенно испугал размер приведенного кода). Далее описывается решение задачи, по сути «в одну строчку» с сложностью временной сложностью O(N) в худшем случае.

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

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.