Можно ли перебирать список внутри другой итерации того же списка? - PullRequest
Новая
       8

Можно ли перебирать список внутри другой итерации того же списка?

0 голосов
/ 23 апреля 2011

У меня есть несколько объектов в ArrayList, и я хочу выполнить обнаружение столкновений и тому подобное.Можно ли делать что-то вроде: 

List<Person> A;
iterA0 = A.iterator();
while (iterA0.hasNext()) {
    Person A = iterA.next();
    iterA1 = A.iterator();
    while (iterA1.hasNext()){
        Person B = iterA1.next();
        A.getsDrunkAndRegretsHookingUpWith(B);
    }
}

Это должно быть ужасное кодирование, верно?Как мне выполнить эту вложенную итерацию соответствующим образом?

Ответы [ 4 ]

4 голосов
/ 23 апреля 2011

Вы можете выполнять итерацию по одному и тому же списку несколько раз одновременно, если он не изменяется ни на одной из итераций. Например: 

List<Person> people = ...;
for (Person a : people) {
    for (Person b : people)
        a.getsDrunkAndRegretsHookingUpWith(b);
}

Пока метод getsDrunkAndRegretsHookingUpWith не меняет список people, все в порядке.

2 голосов
/ 23 апреля 2011

Это пример классической проблемы рукопожатия. В комнате, полной n человек, n выбирают 2 различных возможных рукопожатия. Вы не можете избежать квадратичного времени выполнения.

@ Chris 'answer показывает лучший способ его кодирования.

Re: OP комментарий

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

Вы должны не использовать список для хранения частиц. Если вы моделируете частицы в двух измерениях, используйте quadtree . Если 3 размера, октаву .

0 голосов
/ 23 апреля 2011

Количество итераций может быть уменьшено, если в вашем случае:

  • A.getsDrunkAndRegretsHookingUpWith(B) также подразумевает B.getsDrunkAndRegretsHookingUpWith(A),
  • и A.getsDrunkAndRegretsHookingUpWith(A) всегда будут одинаковыми для всех элементов

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

List<Person> people;
for (int i=0; i<people.size(); i++){
    a = people.get(i);
    for (int j=i+1; j<people.size();j++){ // compare with next element and onwards in the list
        a.getsDrunkAndRegretsHookingUpWith(people.get(j)); // call method
    }
}
0 голосов
/ 23 апреля 2011

Это должно быть ужасное кодирование, верно?

Большинство людей, вероятно, согласятся, что если вы используете Java 5+, и не было особой необходимости выставлять объекты итератора, то вам следует упростить код, используя цикл «для каждого». Однако это не должно иметь никакого значения для производительности и, конечно, не для сложности.

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

Так как же сделать n ^ 2 над собой?

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

В зависимости от отношения real вы можете использовать симметрию / антисимметрию или ассоциативность для сокращения объема работы.

Однако без этой информации (или другой информации о домене) вы не сможете улучшить это решение.

Для вашего реального примера (с участием частиц) вы можете избежать проблемы сравнения O(N^2), разделив экран на области; например используя квадри. Затем вы перебираете точки в одной и той же и соседних областях.

...