Постоянные структуры данных в Java

Question

Кто-нибудь знает библиотеку или хотя бы какие-нибудь исследования по созданию и использованию постоянных структур данных в Java? Я не называю постоянство долговременным хранением, а постоянство с точки зрения неизменности (см. Статью в Википедии).

В настоящее время я изучаю различные способы моделирования API для постоянных структур. Использование компоновщиков представляется интересным решением:

// create persistent instance
Person p = Builder.create(Person.class)
             .withName("Joe")
             .withAddress(Builder.create(Address.class)
                 .withCity("paris")
                 .build())
              .build();

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack");

Person p3 = Builder.update(p)
              .withAddress(Builder.update(p.address())
                .withCity("Berlin")
                .build)
            .build();

Но это все еще чувствует себя несколько сложным. Есть идеи?

Answer 1

Я думаю, очевидные варианты:

o Переключиться на временную структуру данных (построитель) для обновления. Это вполне нормально. StringBuilder за String манипуляция например. Как твой пример.

Person p3 =
    Builder.update(p)
    .withAddress(
        Builder.update(p.address())
       .withCity("Berlin")
       .build()
    )
    .build();

o Всегда используйте постоянные конструкции. Несмотря на то, что копирование выглядит много, на самом деле вы должны делиться почти всеми состояниями, так что это далеко не так плохо, как кажется.

final Person p3 = p
    .withAddress(
        p.address().withCity("Berlin")
    );

o Разобрать структуру данных на множество переменных и объединить с помощью одного огромного и запутанного конструктора.

final Person p3 = Person.of(
    p.name(),
    Address.of(
       p.house(), p.street(), "Berlin", p.country()
    ),
    p.x(),
    p.y(),
    p.z()
 );

o Использовать интерфейсы обратного вызова для предоставления новых данных. Еще более шаблонный.

final Person p3 = Person.of(new PersonInfo(
    public String  name   () { return p.name(); )
    public Address address() { return Address.of(new AddressInfo() {
       private final Address a = p.address();
       public String house  () { return a.house()  ; }
       public String street () { return a.street() ; }
       public String city   () { return "Berlin"   ; }
       public String country() { return a.country(); }
    })),
    public Xxx     x() { return p.x(); }
    public Yyy     y() { return p.y(); }
    public Zzz     z() { return p.z(); }
 });

o Используйте неприятные хаки, чтобы сделать поля временно доступными для кода.

final Person p3 = new PersonExploder(p) {{
    a = new AddressExploder(a) {{
        city = "Berlin";
    }}.get();
}}.get();

(Как ни странно, Крис Окасаки написал мне "Чисто функциональные структуры данных").

Answer 2

Строители сделают ваш код слишком многословным, чтобы его можно было использовать. На практике почти все неизменяемые структуры данных, которые я видел, передаются в состоянии через конструктор. Для чего стоит, вот хорошая серия публикаций, описывающих неизменные структуры данных в C# (которые должны легко конвертироваться в Java):

• Часть 1: Виды Неизменности
• Часть 2: Простой неизменный стек
• Часть 3: Ковариантный неизменяемый стек
• Часть 4: Неизменная очередь
• Часть 5: Lolz! (включено для полноты)
• Часть 6: Простое двоичное дерево
• Часть 7: Подробнее о двоичных деревьях
• Часть 8. Еще больше о бинарных деревьях
• Часть 9: реализация дерева AVL
• Часть 10: Двусторонняя очередь
• Часть 11. Работа с реализацией двусторонней очереди

C# и Java чрезвычайно многословны, поэтому код в этих статьях довольно страшный. Я рекомендую изучить OCaml, F# или Scala и ознакомиться с неизменяемостью этих языков. Освоив эту технику, вы сможете гораздо проще применять тот же стиль кодирования к Java.

Answer 3

Взгляните на функциональную Java. В настоящее время предоставляются постоянные структуры данных:

• Односвязный список (fj.data.List)
• Ленивый односвязный список (fj.data.Stream)
• Непустой список (fj.data.NonEmptyList)
• Необязательное значение (контейнер длиной 0 или 1) (fj.data.Option)
• Set (fj.data.Set)
• Многоцелевое дерево (иначе розовое дерево) (fj.data.Tree)
• Неизменяемая карта (fj.data.TreeMap)
• Изделия (кортежи) арити 1-8 (фж.П1..П8)
• Векторы арити 2-8 (fj.data.vector.V2..V8)
• Остроконечный список (fj.data.Zipper)
• Остроконечное дерево (fj.data.TreeZipper)
• Типобезопасный универсальный гетерогенный список (fj.data.hlist.HList)
• Неизменяемые массивы (fj.data.Array)
• Тип несвязанного объединения (fj.data.Either)

Ряд примеров использования предоставляется с бинарным распределением. Источник доступен по лицензии BSD от Google Code.

Answer 4

Я реализовал несколько постоянных структур данных в Java. Все с открытым исходным кодом (GPL) на код Google для всех, кто заинтересован:

http://code.google.com/p/mikeralib/source/browse/

Основные из них, которые у меня пока есть:

• Постоянный изменчивый тестовый объект
• Постоянные хеш-карты
• Постоянные векторы / списки
• Постоянные наборы (включая специализированный постоянный набор целых)

Answer 5

Выполните очень простую предварительную проверку с динамическим прокси:

class ImmutableBuilder {

    static <T> T of(Immutable immutable) {
        Class<?> targetClass = immutable.getTargetClass();
        return (T) Proxy.newProxyInstance(targetClass.getClassLoader(),
            new Class<?>[]{targetClass},
            immutable);
    }

    public static <T> T of(Class<T> aClass) {
        return of(new Immutable(aClass, new HashMap<String, Object>()));
    }
}

class Immutable implements InvocationHandler {

    private final Class<?> targetClass;
    private final Map<String, Object> fields;

    public Immutable(Class<?> aTargetClass, Map<String, Object> immutableFields) {
        targetClass = aTargetClass;
        fields = immutableFields;
    }

    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
        if (method.getName().equals("toString")) { 
            // XXX: toString() result can be cached
            return fields.toString();
        }

        if (method.getName().equals("hashCode")) { 
            // XXX: hashCode() result can be cached
            return fields.hashCode();
        }

        // XXX: naming policy here
        String fieldName = method.getName(); 

        if (method.getReturnType().equals(targetClass)) {
          Map<String, Object> newFields = new HashMap<String, Object>(fields);
          newFields.put(fieldName, args[0]);
          return ImmutableBuilder.of(new Immutable(targetClass, newFields));
        } else {
            return fields.get(fieldName);
        }
    }

    public Class<?> getTargetClass() {
        return targetClass;
    }
}

использование:

interface Person {
    String name();
    Person name(String name);
    int age();
    Person age(int age);
}

public class Main {

    public static void main(String[] args) {
        Person mark = ImmutableBuilder.of(Person.class).name("mark").age(32);
        Person john = mark.name("john").age(24);
        System.out.println(mark);
        System.out.println(john);
    }
}

Направления роста:

• политика именования (getName, withName, name)
• кэширование toString(), hashCode()
• Реализация equals() должна быть простой (хотя и не реализованной)

Надеюсь, поможет:)

Answer 6

Очень трудно, если не невозможно, сделать вещи неизменными, которые не предназначены для этого.

Если вы можете разработать с нуля:

• используйте только последние поля
• не ссылаться на неизменяемые объекты

Answer 7

См. https://github.com/GlenKPeterson/Paguro для получения информации о постоянных структурах данных для Java.

В некоторых других ответах предлагались библиотеки для неизменяемости, что хорошо, но не то, что просили. Paguro — это библиотека, предоставляющая настоящую постоянную структуру данных, допускающую мутации и сохраняющую при этом предыдущую версию себя!

Answer 8

Вы хотите неизменности:

1. так внешний код не может изменить данные?
2. так однажды установить значение нельзя изменить?

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

Остановить внешний код от изменения данных легко с помощью интерфейсов:

public interface Person {
   String getName();
   Address getAddress();
}
public interface PersonImplementor extends Person {
   void setName(String name);
   void setAddress(Address address);
}

public interface Address {
    String getCity();
}


public interface AddressImplementor {
    void setCity(String city);
}

Затем, чтобы остановить изменение значения после его установки, также "легко" с помощью java.util.concurrent.atomic.AtomicReference (хотя может потребоваться изменение режима гибернации или другого использования персистентного уровня):

class PersonImpl implements PersonImplementor {
    private AtomicReference<String> name;
    private AtomicReference<Address> address;

    public void setName(String name) {
        if ( !this.name.compareAndSet(name, name) 
           && !this.name.compareAndSet(null, name)) {
            throw new IllegalStateException("name already set to "+this.name.get()+" cannot set to "+name);
        }
    }
    // .. similar code follows....
}

Но для чего вам нужно нечто большее, чем просто интерфейсы для выполнения задачи?

Answer 9

В Google Guava теперь размещаются различные неизменяемые / постоянные структуры данных.