Rzadka macierz trójkątna

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?

0

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

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).

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 ;)

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.

0

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

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.

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