Java: Реализация коллекции «повторять до тех пор, пока не изменится» - PullRequest
2 голосов
/ 21 февраля 2010

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

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

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

Каков наилучший способ сделать это? Есть ли коллекция, которая поддерживает это из коробки? Третья сторона тоже в порядке.

Любая помощь будет принята с благодарностью!

Ответы [ 3 ]

4 голосов
/ 21 февраля 2010

Я бы просто использовал логическую переменную, которая установлена ​​в false в начале основного цикла. Когда вносится изменение в список во внутреннем цикле, это может быть установлено в true, если не было внесено никаких изменений, оно остается ложным. Затем основной цикл может продолжить цикл, если это так, или завершить цикл в противном случае

1 голос
/ 21 февраля 2010

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

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

runAlgo(Collection c) {
  // do work

  if (collectionUpdated)
    return runAlgo(c); // potential stackoverflow with huge collection or too many calls from lots of collection updates
  else
    return c;
}
0 голосов
/ 21 февраля 2010

Поскольку вы говорите, что порядок не имеет значения, используйте реализацию интерфейса Set , например HashSet . Вы можете сравнивать множества на равенство просто с помощью метода equals.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...