Составление списка в Java

Question

Скажем, у меня есть java.util.List list, и я хочу создать новый List, добавив элемент e в начало list (т. Е. Я хочу cons e и list). Например, если list равно

[1,2,3,4]

и e равно 5, тогда cons(e,list) будет

[5,1,2,3,4]

Все элементы list и cons(e,list) могут использоваться совместно, но list изменять не следует.

Какой самый простой и / или наиболее эффективный способ реализации cons? Это нормально для результата, который нельзя изменить. Использование библиотеки коллекций Google разрешено.

Что если list является com.google.common.collect.ImmutableList?

Answer 1

public static<T> List<T> cons(List<T> list, T t) {
    ArrayList<T> result = new ArrayList<T>(list);
    result.add(0, t);
    return result;
}

Отредактировано в ответ на комментарии: Поскольку вопрос задавался о «самом простом и / или наиболее эффективном способе реализации минусов», я выбрал «самый простой». Я не удивлюсь, узнав, что есть более эффективные способы. Размещение элемента перед списком - это еще один правильный подход, и первоначальное выделение правильного размера может, вероятно, повысить производительность. Преждевременная оптимизация - корень всего зла.

Answer 2

Clojure обеспечивает такого рода Lisp-й материал. Хотя большинство людей думают об использовании Clojure для языка (как и я), все библиотеки Clojure - это настоящий код Java, и вы можете использовать структуры данных из Java как просто специальную библиотеку, если хотите. Таким образом, вы получите способность делать минусы и тому подобное, и вы получите неизменность, которую использует Clojure. Строки данных Clojure также реализуют эквивалентные типы Java.

Просто мысль из другого направления.

Answer 3

Эффективным решением было бы создание собственной реализации List с ленивым делегированием. Если его нельзя изменить, проблем не будет. Если он создан с помощью метода фабрики, вы можете даже использовать одну из двух различных базовых реализаций в зависимости от того, реализует ли аргумент List RandomAccess или нет.

Для простейшего случая (не проверялось, компилируется ли он, нет проверок работоспособности и т. Д.):

class ConsList<E> extends AbstractList<E>
{
    private final E first;
    private final List<E> rest;

    ConsList( E first, List<E> rest )
    {
        this.first = first;
        this.rest = rest;
    }

    public int get( int index )
    {
        return (index == 0) ? first : rest.get( index - 1 );
    }

    public int size()
    {
        return rest.size() + 1;
    }
}

Я уверен, что некоторые другие методы могли бы быть более эффективными, и последовательный случай был бы лучше обработан, если вместо этого расширить AbstractSequentialList.

Answer 4

Я думаю, что ответ, который вы действительно ищете, таков:

http://functionaljava.googlecode.com/svn/artifacts/2.20/javadoc/fj/data/List.html

Этот метод даже называется cons.

У меня нет опыта работы с этой библиотекой. Просто слышал об этом на днях. Надеюсь, это хорошо!

Answer 5

Это не очень хорошо известно, но API компилятора javac Sun содержит неизменяемую реализацию List, которая возвращает новые неизменяемые списки с использованием таких методов, как append() и prepend(). Чтобы использовать его, вам нужно tools.jar на пути к классам, и этот оператор импорта:

import com.sun.tools.javac.util.List;

Пример кода:

final List<Integer> list = List.of(6, 7);
System.out.println(list);

final List<Integer> newList =
    list.prepend(5)                       // this is a new List
        .prependList(List.of(1, 2, 3, 4)) // and another new List
        .append(8)                        // and another
        .reverse();                       // and yet another
System.out.println(newList);

System.out.println(list == newList);

System.out.println(list.getClass());
System.out.println(newList.getClass());

Выход:

6,7
8,7,6,5,4,3,2,1
ложь
Класс com.sun.tools.javac.util.List
Класс com.sun.tools.javac.util.List

Я знаю, что это внутренний API, и его не следует использовать в производстве, но это очень весело (наконец, коллекция java, которая кажется правильной).

Примечание: Все стандартные изменяемые методы из интерфейсов Collection и List (например, add() addAll()) выдают UnsupportedOperationException, очевидно.

Справка:

• com.sun.tools.javac.util.List ( DocJar )

Answer 6

Поскольку вы упоминаете функцию cons, я предполагаю, что вы подходите к этой проблеме с концептуальной моделью связанных списков, состоящих из cons ячеек. В частности, я предполагаю, что вы думаете о каждом списке, имеющем car (первый элемент) и cdr (подсписок, содержащий все следующие элементы).

Java поддерживает связанные списки как java.util.LinkedList. Они хороши для линейного обхода и могут очень эффективно вставлять элементы. Они наиболее похожи на связанные списки, которые я упоминал выше.

Java также предлагает java.util.ArrayList. Списки такого типа хороши для произвольного доступа, но могут быть медленными при вставке элементов. На самом деле они самые медленные при вставке элемента в начало списка. Поскольку ArrayList реализованы как массивы за сценой, каждый элемент должен быть скопирован на одну позицию вперед в списке, чтобы освободить место для нового первого элемента. Теперь, если вам также понадобится больший массив, ArrayList выделит новый массив, скопирует все элементы и т. Д.

(Google 1015 * упоминается как «произвольный доступ», так что, скорее всего, он больше похож на последний.)

Если вы планируете часто использовать свой метод cons, я рекомендую использовать его со связанными списками. Операция cons по существу добавляет элемент в начале списка. Это имеет мало смысла для линейных структур, таких как массивы. Я рекомендую не использовать списки массивов по этой причине: они концептуально не подходят для работы.

Для очень требовательных: поскольку новый список возвращается каждый раз, когда вызывается cons, копирование должно выполняться независимо от того, является ли список LinkedList или ArrayList. Однако весь принцип операции cons заключается в том, что она работает в связанном списке.

public <E> LinkedList<E> cons(E car, List<E> cdr) {
    LinkedList<E> destination = new LinkedList<E>(cdr);
    destination.addFirst(car);
    return destination;
}

Обратите внимание, что приведенный выше код был написан после прочтения приведенных выше ответов, поэтому я прошу прощения за любой случайный плагиат. Дайте мне знать, если вы это увидите, и я правильно подтвердю.

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

Answer 7

Наверняка LinkedList был бы наиболее эффективным способом вставить элемент в начало списка?

Просто используйте класс LinkedList , который поставляется с Java

Answer 8

Я собираюсь бросить свои 2 цента, а затем посмотреть, если кто-нибудь придумает что-нибудь более элегантное. В общем случае:

<E> List<E> cons(E e, List<E> list) {
    List<E> res = Lists.newArrayListWithCapacity(list.size() + 1);
    res.add(e);
    res.addAll(list);
    return res;
}

С ImmutableList (не знаю, насколько это эффективно):

<E> ImmutableList<E> cons(E e, ImmutableList<E> list) {
    return ImmutableList.<E>builder()
                        .add(e)
                        .addAll(list)
                        .build();
}

Answer 9

Не могли бы вы использовать CompositeCollection ?

public Collection cons(Collection c1, Collection c2)
{
    CompositeCollection cons = new CompositeCollection();
    cons.addComposited(c1);
    cons.addComposited(c2);
    return cons;
}

Это не зависит от того, является ли один из параметров неизменным и поддерживается ли исходная коллекция c1 и c2.

Если вам нужен List, я бы, вероятно, сделал следующее:

public List cons(Collection c1, Collection c2)
{
    ArrayList cons = new ArrayList(c1.size() + c2.size());
    cons.addAll(c1);
    cons.addAll(c2);
    return cons;
}

Answer 10

Еще один вариант, если у вас есть только Iterable.

public static <E> List<E> cons(E e, Iterable<E> iter) {
   List<E> list = new ArrayList<E>();
   list.add(e);
   for(E e2: iter) list.add(e2);
   return list;
}

public static <E> List<E> cons(Iterable<E>... iters) {
   List<E> list = new ArrayList<E>();
   for(Iterable<E> iter: iters) for(E e1: iter1) list.add(e1);
   return list;
}