Java, Scala, .NET, Lisp, Python, IDE's, Hibernate, MATLAB, Mathematica, Physics & Other

суббота, 29 августа 2009 г.

Что делает функцию разделения строки split в джаве такой "уникальной"

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

Посмотрим на пример написанный на Python:

s = ',1,,2,,'
tokens = s.split(',')
print('start')
for token in tokens:
print(token)
print('end')
_Winnie Colorizer


Выполняем.. вывод:
start

1

2


end

Все четко и предсказуемо. На стыке разделителей считается что находится пустая строка.

Теперь посмотрим пример на C#:

String[] tokens = ",1,,2,,".Split(new []{','});
Console.WriteLine("start");
for (int i = 0; i < tokens.Length; ++i )
{
Console.WriteLine(tokens[i]);
}
Console.WriteLine("end");
_Winnie Colorizer


Вывод аналогичен:
start

1

2


end

Ок, значит если я сейчас напишу код на java

String[] tokens = ",1,,2,,".split(",");
System.out.println("start");
for (int i = 0; i < tokens.length; ++i)
{
System.out.println(tokens[i]);
}
System.out.println("end");
_Winnie Colorizer


то можно с полной уверенность ожидать что вывод будет точно таким же. Ага.. Как же - черта с два!

start

1

2
end

Вот таким образом. Стоящие подряд разделители в конце строки почему-то полностью игнорируются.
Джавадок говорит следующее:
This method works as if by invoking the two-argument split method with the given expression and a limit argument of zero. Trailing empty strings are therefore not included in the resulting array.

Опять не понятно - с чего вдруг "empty strings are therefore not included in the resulting array". Ситуацию проясняет только джавадок к методу:
public String[] split(String regex, int limit)

...
The limit parameter controls the number of times the pattern is applied and therefore affects the length of the resulting array. If the limit n is greater than zero then the pattern will be applied at most n - 1 times, the array's length will be no greater than n, and the array's last entry will contain all input beyond the last matched delimiter. If n is non-positive then the pattern will be applied as many times as possible and the array can have any length. If n is zero then the pattern will be applied as many times as possible, the array can have any length, and trailing empty strings will be discarded.
...

Как жаль. А мне было сначала показалось что я нашел багу.. Оказалось просто такая вот дурацкая особенность, которую надо иметь в виду.

понедельник, 24 августа 2009 г.

Коварный Hibernate или проблемма @OneToOne(targetEntity = SomeAbstractEntityClass, fetch = FetchType.LAZY)

Как известно хибернет умеет загружать сущности по асоциации OneToOne ленивым образом.
Для этого нужно указать в аннотации @OneToOne что fetch = FetchType.LAZY. Что это дает?
А то что очень часто когда мы достаем некоторую сущность из базы, нам не нужны сущности прилинкованные к ней. Тогда и вытаскивать их из базы нет смысла. Вот как раз FetchType.LAZY дает то, что прилинкованная по OneToOne сущность подгружается только тогда когда мы начинаем обращаться к полям этой сущности. Полезная штука.. НО! Совсем недавно натолкнулся на совершенно невероятную на первый взгляд вещь..

Покажу на примере.
Пусть у нас имеются такие сущности:

AbstractWeapon implements IWeapon - абстрактное оружие.
Sword extends AbstractWeapon implements ISword - меч.
Bow extends AbstractWeapon implements IBow - лук.
Интерфейсы ISward и IBow наследуются от IWeapon.

Warrior - воин. Который владеет неким "абстрактным" оружием:
@OneToOne(targetEntity = AbstractWeapon.class, fetch = FetchType.LAZY)
@JoinColumn(name = "wr_wp_aa")
public IWeapon getWeapon()
.....

И предположим что у воина есть метод, который по типу оружия определяет к какому классу отнести воина.
Если это меч то - мечник, если лук то соответственно - лучник.

   public WarriorType getType()
{
WarriorType type;

if (weapon instanceof ISword)
{
type = WarriorType.SWORDSMAN;
}
else if (weapon instanceof IBow)
{
type = WarriorType.ARCHER;
}
else
{
throw new IllegalStateException("incorrect type of weapon: " + weapon);
}

return type;
}
_Winnie Colorizer


Теперь сохраняем в базу данных одно оружие - меч, и одного воина - который владеет этоим мечем. А теперь внимание вопрос: что будет если сейчас вытащить этого воина средствами хибернета, и попробовать узнать его тип, вызвав метод getType?

Вы было подумали что метод вернет WarriorType.SWORDSMAN? Увы, вынужден вас огорчить, но вы жестоко ошиблись.. Метод кинет исключение IllegalStateException.

Начинаем дебажить и выясняем всю правду:
weapon на самом деле не Sword, а обьект некого таинственного типа AbstractWeapon_$_javassist_1. Смотрим внимательнее, и видим что дерево наследования у AbstractWeapon_$_javassist_1 имеет примерно такой вид:

com.greentea.relaxation.serverplays.shp.business.weapons.AbstractWeapon_$$_javassist_1
extends
com.greentea.relaxation.serverplays.shp.business.weapons.AbstractWeapon
extends
com.greentea.relaxation.serverplays.shp.business.AbstractEntity
implements
com.greentea.relaxation.serverplays.shp.business.IEntity
implements
com.greentea.relaxation.serverplays.shp.business.weapons.IWeapon
extends
com.greentea.relaxation.serverplays.shp.business.IEntity
implements
org.hibernate.proxy.HibernateProxy
extends
java.io.Serializable
javassist.util.proxy.ProxyObject

Нигде! Как вы видите - нигде, нету в этом дереве типа Sword. Итак, выясняется что weapon это прокси
(реализует интерфейсы org.hibernate.proxy.HibernateProxy и javassist.util.proxy.ProxyObject) для
класса AbstractWeapon. И никаким образом в рантайме честно узнать подтип по instanceof или привести к одному из типов производных от AbstractWeapon не получится..

Существуют конечно обходные пути, например:
- Метод Hibernate.getClass - вернет тип Sword.
- Сам пример немножко надуманный, и можно было бы реализовать getType по другому.
- Также можно вообще радикально решить проблемму отказавшись от LAZY.

Мне кажется что Hibernate делает прокси не совсем правильно. По логике, он даже в случае с LAZY мог бы вначале вытащить DiscriminatorValue из таблицы, определить тип, и сделать свое прокси уже от реального производного типа, т.е. от Sword, а не от абстрактного AbstractWeapon. Но вероятно разработчики Hibernate посчитали что если LAZY то LAZY до конца, и один дополнительный запрос - это будет слишком расточительно. Иначе как это еще можно обьяснить.

вторник, 4 августа 2009 г.

Online Judge unit testing

Задачу 1003 Parity не осилил. Зато придумал тест, на котором мой алгоритм валится.

6
9
1 2 odd
3 4 odd
2 5 odd
2 3 even
1 3 even
2 4 odd
2 3 even
4 5 even
2 3 odd
-1

Правильный ответ 5.

Мне чего-то кажется, что задачи Online Judge неплохо решать используя юнит тестирование. Тоесть, после того как прочитали и поняли условие, не кидаемся сразу же писать код! А спокойно пишем сначала юнит тест. Этот тест должен включать как можно больше разнообразных вариаций входных данных: общие случаи, частые случаи, совсем частные случаи... Также этот тест должен проверять время выполнения и используемую память, чтобы в итоге не превысить пределы установленные в условии задачи. Вот написал себе вспомогательный класс на C# 3.5, который в значительной степени облегчает написание таких юнит тестов:

using System;
using System.IO;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace OnlineJudgeUnitTests
{
public abstract class OnlineJudgeProgramTest
{
private static long toBytes(int memoryMB)
{
return memoryMB * 1024 * 1024;
}

private TimeSpan timeLimit;
private long memoryLimit;
private string basePathToDataFiles;

protected OnlineJudgeProgramTest(TimeSpan timeLimit, int memoryLimitMB,
string basePathToDataFiles)
{
this.timeLimit = timeLimit;
memoryLimit = toBytes(memoryLimitMB);
this.basePathToDataFiles = basePathToDataFiles;
}

private string ReadOutput(string outputFile)
{
return new StreamReader(outputFile).ReadToEnd();
}

protected void StandardFileIOTest(string inputFile, string outputFile)
{
inputFile = basePathToDataFiles + inputFile;
outputFile = basePathToDataFiles + outputFile;

StringWriter output = new StringWriter();
DateTime testStartTime = DateTime.Now;

ExecuteProgram(new StreamReader(inputFile), output);

Validate(testStartTime, ReadOutput(outputFile), output.ToString());
}

protected void StandardStringTest(string inputStr, string outputStr)
{
StringWriter output = new StringWriter();
StringReader input = new StringReader(inputStr);
DateTime testStartTime = DateTime.Now;

ExecuteProgram(input, output);

Validate(testStartTime, outputStr, output.ToString());
}

private void Validate(DateTime startTime, String expectedOutput, String realOutput)
{
if (expectedOutput != null)
{
Assert.AreEqual(expectedOutput, realOutput, "Wrong answer");
}

Assert.IsTrue(DateTime.Now - startTime < timeLimit, "Time limit exceeded");
Assert.IsTrue(GC.GetTotalMemory(false) < memoryLimit, "Memory limit exceeded");
}

protected abstract void ExecuteProgram(TextReader input, TextWriter output);
}

}
_Winnie Colorizer

Код не большой и понятный поэтому объяснять не буду. Чтобы скомпилировать его, вам потребуется сборка Microsoft.VisualStudio.QualityTools.UnitTestFramework.

Итак, достаточно всего лишь унаследовать ваш юнит тест от класса OnlineJudgeProgramTest и реализовать метод ExecuteProgram. После чего тест на входном файле PARITY.in и выходном файле PARITY.out будет выглядеть вот так:

      [TestMethod]
public void TestCase4()
{
StandardFileIOTest("PARITY.in", "PARITY.out");
}
_Winnie Colorizer

Не сложно, правда?
Или, если данные для теста генерируются каким-то хитрым образом, то можно воспользоваться методом StandardStringTest:

      [TestMethod]
public void TestCase5()
{
StandardStringTest(CreateSpecialInput(maxArraySize, maxRulesCount), "5000");
}
_Winnie Colorizer

суббота, 1 августа 2009 г.

Online Judge

Прикольный ресурс http://acm.timus.ru/ где можно пописать всякие мощные алгоритмы. Принцип простой: регистрируемся, берем задачу, решаем, ответ - в виде исходного кода постим прямо на форму в сайте, этот код у них компилируется, выполняется, и уже через несколько секунд выносится вердикт - удовлетворяет ли решение требованиям или нет. А требований 3: правильность решения, используемая память, время выполнения.

Можно писать на: java 1.6, C# 3.5, C++, C, Pascal.

Застрял на задаче 1003. Parity. Пишет ошибку что мое решение (на C#) некорректно, т.е. wrong answer. А в чем некорректно, неизвестно.. Написал уже кучу тестов, все возможные варианты кажется перебрал, и даже скачивал какие-то тесты с архива timus - не помогает.

Постоянные читатели