Обновить
0
0

Пользователь

Отправить сообщение

Дерево ван Эмде Боаса

Время на прочтение6 мин
Охват и читатели20K
Всем доброго времени суток!

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

Дерево ван Эмде Боаса (van Emde Boas tree) — ассоциативный массив, который позволяет хранить целые числа в диапазоне [0; U), где U = 2k, проще говоря, числа, состоящие не более чем из k бит. Казалось бы, зачем нужно еще какое-то дерево, да еще позволяющее хранить только целые числа, когда существует множество различных сбалансриованных двоичных деревьев поиска, позволяющих выполнять операции вставки, удаления и прочие за O(log n), где n — количество элементов в дереве?

Главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

Что же там еще есть такого вкусного?

10 способов улучшить свои навыки программирования

Время на прочтение4 мин
Охват и читатели90K

1. Выучить новый язык программирования


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

Среди языков программирования отличный познавательный эффект и наверстывание опыта дают: Lisp (или Scheme), Форт, PostScript или Factor (стековые языки программирования), Haskell (строго типизированный, чистый функциональный язык) либо OCaml (объектно-ориентированный язык функционального программирования), Пролог (логическое программирование), Erlang (отличные паралельные вычисления).

Читать дальше →

Руководство к дескрипторам

Время на прочтение10 мин
Охват и читатели181K

Краткий обзор


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

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

Читать дальше →

Сага о том, как мы писали консоль

Время на прочтение8 мин
Охват и читатели22K
            Если посадить тысячу мартышек за тысячу пишущих машинок, то за тысячу лет они напишут эмулятор терминала. — вместо эпиграфа.

Извините фальстарт, это не я, это андроидный смартбук.

Когда мы только запускали облако, первой проблемой было «как нам получить консоль». Штатный механизм XCP поразумевает, что консоль рисуется с помощью VNCTerm, а желающий её увидеть должен сначала пойти в XenAPI, получить там session-id консоли, пойти на порт консоли, передать session-id, получить RFB, завёрнутый в HTTP, развернуть HTTP, вынуть RFB (он же VNC), отдать её локальному рендереру VNC (VNC-клиенту или java-апплету с тем же функционалом). При этом консоль закрывалась (сессия рвалась) при каждой перезагрузке виртуальной машины. Она рвалась даже при миграции виртуальной машины. Другими словами, это была технология, которая подразумевала «глянул одним глазком, починил ssh/iptables и забыл». Неудобно, медленно, сложно. Выкатывать такое в продакт совсем не хотелось.

И я залез в дебри serial-howto, console-howto и ещё несколько ужасных документов, рассказывающих о том, как правильно нужно конфигуриовать прерывания на ISA плате у мультикарт, а так же специфику настройки linux-2.2 для работы с оными. Параллельно изучалось устройство консоли в зене (внимательный читатель мог даже заметить, когда именно я более-менее разобрался в этом вопросе — я писал на хабре краткий обзор того, что происходит с консолью).

После этого пришла мысль: нужно писать своё, потому что готового чужого хорошего нет.

Сначала мы хотели взять хотя бы готовые компоненты и сделать из них своё. Я помню до сих пор ту замечательную схему, в которой мы планировали сохранять в БД вывод anyterm'а, делать двойное туннелирование последовательного порта с использованием UDP… Выглядело это, мягко скажем, неприглядно.

Потом пришла в голову мысль выпилить anyterm. Для этого нужно было посмотреть, как работают терминалки. Это было очень забавно и поучительно (желающие могут изучить исходный текст PuTTY). Главной проблемой в этом изучении было то, что они много рисуют на экран. Прямо в процессе обработки ввода. Отделить специфику DC от, собственно, того, что является консолью, было сложно.

Через некоторое время мы пришли к идее «нам нужен свой эмулятор терминала».
Задача казалась относительно простой, пока мы не прикоснулись к бездне, именуемой «escape-коды и типы терминалов...».

Пишущие машинки


Итак, в начале была пишущая машинка. В какой-то момент возникло желание совместить телеграф с пишущей машинкой. Так возник телетайп
Разумеется, инженерам, создававшим телетайп, не было никакого резона делать все с нуля. Они просто приделали коды к каждой клавише пишущей машинки. После некоторых боёв в стиле MS VS Netscape, был создан стандарт html5 на коды для оных машинок, то бишь телетайпов. Если мне память не изменяет, то это ASCII, где предусмотрены все комбинации клавиш, характерные для американской пишущей машинки. Включая код BELL, который, кстати, должен вовсе не делать BEEP, а делать «дзыньк», ибо у пишущих машинок был именно колокольчик, а не спикер.

Читать дальше →

Советы читающему человеку

Время на прочтение4 мин
Охват и читатели48K
Все знают что чтение это не простое считывание строчек текста, это сложный психический процесс со своими особенностями и скрытыми возможностями. Позвольте рассказать о парочке таких особенностей — о двух видах чтения, а так же поделиться полезными советами читающему человеку.
Читать дальше →

NumPy, пособие для новичков. Часть 1

Время на прочтение19 мин
Охват и читатели249K
NumPyLogoNumPy — это расширение языка Python, добавляющее поддержку больших многомерных массивов и матриц, вместе с большой библиотекой высокоуровневых математических функций для операций с этими массивами.

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

Pdmenu или как не дать новичку ошибиться

Время на прочтение3 мин
Охват и читатели2K
image

Привет, Хабр!

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

«Категорически отказать!» — скажете вы и будете правы. Но, что делать, если этот человек — ваш босс?
Читать дальше →

PyGTK: потоки и магия обёрток

Время на прочтение9 мин
Охват и читатели6K
Всем хорош GTK+, но наблюдается большая проблема при работе с ним в многопоточных приложениях. Сам по себе GTK является thread-safe, но требуя принудительной блокировки со стороны пользователя. Вторая проблема заключается в том, что блокировка реализована через мутексы, и вы должны вызывать блокировку строго один раз, иначе ваш код «зависнет» на linux, прекрасно при этом работая на windows.
Как бороться?

БД Oracle для программиста

Время на прочтение9 мин
Охват и читатели99K
Нужно ли программисту прикладных приложений понимать как работает БД? Том Кайт, признанный специалист Oracle, автор знаменитой колонки asktom, в своей книге «Oracle для профессионалов. Архитектура и основные особенности.» настаивает, что это просто необходимо. Даже если в вашей команде есть грамотный администратор, знание того, как работает СУБД Oracle поможет вам лучше понимать друг друга и эффективней взаимодействовать, не говоря уже о случае, когда такого специалиста у вас нет. В данном топике я упомяну об основных вещах, понимание которых позволит грамотно работать с БД Oracle и использовать некоторые её особенности с большой отдачей для вашего приложения. Если же вы уже прочитали вышеупомянутую книгу Тома Кайта, то можете просто исползовать эту статью в качестве памятки. Одно замечание — книжку я читал давно, и тогда еще последней версией БД Oracle была 9i, курсы по администрированию я тоже проходил по девятке, так что, если в десятке и выше что-то поменялось и добавилось, то не обессудьте. Хотя я пишу о довольно фундаментальных вещах, которые вряд ли сильно поменяись.
Читать дальше →

LogLog — находим число уникальных элементов

Время на прочтение5 мин
Охват и читатели33K
Здравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.

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

Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.

Кажется невозможным?

Руководство АНБ по безопасной конфигурации Linux-сервера

Время на прочтение1 мин
Охват и читатели18K
Агентство по национальной безопасности США опубликовало новую версию 200-страничного руководства (PDF) по безопасной конфигурации Red Hat Enterprise Linux 5. Это весьма подробный мануал, который объясняет принципы защищённой системы и на практике указывает все необходимые настройки и перечень сервисов, которые обязательно нужно отключить (это один из базовых принципов: минимизировать количество софта).

Есть и что-то вроде шпаргалки на листе A4, тоже очень удобно.
Читать дальше →

Пример Makefile

Время на прочтение7 мин
Охват и читатели77K
Написание makefile иногда становится головной болью. Однако, если разобраться, все становится на свои места, и написать мощнейший makefile длиной в 40 строк для сколь угодно большого проекта получается быстро и элегантно.

Внимание! Предполагаются базовые знания утилиты GNU make.
Читать дальше →

Что такое Protected Mode и с чем его едят

Время на прочтение5 мин
Охват и читатели31K
Для того, чтобы писать операционку, нужно разбираться во многих деталях. Вот давайте я вас немного просвещу, (но давайте договоримся, что маны вы будете читать сами, чтобы было о чём побеседовать).
Честно говоря, на просторах сети есть туча тучная материалов по PM, да и ileyи pehat несколько рассказали об этом режиме, но меня попросили всё равно описать в общих рамках его. Сейчас кратко выдам теорию (вообще то специально для этого Intel маны писала), потом начнём писать код.
Читать дальше →

Быстрое умножение многочленов при помощи преобразования Фурье — это просто

Время на прочтение9 мин
Охват и читатели84K
Добрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Читать дальше →

Выключение монитора горячей клавишей

Время на прочтение3 мин
Охват и читатели20K


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

OpenSource, Windows и образование

Время на прочтение4 мин
Охват и читатели5.3K
Тема образования и OpenSource последнее время очень активно освещается в средствах масс-медиа.
В большинство случаев это очередные сборки Линуксов с малым количеством образовательных программ «из коробки»
Например:
http://www.edubuntu.org/
http://en.opensuse.org/openSUSE:Education-Li-f-e
http://www.altlinux.ru/solutions/state/school/
http://edumandriva.ru/

Но ведь OpenSource это не только GNU/Linux!
Почему не подумают о тех кто приобрел MS Windows официально (по собственному желанию или принудительно в придачу при покупке нового компьютера)?

Одним из решений предлагается Windows OpenPack (Education)…
Читать дальше →

Стань эффективным ИТ-менеджером!

Время на прочтение1 мин
Охват и читатели17K
ITSM (IT Service Management) — это подход к управлению ИТ в организациях. Сей подход придумали британские ученые в Великобритании ещё в прошлом веке! И вот только сегодня мы запускаем бесплатный он-лайн курс по введению в это чудо. Курс состоит из основного блока (4 слайдкаста, раскрывающих основные понятия, термины и концепции), а так же ряда дополнительных материалов. Курс находится в свободном доступе, пройти его можно в любое время. Так же в любое время можно остановиться и продолжить самообразовываться когда душе будет угодно.


Читать дальше →

IPython advanced usage

Время на прочтение4 мин
Охват и читатели14K
Данный инструмент знаком большинству разработчиков на Python.
В тоже время, не так много людей подозревают о раширенных возможностях предоставляемых данной интерактивной оболочкой, пользуясь в основном автодополнением.

Terminal 2014 python 2014 125ճ0image

Статья построенна на выдержках из обширной, понятной и красивой документации ipython.github.com/ipython-doc/dev/interactive/index.html
Пропустим такие явные вещи, как автодополнение и история команд, сохраняемая мыжду вызовами.
Читать дальше →

Команда dd и все, что с ней связано

Время на прочтение4 мин
Охват и читатели697K

В UNIX системах есть одна очень древняя команда, которая называется dd. Она предназначена для того, чтобы что-то куда-то копировать побайтово. На первый взгляд — ничего выдающегося, но если рассмотреть все возможности этого универсального инструмента, то можно выполнять довольно сложные операции без привлечения дополнительного ПО, например: выполнять резервную копию MBR, создавать дампы данных с различных накопителей, зеркалировать носители информации, восстанавливать из резервной копии данные на носители и многое другое, а, при совмещении возможностей dd и поддержке криптографических алгоритмов ядра Linux, можно даже создавать зашифрованные файлы, содержащие в себе целую файловую систему.
Опять же, в заметке я опишу самые часто используемые примеры использования команды, которые очень облегчают работу в UNIX системах.
Читать дальше →

Оптимизируем процесс работы в консоли

Время на прочтение4 мин
Охват и читатели16K
Все привыкли редактировать текст в текстовых редакторах, блокнотах, веб-формах и т.д. В процессе набора текста мы пользуемся привычными стрелками, кнопками «End» и «Home», более опытные зажимают «Ctrl» и стрелками шагают по словам (что, кстати, не всегда работает). И при переходе на консоль мы ориентируемся на те же самые правила, даже не зная, что bash предлагает очень удобные средства и комбинации клавиш, которые очень упрощают работу и минимизируют количество операций для выполнения задачи. К тому же, в bash есть удобные средства работы с историей, масса различных подстановок и других интересных функций. Самые часто используемые мной и любым опытным администратором я и опишу в этой статье.
Читать дальше →

Информация

В рейтинге
Не участвует
Зарегистрирован
Активность