Итеративная коллекция, которая может быть видоизменена во время итерации

Question

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

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

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

Таким образом, копирование элементов во вновь созданный объект коллекции каждый раз кажется неэффективным по сравнению с тем, который имел эти свойства добавления / удаления.

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

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

Answer 1

Для C # вы можете использовать LinkedList<T> как в добром старом C:

public DoStuff<T>(LinkedList<T> list)
{
    var node = list.First;

    while(node != null)
    {
        // do stuff with node

        node = node.Next;
    }
}

node имеет тип LinkedListNode<T>. Вы можете получить доступ к значению с помощью node.Value, удалить с помощью list.Remove(node). Для T elem у вас также есть list.AddAfter(node, elem), list.AddBefore(node, elem), list.AddFirst(elem) и list.AddLast(elem). Все эти операции являются O (1). Вы можете выполнять все виды итераций с этим, если вы хотите выполнять итерации только по оригинальным элементам, затем кэшировать следующий узел, прежде чем что-либо делать, и запомнить последний узел:

var lastNode = list.Last;
var node = list.First;

while(node != lastNode.Next)
{
    var nextNode = node.Next;

    // do stuff with node

    node = nextNode;
}

Эквивалентная структура данных в Java также называется LinkedList<E>. Однако ListIterator<E> на стандартном List<E> может быть более удобным в использовании.

Answer 2

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

Вы также можете создать свой собственный тип коллекции с таким поведением. Это будет 3 лайнера:

public class ConstantIterationArrayList<T> extends ArrayList<T> {
    public Iterator<T> iterator() {
        return new ArrayList<T>(this).iterator();
    }
}

(Приведенное выше делает копию списка, а затем дает вам итератор для копии, таким образом, удобно гарантируя, что любая модификация этого списка не окажет абсолютно никакого влияния на этот итератор).

Вот реальная проблема с вашим вопросом:

Выше время от времени будут создаваться копии основного хранилища данных (мой фрагмент выше делает это каждый раз, когда вы создаете итератор. CopyOnWriteArrayList делает это каждый раз, когда вы вызываете remove() или add()). Операция «копирование основного хранилища данных» занимает O (n) время, т. Е. Для списка, который вдвое больше, требуется вдвое больше.

ArrayList в общем обладает тем свойством, что операция remove(), если только вы не удаляете элемент в конце или очень близко к концу списка, является операцией O (n) : удаление Элемент из списка занимает в два раза больше времени, если список в два раза больше.

К счастью, современные процессоры имеют значительные кэши и могут работать очень быстро на странице кэша. Что означает: несмотря на тот факт, что копирование данных выглядит неэффективно, на практике, если массив резервных копий помещается на странице или около того, он на намного быстрее, чем хранилища данных на основе семантики LinkedList. Мы говорим о ~ 1000 элементов, которые можно брать или брать. (Обратите внимание, что почти все, что вы делаете с LinkedList, это O (n) , и где ArrayList хорошо работает с современной архитектурой процессора, LinkedList имеет тенденцию работать очень плохо. Дело в том, что LinkedList тоже очень редко правильный ответ!)

Итак, если у вас не более ~ 1000 элементов в этом списке, я бы выбрал CopyOnWriteArrayList или пользовательский класс, который я написал для вас выше.

Однако, если у вас на больше этого значения, ArrayList не является подходящим хранилищем данных для использования здесь. Даже если вы забудете о своих постоянных итерационных потребностях на данный момент; вызывать remove() в списках больших массивов - плохая идея (если только удаление не очень близко к концу списка). В этом случае я бы в общих чертах наметил, какие именно операции вам нужно выполнить с этим типом данных, и какие действительно нужно выполнить быстро, и, как только у вас будет полный список, я постараюсь найти тип коллекции, который точно соответствует вашим потребностям, и в (вероятном) случае не существует ничего конкретного, что идеально подходит, сделайте это сами. Как и выше, когда вам нужно свернуть свой собственный тип данных, обычно хорошей идеей будет позволить большую часть работы выполнить существующими типами данных, поэтому либо расширьте существующий, либо инкапсулируйте один.

Answer 3

В C # это достаточно просто сделать с List<T> и for (...), а не foreach (...):

using System;
using System.Collections.Generic;
using System.Linq;

namespace Demo
{
    static class Program
    {
        static void Main()
        {
            List<int> list = Enumerable.Range(1, 10).ToList();

            for (int i = 0; i < list.Count; ++i)
            {
                if ((list[i] % 3) == 0) // Remove multiples of 3.
                    list.RemoveAt(i--); // NOTE: Post-decrement i
                else if ((list[i] % 4) == 0) // At each multiple of 4, add (2*value+1)
                    list.Add(list[i] * 2 + 1);
                else
                    ; // Do nothing.
            }

            Console.WriteLine(string.Join(", ", list)); // Outputs 1, 2, 4, 5, 7, 8, 10, 17
        }
    }
}

Ключевым моментом здесь является использование индекса, а не foreach, и ничего не изменять до текущего индекса (который при чтении ваших требований не нужен).

Однако если вам нужно добавить или удалить элементы до текущего индекса, тогда этот подход не работает (или, по крайней мере, он становится намного более сложным).