Как сделать так, чтобы циклы for проходили рядом?
Я работаю над маленькой детской программой: на экране куча кружочков разного цвета и размера. Когда больший круг встречает меньший круг, он съедает меньший круг, а когда круг съел достаточно других кругов, он воспроизводится. Это вроде изящно!
Однако, как я это реализовал, процесс обнаружения ближайших кругов и проверки их на съедобность выполняется с помощью цикла for, который проходит через всю живую популяцию кругов ... что занимает все больше и больше времени, поскольку популяция имеет тенденцию увеличиваться в размерах. 3000, прежде чем он начнет падать. Этот процесс не замедляет мой компьютер, я могу пойти и поиграть в Dawn of War или что-то еще, и нет никакого замедления: это просто процесс проверки каждого круга, чтобы увидеть, не столкнулся ли он с каждым другим кругом ... .
Так что мне пришло в голову, что я мог бы попытаться разделить окно приложения на четыре квадранта и заставить кружки в квадрантах выполнять свои проверки одновременно, поскольку у них почти не было бы шансов мешать друг другу: или что-то в этом роде !
Тогда мой вопрос: как сделать так, чтобы циклы работали бок о бок? Скажем, на Яве.
эти круги движутся? случайно? Я думаю, вам нужно немного сказать об этом, прежде чем я выскажу свои предложения.
Ответы 7
ЕСЛИ ваш компьютер имеет несколько процессоров или несколько ядер, вы можете легко запускать несколько потоков и запускать меньшие части циклов в каждом потоке. Многие ПК в наши дни действительно имеют несколько ядер - поэтому сделайте так, чтобы каждый поток получал 1 / n-ю от числа циклов, а затем создавал n потоков.
Компьютеры обычно являются однозадачными, это означает, что они обычно могут выполнять по одной инструкции за раз для каждого процессора или ядра.
Однако, как вы заметили, ваша операционная система (и другие программы), похоже, выполняет множество задач одновременно.
Это достигается путем разделения работы на процессы, и каждый процесс может дополнительно реализовать параллелизм, порождая потоки. Затем операционная система очень быстро переключается между каждым процессом и потоком, создавая иллюзию многозадачности.
В вашей ситуации ваша java-программа представляет собой единый процесс, и вам нужно будет создать 4 потока, каждый из которых будет выполнять свой собственный цикл. Это может быть сложно, потому что потокам необходимо синхронизировать свой доступ к локальным переменным, чтобы один поток не редактировал переменную, в то время как другой поток пытается получить к ней доступ.
Поскольку многопоточность - сложная тема, потребовалось бы гораздо больше объяснений, чем я могу здесь сделать.
Однако вы можете прочитать отличный учебник Suns по параллелизму, который охватывает все, что вам нужно знать:
http://java.sun.com/docs/books/tutorial/essential/concurrency/
Просто знайте, как это называется, эта «многопоточность» - это достаточно информации для меня, чтобы начать узнавать об этом больше: спасибо! Часто просто незнание слова для обозначения чего-либо становится препятствием между возможностью узнать об этом и не узнать.
Ух ты! Потоки не в моей лиге: я прочитал этот учебник и попытаюсь написать что-то свое с потоками, но я думаю, что пройдет некоторое время, прежде чем я смогу использовать их для ускорения обнаружения столкновений. Спасибо!
Если вы действительно хотите заняться параллельным программированием, вам нужно научиться использовать потоки.
У Sun есть руководство по программированию потоков Java здесь: http://java.sun.com/docs/books/tutorial/essential/concurrency/
То, что вы ищете, - это не способ их одновременной работы (как отмечали люди, это зависит от того, сколько ядер у вас есть, и может предложить только двукратное или, возможно, четырехкратное ускорение), а вместо этого как-то сократить количество столкновений, которые вы должны обнаружить.
Вам следует изучить возможность использования квадродерево. Короче говоря, вы рекурсивно разбиваете свою 2D-область на четыре квадранта (по мере необходимости), а затем вам нужно только обнаруживать столкновения между объектами в соседних компонентах. В хороших случаях это может эффективно сократить время обнаружения столкновений с N ^ 2 до N * log N.
проблема, которая у вас здесь, может быть решена без потоков.
Вам нужна пространственная структура данных. Лучше всего подойдет четырехугольное дерево, или, если поле, в котором движутся сферы, фиксировано (я предполагаю, что это так), вы можете использовать простую сетку. Вот идея.
Разделите область отображения на квадратную сетку, каждая ячейка которой не меньше размера вашего самого большого круга. для каждой ячейки ведите список (лучше всего связанный список) всех кругов, центр которых находится в этой ячейке. Затем на этапе обнаружения столкновений пройдите по каждой ячейке и сравните каждый кружок в этой ячейке со всеми другими кружками в этой ячейке и окружающих ячейках.
технически вам не нужно проверять все ячейки вокруг каждой, так как некоторые из них, возможно, уже были проверены.
вы можете комбинировать эту технику с методами многопоточности, чтобы получить еще лучшую производительность.
Вместо того, чтобы пытаться выполнять параллельную обработку, вы можете поискать оптимизацию обнаружения столкновений. Потому что во многих ситуациях выполнение меньшего количества вычислений в одном потоке лучше, чем распределение вычислений между несколькими потоками, к тому же в этом многопоточном бизнесе легко выстрелить себе в ногу. Попробуйте погуглить "алгоритм обнаружения столкновений" и посмотрите, к чему он вас приведет;)
Хех, определенно. Сначала я заставлял каждый мяч проверять мяч друг друга, а это означало, что некоторые мячи проверяли уже съеденные мячи! Я исправил это, и это очень помогло. Я обязательно погуглию эти "алгоритмы обнаружения столкновений", о которых вы говорите!
Звучит очень похоже на мой эксперимент - зацените ...
Меня также интересуют квадродеревья (поэтому я здесь) ... надеюсь, вы все поняли.
Имейте в виду, что если вы измените программу кругов, чтобы она использовала все ядра вашего процессора, это может начать влиять на Dawn of War. Будь осторожен с желаниями :-)