Разбор алгоритма быстрого преобразования фурье (он же Fast Fourier transform, он же FFT).
Целью публикации является отобразить суть алгоритма, а не создание быстрой по скорости работы реализации.
Т.к. в этой программе я буду интенсивно использовать объекты вместо примитивных типов, а также рекурсию,
скорость работы будет заведомо уступать многим другим реализациям FFT, которые можно сейчас найти
в интернете в огромном количестве в открытом доступе.
(далее…)
Для простоты текста заменил System.out.printf() на printf().
%s → String или toString().
printf("Hello %s!", "World"); // "Hello World!"
%n → Перенос строки.
%d → В десятеричном.
%x → В шестнадцатеричном.
%7d → В десятеричном. Минимальная ширина строки 7 знаков.
printf("%7d", 1); // " 1"
%07d → Минимальная ширина строки 7 знаков. Начало забить нулями.
printf("%07d", 1); // "0000001"
%f → Десятичное число с точкой.
%e → Десятичное число с точкой и экспонентой.
%.10f → С точностью 10 знаков после запятой.
printf("%.10f", Math.PI); // "3,1415926536"
%tF → Дата в формате “год-месяц-день”.
printf("%tF", new Date()); // "2011-01-27"
%tT → Время в формате “час:минута:секунда”.
printf("%tT", new Date()); // "22:42:37"
Недавно на досуге решил написать алгоритм КМП (Кнута — Морриса — Пратта) для Scala.
Изначально, мне нужно было решить простенькую задачку – найти последовательность байт в потоке байтов. Сделал на Java. Потом, решил сделать тоже самое на Scala. Занятно, но в стандартной библиотеке коллекций Scala используется именно КМП поиск.
Вот мой вариант.
(далее…)
В целом обработка исключений при работе в GWT через RPC довольно детально описана в разделе документации DevGuideHandlingExceptions
Важный момент на который следуют обратить внимание – throws для метода.
Например, вот Ваш интерфейс:
public interface MyService extends RemoteService {
public String myMethod(String s);
}
Допустим Вы сделали класс MyException который наследуется от RuntimeException. Например, это исключение вы создали для своих прикладных нужд и хотите чтобы оно могло быть перекинуто и обработано на клиенте.
Это конечно удобно, т.к. полученный тип исключений является Unchecked Exception. Таким образом его не нужно явно декларировать, оно может произойти где угодно (не надо прописывать везде throws) и такое исключение Вы не обязаны явно отлавливать.
Другими словами, мы же не пишем для каждого метода throws RuntimeException!
Тем не менее, если где-то у Вас в программе произойдет это исключение:
public class MyServiceImpl extends RemoteServiceServlet implements
MyService {
public String myMethod(String s) {
// Do something interesting with 's' here on the server.
if (isError() ) { throw new MyException("ups");
//
return s;
}
}
То это исключение в методе onFailure(Throwable caught) будет передано просто как InvocationException, а не как MyException!
Дело в том, что если заглянуть в реализацию метода обработки вызова RPC-вызовов:
RemoteServiceServlet. processCall() → RPC.invokeAndEncodeResponse() → RPC.encodeResponseForFailure() → RPCServletUtils.isExpectedException()
мы найдем использование следующей конструкции:
Class< ?>[] exceptionsThrown = serviceIntfMethod.getExceptionTypes();
Другими словами, если Вы хотите чтобы Ваше исключение попадало в onFailure(Throwable caught) как MyException, то нужно обязательно декларировать throws, даже если Ваше исключение extends RuntimeException!
В нашем примере это будет выглядеть так:
public interface MyService extends RemoteService {
public String myMethod(String s) throws MyException;
}
Вот такая вроде мелочь, но если ее не знать, могут возникнуть определенные неудобства.
Оригинальная идея взята из поста Gabriel’s software development blog. Статья довольно старая, опубликована еще в прошлом году .
Если коротко:
def √(x:Double)=Math.sqrt(x)
def ∑(r:Range)(f:Int => Int)=r.foldLeft(0)(_+ f(_))
def ∏(r:Range)(f:Int => Int)=r.foldLeft(1)(_* f(_))
val s= ∑(1 to 100)(x=>√(x))
Это обычный Scala код! Выглядит он прикольным, потому что мы используем знакомые всем со школы/института символы. Но как сделать так, чтобы было удобно вводить эти символы для меня было загадкой.
В итоге недавно случайно придумал как это можно сделать просто и удобно средствами IDE, а точнее в NetBeans.
Я вбил все нужные мне символы в Code Templates (Tools → Options → Editor → Code Templates) и сделал два макроса для [Alt+<] = “←” и [Alt+>] = “⇒”.
Как это работает можно посмотреть здесь:
То есть вы вводите например alpha и жмете [Tab], в результате в код вставляется α. Самое главное, это настраивается только для нужного языка (в частности Scala), таким образом это не мешает в работе с другими языками. Также если вы хотите написать просто alpha, без преобразования, вы просто НЕ нажимайте [Tab] и всё!
Самое главное! Исходники должны быть в UTF-8 (ну или другой юникодной кодировке)!
P.S.: На самом деле вбивать весь греческий алфавит довольно скучное занятие, можно найти файл вроде этого:
C:\Documents and Settings\<USER_NAME>\.netbeans\6.9\config\Editors\text\x-scala\CodeTemplates\org-netbeans-modules-editor-settings-CustomCodeTemplates.xml
и сгенерить туда все аббревиатуры.
Вот пример моего файла – CustomCodeTemplates.zip. Внимание! Это только пример, возможно он Вам не подойдет.
Будьте аккуратны, перед обновлением сделайте резервную копию!
Многие знают, что в Scala возможна перегрузка операторов.
К примеру, пусть у нас будет класс – двухмерная точка:
class Point(val x: Double, val y: Double) {
def -(p: Point) = new Point(x-p.x, y-p.y);
def +(p: Point) = new Point(x+p.x, y+p.y);
}
Работать с ней приятно:
val p1 = new Point(2,2);
val p2 = new Point(1,1);
val p = p2 - p1;
Но что делать, если хочется определить унарный минус, т.е. чтобы можно было писать вот так:
val p = new Point(2,2);
val antiP = -p;
Конечно, вы можете попробовать сделать так:
// ТАК ДЕЛАТЬ НЕ НАДО!
def -() = new Point(-x,-y);
Такой код конечно скомпилируется, но тогда и пользоваться им придется следующим образом:
val antiP = p-;
Что же делать? (далее…)
Начинается семестровый курс по выбору МФТИ “Практикум по программированию на Java и Scala”.
Занятия будут проходить по понедельникам в 408 аудитории Лабораторного корпуса МФТИ.
Начало занятий в 17:05.
Цикл for в Scala.
for ( i < - 1 to 10) {
println(i)
}
Что получится в итоге? Здесь все понятно. На консоль будут выведены числа от 1 до 10 включительно.
Как это работает? Здесь немножко сложнее...
Число 1 — это Int, будет неявно преобразован компилятором в тип RichInt.
У RichInt есть метод to(end:Int), который возвращает объект класса Inclusive, который наследуется от класса Range.
Такие объекты замечательны тем, что позволяют нам пробежаться по некоторому диапазону целых чисел с определенным шагом.
То есть наш цикл, аналогичен следующему примеру:
for ( i < - 1.to(10) ) {
println(i)
}
Кстати, если вы хотите увеличить шаг до двух, вы можете воспользоваться методом to(end: Int, step: Int). Например:
for ( i < - 1 to (10,2) ) {
println(i)
}
Идем дальше.
Оператор < - является генератором, который присваивает переменной i по-очереди значения из интервала [1,10] с шагом 1.
Как работает этот генератор для цикла for ?
Согласно спецификации языка, происходит следующее:
The translation scheme is as follows. In a first step, every generator p < -e, where p is not irrefutable (§8.1) for the type of e is replaced by
p < - e.withFilter { case p => true; case _ => false }
Then, the following rules are applied repeatedly until all comprehensions have been
eliminated.
• A for comprehensionfor (p < -e ) yield e0is translated toe.map { case p => e0 }.
• A for loopfor (p < - e ) e0is translated toe.foreach { case p => e0 }.
...
Таким образом наш цикл, преобразуется к виду:
(1 to 10).foreach {
case i => println(i)
}
Где для для каждого i выполняется println(i).
Все просто и без императивщины.
Небольшое объявление
Благодаря моему бывшему шефу в аспирантуре и кафедре информатики МФТИ, в следующем учебном году в осеннем семестре будет преподаваться семестровый курс по выбору “ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ НА JAVA И SCALA”. Кому интересно — приходите.
|
Из всех существующих на момент написания этого поста реализаций шаблона Singleton (одиночка) мне больше всего нравится эта: public class Singleton {
// Private constructor prevents instantiation from other classes
private Singleton() {}
/**
* SingletonHolder is loaded on the first execution of Singleton.getInstance()
* or the first access to SingletonHolder.INSTANCE, not before.
*/
private static class SingletonHolder {
private static final Singleton INSTANCE = new Singleton();
}
public static Singleton getInstance() {
return SingletonHolder.INSTANCE;
}
}
|
Эту реализацию придумал Bill Pugh. Это гениальный и очень простой способ. При помощи элегантного использования внутреннего класса Вы получаете ленивый (объект Singleton не инициализируется до моменты вызова метод getInstance()) и потоко-безопасный Singleton.
Поскольку в классе Singleton нет статических полей которые нужно инициализировать, класс беспрепятственно загрузится. То есть Вам не нужно ждать, пока мы создадим объект Singleton в самом начале, когда загружаются классы.
Смотрим дальше, когда объект INSTANCE будет создан? Тогда, когда мы вызовем метод getInstance(), что повлечет загрузку внутреннего класса SingletonHolder, что спровоцирует создание объекта INSTANCE. Поскольку фаза инициализации класса гарантировано (спецификацией) “не конкурента“, то у нас нет необходимости использовать synchronized и volatile. Ура!
Архитекторы программного обеспечения разговаривают на языке UML. Это такая своеобразная программисткая латынь. Использовать UML напрямую для программирования неудобно, зато многие его понимают и используют для выписывания рецептов описания архитектуры системы. Нарисовал диаграмму классов и стало понятней что к чему. Её поймет и дельфист и жаваист, и сишник и питоньшик, и сишарпер и рубист (вобщем все кто изучал ООП).
Центральное место в UML занимают диаграммы классов. Это букварь. В интернете можно найти огромное количество информации о диаграммах классов (структура, обозначение классов, интерфейсов, атрибутов, отношений и т.д. ), но при этом относительно мало информации о том, как осуществлять сам процесс проектирование. В этой связи хотел обратить внимание читателя на два особых момента.
Самое главное при создании диаграммы классов использовать принцип “от общего к частному”. На самом деле это один из фундаментальных принципов, который великие художники прошлого открыли уже много лет назад.
Представим, что Вы не умеете хорошо рисовать, но вам очень хочется нарисовать например чью-то голову. Вы берете карандаш, кладете лист бумаги и начинаете рисовать его левый глаз. Потратив на этот несчастный левый глаз больше часа, Вы беретесь за нос, затем за правый глаз, ухо и только потом пытаетесь дорисовать все остальное. Вполне вероятно, что итог работы Вас опечалит (не советую показывать жертве результат работы) – глаз, нос, рот и уши будут не на своем месте. Конечно, бывают среди нас гении, у которых получится шедевр, но все-таки, те, кто занимается этим профессионально проповедуют другой подход – “От общего к частному, от частного к общему”. Вначале делается эскиз, “топорный” рисунок. Затем дальнейшая проработка. Например так:
Точно так же я советую поступать в работе с диаграммами классов в UML. Мы создаем эскиз. Выделяем основные классы, определяем отношения между ними, затем прорабатываем мультипликаторы, поля, методы и их область видимости, сигнатуру вызовов, вспомогательные классы и так далее…
Но начинать нужно с формирования набора базовых классов. Для этого нужно просто нарисовать прямоугольники и написать в них имена основных классов. Затем постепенно прорабатывать все остальное.
Например так: