"Mergowanie" zbioru danych

Witam,

Otóż w mojej tematyce naukowej wystąpiło następujące zagadnienie. Mam dany zbiór trójek liczb całkowitych postaci (h,k,l). Na te trójki nałożone są pewne warunki, np. f(h,k,l)=f(-h,-k,-l) itp. (gdzie f to jakaś funkcja). Zadaniem jest zatem aby z całego tego zbioru usunąć te niepotrzebne trójki i zostawić tylko te unikalne. Wymyśliłem sobie to następująco:

  DO i=1,nreftotA  
    IF(OBSA(i)==1) THEN
      h0=HKLA(i,1); k0=HKLA(i,2); l0=HKLA(i,3)
          DO j=i+1,nreftotA
          h=HKLA(j,1); k=HKLA(j,2); l=HKLA(j,3)
          log1=((h==-h0).AND.(k==-k0).AND.(l==-l0)) ! zmienna logiczna
          pglog=log1 ! zmienna logiczna
          IF(pglog.EQV..TRUE.) THEN
            OBSA(j)=0
          END IF
        END DO
    END IF
  END DO 

To powyżej to kawałek mojego kodu w FORTRANie. nreftotA to liczba trójek w macierzy HKLA (wymiar nreftotA x 3) i wymiar macierzy OBSA. Jak widać algorytm działa dość prosto:

(1) bierze pierwszą i-tą trójkę która "istnieje" (OBSA(i)=1 dla i-tej trójki)
(2) potem patrzy na wszystkie następne trójki (czyli od j=i+1 to końca)
(3) jeśli dla jakiejś j-tej trójki spełniony jest warunek to wtedy uznaje ją za "nieistniejącą" (stawia OBSA(j)=0)

Algorytm działa super, ale nie dla przypadku jak moja macierz HKLA jest bardzo duża (np. 120 tyś. trójek)... Czy da się to zrobić szybciej i efektywniej jakoś w FORTRANie? Zapewne trzeba by wymyślić inny algorytm czy sposób podejścia...

Z góry wielkie dzięki za pomoc.

Pozdrawiam,

Radek

a co ty na to, żeby HKLA nie znajdowały się w tablicy, tylko w drzewie, tak, żebyś nie musiał sprawdzać wszystkich następnych, tylko wyselekcjonowaną grupę podejrzanych?

Brzmi ciekawie i na pewno by dużo przyśpieszyło. Pytanie jak by to można było zaimplementować? Niestety jako dość marny użytkownik FORTRANa nie znam za bardzo takich konstrukcji... Z góry dzięki za pomoc.

ja nie jestem użytkownikiem fortana, więc Ci nie powiem:D

a fortanie można obiekty robić, alb struktury chociaż?

Najpierw pozmieniaj sobie trójki na unikatową formę:
Jeżeli (H<0)lub(H=0)oraz(K<0)lub(H=0)and(K=0)and(L<0) to
H=-H
K=-K
L=-L
Jeżeli potrzebujesz postać oryginalną to zapamiętaj w jakieś tablice że dla tego elementu został zmieniony znak.
Następni posortuj tablicę, radzę zrobić to za pomocą metody kubelkowej (radix).
Wszystkie powtarzające się będą po kolei, więc jednym przeglądem zaznaczysz unikalne.
Po czym ewentualnie dla unikalnych zmieniasz znaki z powrotem na oryginalne.

To w sumie bardzo dobry pomysł. Zastanawiam się obecnie zatem nad następującą rzeczą. Otóż jak mam np. nie taki prosty warunek jak powyżej ale np., że:

f(h,k,l) = f(-h,-k,-l) = f(-h,k,-l) = f(h,-k,l)

Można te "warunki" na trójki (h,k,l) zapisać jako macierze kolejno:

[ 1 0 0] [ -1 0 0] [ -1 0 0] [ 1 0 0]
[ 0 1 0] [ 0 -1 0] [ 0 1 0] [ 0 -1 0]
[ 0 0 1] [ 0 0 -1] [ 0 0 -1] [ 0 0 1]

Jeśli zatem mam np. trójkę (1,2,3) to wygeneruję z niej tymi macierzami oczywiście wszystkie pozostałe czyli (-1,-2,-3), (-1,2,-3) i (1,-2,3). Chciałbym użyć zapisu macierzowego bo jest on bardzo szybki do zrealizowania (przynajmniej w FORTRANie). I pytanie teraz jak (najlepiej w jakiejś ogólnej postaci wykorzystującej tego typu macierze) zapisać te transformacje trójek do unikalnej postaci niezależnie od tego czy natrafi się na (-1,-2,-3) czy (-1,2,-3)?. Myślałem aby kierować się liczbą minusów czy coś w tym stylu, ale nie wydaje się to być najlepsze np. w przypadku gdy warunki wyglądają następująco:

f(h,k,l) = f(-h-k,h,l) = f(k,h,l) = f(-h,-k,-l) = f(h+k,-h,-l) = f(-k,-h,-l)

Z góry dzięki za wszelkie sugestie:)

Radek

Całe wieki nie kodowałem w Fortranie! Moim zdaniem najlepiej by było zastosować funkcję hashującą, wtedy wyszukanie duplikatów będzie miało liniową złożoność obliczeniową.
Mało tego znając z góry jakie mają być warunki stwierdzające równość trójki, można tak dobrać funkcję hashującą, by uwzględniała te warunki.
Za bardzo nie wiem jak by miał wyglądać kod w Fortranie, ale na pewno jest to do zrobienia.

edit: podaj więcej danych: jaki zakres liczb w trójkach? Opisz dokładniej te warunki (jak ogólnie mają wyglądać).

Warunki są takie jak powyżej. Różne możliwe kombinacje lub permutacje. A zakres liczb w 3kach jest np. od -30 do 30 itp. Jeśli by policzyć wszystkie możliwe trójki to np. tak: ntrojek = (230+1)(230+1)(2*30+1) = 226981.

robisz sobie funkcję:
G(H,K,L)=((H+30)*91+K+30)91+L+30;
znajdujesz: P=Min( G(h,k,l), G(-h-k,h,l), G(k,h,l), G(-h,-k,-l), G(h+k,-h,-l), G(-k,-h,-l) )
Zaznaczasz w tablice "Tb" wartości logicznych o rozmiarze 226981: Tb[P]=true; (może być nawet tablica bitów).
Tam gdzie masz true w Tb - kombinacja była w zbiorze.
Z indeksu Tb łatwo wrócić do H,K,L, np Tb[P] jest true więc:
L=(P)mod(91)-30;
K=((P)div(91))mod(91)-30;
H=(P)div(9191)-30;
div - dzielenie na całość (bez reszty).