Реализация алгоритма поиска ближайших точек

@Ponimau · Регистрация: 03.10.2019

Студворк — интернет-сервис помощи студентам

Здравствуйте, возникла проблема с измерением времени работы алгоритмов. Написал программу, которая ищет ближайшие точки методом грубой силы и методом декомпозиции. Все работает, воде бы, неплохо, но сравнивая время работы алгоритмов, заметил, что на 10, 20, 50, 100 точках время работы всегда отличается +- в 5 раз. Хотя, в теории время работы алгоритма полного перебора n^2, а метода декомпозиции nlogn. Можете подсказать, в чем моя проблема?

Реализация метода грубой силы:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import static java.lang.Math.sqrt;
 
import java.util.ArrayList;
 
public class BruteFindClosestPoints {
 
    int index1 = -1;
    int index2 = -1;
    double min;
 
    double BruteFindClosestPoints(ArrayList<Point> arrayPoint) {
        min = Integer.MAX_VALUE;
        double d;
        for (int i = 0; i < arrayPoint.size() - 1; i++) {
            for (int j = i + 1; j < arrayPoint.size()&&j!=i; j++) {
 
                d = Math.pow((arrayPoint.get(j).X - arrayPoint.get(i).X), 2)
                        + (Math.pow((arrayPoint.get(j).Y - arrayPoint.get(i).Y), 2));
                if (d < min) {
                    min = d;
                    index1 = arrayPoint.get(i).getID();
                    index2 = arrayPoint.get(j).getID();
                }
            }
        }
        min = sqrt(min);
        return min;
    }
 
    public int getIndex1() {
        return index1;
    }
 
    public int getIndex2() {
        return index2;
    }
 
    void show() {
        System.out.println("Ближайшие точки (BruteForce): " + (index1) + " и " + (index2) + " с расстоянием: " + min);
    }
}

Метод декомпозиции:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import static java.lang.Math.abs;
import static java.lang.Math.sqrt;
 
import java.util.ArrayList;
 
public class DecompositionFindClosestPoints {
 
    int index1 = -1, index2 = -1;
    int index3 = -1, index4 = -1;
    double m = Integer.MAX_VALUE;
 
    double DecompositionFindClosestPoints(ArrayList<Point> pointSortedX, ArrayList<Point> pointSortedY) {
 
        int lgth = pointSortedX.size();
        if (lgth <= 3) {
            BruteFindClosestPoints a = new BruteFindClosestPoints();
            double dist = a.BruteFindClosestPoints(pointSortedX);
            index1 = a.getIndex1();
            index2 = a.getIndex2();
            return dist;
        }
 
        int mid = lgth / 2;
 
        Point midPoint = new Point(pointSortedX.get(mid));
 
        ArrayList<Point> Pxl = new ArrayList<>(pointSortedX.subList(0, mid + 1));
        ArrayList<Point> Pxr = new ArrayList<>(pointSortedX.subList(mid + 1, lgth));
 
        ArrayList<Point> Pyl = new ArrayList<>();
        ArrayList<Point> Pyr = new ArrayList<>();
 
        for (int i = 0; i < lgth; i++) {
            if (pointSortedY.get(i).getX() <= midPoint.getX()) {
                Pyl.add(pointSortedY.get(i));
            } else {
                Pyr.add(pointSortedY.get(i));
            }
        }
 
        DecompositionFindClosestPoints dl_ = new DecompositionFindClosestPoints();
        DecompositionFindClosestPoints dr_ = new DecompositionFindClosestPoints();
 
        double dl = dl_.DecompositionFindClosestPoints(Pxl, Pyl);
        double dr = dr_.DecompositionFindClosestPoints(Pxr, Pyr);
 
        double d;
 
        if (dl < dr) {
            index1 = dl_.getIndex1();
            index2 = dl_.getIndex2();
            d = dl;
        } else {
            index1 = dr_.getIndex1();
            index2 = dr_.getIndex2();
            d = dr;
        }
 
        ArrayList<Point> strip = new ArrayList<>();
        for (int i = 0; i < pointSortedY.size(); i++) {
            if (abs(pointSortedY.get(i).getX() - midPoint.getX()) < min(d, m)) {
                strip.add(pointSortedY.get(i));
            }
        }
 
        double dist = stripClosest(strip, d, Pxl, Pxr);
 
        if (dist < d) {
            index1 = index3;
            index2 = index4;
            m = dist;
        } else {
            m = d;
        }
 
        return m;
    }
 
    double stripClosest(ArrayList<Point> a, double d, ArrayList<Point> Pxl, ArrayList<Point> Pxr) {
        double min = d;
        double dist;
        for (int i = 0; i < a.size() - 1; i++) {
            for (int j = i + 1; j < a.size(); j++) {
 
                if (a.get(j).getY() - a.get(i).getY() < min) {
 
                    if (!(Pxl.contains(a.get(j)) && Pxl.contains(a.get(i)))
                            || !(Pxr.contains(a.get(i)) && Pxr.contains(a.get(j)))) {
 
                        dist = sqrt(Math.pow((a.get(j).X - a.get(i).X), 2)
                                + (Math.pow((a.get(j).Y - a.get(i).Y), 2)));
 
                        if (dist < min) {
                            min = dist;
                            index3 = a.get(i).getID();
                            index4 = a.get(j).getID();
                        }
                    } else {
 
                    }
                } else {
 
                    j = a.size();
 
                }
            }
        }
        return min;
    }
 
    public int getIndex1() {
        return index1;
    }
 
    public int getIndex2() {
        return index2;
    }
 
    void show() {
        System.out.println("Ближайшие точки (Decomposition): " + (index1) + " и " + (index2) + " с расстоянием: " + m);
    }
 
    double min(double x, double y) {
        return (x < y) ? x : y;
    }
}

Главный класс:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.awt.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Random;
 
 
public class FindPoint {
 
    public static void main(String[] args) {
        long averageTimeDecomposition = 0;
        long averageTimeBrute = 0;
        for (int j = 0; j < 1; j++) {
            ArrayList<Point> point = new ArrayList<>();
            int min = 0;
            int max = 100;
            HashSet<Integer> ptX = new HashSet<>();
            for (int i = 0; i < 10; i++) {
                Random rnd = new Random();
                int rndX = min + rnd.nextInt(max - min + 1);
                int rndY = min + rnd.nextInt(max - min + 1);
                if (!ptX.contains(rndX)) {
                    ptX.add(rndX);
                    point.add(new Point(rndX, rndY, point.size()));
                    System.out.println(point.size() + ": " + " X: " + rndX + " Y: " + rndY);
                } else {
                    i--;
 
                }
 
            }
 
            long startTime = System.nanoTime();
            BruteFindClosestPoints a = new BruteFindClosestPoints();
            a.BruteFindClosestPoints(point);
            a.show();
            averageTimeBrute += System.nanoTime() - startTime;
 
 
            Collections.sort(point, Point.COMPARE_BY_X);
            ArrayList pointX = new ArrayList<>(point);
            Collections.sort(point, Point.COMPARE_BY_Y);
            ArrayList pointY = new ArrayList<>(point);
 
            startTime = System.nanoTime();
            DecompositionFindClosestPoints b = new DecompositionFindClosestPoints();
            b.DecompositionFindClosestPoints(pointX, pointY);
            averageTimeDecomposition += System.nanoTime() - startTime;
            b.show();
 
            System.out.println("---------------------------------------");
        }
        System.out.println("Среднее время грубый: " + (averageTimeBrute / 1000));
        System.out.println("Среднее время декомпозиции: " + (averageTimeDecomposition / 1000));
 
    }
}

Класс с точками:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.Comparator;
import java.util.Random;
 
public class Point {
 
    int X;
    int Y;
    int id;
 
    public Point(int X, int Y, int id) {
        this.X = X;
        this.Y = Y;
        this.id = id;
    }
 
    public Point(Point a) {
        this.X = a.getX();
        this.Y = a.getY();
        this.id = a.getID();
    }
 
    public Point(int id) {
        Random random = new Random();
        this.X = random.nextInt();
        this.Y = random.nextInt();
        this.id = id;
    }
 
    public int getX() {
        return X;
    }
 
    public void setX(int X) {
        this.X = X;
    }
 
    public int getY() {
        return Y;
    }
 
    public void setY(int Y) {
        this.Y = Y;
    }
 
    public int getID() {
        return id;
    }
 
    public void setID(int id) {
        this.id = id;
    }
 
    public static final Comparator<Point> COMPARE_BY_X = new Comparator<Point>() {
        @Override
        public int compare(Point a, Point b) {
            return a.getX() - b.getX();
        }
    };
 
    public static final Comparator<Point> COMPARE_BY_Y = new Comparator<Point>() {
        @Override
        public int compare(Point a, Point b) {
            return a.getY() - b.getY();
        }
    };
 
    @Override
    public String toString() {
        return "Point{" + "X=" + X + ", Y=" + Y + ", id=" + id + '}';
    }
 
 
}

Буду признателен за любую помощь, спасибо.

@xoraxax · 26.11.2019, 14:11

гугли что такое jmh и почему его используют

@Aviz__ · 27.11.2019, 12:29

Сообщение от Ponimau

полного перебора n^2

все совпадает, глянь

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package helper;
 
import java.awt.Point;
import java.util.*;
 
public class Helper {
 
    public static void main(String[] args) {
        List<Point> pointList = getListPointsInSquareArea(new Point(10,50), new Point(50, 10), 10);
        long begin = System.nanoTime();
        //System.out.println(getMinDist(pointList));
        getMinDist(pointList);
        long end = System.nanoTime();
        long time10 = end - begin;
        //System.out.println(time10);
        pointList = getListPointsInSquareArea(new Point(10,50), new Point(50, 10), 100);
        begin = System.nanoTime();
        getMinDist(pointList);
        end = System.nanoTime();
        System.out.println((end - begin)/time10);
    }
 
    // генрит дист точек со случайными координатами, в квадратной области плоскости
    private static List<Point> getListPointsInSquareArea(Point leftUp, Point rightDown, int count) {
        List<Point> pointListRet = new LinkedList<>();
        Random rnd = new Random(System.currentTimeMillis());
        for (int i = 0; i < count; i++) {
            pointListRet.add(new Point(leftUp.x + rnd.nextInt(rightDown.x + 1),
                    leftUp.y + rnd.nextInt(rightDown.y + 1)));
        }
        return pointListRet;
    }
 
    private static DistanceBetweenTwoPoints getMinDist(List<Point> pointList) {
        List<DistanceBetweenTwoPoints> twoPointsListDist = new LinkedList<>();
        for (int i = 0; i < pointList.size(); i++) {
            for (int j = i + 1; j < pointList.size() - 1; j++) {
                twoPointsListDist.add(new DistanceBetweenTwoPoints(pointList.get(i), pointList.get(j)));
            }
        }
        Collections.sort(twoPointsListDist);
        return twoPointsListDist.get(0);
    }
}
 
class DistanceBetweenTwoPoints implements Comparable<DistanceBetweenTwoPoints> {
    private Point first;
    private Point second;
    private double dist;
 
    DistanceBetweenTwoPoints(Point first, Point second) {
        this.first = first;
        this.second = second;
        this.dist = calcDist();
    }
 
    private double calcDist() {
        double dX = second.x - first.x;
        double dY = second.y - first.y;
        return Math.sqrt(dX * dX + dY * dY);
    }
 
 
    @Override
    public int compareTo(DistanceBetweenTwoPoints o) {
        return Double.compare(this.dist, o.dist);
    }
 
    @Override
    public String toString() {
        return "DistanceBetweenTwoPoints{" +
                "\nfirst=" + first +
                ", \nsecond=" + second +
                ", \ndist=" + dist +
                '}';
    }
}

@Ponimau · 27.11.2019, 12:42 **[ТС]**

Да, спасибо, но мой вопрос заключается именно в том, почему в моей программе разница между временем работы алгоритма такое. То есть, от 10 до 100 точек разница всегда +- 5 раз. В коде ли моя ошибка, или же это от того, что в java есть разогревочные процессы, операционка с другими процессами, Garbage Collector?

@Aviz__ · 27.11.2019, 12:47

Сообщение от Ponimau

разница всегда

не всегда)) а в среднем, как раз и будет, теория. ну и мой код более понятен, как минимум...

@xoraxax · 27.11.2019, 12:56

Сообщение от Ponimau

В коде ли моя ошибка, или же это от того, что в java есть разогревочные процессы, операционка с другими процессами, Garbage Collector?

одно другому не мешает же

@Татьяна_Ерм · 11.03.2020, 06:56

Пожалуйста! Добавьте комментарии в свою программу, очень хочу понять принцип что делается! Либо просто хотя бы опишите что к чему

@Aviz__ · 11.03.2020, 08:11

Татьяна_Ерм, спрашивай по коду)) если ничего не понятно, то увы, никто тебе помочь не в силах...

@Татьяна_Ерм · 11.03.2020, 16:50

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

)))

@Aviz__ · 11.03.2020, 18:34

Сообщение от Татьяна_Ерм

а жаль

ога, учитывая, что понять, из названий getListPointsInSquareArea и DistanceBetweenTwoPoints их функционал, просто!

@Татьяна_Ерм · 15.03.2020, 07:22

Вопросы:
1) В методе грубой силы почему цикл именно такой?
for (int i = 0; i < arrayPoint.size() - 1; i++) {
for (int j = i + 1; j < arrayPoint.size()&&j!=i; j++)
2) Начальные заданные индексы что собой представляют?
int index1 = -1;
int index2 = -1;
3) Какой алгоритм сортировки точек используется?
4) Какова сложность у этих двух методов?
5) В методе декомпозиции что означают строки:
ArrayList<Point> Pxl = new ArrayList<>(pointSortedX.subList(0, mid + 1));
ArrayList<Point> Pxr = new ArrayList<>(pointSortedX.subList(mid + 1, lgth));
ArrayList<Point> Pyl = new ArrayList<>();
ArrayList<Point> Pyr = new ArrayList<>();

а также:
double min(double x, double y) {
return (x < y) ? x : y;
}

@Aviz__ · 15.03.2020, 07:35

Сообщение от Татьяна_Ерм

for (int i = 0; i < arrayPoint.size() - 1; i++) {
for (int j = i + 1; j < arrayPoint.size()&&j!=i; j++)

вопрос не понятен! грубая сила подразумевает перебор сравнений каждого элемента со всеми.

Сообщение от Татьяна_Ерм

int index1 = -1;

в моем коде нет

Сообщение от Татьяна_Ерм

Какой алгоритм сортировки точек используется?

никакой, тогда смысл расстановки теряется!

Сообщение от Татьяна_Ерм

Какова сложность у этих двух методов?

двух? из первого вопроса, должно быть понятно, что квадратичная!

@Татьяна_Ерм · 15.03.2020, 17:58

Мои вопросы составлены по исходному коду автора этой темы. Ни на один вы нормально не ответили, уж извините за честность

@Aviz__ · 15.03.2020, 18:32

Не по теме:

Сообщение от Татьяна_Ерм

уж извините за честность

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	26.11.2019, 14:11
	гугли что такое jmh и почему его используют 0

@Ponimau 0 / 0 / 0 Регистрация: 03.10.2019 Сообщений: 9
	27.11.2019, 12:42 [ТС]
	Да, спасибо, но мой вопрос заключается именно в том, почему в моей программе разница между временем работы алгоритма такое. То есть, от 10 до 100 точек разница всегда +- 5 раз. В коде ли моя ошибка, или же это от того, что в java есть разогревочные процессы, операционка с другими процессами, Garbage Collector? 0

@Татьяна_Ерм 0 / 0 / 0 Регистрация: 26.10.2019 Сообщений: 9
	11.03.2020, 06:56
	Пожалуйста! Добавьте комментарии в свою программу, очень хочу понять принцип что делается! Либо просто хотя бы опишите что к чему 0

@Aviz__ 2744 / 2053 / 507 Регистрация: 17.02.2014 Сообщений: 9,472
	11.03.2020, 08:11
	Татьяна_Ерм, спрашивай по коду)) если ничего не понятно, то увы, никто тебе помочь не в силах... 0

@Татьяна_Ерм 0 / 0 / 0 Регистрация: 26.10.2019 Сообщений: 9
	11.03.2020, 16:50
	В чужом коде долго и сложно разбираться, хотела бы по блокам из нескольких строк хотя бы понимать что делается, каждую строчку расписывать конечно не прошу) (а жаль))) 0

@Татьяна_Ерм 0 / 0 / 0 Регистрация: 26.10.2019 Сообщений: 9
	15.03.2020, 07:22
	Вопросы: 1) В методе грубой силы почему цикл именно такой? for (int i = 0; i < arrayPoint.size() - 1; i++) { for (int j = i + 1; j < arrayPoint.size()&&j!=i; j++) 2) Начальные заданные индексы что собой представляют? int index1 = -1; int index2 = -1; 3) Какой алгоритм сортировки точек используется? 4) Какова сложность у этих двух методов? 5) В методе декомпозиции что означают строки: ArrayList<Point> Pxl = new ArrayList<>(pointSortedX.subList(0, mid + 1)); ArrayList<Point> Pxr = new ArrayList<>(pointSortedX.subList(mid + 1, lgth)); ArrayList<Point> Pyl = new ArrayList<>(); ArrayList<Point> Pyr = new ArrayList<>(); а также: double min(double x, double y) { return (x < y) ? x : y; } 0

@Татьяна_Ерм 0 / 0 / 0 Регистрация: 26.10.2019 Сообщений: 9
	15.03.2020, 17:58
	Мои вопросы составлены по исходному коду автора этой темы. Ни на один вы нормально не ответили, уж извините за честность 0