4

Вопрос по java – Как переместить содержимое одного ArrayList в другой?

Есть ли способ переместить все содержимое ArrayList в другой экземпляр ArrayList в O (1)?

Т.е.: только ссылка на резервный массив передается от одного экземпляра к другому (элементы не копируются один за другим).

Например:

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = new ArrayList<>();
a.moveContentsTo(b);
// 'a' is now empty, while 'b' contains everything that 'a' did before and 'a != b'
// It is desired that the 'moveContentsTo' method is O(1)

Еще лучше, есть лиArrayList#swapContents(ArrayList) метод?


Further explanation and use-case:

Further explanation 1: ссылки на «а»; и "b"; не должны быть обменены. Я не ищуtmp = a; a = b; b = tmp; Тип решения.

Further explanation 2: Операция должна быть ~ O (1) во времени.

The use-case: Это полезно, когда объект хочет инкапсулировать список, созданный снаружи:

public class A {
    private ArrayList<String> items = new ArrayList<>();

    /**
     * This method takes the sole ownership of the contents. Whoever
     * passed the list from the outside will not be able to modify
     * contents of 'this.items' from outside the class.
     */ 
    public AnImmutableObject(ArrayList<String> items) {
        if (items != null) {
            items.moveContentsTo(this.items);
        }
    }

    /**
     * Other collections that do not provide the 'move' functionality
     * must be copied. If we just stored the reference to 'items' we
     * would break encapsulation as whoever called the constructor
     * still have write capabilities to the collection.
     */ 
    public A(Collection<String> items) {
        if (items != null) {
            this.items.addAll(items);
        }
    }

    public List<String> getItems() {
        return Collections.unmodifiableList(items);
    }
}

Обратите внимание, что мы хотим избежать копирования (чтобы увеличить скорость и уменьшить использование памяти). Важным моментом является то, что вызываемый должен потерять способность изменять (теперь инкапсулирован)ArrayList.

  • @ Синхарадж: Я не знаю, если это O (1) в С ++, я не смог выяснить, какова сложность времениstd::move или. Более того,std::move полагается на значения r для семантики перемещения и которые недоступны в Java, см. этот ответ:stackoverflow.com/questions/9498381/…

    от
  • Да, похоже на это. Я потратил целую вечность, пытаясь найти эту функцию. Полагаю, нам в конечном итоге придется признать и сказать: нет, в Java нет способа сделать это.

    от sinharaj
  • @ Синхарадж: Я не верю, что вы можете сделать это за O (1) время ... вы можете сделать это за O (n) время ...

    от
  • std::move(a) удостоверяется, чтоa является ссылкой на r-значение. Исходя из этого, вместоcopy конструкторmove конструктор может быть вызван. Последний затем просто перемещает указатель резервного массива из одного контейнера в другой (очевидно, O (1)). Ну, поскольку в Java нет понятия r-значения, нам придется прибегнуть к методам, которые имеют доступ к инкапсулированным данным (как предложеноmoveContentsTo). Этот метод будет делать что-то похожее наmove конструктор в C ++.

    от sinharaj
  • Это не удовлетворяет требованиям. Посмотри пожалуйстаfurther explanation (добавлено постфактум).

    от sinharaj
  • +1 заImmutableList ссылка.

    от sinharaj
  • @Lirik n количество операций, но одновременно! который я считаю, что это похоже на O (1).

    от
  • @sinharaj Я считаю, что нет способа переместить элементы из ArrayList в другой как O (1),unless вы используете многопоточность (назначая поток для каждого элемента в списке, задачей которого является перенос элемента в другой список).

    от
  • @ Eng.Если даже это не будет O (1), вы все равно будете выполнять n операций.

    от
  • @ Eng.Fouad Я получаю то, что вы пытаетесь сказать, но сложность времени не рассчитывается исходя из того, сколько у вас ядер. Кроме того, если у вас n-количество ядер, вы не сможете достичь O (1) времени.

    от
  • Это тоже не соответствует требованиям. Операция должна быть O (1). Если толькоaddAll операции O (1), которые, я полагаю, не являются ".

    от sinharaj
  • Посмотрите на вариант использования - он должен быть эффективным способом передачи коллекций, а также перемещения "владения". Кроме того, посмотрите на семантику перемещения C ++ - 11, я пытаюсь сделать что-то подобное.

    от sinharaj
  • Там должен быть только одинArrayList который владеет владельцем резервного массива.moveContentsTo должны гарантировать, что и за пределамиArrayList получить доступ к резервному массиву (инкапсуляция не должна нарушаться). Например, C ++ - 11 вполне способен сделать это.

    от sinharaj
  • Вы должны скопировать исходный код ArrayList и создать свою собственную версию. ArrayList не допускает таких расширений, потому что для резервного массива установлено значение private.

    от user845279
  • Но неизменностьAnImmutableObject становится скомпрометированным, если вы копируете ссылку на резервный массив вместо содержимого списка массивов. Если вы не заботитесь об этом, скопируйте ссылку наArrayList будет функционально эквивалентен тому, что вы хотите.

    от trutheality
  • Нет ничего, что скопировало бы ссылку на резервный массив (и было бы небезопасно делать это). Почему вы хотите этого? Что вы пытаетесь достичь?

    от trutheality
  • 2

    Тем не менее, если вы ищете настоящий

    @Lirik ответ лучше +1.ArrayList#swapContents(ArrayList)Вот как вы можете это сделать:

    public static void swapContents(ArrayList<String> listA, ArrayList<String> listB)
    {
        List<String> temp = new ArrayList<String>(listA);
        listA.clear();
        listA.addAll(listB);
        listB.clear();
        listB.addAll(temp);
    }
    

  • 2

    AFAIK

    он не очень похож на Java, чтобы отслеживать «владение» ссылок (по крайней мере, на стороне программиста), поэтому я сомневаюсь, что вы найдетеstd::move()как функциональность, которую вы хотите. Это просто не очень нужно в Java. Я предполагаю, что C ++ должен явно отслеживать владение объектом, потому что нет сборки мусора.

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

    public class AnImmutableObject {
    
        private final List<String> items;
    
        /**
         * Creates a new immutable object with the given list of items.
         * Always deep copy from an outside source, because we can't know if the
         * calling code will modify that collection later.
         */ 
        public AnImmutableObject(Collection<String> items) {
            // It's a constructor. We know items needs to be set.
            // We are creating a new array list, using its constructor which deep
            // copies the collection, and immediately wrapping it to make it truly
            // immutable. We are guaranteed that no one will hold a reference to the
            // mutable view of the new ArrayList.
            this.items = Collections.unmodifiableList(new ArrayList<String>(items));
        }
    
        /**
         * Creates a new immutable object with the same items as another.
         * Copying the reference here is completely safe because we
         * enforce the immutability of the items array.
         */ 
        public AnImmutableObject(AnImmutableObject source) {
            items = source.items;
        }
    
        public List<String> getItems() {
            return items;
        }
    }
    

    На этом этапе вы можете «передавать массивы вокруг». (действительно разделите их) в O (1) между вашими неизменными объектами:

    ImmutableObject a = new ImmutableObject(Arrays.asList("A", "B", "C")); // O(n)
    ImmutableObject b = new ImmutableObject(a); // O(1)
    

    Надеюсь, что-то подобное может соответствовать вашим целям.

    Другой путь, по которому вы могли бы пойти, это использоватьгуайява& APOS; sImmutableList, Поскольку они являются неизменными, вы можете смело копировать ссылку наImmutableList в конструкторе.

    Основной подход заключается в обеспечении безопасности для вас, чтобы скопировать ссылки на списки, а не брать на себя ответственность за них.

  • 2

    Это должно сделать это:

    ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
    ArrayList<String> b = a;
    a = new ArrayList<>();
    

    Концептуально говоря,a сейчас пусто иb содержит чтоa содержится раньше. Было одно назначение и не было никакого копирования данных, что является самым быстрым, что вы можете сделать. Удовлетворяет ли это ваше требование, или вы действительно хотитеa по-прежнему ссылаться на тот же массив, за исключением того, что данный массив теперь должен быть пустым?

    Update

    I don't believe that in C++ the time complexity for the move operation is O(1) either. Также целесообразно указать, что «поскольку классы в Java используют ссылочную семантику, в этих языках никогда не существует неявных копий объектов.The problem move semantics solve does not and has never existed in Java.& Quot; (см. ответ FredOverflow:C ++ Rvalue ссылки и семантика перемещения)

    Is there a way to move the entire contents of an ArrayList to another ArrayList so that only the reference to the backing array is passed from one to the other (i.e., so that elements are not copied one by one).

    Учитывая приведенное выше утверждение, то если вы скопируете что-то из массиваa массивb в Java оба массива будут ссылаться на одни и те же данные. Все, что вы делаете с семантикой перемещения в C ++, это то, что вы сохраняете временный объект, который необходимо создать, чтобы сделать такую копию:

    X foo();
    X x;
    // perhaps use x in various ways
    x = foo();
    

    Последний делает:

    destructs the resource held by x,
    clones the resource from the temporary returned by foo,
    destructs the temporary and thereby releases its resource. 
    

    Семантика Move делает:

    swap resource pointers (handles) between x and the temporary,
    temporary's destructor destruct x's original resource.
    

    Вы сохраняете один деструктор, но только в C ++ ... вышеупомянутая проблема не существует в Java! Смотрите эту статью для более подробной информации о семантике перемещения:http://thbecker.net/articles/rvalue_references/section_02.html