Весьма интересный пост, опубликованный недавно на Хабре, и особенно комментарии к нему подтолкнули меня к описанию, пожалуй, единственной симметричной схемы, действительно обеспечивающей страховку от кражи базы паролей с сервера – схемы Лэмпорта («Lamport hash chain»). Алгоритм на самом деле чрезвычайно прост и предложен автором (L.Lamport) еще в 1981 году. Более того, схема в большинстве учебников уже упоминается как «устаревшая», т.к. целью ее разработки была в первую очередь защита от перехвата пароля на этапе передачи, а появившиеся позднее схемы семейства «challenge-handshake» (CHAP, CRAM) решают эту задачу гораздо более эффективно. А вот о втором интересном свойстве схемы Лэмпорта уже потихоньку забыли – она не требует конфиденциальности аутентификационных данных пользователей, хранимых на серверной стороне (свойство, обычно присущее только асимметричным схемам с сертификатам клиентов). Посмотрим, как можно достичь этого свойства с помощью одной только криптостойкой хеш-функции.
Алексей @Scratch
Системный архитектор, криптоманьяк
Руководство АНБ по безопасной конфигурации Linux-сервера
1 мин
18KАгентство по национальной безопасности США опубликовало новую версию 200-страничного руководства (PDF) по безопасной конфигурации Red Hat Enterprise Linux 5. Это весьма подробный мануал, который объясняет принципы защищённой системы и на практике указывает все необходимые настройки и перечень сервисов, которые обязательно нужно отключить (это один из базовых принципов: минимизировать количество софта).
Есть и что-то вроде шпаргалки на листе A4, тоже очень удобно.
Есть и что-то вроде шпаргалки на листе A4, тоже очень удобно.
+112
Беззамочные алгоритмы: ненастойчивый кэш
5 мин
2.9KПеревод
(Тот факт, что русского перевода понятию «lock-free» в литературе ещё не устоялось, — нисколько меня не убеждает, что такого перевода не должно быть.)
Предположим, анализ производительности вашего приложения выявил, что существенная часть процессорного времени тратится в некой вычислительной функции, и более того, эта функция многократно вызывается с одними и теми же параметрами — выполняя одинаковые вычисления вновь и вновь. Напрашивается простая оптимизация — кэш из одной записи, в котором бы хранились исходные данные и результат последнего вычисления.
Само собой, этот код потоконебезопасен: если один поток находится внутри вызова
Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем,
Посмотрим, как можно реализовать наш кэш беззамочно.
Предположим, анализ производительности вашего приложения выявил, что существенная часть процессорного времени тратится в некой вычислительной функции, и более того, эта функция многократно вызывается с одними и теми же параметрами — выполняя одинаковые вычисления вновь и вновь. Напрашивается простая оптимизация — кэш из одной записи, в котором бы хранились исходные данные и результат последнего вычисления.
BOOL IsPrime(int n) { static int nLast = 1; static BOOL fLastIsPrime = FALSE; // если значение параметра не изменилось с прошлого раза, // воспользуемся готовым результатом if (n == nLast) return fLastIsPrime; // вычислим и запомним новый результат nLast = n; fLastIsPrime = slow_IsPrime(n); return fLastIsPrime; }
Само собой, этот код потоконебезопасен: если один поток находится внутри вызова
slow_IsPrime()
, то другой поток, вызвавший IsPrime()
, застанет значения переменных nLast
и fLastIsPrime
несоответствующими одно другому.Простое решение — заключить код в критическую секцию; но простота идёт в ущерб производительности: если, скажем,
nLast
= 5, fLastIsPrime
= TRUE, и два потока одновременно вызывают IsPrime(5)
, то совершенно ни к чему им выстраиваться в очередь: ничего не мешает им одновременно воспользоваться кэшированным значением.Посмотрим, как можно реализовать наш кэш беззамочно.
+14
Потоко-безопасная ленивая инициализация в C++
9 мин
13KПеревод
Реймонд Чен написал занятную серию блогпостов о беззамочной синхронизации. Мне бы хотелось опубликовать эти заметки и для хаброчитателей. Данный пост — введение в серию, скомпилированное из трёх старых постов Чена.
Инициализация статических локальных переменных в C++ непотокобезопасна, причём намеренно!
Спецификацией установлено, что статические локальные переменные (в отличие от глобальных) инициализируются при первом выполнении блока кода, в котором они объявлены.
Попытайтесь сами найти рейс-кондишн во фрагменте кода, который вычисляет результат некоторой функции «лениво» — при первом обращении, и затем сохраняет этот результат для последующих обращений.
(Примерно такой код советуют в популярном C++ FAQ, чтобы не зависеть от выбранного компилятором порядка инициализации глобальных статических переменных.)
- Ленивая инициализация встроенными средствами C++
- Беззамочная синхронизация
- Беззамочная потоко-безопасная ленивая инициализация
Ленивая инициализация встроенными средствами C++
Инициализация статических локальных переменных в C++ непотокобезопасна, причём намеренно!
Спецификацией установлено, что статические локальные переменные (в отличие от глобальных) инициализируются при первом выполнении блока кода, в котором они объявлены.
Попытайтесь сами найти рейс-кондишн во фрагменте кода, который вычисляет результат некоторой функции «лениво» — при первом обращении, и затем сохраняет этот результат для последующих обращений.
int ComputeSomething()
{
static int cachedResult = ComputeSomethingSlowly();
return cachedResult;
}
(Примерно такой код советуют в популярном C++ FAQ, чтобы не зависеть от выбранного компилятором порядка инициализации глобальных статических переменных.)
+43
Беззамочные алгоритмы: модель «сделай, запиши,(попытайся снова)»
4 мин
2KПеревод
Реализованное нами в прошлый раз атомарное умножение является примером более общей модели, которую Реймонд назвал «сделай, запиши,(попытайся снова)».
Мы вычисляем новое значение, и затем вызовом
for (;;) { // берём начальное значение общей переменной, // которую мы собираемся изменять oldValue = sharedVariable; ... берём начальные значения других параметров ... newValue = ... вычисляем новое значение, используя oldValue и копии остальных параметров ... // вместо Xxx может быть Acquire, Release, или ничего if (InterlockedCompareExchangeXxx( &sharedVariable, newValue, oldValue) == oldValue) { break; // запись удалась } ... удаляем newValue ... } // попытаемся снова
Мы вычисляем новое значение, и затем вызовом
InterlockedCompareExchange
записываем его в общую переменную только в том случае, если её значение не изменялось. Если оно изменилось, значит другой поток нас опередил; в этом случае попытаемся выполнить операцию по-новой, с самого начала, — в надежде, что в следующий раз никто нас не «подрежет».+22
Преимущества безблокировочного алгоритма — не только и не столько в производительности
6 мин
2.7KПеревод
Рассчитываю, что заключительный пост серии — в отличие от трёх предыдущих, оказавшихся, по-видимому, чересчур хардкорными — вызовет у хабрапублики не только филологический интерес.
Один из комментаторов серии постов Чена про безблокировочные алгоритмы поинтересовался, в каких условиях эти более сложные алгоритмы существенно превосходят по производительности такие простые примитивы блокировки, как критические секции.
Он совершенно прав, что переход от простого алгоритма к сложному должен быть оправдан замерами производительности: если простой алгоритм удовлетворительно справляется со своей задачей, то нечего искать добра от добра.
Но преимущества безблокировочной синхронизации не сводятся лишь к улучшенной, по сравнению с привычными примитивами блокировки, производительности. (Далее в этом посте мы увидим, как можно получить эти неочевидные преимущества, не переходя на полностью безблокировочную синхронизацию.)
Один из комментаторов серии постов Чена про безблокировочные алгоритмы поинтересовался, в каких условиях эти более сложные алгоритмы существенно превосходят по производительности такие простые примитивы блокировки, как критические секции.
Он совершенно прав, что переход от простого алгоритма к сложному должен быть оправдан замерами производительности: если простой алгоритм удовлетворительно справляется со своей задачей, то нечего искать добра от добра.
Но преимущества безблокировочной синхронизации не сводятся лишь к улучшенной, по сравнению с привычными примитивами блокировки, производительности. (Далее в этом посте мы увидим, как можно получить эти неочевидные преимущества, не переходя на полностью безблокировочную синхронизацию.)
+18
Быстрое умножение многочленов при помощи преобразования Фурье — это просто
9 мин
79KДобрый вечер.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
Этот пост посвящён быстрому преобразованию Фурье. Будут рассмотрены прямое и обратное преобразования (в комплексных числах). В следующей части я планирую рассмотреть их применения в некоторых задачах олимпиадного программирования (в частности, одна задача про «похожесть» строк), а также рассказать про реализацию преобразования в целых числах.
БПФ — это алгоритм, вычисляющий значения многочлена степени n=2k в некоторых n точках за время O(n⋅logn) («наивный» метод выполняет ту же задачу за время O(n2)). За то же время можно выполнить и обратное преобразование. Так как складывать, вычитать и умножать массивы чисел гораздо легче, чем многочлены (особенно умножать), БПФ часто применяется для ускорения вычислений с многочленами и длинными числами.
+98
Spring Remoting — Spring + RMI
4 мин
16KSpring Remoting
Spring framework предоставляет обширные возможности по созданию распределенных приложений. Он не только помогает создавать удаленные службы, но и упрощает доступ к ним. На данный момент в с помощью фреймворка можно организовывать удаленный доступ с помощью большого количества технологий — Caucho’s Hessian и Burlap, собственная реализация удаленного доступа через HTTP, RMI и т.д. Под катом краткий обзор возможностей фреймворка Spring для создания распределенных приложений с помощью RMI.
Spring framework предоставляет обширные возможности по созданию распределенных приложений. Он не только помогает создавать удаленные службы, но и упрощает доступ к ним. На данный момент в с помощью фреймворка можно организовывать удаленный доступ с помощью большого количества технологий — Caucho’s Hessian и Burlap, собственная реализация удаленного доступа через HTTP, RMI и т.д. Под катом краткий обзор возможностей фреймворка Spring для создания распределенных приложений с помощью RMI.
+24
Улучшаем интерфейс Java-приложения
27 мин
99KТуториал
![](https://habrastorage.org/storage/f819d4de/cd76ab22/c4830063/a6efd941.png)
Достаточно много различной раздробленной информации существует на тему работы со Swing и графикой в просторах интернета, а также на тему интерфейсов Java-приложений. Кто-то твердит о том, что Java морально устарела и десктоп-приложения на Java не имеет смысла писать, кто-то с пеной у рта доказывает обратное. В то же время работа идет, приложения пишутся и встают очередные проблемы. В предыдущей статье я уже привел небольшой список полезных библиотек для исключительных случаев, но нередко бывает так, что никакая сторонняя библиотека не позволяет сделать то, что Вам нужно. Именно в такой момент стоит задуматься о возможной необходимости написания своих компонентов.
Итак, в данном посте я постарался изложить самые важные и значимые на мой взгляд моменты по работе со Swing и графикой — как создавать компоненты, как стилизовать интерфейс, чего делать не стоит и многое другое…
+108
Расширяем возможности Java-приложения
11 мин
19KЗдраствуй, Хабражитель!
Вот уже несколько лет проработав над разными десктопными Java-приложениями и в очередной раз копаясь в своих залежах полезных библиотек я понял, что настал момент немного структурировать всю накопившуюся коллекцию и выкинуть лишнее. Заодно, захотелось выделить из нее наиболее редкие экземпляры и дописать небольшие пояснения к ним (что, где и как работает), чтобы при необходимости быстро и легко использовать нужную часть. Собственно информацией о некоторых особо выделяющихся библиотеках из коллекции мне и захотелось поделиться с Вами — вдруг кому-то это окажется интересным или даже полезным.
Итак, сегодня я приведу здесь библиотеки, которые могут Вам помочь решить часто возникающие вопросы вроде «Как сделать это на Java?» по разным узким направлениям разработки.
Сразу скажу, что большая часть приведенных в статье библиотек использует нативные средства, для реализации того или иного функционала. Но это совсем не значит, что от них сразу нужно отказаться. Впрочем, не буду разводить холивар и сразу перейду непосредственно к теме...
Вот уже несколько лет проработав над разными десктопными Java-приложениями и в очередной раз копаясь в своих залежах полезных библиотек я понял, что настал момент немного структурировать всю накопившуюся коллекцию и выкинуть лишнее. Заодно, захотелось выделить из нее наиболее редкие экземпляры и дописать небольшие пояснения к ним (что, где и как работает), чтобы при необходимости быстро и легко использовать нужную часть. Собственно информацией о некоторых особо выделяющихся библиотеках из коллекции мне и захотелось поделиться с Вами — вдруг кому-то это окажется интересным или даже полезным.
Итак, сегодня я приведу здесь библиотеки, которые могут Вам помочь решить часто возникающие вопросы вроде «Как сделать это на Java?» по разным узким направлениям разработки.
Сразу скажу, что большая часть приведенных в статье библиотек использует нативные средства, для реализации того или иного функционала. Но это совсем не значит, что от них сразу нужно отказаться. Впрочем, не буду разводить холивар и сразу перейду непосредственно к теме...
+68
Знакомство с АОП
10 мин
128KПарадигмы программирования
В современном мире IT-разработки существует довольно большое множество различных подходов к написанию программ. Так, например, кому-то нравиться представлять программу в виде последовательности действий, а кто-то считает, что программа должна представлять собой множество объектов, общающихся друг с другом. Совокупности этих идей и понятий образуют своего рода стиль написания программы, который принято назвать – парадигма программирования.
У каждой парадигмы есть свои особенности, однако, главным фактором, различающим их, является понятие основной единицы программы. Вот самые популярные из них:
- инструкция (императивное программирование, FORTRAN/C/PHP),
- функция (функциональное программирование, Haskell/Lisp/F#/Scala),
- прототип (прототипное программирование, JavaScript),
- объект (объектно-ориентированное программирование, С++/Java),
- факт (логическое программирование, PROLOG).
Стоит заметить, что в общем случае язык программирования однозначно не определяет используемую парадигму: на том же PHP можно писать как императивные, так и объектно-ориентированные программы.
В этой статье я хочу рассказать о сравнительно молодой, но крайне, на мой взгляд, полезной парадигме программирования – аспектно-ориентированном программировании.
+97
Двадцать вопросов, которые помогают разработать алгоритм
5 мин
8KКак разработать алгоритм, решающий сложную задачу? Многие считают, что для этого нужно «испытать озарение», что процесс этот не вполне рационален и зависит от творческой силы или таланта.
На самом деле решение любой задачи сводится к сбору информации о наблюдаемом объекте. Причем этот принцип применим как для решения самых сложных научно-исследовательских задач, так и для решения прикладных задач. Работа изобретателя напоминает не столько работу волшебника, сколько путешествие первооткрывателя по неизведанной территории. Главное качество хорошего изобретателя – умение собирать информацию.
Если вы хотите решить сложную задачу, собирайте информацию в самых разных направлениях. Ответив на следующие 20 вопросов, вы легко выстроите план работы над задачей.
На самом деле решение любой задачи сводится к сбору информации о наблюдаемом объекте. Причем этот принцип применим как для решения самых сложных научно-исследовательских задач, так и для решения прикладных задач. Работа изобретателя напоминает не столько работу волшебника, сколько путешествие первооткрывателя по неизведанной территории. Главное качество хорошего изобретателя – умение собирать информацию.
Если вы хотите решить сложную задачу, собирайте информацию в самых разных направлениях. Ответив на следующие 20 вопросов, вы легко выстроите план работы над задачей.
+67
Как не надо писать факториал в Java
10 мин
104KПеревод
Перевод этой статьи уже был однажды опубликован на хабре, но там почему-то осталась за кадром самая важная часть. Ниже — полный перевод.
На написание этой статьи меня вдохновила заметка "Как бы вы написали факториал на Java?". Так что извините, я немного поразглагольствую в коде: у меня есть главная мысль, которую я выскажу в конце.
Если вам надо написать факториал на Java, то большинство из ваc, вероятно, начнёт с чего-нибудь
На написание этой статьи меня вдохновила заметка "Как бы вы написали факториал на Java?". Так что извините, я немного поразглагольствую в коде: у меня есть главная мысль, которую я выскажу в конце.
Если вам надо написать факториал на Java, то большинство из ваc, вероятно, начнёт с чего-нибудь
+129
Динамическое программирование. Классические задачи
8 мин
326KЗдравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.
Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.
Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.
Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Во многих олимпиадных задачах по программированию решение с помощью рекурсии или полного перебора требует выполнения очень большого числа операций. Попытка решить такие задачи, например, полным перебором, приводит к превышению времени выполнения.
Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.
Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
+89
Организация SSH-доступа по одноразовым паролям
4 мин
7KВ любой серьезной компании иногда возникает необходимость в том, чтобы сотрудник, уехавший в отпуск, срочно выполнил свои должностные обязанности. Рассмотрим ситуацию, когда компании необходим конкретный сотрудник, например, системный администратор, который в данный момент возлежит на пляже в тысяче километров от душного офиса. Допустим даже, что этот сотрудник согласен выполнить неожиданно свалившуюся ему на голову работу и на курорте есть интернет-кафе. Но вот проблема: кафе располагается в темном переулке, на его компьютерах стоят популярная ОС, трояны, кейлоггеры и прочие хактулзы, так что набирать пароль root'а от главного сервера компании на подобных машинах довольно неразумно.
Существует несколько решений этой задачи. Например, можно использовать одноразовые пароли, а именно систему s/key, использующую для генерации паролей алгоритмы md4 и md5. Об этой системе и будет рассказано далее.
Существует несколько решений этой задачи. Например, можно использовать одноразовые пароли, а именно систему s/key, использующую для генерации паролей алгоритмы md4 и md5. Об этой системе и будет рассказано далее.
+91
Информация
- В рейтинге
- Не участвует
- Зарегистрирован
- Активность