Jak optymalnie obsłużyć wszystkie punkty w układzie współrzędnych?

Cześć!
Ostatnimi czasy szkolę się z programowania w lispie (a konkretniej w jego odmianie AutoCAD), wydaje mi się że już osiągnąłem jakiś w miarę poziom. Pracuje obecnie nad czymś ciekawym (przynajmniej dla mnie :D) tj zaznaczam serię punktów w programie, i on znajduje 2 najbliższe punkty w zbiorze i jeżeli ich odległość nie przekracza podanej wartości dmax to tworzy koło z 3 punktów.
Generalnie kod działa dlatego w dziale nietuzinkowe tematy :D. I tak się zacząłem zastanawiać nad optymalnym podejściem do tego zagadnienia.
Jak widać niżej, obecnie mam podwójnego loopa punkt do punktu, z drobną optymalizacją. Jak punkt znaleziony to usuwa się z inner loopa.

I teraz się zastanawiam czy nie powinienem np podzielić jakoś zbioru punktów (screen niżej) np na połowę żeby nie loopować po wszystkich dla danego punktu. Tylko dzielenie tego na pół to też jakiś loop do wykonania :D
Jako że jestem geodetą to dużo mam takiej pracy na punktach z dużymi zbiorami danych.
Jakieś książki, posty, strony kanały na YT które polecacie do zabrania się za takie problemy?

        (progn
		(setq loopPtLst PtLst)
			(foreach pt0 PtLst
				(if (member pt0 loopPtLst)
				(progn
					(setq sortedDistLst (bc:CalcDist2D loopPtLst pt0 )) ;;subfunc
					(if (and (< (cdr (nth 0 sortedDistLst))  dmax) (< (cdr (nth 1 sortedDistLst)) dmax ))
						(progn
							(setq pt1 (car(nth 0 sortedDistLst)))
							(setq pt2 (car(nth 1 sortedDistLst)))
							(setq loopPtLst (vl-remove pt0 loopPtLst))
							(setq loopPtLst (vl-remove pt1 loopPtLst))
							(setq loopPtLst (vl-remove pt2 loopPtLst))
							
						)
					)
					(setq circPtR (bc:CalcCircle pt0 pt1 pt2))
					(entmake (bc:makeCircle (car circPtR) (cdr circPtR)))
				);progn if
				);if
			);foreach
        );progn

;*******************************************************************************
; FUNCTION: bc:CalcDist2D
; DESCRIPTION: Calculate the 2D distance between selected point and listpoints. If distance is different than 0 point coordinates and distance is added to cons list.
; PARAMETERS: ptLst searchPt
; RETURNS: A list representing points coordinates and distances
;*******************************************************************************
(defun bc:CalcDist2D (ptLst searchPt / distlst distSpPt)
(setq seratchPtXY (list (nth 0 searchPt) (nth 1 searchPT) 0))
(setq distlst nil)
	(foreach PtX ptLst
		(setq PtXY (list (nth 0 PtX) (nth 1 PtX) 0))
		(if (and (/= (setq distSpPt (distance PtXY seratchPtXY))0) (< distSpPt dmax))
		(progn
			(setq distlst (cons (cons PtX distSpPt) distlst))
		)
		)
	)
	(setq distlst (vl-sort distlst (function (lambda (a b) (< (cdr a) (cdr b))))))
	distlst  ; Return the list of distances
)

Dla takiego problemu pewnie nie szukałbym optymalizacji, bo nie jest to potrzebne dla tej skali: jedno obliczenie (a nie np. co klatkę animacji), mała rodzielczość.

Co do problemu: kto wybiera te punkty (ty czy mogą być jakiekolwiek), kto określa zbiór dostępnych punktów?

Sam problem to ogromna dziedzina algorytmiki o której można przeczytać parę książek https://en.wikipedia.org/wiki/Nearest_neighbor_search

slsy napisał(a):

Dla takiego problemu pewnie nie szukałbym optymalizacji, bo nie jest to potrzebne dla tej skali: jedno obliczenie (a nie np. co klatkę animacji), mała rodzielczość.

Co do problemu: kto wybiera te punkty (ty czy mogą być jakiekolwiek), kto określa zbiór dostępnych punktów?

Sam problem to ogromna dziedzina algorytmiki o której można przeczytać parę książek https://en.wikipedia.org/wiki/Nearest_neighbor_search

Jestem geodetą a punkty są to inwentaryzacje pali wbitych w ziemię. Także punkty to jest pomiar pala na 3 punkty w terenie, wrzucony do CADa więc zbiór zaznaczam ja bądź ktoś kto obecnie wykonuje operat z inwentaryzacji. Wątpię żeby było ich więcej niż kilkaset jedocześnie. Testowałem sobie jak to działa i dla +- 6000 działa to płynnie bo policzyło się w kilka sekund.
Tak jak pisałem pytanieraczej teoretyczne, żebym się mógł dokształcić, strasznie się wkręciłem w takie programowanie :D
Dzięki za źródło zapoznam się!

Ebcio napisał(a):

Tak jak pisałem pytanieraczej teoretyczne, żebym się mógł dokształcić, strasznie się wkręciłem w takie programowanie :D

Jak tak to polecam jakiś podstawowy kurs algorytmiki, który da ci podstawy i potrzebną intuicję w rozwiązywaniu podobnych zadań.

A ja jaj czasami wrzucam do nauki lispa (sbcl common lisp ) ale ostatnio hackuję jak głupi w shellu, Moje ukochane C to teraz tak z 20%.

Taki niby własny lisp ma niemal każdy program cadowski, słusznie, ze Kolega się tego uczy.
Osobiście mi się lisp do niczego jeszcze nie przydał. Ale samo programowanie pozwala zaoszczędzić w pracy kupę czasu.

Pozdroooo!!!!

ksh napisał(a):

A ja jaj czasami wrzucam do nauki lispa (sbcl common lisp ) ale ostatnio hackuję jak głupi w shellu, Moje ukochane C to teraz tak z 20%.

Taki niby własny lisp ma niemal każdy program cadowski, słusznie, ze Kolega się tego uczy.
Osobiście mi się lisp do niczego jeszcze nie przydał. Ale samo programowanie pozwala zaoszczędzić w pracy kupę czasu.

Pozdroooo!!!!

Też się ostatnimi czasy wkręcam w cyberbezpieczeństwo :D PS całkiem dobry, polecam szkolenie od Pana Maziarza bardzo dużo praktycznych zastosowań było.
A co do LISPa to myślałem o naucze Clojure'a i przebranżowieniu tylko mało pracy w tym niestety w Polszy :D

Ebcio napisał(a):

I tak się zacząłem zastanawiać nad optymalnym podejściem do tego zagadnienia.

Rzekomo R-tree radzi sobie calkiem niezle. Jak kiedys probowalem uzyc (do nieco innego zagadnienia) to te milisekundy byly dla mnie za wolne wiec zastapilem niedokladna ale duzo szybsza wersja oparta na zwyklych tablicach.

Jako że jestem geodetą to dużo mam takiej pracy na punktach z dużymi zbiorami danych.

No tak, geodeci tam maja. Z dokumentacji najbardziej rozpowszechnionej bazy we wszechswiecie: "R-Trees are most commonly used in geospatial systems ..." (https://www.sqlite.org/rtree.html).

Jako programista, który pracuje przy CAD, który ma nawet dedykowany moduł dla geodetów, dorzuce swoje trzy grosze. Przede wszystkim, używasz złego narzędzia, AutoCAD prawie nigdy nie jest najlepszym wyborem, to po Civil3D (też od autodesku) spodziewałbym narzędzi do tego typu pracy TUTAJ masz nawet jakiś webinar dla geodetów. A teraz już na temat.

Wątpię żeby było ich więcej niż kilkaset jedocześnie. Testowałem sobie jak to działa i dla +- 6000 działa to płynnie bo policzyło się w kilka sekund.

Kilka sekund to baaardzo długo dla kilku tysięcy punktów, ale fakt, rzadko kiedy ktoś ma potrzebę by w jednej chwili pracować z tak dużą pulą. To, że działa wolno to niekoniecznie musi być Twoja wina, nie spodziewałbym się by autocad miał jakiś specjalnie wydajny interpreter. Tym nie mniej jak patrzę na Twój skrypt to złożoność tego jest zdecydowanie za duża jak na zadanie pt. znajdź dwa najbliższe punkty.

(setq loopPtLst PtLst)
			(foreach pt0 PtLst
				(if (member pt0 loopPtLst) ;;
                (progn
					(setq sortedDistLst (bc:CalcDist2D loopPtLst pt0 )) ;;subfunc

W pierwszej iteracji, w najgorszym przypadku, czterokrotnie iterujesz po tej samej liście. Chociaż realistycznie pewnie będą to trzy przejścia bo strzelam, że setq loopPtLst PtLst zrobi jakiś memcpy jeśli dobrze rozumiem, że to instrukcja przypisania. Przede wszystkim, nie robiąc wielkich modyfikacji, (if (member pt0 loopPtLst) ;; wydaje się redudantne. To jest lista z której usuwasz punkty, tak więc CalcDist2D powinien zwrócić Ci pustą listę na której nie wykonasz żadnej operacji. Także powinieneś móc sie obejść bez tego ifa.

Tak więc tutaj muszę się zgodzić z @slsy, problemem nie jest Twoja nie znajomość lispa, ja też go nie znam, a raczej brak ogólnej intuicji programistycznej, którą niestety zdobywa się poprzez naukę, praktykę i eksperymenty. Piszę niestety, bo przez większość czasu, jest to mało seksowny proces.

I jeszcze może offtop.

Taki niby własny lisp ma niemal każdy program cadowski

A wymienisz jakiś jeszcze oprócz tych z serii AutoCAD? Bo żaden inny od autodesku, Civil3D, Maya, 3dsMax, nie używa nic lispopodobnego gdy się ostatnio orientowałem.

Na poczatek dzieki za odpowiedz!
Co do samego civila to wiem że jest o wiele lepszy, niestety moje zarobki nie pozwalają mi placic za licencje 20k rocznie na samym civilu kiedyś pracowaliśmy w firmie w której obecnie pracuje ale z tego samego powodu zrezygnowaliśmy i pracujemy teraz na zmiennikach typu ZWCad czy Brisccad :D

Co do samego kodu:
Tak, zdaje sobie sprawę że nie jest to optymalne podejście, CAD na pewno też dorzucił swoje bo z tego co kojarzę lispy działają tylko na 1 wątku procka.
Dlatego też pytam jakbyście się za to zabrali jako bardziej doświadczone osoby. Odpowirdz z Rtree bardzo ciekawa, algoritmika też się zacząłem interesować.
Zrobiłem to dostępnymi narzędziami które oferuje lisp, dlatego tez nie jest to optymalne, stąd moje pytanie jakby się zabrać za to jakbym jednak myślał o wydajności ,odpowiedzi kolegów wyżej są bardzo pomoce. Jak będę pracował nad kolejnym "projektem" to pomyślę nad stworzeniem sobie funkcji która będzie to robić lepiej :D

Co do samego ifa to wydaje mi się że jest on właśnie jedyna opcja "optymalizacji", jak widzisz w liście niżej punkty które zostały znalezione i uzyte do okręgów, są usuwane z listy wewnętrznej "loopPtLst". A zewnętrzny lisp loopuje po wszystkich. Jeżeli punkt z listy zewnetrznej nie jest na lisącie wewnętrznej to jest pomijany, czyli na każdy usuniety punkt jedna iteracja jest odejmowana.

Co do pytania z offtopa to wydaje mi się że ksh odnosił się nie do samych tworów Autodeska, a jego zamienników właśnie tak jak pisałem niżej Brisccad, ZwCAD, GstarCAD, AcadGeo.

Co do samego ifa to wydaje mi się że jest on właśnie jedyna opcja "optymalizacji", jak widzisz w liście niżej punkty które zostały znalezione i uzyte do okręgów, są usuwane z listy wewnętrznej "loopPtLst". A zewnętrzny lisp loopuje po wszystkich. Jeżeli punkt z listy zewnetrznej nie jest na lisącie wewnętrznej to jest pomijany, czyli na każdy usuniety punkt jedna iteracja jest odejmowana.

Ale potem "loopujesz" jeszcze raz do tego samego miejsca w tej samej liście w bc:CalcDist2D loopPtLst pt0. Czyli robisz dwa razy to samo. Albo w tym ifie zwrócisz jakiś index od którego zaczniesz przeszukiwanie w bc:CalcDist2D albo usuń tego ifa i z tejże funkcji zwróć pustą listę rezultatów jeśli nic nie znalazłeś.

Aaaah, dopiero zakumalem dzieki trzeba było z pracy wyjść żeby mozg zaczal pracować.

Pytania z serii jak zoptymalizować "na poważnie" stukturę danych i algorytm w języku X to często pytania na które odpowiedź brzmi - to zależy na jakich implementacjach tych struktur pracuje dany język i na jakim CPU jest uruchomiony interpreter czy maszyna wirtualna ub sam program jeśli mowa o kompilowanych i o jakich danych mowa (ilość danych, charakterystyka danych - ich zares, kompresowalność, entropia itd).

W dobie ostro wielomegabajtowych cache i wielokanałowych pamięci zwłaszcza na stacjach roboczych pułap wielkośi danych przy których zaczyna mieć praktyczny sens przejmowanie się używaniem czegoś bardziej skomplikowanego niż zwykłych tablic czyli sąsiadujących ze sobą pól pamięci z jednoznacznie indeksowanymi pozycjami. Taka forma najczęściej jest miła obecnym mechanizmom cache procesora i umożliwia bardzo szybkie dostępy do danych na jakich operujesz. Próby używania czegoś innego mogą wręcz spowalniać operacje.

Myślo sprawie jak o cache będącym blatem stołu wypełnionym najczęściej prównywanymi danymi o skończonej ilości elementów, RAM jako szufladzie w niedalekiej komodzie do której musisz podejś gdzie każda szuflada to odrębna kość RAM a o dysku jako obszernej piwnicy do której musisz zejść i w której trzymasz różne zestawy danych z różnych projektów.

To w jaki sposób i w jakiej ilości przenosi się między tymi trzema "strefami" elementy i w którą stronę to już zależy odróżnych architektur,ale daje w ogólnej postaci jakieś wyobrażenie z czym mamy do czynienia. BTW tak, tojak sobie zorganizujesz w piwnicy te różne zestawy danych to jakiś tam analog systemu plików i drzewa katalogów w pewnych stopniach.

Ilość różnych detali na tych poziomach potrai być znaczna a mnogość rozwiązań komunikacji między różnymi poziomami pamięc między różnymi modelami czy generacjami procesorów nawet od jednego producentai sprawia, że raczej się celuje w "ogólnie w miarę szybkie" rozwiązania. Co jest "w miarę szybkie" często lepiej ci uzmysłowi wykonanie benchmarku zwłaszcza na reprezentatywnych danych niż próba zakładania czegokolwiek o szybkości jakiegoś rozwiązania z góry. Tutaj nawet doświadczeni brodaci guru klepiący od niemowlęctwa systemy operacyjne w języku maszynowym mogą polec jeśli nie wykonają testów kilku wariantów na kilku maszynach. Tak, wiem, szokujące.

Nie byłoby lepiej obliczenia przeprowadzić np w Pythonie? Skoro interpreter w AutoCAD jest wolny. Chyba że jest jakiś duży problem z wczytaniem wyników działania zewnętrznego skryptu.

Możesz podzielić powszechnie siatkę na kwadratów, zrobisz to w czasie O(n) - czytaj czas rośnie liniowo do liczby punktów, czyli dla 1000 punktów robisz 1000 operacji, uczciwie i szybkie. Petla w petli to O(n^2) czyli czas rośnie z kwadratem liczby punków. Czyli czas pętli w petli dla 1000 punktów, to 1000^2 czyli milion-operacji, Jak masz 4 petle w sobie, czyli O(n^4) to milion milionów operacji :)

Dzielisz powiechnie na równe kwadraty o rozmiarze maksymalnego dystansu każdy. Iterujesz po liście punków, jeśli punkt znajduje się w kwadracie zapisujesz go do listy punktów w kwadracie.
Gdy już uzyskasz taka strukturę danych. Znalezienie najblizszych punktów sprowadza sie do przeszukania klastra xy i +/- 1 na koło. Nie da sie zrobic wyszukiwania minalnej wartośći szybciej niz liniowo. Dalej będzie pętla w pętli, czyli O(n^2) ale zamiast dla wszystkich punktów tylko dla tych faktycznie najbliższych. wiec zamiast 1000 * 1000 bedzie 1000*50.

Jest jeszcze takie coś jak złożoność pesymistyczna, jeśli wszystkie punkty będą w jednym kwadracie, to dalej miał 1000*1000 + 1000(na startowe grupowanie), ale to przykład nie praktyczny dla geodety.

Dodatkową mikro optymalizacją moze być pociecie powszchni na mniejsze kwadraty, czy sprawdzanie klastów od najbliższych. To są heurystyki czyli założenia z czapki mogące działać dla okreslnych danych, a dla innych nie. Np. Jak potniesz na za dużo zamałych cześci, bedziesz poświecał czas na sprawdzanie pustych kwadratów.

Można też spróbować zapisywać sprawdzone pary w jakieś hash-mapie. Optymistycznie może to zbić ilośc operacji o połowe. Praktycznie, to moze się opłacać lub nie opłacać lub wychodzić na zero, bo sprawdzenia i dodawanie do mapy kosztuje.

1. OP nie podał ile punktów to "duży zbiór". 1000 punktów to pikuś. Czy milion punktów to pikuś to już zależy od procesora i wydajności implementacji interpretera. W C na starym Xeonie o niepowalającym taktowaniu porównanie "na brute force" 2 punktów każdy z każdym bez powtórzeń spośród miliona zgrupowanego w tablicy to kwestia około kilku minut jeśli robi się to w C i powłącza optymalizacje -03.
2. Dzielenie na siatkę może się nie opłacać jeśli to operacja jednorazowa lub dane nigdy nie będą zmieniane. Wtedy wystarczy stworzyć listy sąsiadów o interesyjących cechach. Samo dzielenie na siatkę jest formą znajdywania sąsiadów w obrebie kwadratu siatki.
3. Dzielenie na siatkę jak już wykonywać to najlepiej zapisać jakoś by wykorzystywać przy wstawianiu/usuwaniu punktów w przyszłości, zwłaszcza jeśli będzie to znacząca ilość danych.
4. Pocięcia na "za dużo części" nie musi oznaczać potrzeby sprawdzania tych pustych. Je można pomijać jeśli stworzysz jakąś formę listy pól w których znajduje się minimum jeden element. Przy wstawianiu też nie trzeba się pustymi przejmować.
5. te kwadraty z elementami można ponownie potraktować jako elementy jakiejś siatki tworzymy wtedy wyższą hierarchię której cechy można zapisać i wykorzystywać przy przeszukaniach i potem zrobić tak jeszcze kilka warstw ale na współczesnych CPU to już zaczyna być opłacalne dopiero przy dość astronomicznych ilościach punktów.

1. Złożoność podałem w notacji duzego O, która jest nie zależna od ilości punktów. Przykład z 1000 wynikał z tego że OP uczy się programować i może nie wiedzieć co to O(n^2).

Wtedy wystarczy stworzyć listy sąsiadów o interesyjących cechach.

2. Sortowanie kubełkowe i przeszukiwanie kubełków(czyli de-facto ta siatka) jest algorytmem , który można za implementować. I rozwiazać problem zbijajać złożoność n^2 do n. Lista o jakiś tam cechach, to masło maślane, bzdura. Nie do zaimplementowania. Sorka ze tak nie miło, ale sam widzisz.

Dzielenie na siatkę jak już wykonywać to najlepiej zapisać jakoś by wykorzystywać przy wstawianiu/usuwaniu punktów w przyszłości,

3. Znowu coś tam , jakoś, w przyszłości. Konkrety!

4. kolejne coś tam jakoś, i nie wypowiedziana sugestia korzystania z innej struktury danych.
   Jak to ma się do tego że sturktura danych o której pisałem, ma wade o której pisałem. Nie wiem.

5. ja to wiem, ty to wiesz, op tego nie wiem. Tak i tak, napisałem ze to może być cos co ma sens lub go nie ma, niemo mając w głowie wymieniane przez Ciebie powody.

@_flamingAccount

Możesz podzielić powszechnie siatkę na kwadratów....

Tak jak to napisałeś to zdałem sobie sprawę, że robiłem coś podobnego jakiś czas temu. Nie skojarzyłem od razu bo to była chmura punktów ilustrująca ukształtowanie terenu a nie punkty geodezyjne. Inicjalny rozmiar "kratki" oszacowywałem poprzez wzór

min(extent.Xmax - extent.Xmin, extent.Ymax - extent.Ymin ) / sqrt(pointCount)

gdzie extent to cały "kwadrat" w której znajdują się wszystkie punkty.