Rzadka macierz trójkątna

Odpowiedz Nowy wątek
2018-11-12 10:50
0

Piszę sobie sam dla siebie prosty projekt w Pythonie (żeby odpocząć po tym całym programowaniu w pracy ;)) i jak to mam w zwyczaju w tego typu projektach dla zabawy, przeintelektualizuję wszystko co się da i jak się da — przedwczesna optymalizacja na każdym kroku, dziwne i rzadziej spotykane algorytmy implementowane z palca itd. Ot, to mnie bawi.

Jedną rzeczą, którą próbuję zrobić, a co do której nie mam dobrego pomysłu, jest skojarzenie dwóch zmiennych. Dokładniej: mam sporo elementów (w praktyce koło dziesięciu tysięcy, ale wolę założyć, że miliony — bo to bliższe idei tego przesadzonego projektu) oraz niezbyt dużo (rząd wielkości taki, jak liczby elementów) takich skojarzeń. Skojarzenia tyczą się pary nieuporządkowanej.

I teraz chcę to jakoś sprytnie trzymać, by móc szybko sprawdzić:

  • czy dwie wartości są skojarzone
  • z jakimi wartościami skojarzona jest dana zmienna

Co mi przyszło do głowy:

  • słownik indeksowany parą uporządkowaną i wrzucanie na dwa razy — ale to zły pomysł, bo znalezienie wszystkich skojarzeń zmiennych jest wolne
  • scipy.sparse
  • trzymanie w każdej ze zmiennych kopca z odwołaniami do innych zmiennych, z którymi jest skojarzona

Jakieś lepsze pomysły? A jak nie lepsze, to chociaż ciekawe?

Pozostało 580 znaków

2018-11-12 12:45
0

Wytłumacz dokłądnie o co Ci chodzi i jak się to ma do rzadkiej macierzy trójkątnej???


Pozostało 580 znaków

2018-11-12 12:51
0

Nie wiem czy umiem dokładniej…

Mam duży zbiór obiektów. Chcę mieć mapowanie typu {x; y} → bool, tzn. odwzorowanie pary nieuporządkowanej tych obiektów do wartości PRAWDA/FAŁSZ. Wartości typu PRAWDA będzie bardzo mało w stosunku do wartości FAŁSZ.

Stąd właśnie macierz trójkątna (bo albo dwie wartości są powiązane, albo nie, kolejność nie ma znaczenia — więc nie muszę trzymać całej macierzy symetrycznej, jak mi wystarczy pół) i rzadka (bo mało wartości się tam pojawi).

Pozostało 580 znaków

2018-11-12 13:18
1

Ale co dokładnie Cię gnębi? Format przechowywania macierzy?

W scipy jest CSR/CSC ale generalnie to to nie jest zbyt szybki format, jeśli dla poszczególnych wierszy/kolumn indeksy wartości nie są posortowane, to wyszukiwanie elementu może być bardzo czasochłonne. Choć w scipy jest szansa, że są sortowane.

Skoro to macierz symetryczna, to możesz spróbować poszukać implementacji Sparse Skyline Format ;)


Prosząc o pomoc w wiadomości prywatnej odbierasz sobie szansę na otrzymanie pomocy od kogoś bardziej kompetentnego :)
edytowany 1x, ostatnio: superdurszlak, 2018-11-12 13:18

Pozostało 580 znaków

2018-11-12 14:29
0

I teraz chcę to jakoś sprytnie trzymać, by móc szybko sprawdzić:
czy dwie wartości są skojarzone

Słownik w dwie strony (jakiś BiMap z javy na przykład).

z jakimi wartościami skojarzona jest dana zmienna

Osobny słownik <klucz, lista sąsiadów>.

Przy dodawaniu skojarzenia dodajesz do obu struktur.

Pozostało 580 znaków

2018-11-12 14:57
0

Duże pamięciowo. Nie podoba mi się za bardzo.

Pozostało 580 znaków

2018-11-12 15:50
0

No to musisz się zdecydować, bo mówisz, że jest ich niezbyt dużo a potem rząd wielkości taki, jak liczby elementów, więc w końcu jest to niezbyt dużo, czy nie. Moje rozwiązanie zwiększa jedynie stałą przy złożoności pamięciowej, skojarzeń ciągle jest proporcjonalnie tyle samo. Poza tym cudów nie ma, zbijasz złożoność czasową lub pamięciową, obu naraz raczej nie zbijesz.

Niezbyt dużo, bo mogło by być kwadratowo względem liczby elementów, a jest tylko liniowo. - enedil 2018-11-12 16:04
Moja struktura też przechowuje liniową liczbę elementów, a jednak jest to duże pamięciowo. - Afish 2018-11-12 16:05

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0