Хорошо, ниже моя последняя реализация, включающая обратную связь (в основном от Стивена, Кэмерона и Петро), которая включает в себя полное устранение конфликта toArray () [] - vs-interator (). Next (). И я прибавил в комментариях, чтобы более точно различать, что происходит и почему. И чтобы лучше понять, почему я конкретно реализовал оригинальный совет Петро «использовать набор отслеживания» (поддержанный Кэмероном). И сразу после фрагмента кода я сопоставлю его с другими предлагаемыми решениями.
private Set<Coordinate> floodFind3(Coordinate coordinate)
{
Set<Coordinate> area = new LinkedHashSet<Coordinate>(); //includes only area of value (which is the same as at coordinate)
area.add(coordinate);
Value value = getCoordinateValue(coordinate); //value upon which to expand area
Set<Coordinate> checked = new LinkedHashSet<Coordinate>(); //every coordinate evaluated regardless of value
checked.add(coordinate);
Queue<Coordinate> candidates = new LinkedList<Coordinate>(); //coordinates evaluated, were of value, and are queued to iterate through their adjacents
candidates.add(nordinate);
while (!candidates.isEmpty())
{
for (Nordinate coordinateAdjacent: this.query.getNordinates().getAdjacent(candidates.remove()).getOrthogonal())
{
if (checked.add(coordinateAdjacent)) //only expands containing value and !value
{
if (getCoordinateValue(coordinateAdjacent) == value)
{
area.add(coordinateAdjacent); //only expands containing value
candidates.add(coordinateAdjacent); //expands and contracts containing value
}
}
}
}
return area;
}
Я обновил метод несколькими значительными способами:
-
Еще один параметр метода меньше: я удалил параметр, так как он был извлечен из поиска, и устранил возможную логическую проблему, когда начальная координата указывает на местоположение, содержащее значение!
-
Три коллекции отслеживают поиск; область (Set), отмеченные (Set) и кандидаты (Queue). Комментарии кода разъясняют конкретное использование каждого. Использовал LinkedHashSet для надежной воспроизводимости при поиске ошибок и проблем с производительностью (/1448483/poryadok-iteratsii-hashset). После стабилизации я, скорее всего, вернусь к более быстрой реализации HashSet.
-
Перед тестом «is value» изменился порядок проверки «проверена ли уже оценка», чтобы каждая координата посещалась только один раз. Это позволяет избежать повторного просмотра значения соседних координат более одного раза. Также включено умное двойное использование Стивеном метода Set add (). Это становится очень важным, поскольку область затопления становится более похожей на лабиринт (змеиный / паучий).
-
Сохраняйте "==" для проверки значения, вызывая сравнение ссылок. Значение определено как Enum Java 1.5, и я не хотел зависеть от HotSpot, чтобы встроить вызов метода .equals () и сократить его до сравнения ссылок. Если бы ценность когда-либо изменилась с того, чтобы быть Enum, этот выбор мог бы вернуться, чтобы укусить меня. Tyvm Стивену за указание на это.
Решения Петро и Стефана посещают координаты, содержащие значение, только один раз, но требуют повторного пересмотра координат, содержащих! Value, более одного раза, что может привести к нескольким повторным проверкам выборок / значений для областей, состоящих из длинных лабиринтных туннелей. Хотя «длинные лабиринтоподобные туннели» можно считать патологическим случаем, это более типично для конкретной области, для которой мне нужен этот метод. И мое «второе» попытанное решение (которое имело низкую производительность, вызов LinkedList содержит ()) было сомнительным как реальный ответ ({кивок Стивену на этом).
Спасибо за ваши отзывы.
Далее, много эмпирических испытаний с единичными вариациями / изменениями в течение сотен миллионов вызовов. Я обновлю этот ответ с деталями когда-нибудь в эти выходные.