Оптимальный поиск значений в диапазоне

Driwars · Регистрация: 03.09.2013

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

Имеется 2 коллекции.
Нужно удалить похожие значения.
код

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
double corr =0.05;
            foreach(var i in io)
            {
              foreach( var m in ma)
            {
                if (m < (i + corr) && m > (i - corr)) 
                {
                
                }
            
            
            }
            
            }

сработал бы будь в коллекциях десятки значений, но в первой 10 тысяч во второй 65 тысяч значений. Количество итераций космическое.

Psilon · 20.02.2015, 23:50

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

У меня получился другой результат. Код вернул совпавшие точки.

вернет совпавшие это то же самое, что удалит не совпавшие

Driwars · 20.02.2015, 23:59 **[ТС]**

Psilon, !false

Подскажите ещё как точнее составить условие поиска
На таком

C#
1
if ((Math.Abs(x.Lat - y.Lat) <= _epsilon)  &&(Math.Abs(x.Lng - y.Lng) <= _epsilon))

ловит мало совпадений
Примеры: первый что нашел, второй что осталось. На втором много точек гораздо ближе к линии чем в найденном.

Driwars · 21.02.2015, 00:03 **[ТС]**

вложение

Driwars · 22.02.2015, 17:17 **[ТС]**

Psilon, Проблема оказалась не в условии, а в алгоритме, он находит меньше половины, полным перебором находит все.
Придумал вот такой код на 1 проход, но чего то не хватает.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 PointLatLngComparer pc = new PointLatLngComparer(); \\ сортирует по величине Lat
           io.Sort(pc);
           ma.Sort(pc);
           int count = 0;
           double latcor = 0.0005;
           double lngcor = 0.0012;
            for (int i = 0; i < ma.Count; i++ )
            {
                PointLatLng ro1 = ma[i];
                PointLatLng ro2 = io[count];
                if (Math.Abs(ro1.Lat - ro2.Lat) < latcor) 
                {
                  if (Math.Abs(ro1.Lng - ro2.Lng) < lngcor) 
                    {
                        poi.Add(ma[i]);
                        count++;
                    }
                 }
             }

Добавлено через 17 часов 21 минуту
Я так не играю. 0.3 секунды

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

C#
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
while (i < ma.Count)
            {
                PointLatLng ro1 = ma[i];
                PointLatLng ro2 = io[count];
                if (ro2.Lat < (ro1.Lat - latcor))
                {
                    if (count + 1 < io.Count)
                    {
                        count++;
                        i = c;
                        c = 0;
                    }
                    else
                    {
                        break;
                    }
                }
 
                if (Math.Abs(ro1.Lat - ro2.Lat) < latcor)
                {
                  if (c == 0)
                    {
                        c = i;
                    }
                    if (Math.Abs(ro1.Lng - ro2.Lng) < lngcor)
                    {
                        if (!poi.Contains(ma[i]))
                        {
                            poi.Add(ma[i]);
                        }
                        if (Math.Abs(ma[i + 1].Lat - ro2.Lat) < latcor)
                        {}
                        else
                        {
                            if (count + 1 < io.Count)
                            {
                                count++;
                                i = c;
                                c = 0;
                            }
                            else
                            {
                                break;
                            }
                        }
                     }
                  }
                i++;
            }

@amarf · 22.02.2015, 19:33

Так сделайте проверку перед добавлением точек в первую коллекцию, так что юы туда не могли попасть 2 одинаковых точки. Или в этом есть какой то смысл? (в двух одинаковых точках)

Driwars · 22.02.2015, 19:48 **[ТС]**

amarf, Смысла конечно нет в 2х одинаковых. Игра не стоит свеч, проверка позволит выиграть 0.001с в лучшем случае, а потеряется на пере генерации файла куда больше.

Новые блоги и статьи Все статьи Все блоги /
Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .

Driwars 71 / 62 / 33 Регистрация: 03.09.2013 Сообщений: 306
	21.02.2015, 00:03 [ТС]
	вложение Миниатюры 0

@amarf Жуткая тВарЬ 394 / 329 / 135 Регистрация: 06.02.2015 Сообщений: 962 Записей в блоге: 1
	22.02.2015, 19:33
	Так сделайте проверку перед добавлением точек в первую коллекцию, так что юы туда не могли попасть 2 одинаковых точки. Или в этом есть какой то смысл? (в двух одинаковых точках) 0

Driwars 71 / 62 / 33 Регистрация: 03.09.2013 Сообщений: 306
	22.02.2015, 19:48 [ТС]
	amarf, Смысла конечно нет в 2х одинаковых. Игра не стоит свеч, проверка позволит выиграть 0.001с в лучшем случае, а потеряется на пере генерации файла куда больше. 0