Pull to refresh
0
0

User

Send message

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

Reading time6 min
Views19K
Всем доброго времени суток!

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

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

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

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

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

Reading time4 min
Views89K

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


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

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

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

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

Reading time10 min
Views174K

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


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

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

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

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

Reading time8 min
Views22K
            Если посадить тысячу мартышек за тысячу пишущих машинок, то за тысячу лет они напишут эмулятор терминала. — вместо эпиграфа.

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

Когда мы только запускали облако, первой проблемой было «как нам получить консоль». Штатный механизм 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, а делать «дзыньк», ибо у пишущих машинок был именно колокольчик, а не спикер.

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

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

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

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

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

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

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

Reading time3 min
Views1.9K
image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример Makefile

Reading time7 min
Views76K
Написание makefile иногда становится головной болью. Однако, если разобраться, все становится на свои места, и написать мощнейший makefile длиной в 40 строк для сколь угодно большого проекта получается быстро и элегантно.

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

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

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

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

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

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

Reading time3 min
Views19K


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

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

Reading time4 min
Views5.2K
Тема образования и 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)…
Читать дальше →

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

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


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

IPython advanced usage

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

Terminal 2014 python 2014 125ճ0image

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

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

Reading time4 min
Views649K

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

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

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

Information

Rating
Does not participate
Registered
Activity