Итерируемая коллекция, которая может изменяться во время итерации

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

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

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

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

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

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

Для C#: обычные Коллекции не могут быть изменены из контекста перечислителя, но вы можете проверить Библиотека потока данных TPL

Pretasoc 10.09.2018 09:59

В java см. List#listIterator и ListIterator

Misha 10.09.2018 10:06

Почему вы просите C# и java? Если он вам нужен для java, но есть класс на C#, как это вам помогло?

Tim Schmelter 10.09.2018 10:10

@TimSchmelter Это помогает мне, потому что я программирую и то, и другое, и я хочу знать это для собственного обучения. Это не так уж и странно, правда?

ErikE 10.09.2018 10:13

Я могу только второй @Misha на Java, просто использовать изменяемый список и получить ListIterator. Но модификации на месте не всегда более эффективны, чем заполнение нового списка.

Holger 10.09.2018 11:20

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

Matthew Watson 10.09.2018 13:30

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

ErikE 10.09.2018 20:04
3
7
326
3

Ответы 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, и ничего не менять до текущего индекса (который из чтения ваших требований не требуется).

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

Какова эффективность удаления элемента из середины списка?

ErikE 10.09.2018 10:19

@ErikE: stackoverflow.com/questions/6052003/… (MSDN: «Этот метод представляет собой операцию O (n), где n - (Счетчик - индекс)»)

Tim Schmelter 10.09.2018 10:25

Я ожидал, что в окончательном списке будет 9, потому что добавленные элементы не должны повторяться.

ErikE 10.09.2018 10:26

@MatthewWatson Вот чего я и боялся ... перетасовать все оставшиеся предметы.

ErikE 10.09.2018 10:28

@ErikE Тогда вы должны добавить это к своим требованиям. Они говорят New elements can be added, but will not affect the current iteration., тогда как вы имели в виду New elements can be added, but will not affect the current iteration **or any future iteration**.

Matthew Watson 10.09.2018 10:28

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

Matthew Watson 10.09.2018 10:29

@MatthewWatson Я пытался прояснить это требование, прошу прощения, это было двусмысленно. «Итерация» может относиться ко всему процессу или к одному из многих. Как и в случае с IEnumerable, вы запрашиваете у него IEnumerator, а затем выполняете перечисление, но другой поток может начать перечисление того же IEnumerator и получить другой список. Второе предложение после двусмысленного я также добавил ранее, чтобы было понятнее.

ErikE 10.09.2018 10:35

Для 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> может быть более чистым в использовании.

Как избежать появления новых элементов в процессе итерации, если использовать ListIterator?

ErikE 10.09.2018 10:38

Вы можете просто пропустить добавленный элемент. listIterator.add(e); и сразу же listIterator.next();.

V0ldek 10.09.2018 11:21

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

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

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

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

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

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

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

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

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

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

Похоже, что реализация, которую я изначально написал в связанном ответе (внизу моего вопроса), вероятно, близка к лучшей, которую я собираюсь получить, а?

ErikE 10.09.2018 20:09

Другие вопросы по теме