Алгоритмы *

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

Все началось с данного топика на сайте gamedev.ru. Топикстартер предложил найти сортировку, которая обладает следующими свойствами:

1. Время выполнения — гарантированные O(nlogn).
2. Использование O(1) дополнительной памяти.
3. Применимость для сортировки данных в односвязных списках (но не ограничиваясь ими).

Оговорки на все три ограничения:

1. Гарантированные O(nlogn) означают, что, например, среднее время быстрой сортировки не подходит — должно получаться O(nlogn) для любых, даже самых худших входных данных.
2. Рекурсию использовать нельзя, поскольку она подразумевает O(logn) памяти на хранение стека рекурсивных вызовов.
3. Произвольного доступа к элементам сортируемого массива нет, мы можем двигаться итератором от любого элемента только к соседнему (за O(1)), причем только в одном направлении (вперед по списку). Модифицировать сам список (перевешивать указатели на следующие элементы) нельзя.

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

Под катом можно узнать, что в итоге получилось у нас.

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

(возможно вы уже видели эту картинку, хотя странно, что на хабре так мало материалов по квантовой информатике)

Спасибо гениальным инженерам Google, теперь мы все дружно можем превратить наши настольные ПК в квантовые компьютеры. Ну, хорошо, не совсем так: подразумевается лишь моделирование работы квантового компьютера на его младшем собрате путем запуска веб-приложения для Chrome. Quantum Computing Playground позволяет прогонять известные квантовые алгоритмы (такие как алгоритм Гровера, Шора) и писать собственных квантовые программы.

За исключением непосредственного приобретения квантового компьютера — что, несмотря на заявления D-Wave, вряд ли когда-нибудь удастся — решение от Google является наиболее удачным шагом в сторону популяризации квантового зверя. Если хочется лично встать на первую ступеньку вычислений будущего, это тот самый шанс. У вас есть дети? Вы обязаны посадить их в эту песочницу как минимум на шесть часов, чтобы они научились всем тонкостям квантовых вычислений.

Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь (архив, ~5 МБ).

Введение

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

Предположим, что у нас есть несколько последовательных метаграмм, скажем:

мнение-мление-тление-трение-прение-поение-роение-рдение-бдение-биение

они образуют цепь метаграмм, или цепочку слов.

Отсюда проистекает игра под названием цепь слов (word ladder), которую придумал в далеком 1879 году Льюис Кэрролл.

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

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

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

• Введение
• Свойства особых точек
• Детекторы углов
  
  • Moravec
  • Harris
  • Shi-Tomasi
  • Förstner
  • SUSAN
  • Trajkovic
  • FAST
  • CSS
  • Детектор, основанный на глобальных и локальных свойствах кривизны
  • CPDA
• Выводы

Привет, друг! В этот раз я опять подниму вопрос о графике в ААА-играх. Я уже разобрал методику HDRR (не путать с HDRI) тут и чуть-чуть поговорил о коррекции цвета. Сегодня я расскажу, что такое SSLR (так же известная как SSPR, SSR): Screen Space Local Reflections. Кому интересно — под кат.

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

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

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


Этот человек сидит среди ромашек, чтобы привлечь ваше внимание к статье.

Одна из величайших шахматных партий всех времен и народов — это, вне всяких сомнений, сражение Гарри Каспарова и суперкомпьютера Deep Blue от IBM, в 1997 году. Это была уже вторая игра Каспарова с суперкомпьютером, матч-реванш машины.

Первая партия в игре была очень сложной и напряженной, у Каспарова было поначалу преимущество, но, начиная с 44 хода, он перестал понимать логику игры машины, и, в итоге, проиграл весь матч. Спустя некоторое время Каспаров даже обвинил инженеров IBM в «читерстве»: манипуляциях с ПО машины, которые и привели к поражению. Спустя 17 лет ситуация прояснилась — Каспаров проиграл из-за сбоя в алгоритме работы компьютера в самой первой партии всего сражения.

Шёл уже последний час этого воскресенья, я уже думал идти спать, но добрый sourcerer прислал мне картинку с моего заброшенного сайта, которую можно увидеть ниже, и текст «красиво!». Эти картинки я рисовал лет пять назад, с помощью т. н. алгоритма времени убегания, но для применимости данного алгоритма, нужно уметь для заданного набора преобразований разбивать плоскость на регионы, тогда я не придумал, как это сделать, и больше к этому алгоритму не возвращался. Но сейчас я сразу сообразил, что делать, и написал Диме: «Сначала Random IFS, потом kNN, а затем Escape-Time Algorithm!»



Под рукой у меня был только старый нетбук, который мне дали друзья на время, пока мой ноутбук в ремонте. Дима мне ещё что-то говорил, я ему что-то отвечал, но у меня уже в голове писался код, и я искал на нетбуке хоть какой-нибудь компилятор или интерпретатор и нашёл C++ Builder 6! После этого я понял, что утро я встречу наедине с борландовским компилятором. Через пять часов я отправил Диме новых картинок, но он, как нормальный человек, давно спал…

снизу фотографии настоящих жуков, сверху — моя реализация

Продолжение предыдущей статьи, на этот раз пишем шейдер.

Расскажу о различных реализациях эффекта размытия на GLSL.

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

Также, я расскажу, как мы иногда можем существенно облегчить этот процесс, используя уже собранные геномы близкородственных организмов. Этой задачей я занимался в рамках написания своей магистерской диссертации в Санкт-Петербургском Академическом Университете, а обучение проходило совместно с Институтом Биоинформатики. Поскольку получившийся алгоритм достаточно специфичен, я начну с описания проблемы в целом, дам обзор некоторых «хардварных» методов ее решения, а затем немного расскажу о том, что же получилось у меня.

В этой статье предлагаются правила для двумерного клеточного автомата, который, с одной стороны очень похож на игру Жизнь Джона Конвея (Conway’s Game of Life), а с другой — обладает существенными отличиями. Прежде всего, его отличает увеличенное до трех количество состояний клеток, повышенная способность к самоорганизации, неограниченное время активной эволюции и неограниченное количество движущихся конфигураций.

Для стабильных конфигураций новые правила совпадают с правилами игры Жизнь, поэтому все стабильные конфигурации в игре Жизнь существуют и в новых правилах. В описываемом клеточном автомате существует большой класс движущихся конфигураций, космических кораблей. Все эти конфигурации перемещаются по одному и тому же поступательному механизму, который напоминает движение и шагового экскаватора и человека на костылях. Подобные космические корабли я назвал степпер (stepper), а само правило Steppers. Так его и будем называть в дальнейшем.

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


[00] Пример движущейся конфигурации, генерирующей поток степперов

Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


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

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

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

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

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

Ранее система показывала неплохие результаты, но разработчики могли управлять 10-100 роботами одновременно, не более. Теперь команда достигла очередного успеха: самоорганизовать удалось уже более 1000 роботов, если быть точным, то 1024. Сами роботы называются Kilobots (собственно, все логично).

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

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