Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #32730 > unrolled thread

k-d tree - jak zapisać na dysku

Back to article view | Back to pl.comp.programming

Contents

  k-d tree - jak zapisać na dysku DMR <mezzogm@gmail.com> - 2019-07-24 10:25 -0700
    Re: k-d tree - jak zapisać na dysku heby <heby@poczta.onet.pl> - 2019-07-24 20:23 +0200
      Re: k-d tree - jak zapisać na dysku godek.maciek@gmail.com - 2019-07-28 23:55 -0700
        Re: k-d tree - jak zapisać na dysku heby <heby@poczta.onet.pl> - 2019-07-29 09:26 +0200
        Re: k-d tree - jak zapisać na dysku DMR <mezzogm@gmail.com> - 2019-07-29 07:11 -0700
    Re: k-d tree - jak zapisać na dysku AK <nobody@nowhere.net> - 2019-07-24 21:15 +0200
      Re: k-d tree - jak zapisać na dysku DMR <mezzogm@gmail.com> - 2019-07-24 12:58 -0700
        Re: k-d tree - jak zapisać na dysku heby <heby@poczta.onet.pl> - 2019-07-24 22:42 +0200
        Re: k-d tree - jak zapisać na dysku AK <nobody@nowhere.net> - 2019-07-26 20:42 +0200
          Re: k-d tree - jak zapisać na dysku DMR <mezzogm@gmail.com> - 2019-07-26 13:09 -0700
            Re: k-d tree - jak zapisać na dysku heby <heby@poczta.onet.pl> - 2019-07-26 22:33 +0200
              Re: k-d tree - jak zapisać na dysku AK <nobody@nowhere.net> - 2019-07-26 22:58 +0200
            Re: k-d tree - jak zapisać na dysku AK <nobody@nowhere.net> - 2019-07-26 22:52 +0200
    Re: k-d tree - jak zapisać na dysku fir <profesor.fir@gmail.com> - 2019-07-29 02:36 -0700
      Re: k-d tree - jak zapisać na dysku fir <profesor.fir@gmail.com> - 2019-07-29 07:04 -0700
      Re: k-d tree - jak zapisać na dysku DMR <mezzogm@gmail.com> - 2019-07-29 07:15 -0700

#32730 — k-d tree - jak zapisać na dysku

Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
Jakieś równie wyrafinowane pomysły? :-)

[toc] | [next] | [standalone]

#32731

On 24/07/2019 19:25, DMR wrote:
> Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
> Jakieś równie wyrafinowane pomysły? :-)

Może taki: wybierz sobie jakiś adres z przepastnej przestrzeni 64bit i 
zarezerwuj go systemowo. Potem zrób allokator przydzielający obiekty 
tylko w tym rejonie.

Zapis i odczyt staje się wtedy trywialny.

Bardziej wyrafinowany: napisz własny offset_ptr<> który zamiast 
wskaźnika w środku trzyma offset od jakiejś statycznej zmiennej bazowej 
i przelicza je w czasie rzeczywistym na wskaźniki podczas wołania.

[toc] | [prev] | [next] | [standalone]

#32749

W dniu środa, 24 lipca 2019 20:23:09 UTC+2 użytkownik heby napisał:
> On 24/07/2019 19:25, DMR wrote:
> > Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
> > Jakieś równie wyrafinowane pomysły? :-)
> 
> Może taki: wybierz sobie jakiś adres z przepastnej przestrzeni 64bit i 
> zarezerwuj go systemowo. Potem zrób allokator przydzielający obiekty 
> tylko w tym rejonie.
> 
> Zapis i odczyt staje się wtedy trywialny.

Pomysł w istocie zajebisty.
A teraz zagadka: co się stanie,
gdy dwóch użytkowników zechce
w tym samym czasie skorzystać
z tego programu?

Pomysł z własnym alokatorem
jest ok: niech Twoja aplikacja
alokuje sobie tylko jeden blok
pamięci przy pomocy malloc
(nazwijmy go base), a Twój alokator
będzie przydzielał adresy jako
ofsety względem base, tak że efektywny
adres to będzie base+offset.

Po stronie asemblera takie rozwiązanie
nie wydłuży czasu dostępu do pamięci,
bo przynajmniej intel koduje dodawanie
bazy i offsetu w jednej instrukcji
adresowania pośredniego.

Później tylko zrzucasz zaalokowany kawałek
pamięci do pliku binarnego.

Przy ładowaniu podobnie - alokujesz sobie
tyle pamięci, ile zajmuje plik binarny
(otrzymany adres to Twój nowy base)
i ładujesz zawartość pliku pod ten adres.

Ponieważ ta technika nie ma większego
związku z drzewami k-wymiarowymi, jako
bonus do odpowiedzi załączam link do
implementacji kd-tree, którą kiedyś
robiłem na studia. Jest oczywiście
w Lispie (no a w czym), ale nie zajmowałem
się tam zagadnieniem serializacji:
https://bitbucket.org/panicz/studies/src/default/geometria-grafy-algorytmy/lab3/kd.scm

[toc] | [prev] | [next] | [standalone]

#32751

On 29/07/2019 08:55, godek.maciek@gmail.com wrote:
> Pomysł w istocie zajebisty.
> A teraz zagadka: co się stanie,
> gdy dwóch użytkowników zechce
> w tym samym czasie skorzystać
> z tego programu?

Myślę że rozwiązaliśmy to w latach 60tych pamięcią wirtualną procesów.

Jesli zasz zastanawia Cie co jeśli to oprogramowanie serwerowe z 
wielodostepem to autor pytania nic nie napisał więc może to być nie 
tylko pytanie o serwer ale o np. serwer na 6502. I wtedy cokolwiek nie 
wymyślisz to dupa. Założenie więc jakieś minimalne musiało zostać 
wyssane z palca, że system jest z pamięcią wirtualną i że takie drzewo 
jest jedno. Ponadto tworzenie osobnych procesów nie jest reglamentowane 
obecnie w żaden sposób poza RAMem i może resourcami, ale to windows.

Jeśli zaś naprawdę chcesz wnikać bardzo głęboko do dalej jest możliwy 
wielodostęp z zafixowanym adresem pamięci. To tylko kwestia dodania 
numeru allokatora do zrzucanego pliku. Masz troche exbibajtów do 
wykorzystania, dasz sobie radę z pomieszczeniem się N razy a pamięci. 
Myślę że możesz zacząć się martwić przy miliardzie userów na raz.

[toc] | [prev] | [next] | [standalone]

#32754

Choć jestem jeno pyłem i prochem marnym, to mnie się cały czas zdaje, że piszemy tu o tym samym... :-)

[toc] | [prev] | [next] | [standalone]

#32733

On 2019-07-24 19:25, DMR wrote:
> Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
> Jakieś równie wyrafinowane pomysły? :-)

Jaki język prog.?

AK

[toc] | [prev] | [next] | [standalone]

#32734

> Jaki język prog.?

"struktura poszyta wskaźnikami" :-)

C/C++, ale nie o lingwistykę tu biega, tylko raczej o ogólną rozkminę tematu.
Kolega wyżej zasugerował coś w ten deseń - można podziałać w apriorycznie zaalokowanym bloku pamięci, a potem przeliczyć offsety wskaźników względem punktu wejścia.
Ma to sens?
Czy wypocina straszna?

[toc] | [prev] | [next] | [standalone]

#32736

On 24/07/2019 21:58, DMR wrote:
> Kolega wyżej zasugerował coś w ten deseń - można podziałać w apriorycznie zaalokowanym bloku pamięci, a potem przeliczyć offsety wskaźników względem punktu wejścia.

Nie, żadnego liczenia offsetów. offset_ptr<> zawiera już poprawny 
offset, bez względu na to gdzie zostanie całośc załadowana. Taka 
struktura wymaga tylko załadowania pooola pamięci z dysku i odtworzenia 
*jednej* zmiennej globalnej która jest jedyną zmieniającą się wartością 
wskazującą na bufor allokatora, poola czy czegoś innego do zarządzania 
pamięcią.

Można to rozwijać dalej, np. offsety są zależne od typu i każdy typ ma 
własny allokator ładowany w dowolne miejsce pamięci aby oszczędzić 
fragmentację.

Jednak czasy 32 bitów pamięci wirtualnej słusznie mineły.

> Ma to sens?
> Czy wypocina straszna?

Takie sztuczki używałem kiedyś m.in. w kompaktującym allokatorze pamięci 
na mikrokontrolerze. Opakowane w jakiś smart_ptr<> powodowało że cała i 
skomplikowana abstrakcja była przezroczysta.

[toc] | [prev] | [next] | [standalone]

#32738

On 2019-07-24 21:58, DMR wrote:
>> Jaki język prog.?
> 
> "struktura poszyta wskaźnikami" :-)
> 
> C/C++, ale nie o lingwistykę tu biega, tylko raczej o ogólną rozkminę tematu.
> Kolega wyżej zasugerował coś w ten deseń - można podziałać w apriorycznie zaalokowanym bloku pamięci, a potem przeliczyć offsety wskaźników względem punktu wejścia.
> Ma to sens?
> Czy wypocina straszna?

Czy straszna to nie wiem (IMHO nie calkiem), ale jednak w pewnym sensie
"wypocina".
Do takich celow sluza obiektowe/drzewiaste/grafowe bazy danych.
Np. ObjectDB w Javie, a w C++ np. ObjectStore czy inny Versant.

PS: dlatego spytalem o jezyk.

AK

[toc] | [prev] | [next] | [standalone]

#32739

Ja tam jestem amator, a więc jako osobnik nieprzewidywalny mogę w ogóle nie wiedzieć, że się "normalnie" nie da... ;-)



> Czy straszna to nie wiem (IMHO nie calkiem),
> ale jednak w pewnym sensie "wypocina".


Logika podpowiada, że skoro dane na dysku są jednym "klockiem", to jeśli podobnie zorganizuje się je w pamięci, powinno to zadziałać najsprawniej.
Pozostaje wtedy tylko przeliczyć offsety wskaźników na zero przy zapisie i względem początku zaalokowanego obszaru przy odczycie.
Prościej się chyba nie da. :-)
Ewentualnie można by zapisywać węzły w "odpowiedniej" kolejności - ale to na pierwszy rzut oka trywialne zadanie, wcale takim nie jest. Przynajmniej ja się poddałem.

Mam taką strukturę, którą tworzy się tylko raz, żeby jej potem wielokrotnie używać - koncepcja sortowania/porządkowania danych i budowania na nowo drzewa za każdym odczytem, jakoś mnie tak uwiera...

[toc] | [prev] | [next] | [standalone]

#32740

On 26/07/2019 22:09, DMR wrote:
> Pozostaje wtedy tylko przeliczyć offsety wskaźników na zero przy zapisie

Czyli serializacja bo zmieniasz dane w locie. Czyli nie tak jak chciałeś 
w pierwszym mailu, czyli szybko.

> Prościej się chyba nie da. :-)

Da się. Pytanie na ile to krytyczne aby było naprawdę szybko bo idę o 
zakład że nie ma to żadnego znaczenia praktycznego.

[toc] | [prev] | [next] | [standalone]

#32742

On 2019-07-26 22:33, heby wrote:
> Da się. Pytanie na ile to krytyczne aby było naprawdę szybko bo idę o 
> zakład że nie ma to żadnego znaczenia praktycznego.

Tez tak sądze/twierdzę. Wczytywanie z dysku w spodziewanycm "kontekscie"
malo znaczy.
Duzo znaczy to co sie dzieje pozniej w pamieci, czyli
znajdowanie najblizszych (i niekoniecznie niepijących) sąsiadów :)

AK

[toc] | [prev] | [next] | [standalone]

#32741

On 2019-07-26 22:09, DMR wrote:
> Logika podpowiada, że skoro dane na dysku są jednym "klockiem", to jeśli podobnie zorganizuje
  się je w pamięci, powinno to zadziałać najsprawniej.

No ale co np, z transakcjami itp?.
"Nie wiem , nie znam sie,zarobiony jestem", no ale wiem ze
np. Perst czy McObject do Javy maja "wbudowana" oblugę spartial data,
w szczegolnosci indeksy do kd-tree.
ObjectStore zapewne tez, bo przeciez *.dwg AutoCADa to tak naprawde
ObjectDatabase "zapewne" przystosowane do problemu najblizszego
sasiedstwa...

PS: Sorry, ale zajmowalem sie CADami "wieki temu".
PS1: Do ogolnego/grafowego repo polecam OrientDB.
     Jak dla mnie rewalka w segmencie OpenSource.

PS1: Tak tak.. SQL/table_relations to nie wszystko/dla mnie nie top.
Graph/tree databases to wcale nie tylko sredniowiecze (Ingres).

AK

[toc] | [prev] | [next] | [standalone]

#32752

W dniu środa, 24 lipca 2019 19:25:15 UTC+2 użytkownik DMR napisał:
> Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
> Jakieś równie wyrafinowane pomysły? :-)

jak dla mnie jest to dosyc żenujace pytanie

w popkulturze funkcjonuje jakies powiedzenie "nie ma glupich pytan" ale
w praktycznym programowaniu bywa mocno odwrotnie: duzo pytan jest mega glupie (mega glupich)

dlatego szczerze mowiac trzbby bardzo uwazac o co sie pyta i na co sie odpowiada

[i jest to dosyc trudna kwestia, poruszyc takie pytania by przynioslo to wyjatkowo uzyteczny rezultat..zwlaszcza ze rozni ludzi interesuja sie nieco roznymi rzeczami (ja ostatnio znowu nieco zainteresowalem sie pisaniem na androida)]

[toc] | [prev] | [next] | [standalone]

#32753

W dniu poniedziałek, 29 lipca 2019 11:36:27 UTC+2 użytkownik fir napisał:
> W dniu środa, 24 lipca 2019 19:25:15 UTC+2 użytkownik DMR napisał:
> > Misterna i wyrafinowana struktura poszyta wskaźnikami została utworzona w pamięci, a teraz trzeba ją zapisać na dysku - tak, żeby się przy wczytywaniu jak najszybciej odtworzyła w stanie "operacyjnym".
> > Jakieś równie wyrafinowane pomysły? :-)
> 
> jak dla mnie jest to dosyc żenujace pytanie
> 
> w popkulturze funkcjonuje jakies powiedzenie "nie ma glupich pytan" ale
> w praktycznym programowaniu bywa mocno odwrotnie: duzo pytan jest mega glupie (mega glupich)
> 
> dlatego szczerze mowiac trzbby bardzo uwazac o co sie pyta i na co sie odpowiada
> 
> [i jest to dosyc trudna kwestia, poruszyc takie pytania by przynioslo to wyjatkowo uzyteczny rezultat..zwlaszcza ze rozni ludzi interesuja sie nieco roznymi rzeczami (ja ostatnio znowu nieco zainteresowalem sie pisaniem na androida)]

jesttak dlatego (jak juz zdaje sie pisalem) ze wiele pytan, i zwiazanych z nimi odpowiedzi, spowalnia cie (mnie) lokujac cie w jakiejs cyfrowej d00p1e
- podczas gdy czlowiek nauczywszy sie omijac te spowalniacze moglby naprawde zrobic i nauczyc sie duzo wiecej, bez porownania wiecej i szybciej

jest to cos co mnie ostatnio trapi, dlatego z nichecia patrze na fora i takie na nich pytania... (choc sam oczywiscie robilem kiedy mega duzo bledow tego typu) od pewnego czasu sam lekko nauczylem sie zreszta chyab  podchodzic do sprawy bardziej profesjonalnie i tak nie utykac w 
tych programistycznych 'pitstopach' 
ale oczywiscie ciagle bardzo duzo mi brakuje

generalnie wiadomo z grubsza jednak o co chodzi, ludzie powinni sie nauczyc (ci ktorzy chca sprawnie kodowac) bardziej myslec o projektach 'napisanych' / 'przelecianych' od poczatku do konca sprawnie i szybko a nie tkwic za bardzo w problemowych dziurach

dla forum problem jest podwujny bo o ile tak szybko leciec z projektami pewnie jakos mozna sie nauczyc to by dyskutowac o tym na forum potrzeba juz co najmniej dwu ludzi to potrafiacych, potrafiacych tez o tym pisac (a porzebne by bylo pisanie z pewnymi szczegolami), chetnych tez skupic sie na tym samym temacie itd itp

[toc] | [prev] | [next] | [standalone]

#32755

> jak dla mnie jest to dosyc żenujace pytanie


Być może czegoś nie rozumiesz.
Ucz się, ucz! Bo nauka to potęgi klucz! :-)

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web