Один из часто рассматриваемых паттернов — паттерн Builder. В основном рассматриваются варианты реализации «классического» варианта этого паттерна:
MyClass my = MyClass.builder().first(1).second(2.0).third("3").build();
Паттерн прост и понятен как табурет, но чувствуется какая-то недосказанность — то минимальный вариант объявляется антипаттерном, то более сложные случаи игнорируются. Хотелось бы исправить этот момент, рассмотрев предельные случаи и определив минимальную и максимальную границы сложности этого паттерна.
Итак, расссмотрим их:
Минимальный builder или Реабилитация double brace initialization
Сначала рассмотрим минимальный builder, про который часто забывают — double brace initialization (
http://stackoverflow.com/questions/1958636/what-is-double-brace-initialization-in-java, http://c2.com/cgi/wiki?DoubleBraceInitialization). Используя double brace initialization мы можем делать следующее:
new MyClass() {{ first = 1; second = 2.0; third = "3"; }}
Что мы тут видим?
- Нарушение совместимости equalsЧто такое «совместимость equals»? Дело в том что стандартный equals примерно такой:
@Override public boolean equals(Object obj) { if(this == obj) return true; if(!super.equals(obj)) return false; if(getClass() != obj.getClass()) return false; ... }
И при сравнении с унаследованным классом equals будет возвращать false. Но мы создаём анонимный унаследованный класс и вмешиваемся в цепочку наследования.
- Возможная утечка памяти, т.к. анонимный класс будет держать ссылку на контекст создания.
- Инициализация полей без проверок.
Кроме того, таким образом невозможно создавать immutable объекты, так как нельзя использовать final полей.
В результате обычно double brace initialization используют для инициализации составных структур. Например:
new TreeMap<String, Object>() {{ put("first", 1); put(second, 2.0); put("third", "3"); }}
Тут используются методы, а не прямой доступ к полям и совместимость по equals обычно не требуется. Так как же мы можем использовать такой ненадёжный хакоподобный метод? Да очень просто — выделив для double brace initialization отдельный класс билдера.
Код такого билдера содержит только определения полей с установленными значениями по умолчанию и методы построения, отвечающие за проверку параметров и вызов конструкторов:
public static class Builder {
public int first = -1 ;
public double second = Double.NaN;
public String third = null ;
public MyClass create() {
return new MyClass(
first ,
second,
third
);
}
}
Использование:
new MyClass.Builder(){{ first = 1; third = "3"; }}.create()
Что мы получаем?
- Builder не вмешивается в цепочку наследования — это отдельный класс.
- Builder не течёт — его использование прекращается после создания объекта.
- Builder может контролировать параметры — в методе создания объекта.
Voila! Double brace initialization реабилитирована.
Для использовании наследования, Builder разделяется на две части (один с полями, другой — с методом создания) следующим образом:
public class MyBaseClass {
protected static class BuilderImpl {
public int first = -1 ;
public double second = Double.NaN;
public String third = null ;
}
public static class Builder extends BuilderImpl {
public MyBaseClass create() {
return new MyBaseClass(
first ,
second,
third
);
}
}
...
}
public class MyChildClass extends MyBaseClass {
protected static class BuilderImpl extends MyBaseClass.BuilderImpl {
public Object fourth = null;
}
public static class Builder extends BuilderImpl {
public MyChildClass create() {
return new MyChildClass(
first ,
second,
third ,
fourth
);
}
}
...
}
Если нужны обязательные параметры, они будут выглядеть так:
public static class Builder {
public double second = Double.NaN;
public String third = null ;
public MyClass create(int first) {
return new MyClass(
first ,
second,
third
);
}
}
Использование:
new MyClass.Builder(){{ third = "3"; }}.create(1)
Это настолько просто, что можно использовать хоть как построитель параметров функций, например:
String fn = new fn(){{ first = 1; third = "3"; }}.invoke();
Полный код на github.
Перейдём к сложному.
Максимально сложный Mega Builder
А что, собственно, можно усложнить? А вот что! Сделаем Builder, который в compile-time будет:
- не позволять использовать недопустимые комбинации параметров
- не позволять строить объект если не заполнены обязательные параметров
- не допускать повторной инициализации параметров
Что нам понадобится для этого? Для этого нам понадобится создать интерфейсы со всеми вариантами сочетаний параметров, для чего сначала сделем декомпозицию объекта на отдельные интерфейсы соответствующие каждому параметру.
Нам понадобится интерфейс для присвоения каждого параметра и возврата нового билдера. Он должен выглядеть как-то так:
public interface TransitionNAME<T> { T NAME(TYPE v); }
При этом NAME должен быть разным для каждого интерфейса — ведь их потом надо будет объединять.
Также понадобится и getter, чтобы мы могли получить значение после такого присвоения:
public interface GetterNAME { TYPE NAME(); }
Поскольку нам понадобится связка transition-getter, определим transition-интерфейс следующим образом:
public interface TransitionNAME<T extends GetterNAME> { T NAME(TYPE v); }
Это также добавит статического контроля в описаниях.
Примерно понятно, наборы каких интерфейсов мы собираемся перебирать. Определимся теперь, как это сделать.
Возьмём такой же как в предыдущем примере 1-2-3 класс и распишем для начала все сочетания параметров. Получим знакомое бинарное представление:
first second third
- - -
- - +
- + -
- + +
+ - -
+ - +
+ + -
+ + +
Для удобства представим это в виде дерева следующим образом:
first second third
- - - /
+ - - /+
+ + - /+/+
+ + + /+/+/+
+ - + /+/-/+
- + - /-/+
- + + /-/+/+
- - + /-/-/+
Промаркируем допустимые сочетания, например так:
first second third
- - - / *
+ - - /+ *
+ + - /+/+ *
+ + + /+/+/+
+ - + /+/-/+ *
- + - /-/+
- + + /-/+/+ *
- - + /-/-/+ *
Удалим лишние узлы — терминальные недопустимые узлы и пустые узлы. В общем случае это циклический процесс, продолжающийся пока есть узлы для удаления, но в данном случае у нас только один терминальный недопустимый узел.
first second third
- - - / *
+ - - /+ *
+ + - /+/+ *
+ - + /+/-/+ *
- + - /-/+
- + + /-/+/+ *
- - + /-/-/+ *
Как же реализовать это?
Нам нужно, чтобы каждое присвоение элемента приводило к сокращению оставшихся вариантов использования. Для этого каждое присвоение элемента через transition-интерфейс должно возвращать новый класс builder-а плюс getter-интерфейс для этого transition минус этот transition-интерфейс.
Нарисуем интерфейсы:
public interface Get_first { int first (); }
public interface Get_second { double second(); }
public interface Get_third { String third (); }
public interface Trans_first <T extends Get_first > { T first (int first ); }
public interface Trans_second<T extends Get_second> { T second(double second); }
public interface Trans_third <T extends Get_third > { T third (String third ); }
Табличку с этим рисовать неудобно, сократим идентификаторы:
public interface G_1 extends Get_first {}
public interface G_2 extends Get_second{}
public interface G_3 extends Get_third {}
public interface T_1<T extends G_1> extends Trans_first <T> {}
public interface T_2<T extends G_2> extends Trans_second<T> {}
public interface T_3<T extends G_3> extends Trans_third <T> {}
Нарисуем табличку переходов:
public interface B extends T_1<B_1 >, T_2<B_2 >, T_3<B_3 > {} // - - - / *
public interface B_1 extends T_2<B_1_2>, T_3<B_1_3> {} // + - - /+ *
public interface B_1_2 extends {} // + + - /+/+ *
public interface B_1_3 extends {} // + - + /+/-/+ *
public interface B_2 extends T_1<B_1_2>, T_3<B_2_3> {} // /-/+
public interface B_2_3 extends {} // - + + /-/+/+ *
public interface B_3 extends T_1<B_1_3>, T_2<B_2_3> {} // - - + /-/-/+ *
Определим Built интерфейс:
public interface Built { MyClass build(); }
Промаркируем интерфейсы, где уже можно построить класс интерфейсом Built, добавим getter-ы и определим получившийся Builder-интерфейс:
// транзит
// | можем строить
// геттеры | |
// | | |
// ------------- ---------------------------------- -----
//
// first first first
// | second | second | second
// | | third| | third | | third
// | | | | | | | | |
public interface B extends T_1<B_1 >, T_2<B_2 >, T_3<B_3 >, Built {} // - - - / *
public interface B_1 extends G_1, T_2<B_1_2>, T_3<B_1_3>, Built {} // + - - /+ *
public interface B_1_2 extends G_1, G_2, Built {} // + + - /+/+ *
public interface B_1_3 extends G_1, G_3, Built {} // + - + /+/-/+ *
public interface B_2 extends G_2, T_1<B_1_2>, T_3<B_2_3> {} // /-/+
public interface B_2_3 extends G_2, G_3, Built {} // - + + /-/+/+ *
public interface B_3 extends G_3, T_1<B_1_3>, T_2<B_2_3>, Built {} // - - + /-/-/+ *
public interface Builder extends B {}
Этих описаний достаточно, чтобы по ним можно было в run-time соорудить proxy, надо только подправить получившиеся определения, добавив в них маркерные интерфейсы:
public interface Built extends BuiltBase<MyClass> {}
public interface Get_first extends GetBase { int first (); }
public interface Get_second extends GetBase { double second(); }
public interface Get_third extends GetBase { String third (); }
public interface Trans_first <T extends Get_first > extends TransBase { T first (int first ); }
public interface Trans_second<T extends Get_second> extends TransBase { T second(double second); }
public interface Trans_third <T extends Get_third > extends TransBase { T third (String third ); }
Теперь надо получить из Builder-классов значения чтобы создать реальный класс. Тут возможно два варианта — или создавать методы для каждого билдера и статически-типизированно получать параметры из каждого builder-а:
public MyClass build(B builder) { return new MyClass(-1 , Double.NaN , null); }
public MyClass build(B_1 builder) { return new MyClass(builder.first(), Double.NaN , null); }
public MyClass build(B_1_2 builder) { return new MyClass(builder.first(), builder.second(), null); }
...
или воспользоваться обобщённым методом, определённым примерно следующим образом:
public MyClass build(BuiltValues values) {
return new MyClass(
// значения из values
);
}
Но как получить значения?
Во-первых у нас есть по-прежнему есть набор builder-классов у которых есть нужные getter-ы. Соответственно надо проверять есть ли реализация нужного getter и если есть — приводить тип к нему и получать значение:
(values instanceof Get_first) ? ((Get_first) values).first() : -1
Конечно, можно добавить метод получения значения, но оно будет нетипизированным, так как мы не сможем получить тип значения из существующих типов:
Object getValue(final Class< ? extends GetBase> key);
Использование:
(Integer) values.getValue(Get_first.class)
Для того чтобы получить тип, пришлось бы создавать дополнительные классы и связки наподобие:
public interface TypedGetter<T, GETTER> { Class<GETTER> getterClass(); };
public static final Classed<T> GET_FIRST = new Classed<Integer>(Get_first.class);
Тогда метод получения значения мог бы быть определён следующим образом:
public <T, GETTER> T get(TypedGetter<T, GETTER> typedGetter);
Но мы попытаемся обойтись тем что есть — getter и transition интерфейсами. Тогда, без приведений типов, вернуть значение можно только вернув getter-интерфейс или null, если такой интерфейс не определён для данного builder:
<T extends GetBase> T get(Class<T> key);
Использование:
(null == values.get(Get_second.class)) ? Double.NaN: values.get(Get_second.class).second()
Это уже лучше. Но можно ли добавить значение по-умолчанию в случае отсутствия интерфейса, сохранив тип? Конечно, возможно возвращать типизированный getter-интерфейс, но всё равно придётся передавать нетипизированное значение по умолчанию:
<T extends GetBase> T get(Class<T> key, Object defaultValue);
Но мы можем воспользоваться для установки значения по умолчанию transition-интерфейсом:
<T extends TransBase> T getDefault(Class< ? super T> key);
И использовать это следующим образом:
values.getDefault(Get_third.class).third("1").third()
Это всё что можно типобезопасно соорудить с существующими интерфейсами. Создадим обобщённый метод инициализации иллюстрирующий перечисленные варианты использования и проинициализируем результирующий билдер:
protected static final Builder __builder = MegaBuilder.newBuilder(
Builder.class, null,
new ClassBuilder<Object, MyClass>() {
@Override public MyClass build(Object context, BuiltValues values) {
return new MyClass(
(values instanceof Get_first) ? ((Get_first) values).first() : -1,
(null == values.get(Get_second.class)) ? Double.NaN: values.get(Get_second.class).second(),
values.getDefault(Get_third.class).third(null).third()
);
}
}
);
public static Builder builder() { return __builder; }
Теперь можно его вызывать:
builder() .build();
builder().first(1) .build();
builder().first(1).second(2) .build(); builder().second(2 ).first (1).build();
builder().first(1) .third("3").build(); builder().third ("3").first (1).build();
builder() .second(2).third("3").build(); builder().third ("3").second(2).build();
builder() .third("3").build();
Скачать код и посмотреть на работу context assist можно отсюда.
В частности:
Код рассматриваемого примера: MyClass.java
Пример с generic-типами: MyParameterizedClass.java
Пример не-статического builder: MyLocalClass.java.
Итого
- Double brace initialization не будет хаком или антипаттерном, если добавить немного билдера.
- Гораздо проще пользоваться динамическими объектами + типизированными дескрипторами доступа (см. в тексте пример с TypedGetter) чем использовать сборки интерфейсов или другие варианты статически-типизированных объектов, поскольку это влечёт за собой необходимость работы с reflection со всеми вытекающими.
- С использованием аннотаций возможно удалось бы упростить код proxy-генератора, но это усложнило бы объявления и, вероятно, ухудшило бы выявление несоответствий в compile-time.
- Ну и наконец, в данной статье мы
окончательно и бесповоротноопределили минимальную и максимальную границу сложности паттерна Builder — все остальные варианты находятся где-то между ними.
Комментарии (47)
kokorins
04.09.2015 15:56+1У первого подхода есть еще одна неприятность, что поля должны быть инициализированы финальными значениями, а значит что-нибудь простое
public class HelloWorld{ static class A { int a=0; } public static void main(String []args){ List<A> as = new ArrayList<>(); for(int i=0; i<10; ++i) as.add(new A(){{a=i;}}); } }
не скомпилируется, так как i не final.
speakingfish
04.09.2015 17:36Да вы правы, такое не прокатит.
Но, в общем, все уже привыкли не только к особенностям анонимных классов, но и вовсю используют лямбды Java 8 и знают про final/effectively final.
Я например чаще использую for each, тогда в аналогичном коде для Java 8+ ничего не надо будет менять, только для Java < 8 надо будет добавить final:
for(final int i : new int[] {1,2,3}) { new MyClass.Builder(){{ first = i; third = "3"; }}.create(); }
Athari
04.09.2015 21:46+2Чего только не придумают, чтобы не писать на C#. ;-D
Второй пример уже любопытен, но его применимость в реальных проектах под вопросом. Необходимых условий получается многовато:
1. Спец, который может одолеть весь этот матан.
2. Нубы в большой концентрации, которых нужно ограничивать.
3. Более-менее стабильный интерфейс, потому что проделывать это каждый раз невесело.
4. Малое количество вариантов, потому что код растёт экспоненциально (?).gurinderu
04.09.2015 22:22+1а как вам поможет c# при реализации паттерна builder?
Athari
04.09.2015 22:51+3В случае самого простого «билдера» отдельный класс не нужен:
а) Можно задавать read-write свойства в блоке инициализации. Если какие-то свойства обязательны, добавить их в конструктор.
В отличие от Java, отдельный класс для каждого случая генерироваться не будет, никакой контекст захватываться тоже не будет, это просто запись свойств.new Foo(1) { Bar = 2, Baz = 3 }
б) Можно сделать конструктор или статический метод со всеми доступными свойствами, для всех опциональных задать значения по умолчанию, вызывать с именованными аргументами:
Этот способ даёт возможность пропускать имена аргументов, но можно прописать в конвенции (а также прикрутить проверку в IDE и при коммите по вкусу), что в таких случаях использование именованных аргументов обязательно.new Foo(foo: 1, bar: 2, baz: 3) Foo.CreateFromBar(2, baz: 3)
Инициализация коллекций и словарей поддерживается для конструкторов:
Кажется, обсуждали поддержку блока инициализации ещё и для статических методов, но не помню, к чему там пришли.new Foo { Bars = { 1, 2, 3 }, Bazs = { [1] = 2, [3] = 4 } }
Чуть больше кода в этом комментарии: habrahabr.ru/post/244521/#comment_8154859 (что характерно, тоже заминусованном).speakingfish
05.09.2015 00:39+1По поводу варианта А — в этом случае наверное не может быть final полей и не могут выполнятся проверки.
Вот вариант Б — да, именованные параметры со значениями по умолчанию сделали бы многие простые билдеры ненужными, однако…
Сейчас я добавил сокращённые версии классов с минимальным билдером. Там по новым ссылкам можно их увидеть github.com/speaking-fish/java-sf-builder-simple-example — классы New*
В них в конструктор класса передаются не все параметры, а только билдер. Т.е. теперь не надо перечислять все параметры в функциях.
Вы же согласны что лучше иметь сложные проверки отдельно от конструктора, в билдере.
Т.е. тогда в C# билдер останется, но не отдельным классом а отдельной функцией, так?
Тогда возникает вопрос, а как будет работать наследование?
Если у меня наследуется класс билдера — то он наследует все свои поля и их потом не надо опять все перечислять.
А что с параметрами функции? Их можно унаследовать или в унаследованных классах придётся как перечислять всё больше и больше параметров и делать какие-то проверки чтобы их случайно не упустить, и в каждом классе потом искать и исправлять дефолтные значения или определять еще для них константы и использовать константы?
Поясните этот момент.
Это вообще скорее не C# касается, а всех языков с возможностью использования именованных параметров функций.
Т.е. в результате, отдельный класс билдера будет проще использовать и в таких языках.
PS. А инициализация коллекций и словарей многоуровневая или только первый уровень поддерживается?Athari
05.09.2015 07:40По поводу варианта А — в этом случае наверное не может быть final полей и не могут выполнятся проверки.
Read-only поля и свойства задать так не получится, им можно задавать значение только в конструкторе, а вот проверки можно положить в сеттер свойств, если они read-write.
Вы же согласны что лучше иметь сложные проверки отдельно от конструктора, в билдере.
Почему? Это банальная проверка аргументов в конструкторе.
Тогда возникает вопрос, а как будет работать наследование?
Если честно, я нечасто вижу глубокие иерархии сложных объектов с билдерами на десятки свойств, поэтому вопросом, что делать в общем случае, я не задавался. :) Если количество свойств идёт на десятки, а глубина иерархии дальше одинарной, то я бы не занимался сомнительной копипастой фабричных методов с именованными аргументами, а занялся бы поиском более вменяемого интерфейса, вероятно, с отдельными билдерами, у которых задание свойств собрано в осмысленные выражения. Это тот момент, когда нужно отвлечься от механического кодинга и включить мозг.
Всё-таки мы говорим про простые билдеры. В их рамках копипаста нескольких аргументов займёт меньше места, чем разведение иерархии билдеров. Набивать код проблемы не составит, решарпер всё сам скопипастит. Хотя, конечно, нехорошо, что значения будут дублироваться. Можно в константы вынести, если есть опасения, что значения изменятся.
Скажем, вот код, эквивалентный вашим NewBaseClass.java и NewChildClass.java (где-то в два раза короче):
using static System.Console; class CsBaseClass { public int First { get; } public double Second { get; } public string Third { get; } public CsBaseClass (int first = -1, double second = double.NaN, string third = null) { First = first; Second = second; Third = third; } public override string ToString () => $"{GetType().Name} - First: {First}, Second: {Second}, Third: {Third}"; } class CsChildClass : CsBaseClass { public object Fourth { get; } public CsChildClass (int first = -1, double second = double.NaN, string third = null, object fourth = null) : base(first, second, third) { Fourth = fourth; } public override string ToString () => $"{base.ToString()}, Fourth: {Fourth}"; } class Program { static void Main () { WriteLine(new CsBaseClass(first: 1, third: "3")); WriteLine(new CsChildClass(first: 1, third: "3", fourth: 4)); } }
Если количество свойств доберётся до десяти я так, конечно, делать не буду. :)
В C# 7 планируется сделать что-то вроде этого (не следил за последними обновлениями, могу соврать; там были заморочки с именованием аргументов и свойств):
using static System.Console; class CsBaseClass (int First = -1, double Second = double.NaN, string Third = null); class CsChildClass : CsBaseClass (int First = -1, double Second = double.NaN, string Third = null, object Fourth = null); class Program { static void Main () { WriteLine(new CsBaseClass(First: 1, Third: "3")); WriteLine(new CsChildClass(First: 1, Third: "3", Fourth: 4)); } }
В этом случае даже с константами для избавления от копипасты код будет несоразмеримо короче, чем с билдерами.
PS. А инициализация коллекций и словарей многоуровневая или только первый уровень поддерживается?
Многоуровневая.speakingfish
07.09.2015 01:07Пример билдера который никак нельзя воткнуть ни в конструктор ни в основной билдер:
public class LocalBuilderExample { protected final double base; public LocalBuilderExample(double base) { super(); this.base = base; } public class BaseBuilder extends NewBaseClass.BuilderImpl { public NewBaseClass create() { if(!Double.isNaN(base)) { first = (int) Math.round(base) + first; if(!Double.isNaN(base)) { second = base + second; } else { second = base; } } return new NewBaseClass(this); }; } }
Вы предлагаете в таком случае дублировать все описания параметров вместе со всеми дефолтными значениями.
Скажем, вот код, эквивалентный вашим NewBaseClass.java и NewChildClass.java (где-то в два раза короче):
В вашем коде не хватает констант для дефолтных значений — это соответственно увеличит код.
Добавим их и сравним построчно код игнорируя пустые строки (я убрал модификаторы доступа чтобы влезло):
C# Java class BaseClass { = class BaseClass { + static class BuilderImpl { + int first = -1 ; + double second = Double.NaN; + String third = null ; + } +5 + static class Builder extends BuilderImpl { + BaseClass create() { return new BaseClass(this); } + } +3 const int DEFAULT_First = -1 ; + const double DEFAULT_Second = double.NaN; + const string DEFAULT_Third = null ; + +3 const int First { get; } = final int first ; const double Second { get; } = final double second; const string Third { get; } = final String third ; + int first () { return first ; } + double second() { return second; } + String third () { return third ; } +3 BaseClass( = BaseClass( int first = DEFAULT_First , = BuilderImpl builder double second = DEFAULT_Second, + string third = DEFAULT_Third , + ) { +2= ) { First = first; = this.first = builder.first ; Second = second; = this.second= builder.second; Third = third; = this.third = builder.third ; } = } } = } =12 +5 +11 +6 17 23 class ChildClass : BaseClass { = class ChildClass extends BaseClass { + static class BuilderImpl extends BaseClass.BuilderImpl { + Object fourth = null; +3 } + static class Builder extends BuilderImpl { + ChildClass create() { return new ChildClass(this); } +3 } const object DEFAULT_Fourth = null; + +1 const object Fourth { get; } = final Object fourth; + Object fourth() { return fourth; } +1 ChildClass ( = ChildClass( int first = DEFAULT_First , = BuilderImpAthari
07.09.2015 02:47Вы предлагаете в таком случае дублировать все описания параметров вместе со всеми дефолтными значениями.
Что-то мешает вынести в отдельную функцию?
В вашем коде не хватает констант для дефолтных значений — это соответственно увеличит код.
Тут есть нюанс. Изменение значений по умолчанию — это катаклизм, потому что ломает обратную совместимость. Куда эти значения ни прячь, подобное изменение потенциально ломает весь код. Поэтому значения по умолчанию следует использовать тогда, когда ты уверен, что они не изменятся и ничто не сломают.
Причём в случае значений по умолчанию, прошитых в аргументах конструктора, преступление чуть меньшее, потому что реальные значения вкомпиливаются в код, то есть ломается только сорцовая совместимость, но не бинарная на границе сборок. В случае билдера ломается и то, и другое.
Учитывая такую ситуацию, в случае использования трёх-пяти значений я ограничусь копипастой, даже если это не самый красивый и идеологически верный способ. Потому что, если мне захочется менять значения по умолчанию, чего я делать не должен, я и так всё поломаю к чертям, так зачем же платить больше? Мне всё равно нужно проверить абсолютно все использования конструкторов во всём коде, изменение самого конструктора — это сущая мелочь на фоне этого.
Добавим их и сравним построчно код игнорируя пустые строки (я убрал модификаторы доступа чтобы влезло)
Знаете, ваше форматирование в виде
ChildClass ( int first = DEFAULT_First , double second = DEFAULT_Second, string third = DEFAULT_Third , object fourth = DEFAULT_Fourth ) : base( first , second, third ) { Fourth = fourth; }
Мне сильно напомнило документацию по Win32 в MSDN. Там тоже аргументы в столбик всегда рисуют. :)
HWND hwnd = CreateWindowEx( 0, CLASS_NAME, L"Learn to Program Windows", WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, CW_USEDEFAULT, CW_USEDEFAULT, CW_USEDEFAULT, NULL, NULL, hInstance, NULL );
Давайте уж тогда исключим форматирование из уравнения и коллапсируем whitespace ("\s+" => " "). Мерять только строчками некорректно, потому что сложность восприятия строчек разной длины разная.
Сравниваемый кодC#:
using static System.Console; public class CsBaseClass { public const int DefaultFirst = -1; public const double DefaultSecond = double.NaN; public const string DefaultThird = null; public int First { get; } public double Second { get; } public string Third { get; } public CsBaseClass (int first = DefaultFirst, double second = DefaultSecond, string third = DefaultThird) { First = first; Second = second; Third = third; } public override string ToString () => $"{GetType().Name} - First: {First}, Second: {Second}, Third: {Third}"; } public class CsChildClass : CsBaseClass { public const object DefaultFourth = null; public object Fourth { get; } public CsChildClass (int first = DefaultFirst, double second = DefaultSecond, string third = DefaultThird, object fourth = DefaultFourth) : base(first, second, third) { Fourth = fourth; } public override string ToString () => $"{base.ToString()}, Fourth: {Fourth}"; static void Main () { WriteLine(new CsBaseClass(first: 1, third: "3")); WriteLine(new CsChildClass(first: 1, third: "3", fourth: 4)); } }
Java:
public class NewBaseClass { protected static class BuilderImpl { public int first = -1 ; public double second = Double.NaN; public String third = null ; } public static class Builder extends BuilderImpl { public NewBaseClass create() { return new NewBaseClass(this); } } protected final int first ; protected final double second; protected final String third ; protected NewBaseClass(BuilderImpl builder) { super(); this.first = builder.first ; this.second= builder.second; this.third = builder.third ; } public int first () { return first ; } public double second() { return second; } public String third () { return third ; } @Override public String toString() { return "MyClass [first=" + first + ", second=" + second + ", third=" + third + "]"; } } public class NewChildClass extends NewBaseClass { protected static class BuilderImpl extends NewBaseClass.BuilderImpl { public Object fourth = null; } public static class Builder extends BuilderImpl { public NewChildClass create() { return new NewChildClass(this); } } protected final Object fourth; protected NewChildClass(BuilderImpl builder) { super(builder); this.fourth = builder.fourth; } public Object fourth() { return fourth; } @Override public String toString() { return "MyChildClass [first=" + first + ", second=" + second + ", third=" + third + ", fourth=" + fourth + "]"; } public static void main(String[] args) { System.out.println(new NewBaseClass.Builder(){{ first = 1; third = "3"; }}.create()); System.out.println(new NewChildClass.Builder(){{ first = 1; third = "3"; fourth = 4; }}.create()); } }speakingfish
07.09.2015 17:37Вы предлагаете в таком случае дублировать все описания параметров вместе со всеми дефолтными значениями.
Что-то мешает вынести в отдельную функцию?
Создание новой функции приведёт к дублированию всего описания параметров. А в случае билдера — нет.
Сделал одинаковое форматирование и добавил на github: github.com/speaking-fish/java-sf-builder-simple-example/tree/master/comparison
Получилось следующее:
Полный код:
C#: 41 lines (28 sloc) 1.217 kB
Java: 51 lines (35 sloc) 1.616 kB
Java +24% lines +25% sloc +32% байт
Без toString и main:
C#: 30 lines (21 sloc) 0.813 kB
Java: 42 lines (29 sloc) 1.13 kB
Java +40% lines +38% sloc +39% байт
Без полей и getter-ов — рассматриваем только разницу именованные параметры / билдер:
C#: 24 lines (17 sloc) 0.674 kB
Java: 32 lines (22 sloc) 0.875 kB
Java +33% lines +29% sloc +30% байт
Выводы: В худшем синтетическом случае кода больше на 40% и то это сокращение в основном из-за getter-ов. В реальном коде увеличение кода даже в таком минимальном варианте (только два класса) не будет более чем на треть.
Как я уже сказал, этот код вручную писать необязательно. «Написание» конструктора для класса-потомка у меня свелось к аккорду
Обычно надо не только сгенерить код но и поддерживать его.
Что будет в случае следующих рефакторингов?:
Изменение типа поля.
Изменение названия поля.
Изменение значения по умолчанию.
Перенос поля из одного класса в другой.
В случае выделенного объекта билдер это простые контролируемые компилятором операции.
А как с параметрами?
Athari
09.09.2015 00:09Создание новой функции приведёт к дублированию всего описания параметров. А в случае билдера — нет.
Вообще-то дублирование параметров — неизбежное зло. Вам никогда не приходилось прокидывать аргументы через несколько вызовов по цепочке? Конкретно в этом случае можно выделить обработку конкретно этих двух аргументов в отдельную функцию. Это будет осмысленная функция с нормальным названием и ясным функционалом, поэтому это совершенно нормальное явление.
Вы так говорите про дублирование, как будто слово «first» повторяется в джавовом коде реже, чем в шарповом. Пока что во всех версиях на обоих языках дублирования хоть попой кушай. Хоть как-то приближается к избавлению от дублирования только планируемый синтаксис C# 7, и то там одним упоминанием названия невозможно обойтись.
Выводы: В худшем синтетическом случае кода больше на 40% и то это сокращение в основном из-за getter-ов. В реальном коде увеличение кода даже в таком минимальном варианте (только два класса) не будет более чем на треть.
Для меня 30–50% — это очень даже ощутимое число. И, как я уже сказал, различия в количестве классов даже более важны, чем слоки, байты и непробельные символы.
Что будет в случае следующих рефакторингов?
Ну, будет работа не на часик, а на два. Вроде, даже решарпер не очень поможет, потому что полноценная обработка цепочек конструкторов не реализована. Фиче-реквест был, но, вроде, до него ещё не добрались.
В случае выделенного объекта билдер это простые контролируемые компилятором операции.
Я ж уже говорил: это весьма эфемерный бонус. Тип и имя поля-то вы измените, даже сэкономите 50% времени относительно грязной версии с копипастой, но ведь всё равно основное время будет убито на поиск и исправление всех использований во всём коде. Все перечисленные вами изменения ломают обратную совместимость, не получится изменить только одно место.speakingfish
09.09.2015 19:28Вообще-то дублирование параметров — неизбежное зло. Вам никогда не приходилось прокидывать аргументы через несколько вызовов по цепочке?
Нет никакого неизбежного зла — при необходимости часть или весь список параметров превращается в один объект.
Зависит от того насколько то или иное удобно.
Вы так говорите про дублирование, как будто слово «first» повторяется в джавовом коде реже, чем в шарповом.
Слово first встречается только при певром упоминании — в первом объекте и билдере.
Хоть как-то приближается к избавлению от дублирования только планируемый синтаксис C# 7
Этот сахар опять только для первого объявления а не для всех последующих.
Для меня 30–50% — это очень даже ощутимое число. И, как я уже сказал, различия в количестве классов даже более важны, чем слоки, байты и непробельные символы.
Там не было 50% — максимум 40%. Количество классов само по себе ничему не вредит — например мы пользуемся в больших количествах анонимными классами просто потому что так удобнее.
Что будет в случае следующих рефакторингов?
Ну, будет работа не на часик, а на два. Вроде, даже решарпер не очень поможет, потому что полноценная обработка цепочек конструкторов не реализована. Фиче-реквест был, но, вроде, до него ещё не добрались.
В случае выделенного объекта билдер это простые контролируемые компилятором операции.
Я ж уже говорил: это весьма эфемерный бонус. Тип и имя поля-то вы измените, даже сэкономите 50% времени относительно грязной версии с копипастой, но ведь всё равно основное время будет убито на поиск и исправление всех использований во всём коде. Все перечисленные вами изменения ломают обратную совместимость, не получится изменить только одно место.
Т.е. вы отвечаете примерно так: «Да, рефакторинга никакого быть не может. Значит и вам он не нужен.» или что «раз придётся копировать код, то пусть так и будет».
Я всё же не столь категоричен, т.к. выбор зависит от ситуации — надо только описать как преимущества так и недостатки обоих подходов.Athari
09.09.2015 23:32Нет никакого неизбежного зла — при необходимости часть или весь список параметров превращается в один объект.
Зависит от того насколько то или иное удобно.
Вы будете ради двух-трёх аргументов заводить отдельный класс ради использования один раз?
Слово first встречается только при певром упоминании — в первом объекте и билдере.
Откройте файл, нажмите Ctrl+F, введите «first» и посчитайте. Вот это всё — дублирование.
Количество классов само по себе ничему не вредит
Это усложняет восприятие кода. Может быть, вы супермен, и для вас разницы между 2000 и 6000 классов нет, а вот для меня есть.speakingfish
10.09.2015 00:56Вы будете ради двух-трёх аргументов заводить отдельный класс ради использования один раз?
Это усложняет восприятие кода.
Нет конечно.
Но когда когда количество аргументов функции увеличится вместе с увеличением числа пробросов этих аргументов то для упрощения кода я скорее всего объединю их в класс.
Всё зависит от того что в итоге получается удобнее — пробрасывать каждый раз все параметры но увеличить количество классов, или каждый раз пробрасывать все параметры не увеличивая количество классов.
Откройте файл, нажмите Ctrl+F, введите «first» и посчитайте. Вот это всё — дублирование.
Только мы обсуждаем сейчас не автоматическую генерацию геттеров, а именованые параметры vs объекты.Athari
10.09.2015 02:45Только мы обсуждаем сейчас не автоматическую генерацию геттеров, а именованые параметры vs объекты.
Сразу видно, что не последовали совету. :) Посмотрите самую первую версию классов, которую я привел на C# (там, где ни констант, ни билдеров). Слово «first» повторяется 8 раз, да даже слово «fourth» 6 раз (не считая Main). В версии с константами — 11 и 8. С джавой и билдерами — 10 и 8 (без геттеров — 8 и 6). А вот в планируемой версии C# 7 — 2 и 1, и это при том, что функциональности даже больше реализовано (GetHashCode, в частности). Вот это — реально избавление от дублирования. Всё остальное — так, игрушки.
Что я хочу сказать: вы видите только одно дублирование — дублирование аргументов. А вообще-то в обоих языках дублирования дофига, и оно совсем в другом месте.
Это всё равно что оптимизировать в 10 раз скорость выполнения кода, который отнимает меньше 1% времени. Звучит круто, но бесполезно.speakingfish
11.09.2015 19:28Без констант будет не эквивалентный код так как дефолтные значения буду размазаны по всем классам.
Тогда и без сгенерированных геттеров, сравним — мы же сравниваем только именованные параметры vs builder?:
против1: public BaseClass(int first = -1... 2: First = 3: first;
1: public int first = -1 2: protected int first; 3: first = 4: src.first;
builder проигрывает на одно упоминание в базовом классе
против1: public ChildClass(int first = -1... 2: base(first...0:
в производном builder выигрывает на два упоминания
итого builder выигрывает на одно упоминание даже у кода с размазанными по всем классам константами
Это всё равно что оптимизировать в 10 раз скорость выполнения кода, который отнимает меньше 1% времени.
Повторюсь — поэтому надо самому определять что удобнее в каждой ситуации.
А наследование в общем-то для того и нужно, чтобы не дублировать код — странно было бы не пользоваться им при необходимости.
Athari
07.09.2015 03:09Можно пример?
class Foo { public Foo Foo { get; set; } public List<Foo> FooList { get; } = new List<Foo>(); public Dictionary<Foo, Foo> FooDic { get; } = new Dictionary<Foo, Foo>(); static void Main () { new Foo { Foo = new Foo { FooList = { new Foo(), new Foo() }, FooDic = { [new Foo()] = new Foo(), [new Foo()] = new Foo() }, Foo = new Foo { FooList = { new Foo { FooList = { new Foo { FooList = { new Foo() } } } } }, FooDic = { [new Foo { Foo = new Foo() }] = new Foo { Foo = new Foo() }, [new Foo { FooDic = { [new Foo()] = new Foo() } }] = new Foo { FooDic = { [new Foo()] = new Foo() } } } } } }; } }
Есть ещё возможность к любой коллекции добавить метод Add с произвольными аргументами и добавлять элементы в фигурных скобках, но это в основном используется для словарей, а для них в C# 6 добавили отдельный синтаксис с квадратными скобками. Но вообще фича осталась, иногда полезна.
Ещё есть нюанс, что в зависимости от того, нужно ли создать объект или просто изменить его, либо используется new, либо не используется. В примере выше объект всегда создаётся в иницилизаторе, а коллекции всегда создаются сами. Но можно и наоборот.new Foo { Foo = { Foo = new Foo() } }тоже будет работать, если свойство не будет null после вызова конструктора (но конкретно в этом случае будет stack overflow).speakingfish
07.09.2015 17:47Конструкция конечно вложенная но инициализации тут одноуровневые.
Вот например сначала отдельно инициализируется класс, который потом используется при инициализации Foo
new Foo {
Foo = new Foo {...}
}
А это уже похоже:
new Foo { Foo = { Foo =… } }
А как инициализировать List<List> или Dictionary<Foo, List>?Athari
09.09.2015 00:21А как инициализировать List<List> или Dictionary<Foo, List>?
Как-то так:
using System.Collections.Generic; class Foo { static void Main () { var foos = new List<Dictionary<List<Dictionary<Foo, Foo>>, List<List<Foo>>>> { new Dictionary<List<Dictionary<Foo, Foo>>, List<List<Foo>>> { [new List<Dictionary<Foo, Foo>> { new Dictionary<Foo, Foo> { [new Foo()] = new Foo() } }] = new List<List<Foo>> { new List<Foo> { new Foo() } } } }; } }speakingfish
09.09.2015 20:07Понятно. Но все так же не синтаксис инициализации двумерного массива.
Athari
09.09.2015 23:36Как вы себе это представляете? У коллекций могут быть наследники, поэтому без указания классов не выйдет.
speakingfish
10.09.2015 01:11Да я понял что многоуровневого аналога как для двумерного массива нет
Я предполагал что это могло бы выглядеть наподобие:
var foos = new List<Dictionary<List<Dictionary<Foo, Foo>>, List<List<Foo>>>> { [ [ [[new Foo() = new Foo()], [new Foo() = new Foo()]] = [[new Foo(), new Foo()], [new Foo(), new Foo()]], [[], [new Foo() = new Foo()]] = [[], []] ], [ [] = [[new Foo(), new Foo()], []], ]; ] };Athari
10.09.2015 03:01Выглядит ужасающе, чёрт ногу сломит. :) Но от полноценных литералов для списков и словарей я бы не отказался.
speakingfish
11.09.2015 19:29Если компактный код выглядит ужасающие, можно разбавить его комментариями :)
gurinderu
05.09.2015 10:15Я если честно, не совсем понял как приведенный код относится к паттерну builder? Это же вроде обычная инициализация объекта. В Java тоже можно сделать конструкторы и сеттере без дополнительного класса. Паттерн builder нужен же для конструирования сложных объектов, чего нету в вашем примере. Отличным примером является написание query builder'а. Если вы напишите пример и он будет выглядеть много красивее, чем на Java, то я скажу вам огромное спасибо.
Athari
05.09.2015 12:32+1Автор под «простым билдером» подразумевает билдер, который просто задаёт значения некоторых свойств, без каких-либо украшений. Такой тривиальный билдер в шарпе «встроенный» за счёт именованных параметров и значений аргументов по умолчанию, в джаве тривиальная «встроенная» версия будет приводить к созданию классов и заглатыванию контекста, поэтому нужен более сложный код.
В случае осмысленного сложного билдера каких-либо принципиальных отличий не будет. Ну, что-то сэкономится по мелочам за счёт синтаксического сахара, не более.
Regis
04.09.2015 23:52На самом деле для использования даже сложных билдеров знание «матана» не нужно, так как это обычно всё вызывается в fluent-стиле и промежуточные шаги нигде явно не пристутствуют.
Яркий пример использования подобных билдеров — библиотека JOOQ:
Result<...> query = create.select(BOOK.AUTHOR_ID, BOOK.TITLE) .from(BOOK) .groupBy(AUTHOR_ID) .fetch();
DemetrNieA
05.09.2015 05:18>> Для использовании наследования, Builder разделяется на две части (один с полями, другой — с методом создания) следующим образом:
Так делать не стоит, сейчас объясню почему:
1. Если Вы используете билдеры и наследование, то оно Вам для чего-либо нужно. И обычно не просто для экономии места при написании переменных, а для того, чтобы переиспользовать билдер:
List<? extends BaseEntity> entities; public void addEntity(BaseEntity.Builder builder) { entities.add(builder.build()); }
2. После присвоения базового параметра при такой реализации будет возвращена ссылка на базовый билдер, т.е. нельзя будет сделать такое:
ExtendedEntity.newBuilder().baseParameter(value).extendedParameter(value2).build();
Это можно обойти хитрым использованием дженериков при наследовании. Могу написать код, если он кому-либо интересен.
По поводу «Mega Builder» — можете привести пример реализации и использования?speakingfish
07.09.2015 01:47>> Для использовании наследования, Builder разделяется на две части (один с полями, другой — с методом создания) следующим образом:
Так делать не стоит, сейчас объясню почему
Это написано про минимальный билдер, который сооружается из double brace initialization, а он не является fluent-интерфейсом.
Mega Builder является fluent-интерфейсом, но он не может поддерживать такого сокращённого наследования с помощью пареадресации унаследованному билдеру, поскольку в унаследованном классе могут быть вообще совершенно другие валидные сочетания параметров, и поэтому их надо полностью описывать заново.
В статье есть все ссылки на описываемый код: github.com/speaking-fish/java-sf-builder-mega github.com/speaking-fish/java-sf-builder-simple-example
Throwable
06.09.2015 02:59В тему: есть прекрасный проект Joda-Beans, который решает многие задачи и исправляет косяки спецификации Java Beans: генерирует автоматически boilerplate code для properties (в том числе и билдеры), добавляет метаданные, equals/hashcode, immutability, etc… Другая хорошая альтернатива — Groovy, которая при необходимости также может генерировать билдеры для объектов.
nehaev
06.09.2015 07:37+3> Другая хорошая альтернатива — Groovy, которая при необходимости также может генерировать билдеры для объектов.
А еще лучше Scala с кейс-классами и статической типизацией.Throwable
07.09.2015 11:46Scala — это все-таки отдельная область, с собственной системой типов, стандартной библиотекой, экосистемой, и парадигмами, которые имеют лишь определенную совместимость с Java. Смешивать в решении одновременно Java и Scala, довольно нецелесообразно, хотя и можно.
Groovy же натурально интегрируется с Java, не выходя из ее парадигмы. В данном случае я имел ввиду такой мощный инструмент Groovy как AST. В стандартной библиотеке уже есть гибкие трансформации для создания properties и билдеров. При указании @CompileStatic Groovy AST генерирует код, который 100% интероперабелен с Java и не требует присутствия groovy в рантайме.
grossws
09.09.2015 00:40+1Есть ещё project lombok, который используется в compile-time и удобен для описания POJO (умеет генерировать геттеры, сеттеры, toString, hashCode/equals, билдеры). Просто POJO-класс аннотируется и lombok.jar добавляется в classpath.
yaneblog
Вызывают ли одобрение нижеперечисленные подходы:
projectlombok.org/features/Builder.html
projectlombok.org/features/Builder.html#singular
?
speakingfish
Идея обвязывать заодно первый уровень коллекций интересная.
По идее, если уж так делать, то можно было бы и следующие уровни обвязывать и не только коллекций но и просто вложенных классов.
Почему коллекции инициализируются только или элементами ли коллекциями? Что если я использую ленивые итераторы?
Непонятно в каком месте реализовывать валидацию.
Посмотрел сгенерированный код projectlombok.org/features/Singular-snippet.html
Метод public SingularExample build() как-то переусложнён — всё это можно было бы спокойно вынести в хелперы.
Почему списки билдера инициализируются ArrayList а не LinkedList?
Непонятно как организовать обязательные поля и как соорудить контекстно-зависимый билдер.
vedenin1980
Странный вопрос, на практике LinkedList почти всегда проигрывает ArrayList, как по скорости работы, так и по потребляемой памяти.
speakingfish
И действительно.
habrahabr.ru/post/233797
---Add elements ( 6kk )
LinkedList: 2264 ms
ArrayList: 493 ms
ArrayList is faster
withoutuniverse
с помощью итератора (когда не нужно ходить по списку каждую итерацию для поиска последнего элемента) LinkedList быстрее.
пруф
vedenin1980
Смотрите, такие тесты (вставить тысячу элементов в одно место) мало полезны, так как
1) Если нужно вставить тысячу элементов в начало или середину — создаем новый ArrayList на тысячу элементов и вставляем его как addAll — получится быстрее чем у LinkedList,
2) Если нужно вставлять элементы в произвольные места списка, то сложность итерирования LinkedList съест всякую пользу от скорости вставки по сравнению с ArrayList,
3) Если нужно часто удалять элементы, проще в ArrayList записывать null, а потом null'ы игнорировать — ArrayList будет куда быстрее,
4) Если нужно часто вставлять элементы в произвольные места списка — лучше использовать SortedMap'у c числовым ключом (элементы вставляются быстро по ключу и итерирование будет тоже быстрым).
5) Надо не забывать что в реальных случаях, List надо создать, обработать и куда-то записать результат. Создание и запись результата у LinkedList настолько дорогие, что как правило любая польза от алгоритма это не перевешивает,
6) Не стоит забывать что КАЖДЫЙ элемент LinkedList это отдельный элемент Node с ссылкой на значение и первый и последний элемент, поэтому во-первых, каждый элемент ест минимум в 8 раз больше памяти, создание нового объекта весьма дорого, так и сборка мусора после LinkedList в разы дороже, если ArrayList на миллион элементов собирается как один объект, то в LinkedList как миллион и один объект.
7) плюс LinkedList хранится в памяти в разных блоках, а ArrayList в одном, что ускоряет обработку,
Поэтому такие пруфы в реальных задачах смысла не имеют, использование LinkedList крайне крайне редко оправдано.
vedenin1980
В 6 пункте я имел в виду, конечно, что каждый элемент LinkedList это отдельный объект класса Node.
withoutuniverse
Вся проблема в оверхеде при аллокации памяти при изменении очередности элементов. В LinkedList этой проблемы нету.
Вы рассматриваете абстрактных коней в вакууме, а вам приводят объективные доводы в пользу той или иной структуры хранения данных.
Потому пройдемся по списку:
1) Пример надуман, да и не представляю что создать миллионный массив + 1000 быстрее, чем просто добавить 1000
2) Приведите пример? В чем сложность итерирования вообще чего либо?
3) Это заставит приложение разрастить просто нереально, о эффективном использовании памяти речь не будет идти вовсе. (Не забываем про аллокацию при достижении лимита выделенной памяти под массив)
4) Вода, нужен пруф и тесты
5) Снова вода и снова нужны пруф и тесты
6) Каждый элемент массива — указатель. Конечно памяти ест меньше, но ваше сравнение некорректное, ведь для каждой структуры свои цели — советую почитать что и где лучше использовать.
7) При добавлении неизвестного количества элементов LinkedList даст фору именно по этой причине.
Вы написал «пруфы смысла не имеют» — не надо так. Я сам использую почти всегда ArrayList, но лишь по той причине, что скорость работы и количество аллокаций мне не важны. В BigData разговор был бы совсем другой.
vedenin1980
Пруф? Официальная документация вам будет достаточным пруфом?
Английским же языком сказано, что LinkedList даже при добавлении в центр/середину как правило будет хуже и надо очень хорошо подумать прежде чем его использовать.
>> 2) Приведите пример? В чем сложность итерирования вообще чего либо?
Тем что сложность итерирования в LinkedList O(n), а добавление O(1), сложность итерирования в ArrayList — O(1), а добавления O(n). То есть добавить элемент в случайное место сложность будет одинаковая O(n), но как сказано в официальной документации у LinkedList это O(n) будет намного хуже, чем O(n) ArrayList.
>> 3) Это заставит приложение разрастить просто нереально, о эффективном использовании памяти речь не будет идти вовсе. (Не забываем про аллокацию при достижении лимита выделенной памяти под массив)
Вовсе нет, если кол-во null будет больше половины. можно скопировать не null элементы в новый массив это O(n), но все n удаления c перемещениями будут O(n), то есть O(2*n). В то время как в LinkedList перемещения с ударениями будут O(n^2). Учитывая намного большие затраты памяти в LinkedList, даже заранее выделение достаточного лимита и трата лишней памяти в ArrayList будет экономнее
>>4) Вода, нужен пруф и тесты
>>5) Снова вода и снова нужны пруф и тесты
Достаточно просто посчитать сложность алгоритмов (вставка и итерирование Map'ы это O(1), что куда лучше чем O(n) у LinkedList) и посмотреть что написано в офф.документации про LinkedList.
>>7) При добавлении неизвестного количества элементов LinkedList даст фору именно по этой причине.
Не даст, достаточно выделить достаточно памяти под ожидаемый алгоритм если нужно оптимизировать скорость или ограничить память, если небольшая потеря производительности при переаллокации допустима.
>>скорость работы и количество аллокаций мне не важны. В BigData разговор был бы совсем другой.
Вы серьезно? Когда я оптимизировал работу с BigData мне приходилось отказываться не только от LinkedList, но даже от HashMap и ArrayList и работать тупо с массивами.
withoutuniverse
Про выдержку на английском я тоже согласен, о чем и написал в конце предыдущего сообщения. «тупо массив» использовать не выйдет при неизвестном количестве элементов, и придется писать заново велосипед для расширения массива, который уже внутри ArrayList. Хотя в случае с забиванием null пожалуй соглашусь с вами, потери тут будут минимальны.
А вот по сложности алгоритмов — вы путаете произвольный доступ к случайному элементу и итерирование. Было бы странным при практически равных показателях на операции с чтением всех элементов иметь в одном случае o(n) а в другом o(1).
Также хотел бы ОБЯЗАТЕЛЬНО обратить внимание на пункт с последовательностью в памяти к элементам, что должно было бы упростить доступ к ним — в java в памяти последовательно лежит только массив указателей на указатели, сами же указатели на объекты и объекты будут непоследовательно лежать в памяти, в разных местах.
speakingfish
Интересно. ArrayList же просто обёртка над массивом. Что в нём было неэффективно и возможна ли другая более эффективная обёртка над массивом?
И чем вы заменили HashMap? Параллельными сортированными массивами? И возможна ли эффективная обёртка?
vedenin1980
ArrayList неэффективен если надо работать с примитивными типами, так он всегда использует обертки примитивов, что ест память и производительность. Конечно, существуют trove коллекции, но зачем вводить лишнею обертку над массивами с неизвестным overhead'ом (да и не для всего они подходят), если массива хватало за глаза? Тем более что при больших данных проблема была не в том что неизвестно сколько элементов в массивах, а в том чтобы засунуть работу с миллиардами записей в несчастные сто гигабайт памяти, не убив производительность.
Массивом с похожим функционалов как у HashMap'ы (большую часть тупо скопипастили) но с клонированием ключей и значений вместо создания новых объектов и одновременным поиском/вставкой. Это позволило ускорить работу в пару раз (что в результате позволило сэкономить часы работы сервера ежедневно).
speakingfish
Т.е. эти оптимизации в основном были связаны с неэффективной работой Java с массивами примитивных типов?
vedenin1980
Нет, главные оптимизации были с катомными HashMap — клонирование объектов ключа и значения вместо дорого создания объектов и реализация метода getOrCreate, когда объект находится или создается одной итерацией, а не двумя. Примитивные типы это уже поскольку постольку.