Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.

Работа уникальная, в своём роде, потому что в этом случае графическое отображение особенно сложно сделать: ведь, по сути, нет данных для анализа. «Но алгоритмы также демонстрируют, что визуализация — это больше, чем просто инструмент для поиска закономерностей среди данных, — пишет Майк Босток. — Визуализация использует зрительную систему человека, чтобы расширить человеческий интеллект: с её помощью мы лучше понимаем важные абстрактные процессы и, надеюсь, другие вещи тоже».

Проще говоря, зрение помогает нам думать.

Хожу по job interview. Где-то скучно, где-то весело. Где-то интересно. На одном из таких меня попросили написать функцию, которая умеет складывать два числа. Я написал:

  it ('should add two numbers', function () {
    var add = function (a,b) {
      return a + b;
    };

    assert.equal(add(2,3), 5);
  });

А если, говорят, сигнатура функции должна быть типа такой: add(num1)(num2)? Не вопрос, говорю. Думая, что хитрый буржуин хочет проверить, знаю ли я про то, что можно возвращать функции из функций, пишу вот такое:

  it ('should be called like add(num1)(num2)', function () {
    var add = function (a) {
      return function (b) {
        return a + b;
      };
    };

    assert.equal(add(2)(3), 5);
  });

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

Если коротко, то «потому что могут». И т.к. стек «дёшев» мы располагаем их на стеке, когда только это возможно.

Длинный ответ он … длинный.

Какое-то время назад я писал о том, что «ссылки» — это не «адреса», когда речь идёт о C# и размещении его объектов в памяти. Хотя это действительно так, но это всего лишь деталь реализации, но не смысл «ссылки». Другая деталь реализации, которую часто путают с сутью — это то, что «память под значимые типы (value types) выделяется на стеке». Я часто это вижу, потому что именно так написано в нашей документации.

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

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

Интро

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

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

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

Приветствую!

Продолжу серию постов посвященных программированию, на этот раз я хочу поговорить на тему сетевого взаимодействие посредством TCP соединения между .Net приложениями. Статья может быть полезна новичкам или тем кто еще не сталкивался с сетью по отношению к .Net. Полностью работоспособный пример прилагается: http://yadi.sk/d/1OxmAFuCN3kmc.

Подробности под катом.

Сколько раз вы испытывали проблемы с производительностью SQL Server'а и решали, куда именно смотреть?

Одна из самых редко используемых методологий устранения проблем с производительностью SQL Server'а называется «Ожидания и очереди» (также известная как «статистика ожиданий»). Основная предпосылка методологии состоит в том, что SQL Server постоянно отслеживает, какие потоки выполнения должны ждать. Вы можете запросить у SQL Server'а эту информацию для того чтобы сократить перечень возможных причин проблем с производительностью. «Ожидания» — это то, что отслеживает SQL Server. «Очереди» — это ресурсы, доступ к которым ожидают потоки. Система обычно фиксирует огромное количество ожиданий, и все они означают ожидание доступа к различным ресурсам. Для примера, ожидание PAGEIOLATCH_EX означает, что поток ожидает чтения страницы данных с диска в буферный пул. Ожидание LCK_M_X означает, что поток ожидает возможности наложить эксклюзивную блокировку на что-то.

Отличная новость состоит в том, что SQL Server знает, в чем именно заключаются проблемы с производительностью, и все что вам нужно — это спросить у него… и потом правильно интерпретировать то, что он скажет, что может быть немного сложнее.

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

Когда я изучал События (не в рамках .NET!), потратил много сил, чтобы, наконец-то, разобраться, как они устроены и должны конструироваться. Поэтому, я решил опубликовать свою методику понимания структуры пользовательского события, коим представляется ключевое слово event в С#.
Не буду цитировать и без того замученную MSDN, а постараюсь объяснить понятно и доступно.

Введение

В алгоритмическом трейдинге при создании механических торговых систем (МТС) очень важен вопрос времени жизни торговых алгоритмов. Да, и найти их в принципе достаточно сложно. В условиях постоянно меняющегося рынка рано или поздно наступает момент, когда даже самый совершенный и прибыльный алгоритм начинает приносить убытки. И его нужно, что называется, «подкручивать» или оптимизировать под текущие условия рынка. Одними из самых распространенных являются торговые системы (ТС), работающие со свечными графиками с их многообразием индикаторов для технического анализа.

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

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

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

Ключи

Redis — хранилище данных в формате «ключ-значение». Факты о ключах:

• Ключи в Redis — бинарно-безопасные (binary safe) строки.
• Слишком длинные ключи — плохая идея, не только из-за занимаемой памяти, но так же и в связи с увеличением времени поиска определенного ключа в множестве в связи с дорогостоящим сравнением.
• Хорошая идея — придерживаться схемы при построении ключей: «object-type:id:field».

Типы данных Redis

• Строки (strings). Базовый тип данных Redis. Строки в Redis бинарно-безопасны, могут использоваться так же как числа, ограничены размером 512 Мб.
• Списки (lists). Классические списки строк, упорядоченные в порядке вставки, которая возможна как со стороны головы, так и со стороны хвоста списка. Максимальное количество элементов — 2³² — 1.
• Множества (sets). Множества строк в математическом понимании: не упорядочены, поддерживают операции вставки, проверки вхождения элемента, пересечения и разницы множеств. Максимальное количество элементов — 2³² — 1.
• Хеш-таблицы (hashes). Классические хеш-таблицы или ассоциативные массивы. Максимальное количество пар «ключ-значение» — 2³² — 1.
• Упорядоченные множества (sorted sets). Упорядоченное множество отличается от обычного тем, что его элементы упорядочены по особому параметру «score».

Про типы данных Redis есть отдельная хорошая статья: «Структуры данных, используемые в Redis».

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

На данный момент все рынки автоматизированы. По этой причине какие-то экономические объяснения ценообразования являются некими рудиментами. Рулят алгоритмы + некое ручное вмешательство.

Задача каждого торгового алгоритма всегда одна и та же — принести денег владельцу. Алгоритм тем лучше, чем больше денег он в состоянии принести.

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

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

Не так давно наткнулся на статью о том, как Michael Kozakov не смог решить алгоритмическую задачу на собеседовании в Twitter. Решение этой задачи — почти в чистом виде один из самых стандартных алгоритмов на графах, а именно, алгоритм Дейкстры.
В этой статье я постараюсь рассказать алгоритм Дейкстры на примере решения этой задачи в несколько усложненном виде. Всех, кому интересно, прошу под кат.

От переводчика. Судя по своему опыту, а также по опыту знакомых коллег-программистов, могу сказать, что для начинающего разработчика среди всех базовых функций языка C# и платформы .NET делегаты и события являются одними из наиболее сложных. Возможно, это из-за того, что необходимость делегатов и событий на первый взгляд кажется неочевидной, или же из-за некоторой путаницы в терминах. Поэтому я решил перевести статью Джона Скита, рассказывающую о делегатах и событиях на самом базовом уровне, «на пальцах». Она идеальна для тех, кто знаком с C#/.NET, однако испытывает затруднение в понимании делегатов и событий.

Представленный здесь перевод является вольным. Однако если под «вольным», как правило, понимают сокращённый перевод, с упущениями, упрощениями и пересказами, то здесь всё наоборот. Данный перевод является немного расширенной, уточнённой и обновлённой версией оригинала. Я выражаю огромную благодарность Сергею Теплякову aka SergeyT, который внёс неоценимый вклад в перевод и оформление данной статьи.

Люди часто испытывают затруднения в понимании различий между событиями и делегатами. И C# ещё больше запутывает ситуацию, так как позволяет объявлять field-like события, которые автоматически преобразуются в переменную делегата с таким же самым именем. Эта статья призвана прояснить данный вопрос. Ещё одним моментом является путаница с термином «делегат», который имеет несколько значений. Иногда его используют для обозначения типа делегата (delegate type), а иногда — для обозначения экземпляра делегата (delegate instance). Чтобы избежать путаницы, я буду явно использовать эти термины — тип делегата и экземпляр делегата, а когда буду использовать слово «делегат» — значит, я говорю о них в самом широком смысле.

Некоторое время назад, я решил, что хочу знать больше подробностей о работе многопоточности в .NET и что я уделял этому незаслуженно мало внимания в прошлом. Информации на эту тему великое множество (отправной точкой я для себя выбрал этот раздел книги «C# in a nutshell»), но, как оказалось, только малая часть ресурсов пытаются объяснить что-то в деталях.

Каждый мастер должен знать свои инструменты, а что может использоваться чаще коллекций? Поэтому я решил сделать небольшой обзор многопоточных коллекций и начать с ConcurrentDictionary (беглый обзор уже встречался здесь, но его там совсем мало). Вообще, я несколько удивился, что такой статьи для .NET еще нет (зато хватает по Java).

Итак, поехали.

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

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

Оптимальная сортировка

Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n² ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

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

Количество ложно-положительных срабатываний фильтра Блума.

Описание

Фильтр Блума — это рандомизированная структура данных для запросов, разработанная Бёртоном Блумом в 1970 году. Фильтр Блума даёт ошибочный ответ на запрос, т.н. ложно-положитеное срабатывание. Т.е. если мы добавляем некоторый элемент, то существует отличная от нуля вероятность, что фильтр Блума вернет ответ что элемент находится в векторе, хотя его там нет.

Грубо говоря, фильтр Блума возвращает 2 возможных ответа:

1. элемента нет в векторе
2. элемент возможно есть в векторе

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

Многие из Вас наверняка читали в далеком 2007-ом, увлекательную статью пользователя ACiD — The Scene — настоящий андеграунд Интернета, и судя по комментариям, некоторые даже посмотрели указанный в статье сериал The Scene в оригинале. Для тех кто не вкурсе, или забыл, немного информации.

Сцена — веб-сериал, созданный Jun Group Entertainment в 2004-2006гг. Первый в своем роде фильме действие которого происходит на экране компьютеров его героев, где мы видим, как они общаются в чате.

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

Недавно я наткнулся на этот сериал на рутрекере, подумав что его перевели с субтитрами или голосом как множество других шоу. Но все оказалось намного интересней: Пользователю под ником ID-Daemon ценой невероятных усилий за полгода, удалось практически вручную отрисовать первую серию. На данный момент полностью русифицировано 12 из 20 серий первого из двух сезонов.

Русская версия шоу предоставлена полной заменой анимации и синхронизации диалогов в чатах, текста писем, и некоторых ключевых частей интерфейса Windows XP. Также была полностью озвучена Речь.



Под катом ссылки на раздачи, Рецензия, Саундтрек, а также полная история пользователя ID-Daemon связанная с этим сериалом, которой он сопровождает свои релизы, в попытках популяризовать это не стандартное для обычных людей шоу и получить право публикации сериала в разделе Сериалы. На данный момент шоу расположено в ветке Rutracker.org » Разное » Разное » Видео

Продолжение.
Предыдущие части: 1-3, 4-6, 7-9, 10-13
Продолжение. Каскадное удаление данных.

14. Другой пример: база данных интернет-магазина.

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

Система интернет-магазина.

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

• Отображение товаров
• Классификация товаров
• Регистрация клиентов
• Добавление товаров в корзину покупок
• Отображение содержимого корзины покупок
• Оформление заказов посетителями
• И т.д.

Определяем сущности и отношения.

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