Mam listę składającą się z kilku tysięcy setów.
Każdy set jest unikalny.
Chcę jak najszybciej dostać set, który zawiera szukany przeze mnie element.
Niestety zwykłe:
for _set in list_of_sets:
if x in _set:
return _set
Odpada gdyż jest za wolne. Macie jakiś pomysł jak by to przyśpieszyć?
Proponowałbym użyć filter() czyli było by coś tak:
result = filter(lambda x: value in x, list_of_sets)
Generalnie, jeśli tak Chcesz szukać (znaleźć pierwszy zbiór, zawierający dany element, w dowolnej liście zbiorów), to naturalnym patternem będzie wyszukiwanie liniowe, a to ma złożoność, jakkolwiek nie zrobione - petla, list comprehension - długość listy zbiorów.
A możesz dostać te dane w innej strukturze? I pytanie czy faktycznie musisz dostać ten set? Może wystarczyłby Ci index listy?
Mam po prostu różne zbiory elementów. To, ze są to zbiory i są na liście to jest moja decyzja.
Problem jest taki:
[{"a", "c"}, {"d", "b", "e"}, {"m", "y"}]
Gdzie literki to oczywiście np. jakieś wyrazy. Chodzi o to, że w aktualne rozwiązanie (liniowe) mnie nie satysfakcjonuje czasowo. Przykładowo mam input "m" i muszę zwrócić cały zbiór {"m", "y"}.
Tak że jeśli jakiś inny zbiór danych bardziej tu pasowałbym (dlatego m.in tu napisałem) to proszę o propozycję. Index listy to też informacja o zbiorze prawda @TomRiddle? Bo inaczej nie rozumiem jeśli nie
Możesz zrobić mapę, w której będziesz trzymać powiązanie pomiędzy elementem, a zbiorem.
Najpierw odpowiedz na pytania:
Jeżeli element może należeć tylko do 1 zbioru, to możesz zrobić odwrotne mapowanie kosztem pamięci. Tzn zrobić pomocniczą mapę, która dla każdego elementu trzyma odnośnik do zbioru, w którym ten element się znajduje.
Jeżeli element może należeć do różnych zbiorów, to robisz mapę do listy/zbioru zbiorów.
Po prostu to rozwiązanie jest dosyć dziwne. Lista to inna nazwa na kolekcje która zachowuje kolejność i pozwala na duplikaty (+null, zależnie od języka). Zbiór to inna nazwa na kolekcje która nie przechowuje duplikatów i ani kolejności.
Używanie ich raz wydaje się conajniej dziwne. Wygląda jak problem X/Y.
Daj sobie pomóc i poda więcej szczegółów dokładnie co to rozwiązanie ma tworzyć. Być może da się ominąć jakiś element tej Twojej struktury i skrócić czas potrzebny na wyszukanie.
Pomysl moze glupi, ale moze by sprobowac rozbic to na watkach ? W zaleznosci jak dluga jest lista np zakladajac ze jest 30 zbiorow - Kazdy watek dostawal by co dziesiaty zbior. Asynchronicznosc powinna to troche przyspieszyc.
tsz napisał(a):
Możesz zrobić mapę, w której będziesz trzymać powiązanie pomiędzy elementem, a zbiorem.
Mogłem wspomnieć, że próbowałem już tego ale niestety wtedy dodawanie mocno kuleje z tego względu, że co jakiś czas przy dodawaniu te zbiory są łączone w jeden. W wypadku takiego łączenia wszystkie odnośniki do setu B powinny wskazywać na set A. Problem jest tego typu, że w Pythonie nie da się po prostu dodać jakiegoś wskaźnika na drugi obiekt.
nalik napisał(a):
Najpierw odpowiedz na pytania:
- Czy element może należeć tylko do 1 zbioru?
- Czy wyszukiwanie zbioru jest najbardziej krytyczną operacją?
- Dlaczego trzymasz elementy w zbiorze? Może to nie jest odpowiednia struktura dla twoich potrzeb? Jaki problem rozwiązują te zbiory?
Jeżeli element może należeć tylko do 1 zbioru, to możesz zrobić odwrotne mapowanie kosztem pamięci. Tzn zrobić pomocniczą mapę, która dla każdego elementu trzyma odnośnik do zbioru, w którym ten element się znajduje.
Jeżeli element może należeć do różnych zbiorów, to robisz mapę do listy/zbioru zbiorów.
TomRiddle napisał(a):
Po prostu to rozwiązanie jest dosyć dziwne. Lista to inna nazwa na kolekcje która zachowuje kolejność i pozwala na duplikaty (+null, zależnie od języka). Zbiór to inna nazwa na kolekcje która nie przechowuje duplikatów i ani kolejności.
Używanie ich raz wydaje się conajniej dziwne. Wygląda jak problem X/Y.
Daj sobie pomóc i poda więcej szczegółów dokładnie co to rozwiązanie ma tworzyć. Być może da się ominąć jakiś element tej Twojej struktury i skrócić czas potrzebny na wyszukanie.
Mam aplikację która zawiera zbiory wyrazów.
{"a", "c"}, {"d", "b", "e"}, {"m", "y"} (przyjmijmy, że literki to wyrazy.
Są dwie trzy opcje:
Do zbioru (lub innego typu jeśli zaproponujecie jakiś inny), który zawiera wyraz "a" dodaj nowy wyraz "b"
Do zbioru (lub innego typu jeśli zaproponujecie jakiś inny), który zawiera wyraz "d" oraz "b" dodaj nowy wyraz "m"
(czyli można też wyszukiwać na podstawie kilku wyrazów, ale to szczegół chyba?)
Wyszukanie zbioru bez dodawania nowego wyrazu.
Pokaż mi wszystkie wyrazy, które są połączone z wyrazem "c" - czyli użytkownik powinien dostać "a" oraz "c"
Połączenie danych zbiorów.
Połącz zbiór, który zawiera "b" ze zbiorem, który zawiera "y"
Oczywiście słowo zbiór oznacza w moim przypadku zarówno set jak i zbiór z takiego punktu widzenia użytkownika, a czy to będzie set to już osobna kwestia - jest to dla mnie nie istotne
ledi12 napisał(a):
Pomysl moze glupi, ale moze by sprobowac rozbic to na watkach ? W zaleznosci jak dluga jest lista np zakladajac ze jest 30 zbiorow - Kazdy watek dostawal by co dziesiaty zbior. Asynchronicznosc powinna to troche przyspieszyc.
Pomysł by nie był głupi gdyby faktycznie chodziło tylko o przyśpieszenie procesu. Problem nie jest z maszynami itd. tylko z samym kodem, chciałbym po prostu przyśpieszyć to jednowątkowo, nie jest to problem na tyle krytyczny by komplikować go do korzystania z wątków.
Tak pomijając dodatkowe struktury danych, najprościej można do tego podejść sortując sobie tą listę zbiorów według częstości wyszukiwań tychże. Jeżeli 99% wyszukiwań to, dajmy na to, elementy stu zbiorów, a 1% to elementy z pozostałych kila tysięcy, to trzymanie tych 100 na samym początku listy już powinno dawać jakiś obserwowalną poprawę, bo się będziesz wcześniej zatrzymywal. Zależy co konkretnie w tych zbiorach trzymasz, jeżeli wyszukujesz równomiernie to naturalnie nic to nie da.
Raczej równomiernie i zmienia się też to w czasie, musiałbym statystki prowadzić a to za duże utrudnienie. Nie jest to na tyle krytyczne, ale fajna propozycja. Cache oczywiście też odpada
anonimowy napisał(a):
tsz napisał(a):
Możesz zrobić mapę, w której będziesz trzymać powiązanie pomiędzy elementem, a zbiorem.
Mogłem wspomnieć, że próbowałem już tego ale niestety wtedy dodawanie mocno kuleje z tego względu, że co jakiś czas przy dodawaniu te zbiory są łączone w jeden. W wypadku takiego łączenia wszystkie odnośniki do setu B powinny wskazywać na set A. Problem jest tego typu, że w Pythonie nie da się po prostu dodać jakiegoś wskaźnika na drugi obiekt.
OK, w takim razie zamiast zwykłej mapy dajesz Find-Union (koncepcyjnie można uznać za to samo, tylko wielopoziomowo, w postaci drzewa). Wszystkie odnośniki są połączone z korzeniem swojego drzewa, a nie bezpośrednio ze zbiorem. Zamiast przepinać wszystkie odnośniki na zapas, podpinasz jedynie korzeń jednego drzewa pod inne drzewo. Kod do znalezienia na angielskiej wiki, albo każdej lepsze książce do algorytmów.
Oczywiście zbiory wyrazów i tak należy połączyć, żeby nie ucierpiało wyszukiwanie sąsiadów ze zbioru.
Swoją drogą, zrób benchmarki albo chociaż jakieś wstępne wyliczenia, bo mam wrażenie ze rozwiązujesz problem, którego nie ma. Odwrotny indeks w postaci mapy powinien spokojnie wystarczyć. Więc zastanawiam się jak stwierdziłeś, że jest za wolno. O jakiej liczbie zbiorów i średniej liczby elementów na zbiór mówimy i jak często te zbiory są ze sobą łączone?
Problem jest tego typu, że w Pythonie nie da się po prostu dodać jakiegoś wskaźnika na drugi obiekt.
To żart, prawda? :D Przecież mógłbyś zrobić mapę która ci to załatwia i wprowadza element pośredniości, w takim sensie że ze mapujesz sobie literka->index_logiczny, a obok masz inną mapę która mapuje index_logiczny->index_fizyczny i finalnie mapę index_fizyczny->zbiór.
Jak robisz joinowanie zbiorów o index_logicznyk i m to robisz po prostu zmianę w tej drugiej mapie k->index_fizyczny_połączonych, oraz m->index_fizyczny_połączonych i voila.
import uuid
class MagicSets(object):
def __init__(self):
self.physical = {}
self.logical = {}
self.mapping = {}
def add_new_set(self, data):
new_physical_id = uuid.uuid4()
self.physical[new_physical_id] = data
new_logical_id = uuid.uuid4()
self.logical[new_logical_id] = new_physical_id
for key in data:
self.mapping[key] = new_logical_id
def _find_logical_idx(self, matcher):
return self.mapping[matcher]
def _find_physical_idx(self, matcher):
return self.logical[self._find_logical_idx(matcher)]
def find_matching_set(self, matcher):
return self.physical[self._find_physical_idx(matcher)]
def add_value_to_matching_set(self, new_value, matcher):
self.find_matching_set(matcher).add(new_value)
def join_matching_sets(self, matcher1, matcher2):
physical_index1 = self._find_physical_idx(matcher1)
logical_index1 = self._find_logical_idx(matcher1)
found_set1 = self.physical[physical_index1]
physical_index2 = self._find_physical_idx(matcher2)
logical_index2 = self._find_logical_idx(matcher2)
found_set2 = self.physical[physical_index2]
joined_set = set(found_set1)
joined_set.update(found_set2)
# create new physical entry
new_physical_id = uuid.uuid4()
self.physical[new_physical_id] = joined_set
# wire both logical sets to new physical entry
self.logical[logical_index1] = new_physical_id
self.logical[logical_index2] = new_physical_id
# # cleanup
del self.physical[physical_index1]
del self.physical[physical_index2]
def main():
m = MagicSets()
for s in [{"a", "c"}, {"d", "b", "e"}, {"m", "y"}]:
m.add_new_set(s)
print(m.find_matching_set('a'))
m.add_value_to_matching_set('x', 'a')
print(m.find_matching_set('a'))
m.join_matching_sets('a', 'b')
print(m.find_matching_set('a'))
print(m.find_matching_set('b'))
main()
Musiałem kilka razy edytowac bo pomieszałem gdzieś ID, ale teraz już jest chyba ok.
anonimowy napisał(a):
Problem jest tego typu, że w Pythonie nie da się po prostu dodać jakiegoś wskaźnika na drugi obiekt.
Późno było jak to czytałem i nie zauważyłem tego fragmentu. Przecież w pythonie obiekty trzymane są przez referencję ... Nie potrzebujesz wskaźnika, dwa pola/zmienne będą odnosić się do tego samego obiektu gdy dokonasz przypisania jednego do drugiego.
Shalom napisał(a):
Problem jest tego typu, że w Pythonie nie da się po prostu dodać jakiegoś wskaźnika na drugi obiekt.
To żart, prawda? :D Przecież mógłbyś zrobić mapę która ci to załatwia i wprowadza element pośredniości, w takim sensie że ze mapujesz sobie
literka->index_logiczny, a obok masz inną mapę która mapujeindex_logiczny->index_fizycznyi finalnie mapęindex_fizyczny->zbiór.
Jak robisz joinowanie zbiorów o index_logicznykimto robisz po prostu zmianę w tej drugiej mapiek->index_fizyczny_połączonych, orazm->index_fizyczny_połączonychi voila.
Nie to nie żart. Nie wiem dlaczego Ci przyszło to do głowy, też zalatuję to nutką chamstwa ale pomińmy to. Dzięki za sugestię. Próbowałem już coś podobnego
Twój kod wywali się już na
def main():
m = MagicSets()
for s in [{"a", "c"}, {"d", "b", "e"}, {"m", "y"}]:
m.add_new_set(s)
m.join_matching_sets('a', 'b')
m.join_matching_sets('b', 'y')
print(m.find_matching_set('a'))
Z prostego względu, że nie odświeżasz mappingu przy każdym dodawaniu nowego znaku lub przy łączeniu setów (tak jak w pokazanym przykładzie).
Jasne można sobie to za każdym razem odświeżać, ale to zabija wydajność i proste rozwiązanie na liście lepiej się spisze.
To właśnie miałem na myśli przez brak wskaźnika. Przy wskaźniku jak rozumiem wystarczyło by zmienić docelowy element a każda zmienna wskazująca na niego miała by nowe dane.
Nie rozumiem do końca jakbyś chciał to zaimplementować, ale przecież w Pythonie możesz sobie zrobić choćby coś takiego:
ptr = {'ref': obiekt}
I masz taki prosty wskaźnik.
anonimowy napisał(a):
To właśnie miałem na myśli przez brak wskaźnika. Przy wskaźniku jak rozumiem wystarczyło by zmienić docelowy element a każda zmienna wskazująca na niego miała by nowe dane.
Jaka jest Twoim zdaniem różnica pomiędzy owym mitycznym wskaźnikiem, a trzymaniem obiektów przez referencję?
Poza tym, podałem Ci nazwę algorytmu, który Ci pomoże, nawet nie sprawdziłeś.
@tsz @nalik
some_set = {"a", "b"}
some_set_2 = {"d", "e"}
some_set_3 = {"h", "i"}
ptr = {
'a': some_set,
'b': some_set,
'd': some_set_2,
'e': some_set_2,
'h': some_set_3,
'i': some_set_3,
}
print(ptr["a"]) # {'a', 'b'}
print(ptr["b"]) # {'a', 'b'}
new_set = set()
new_set.update(some_set, some_set_2)
print(new_set) # {"a", "b", "c", "d"}
for char in new_set:
ptr[char] = new_set
Problem jest z ostatnią pętlą. Musi ona być co niszczy wydajność.
Myślałem, że wskaźnik działa tak, że wskazałbym, że some_set ma wskazywać na new_set i problem z pętlą znika.
Problem z referencją jest taki, że każdy obiekt, który odnosi się do jakiegoś obiektu będzie się odnosił do niego i nie możemy tego zmienić w żaden sposób
some_set = {"ref": {"a", "b"} }
some_set_2 = {"ref": {"d", "e"} }
some_set_3 = {"ref": {"h", "i"} }
ptr = {
'a': some_set,
'b': some_set,
'd': some_set_2,
'e': some_set_2,
'h': some_set_3,
'i': some_set_3,
}
print(ptr["a"]['ref']) # {'a', 'b'}
print(ptr["b"]['ref']) # {'a', 'b'}
new_set = {'ref': set()}
new_set['ref'].update(some_set['ref'], some_set_2['ref'])
print(new_set['ref']) # {"a", "b", "c", "d"}
some_set['ref'] = new_set['ref']
some_set_2['ref'] = new_set['ref']
some_set_3['ref'] = new_set['ref']
Wiem, że paskudne, ale powinno być wydajniejsze. I pewnie użycie dedykowanej klasy zamiast słownika byłoby szybsze.
@tsz
Oo, ciekawa koncepcja, to jest prawie to samo co @Shalom zaproponował tylko, że napisane w inny sposób (imo prostszy)
some_set = {"ref": {"a", "b"} }
some_set_2 = {"ref": {"d", "e"} }
some_set_3 = {"ref": {"h", "i"} }
ptr = {
'a': some_set,
'b': some_set,
'd': some_set_2,
'e': some_set_2,
'h': some_set_3,
'i': some_set_3,
}
new_set = {'ref': set()}
new_set['ref'].update(
some_set['ref'],
some_set_2['ref']
)
some_set['ref'] = new_set['ref']
some_set_2['ref'] = new_set['ref']
new_set = {'ref': set()}
new_set['ref'].update(
some_set['ref'],
some_set_3['ref']
)
some_set['ref'] = new_set['ref']
# some_set_2 has to be here as well
some_set_3['ref'] = new_set['ref']
for key, value in ptr.items():
print(key, value)
# e {'ref': {'e', 'b', 'd', 'a'}}
# d {'ref': {'e', 'b', 'd', 'a'}}
# a {'ref': {'e', 'd', 'a', 'b', 'i', 'h'}}
# b {'ref': {'e', 'd', 'a', 'b', 'i', 'h'}}
# i {'ref': {'e', 'd', 'a', 'b', 'i', 'h'}}
# h {'ref': {'e', 'd', 'a', 'b', 'i', 'h'}}
Problem jest taki, że musisz aktualizować za każdym razem te ścieżki znowu. Zobacz sobie jak chcę połączyć set złączony z dwóch to wszystkie elementy (e, d), które były ze set_2 muszą teraz też wskazywać na ten nowy. Więc znowu w pętli muszę jechać po tych obiektach, które były połączone
W sumie to można używać po prostu już istniejącego setu. I dla wydajności to będzie lepsze niż tworzenie nowego obiektu. Chyba że jest jakiś dobry powód, żeby ten stary set nie był zmieniany.
some_set = {"ref": {"a", "b"} }
some_set_2 = {"ref": {"d", "e"} }
some_set_3 = {"ref": {"h", "i"} }
ptr = {
'a': some_set,
'b': some_set,
'd': some_set_2,
'e': some_set_2,
'h': some_set_3,
'i': some_set_3,
}
some_set['ref'].update(
some_set_2['ref']
)
some_set_2['ref'] = some_set['ref']
some_set['ref'].update(
some_set_3['ref']
)
some_set_3['ref'] = some_set['ref']
for key, value in ptr.items():
print(key, value)
# a {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
# b {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
# e {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
# d {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
# i {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
# h {'ref': {'a', 'b', 'e', 'd', 'i', 'h'}}
Raz jeszcze - ciekawe propozycja, ale nadal ona nie rozwiązuje głównego problemu. Zobacz na kod poniżej: przy łączeniu połączonych wcześniej setów:
some_set = {"ref": {"a", "b"} }
some_set_2 = {"ref": {"d", "e"} }
some_set_3 = {"ref": {"h", "i"} }
some_set_4 = {"ref": {"q", "w"} }
ptr = {
'a': some_set,
'b': some_set,
'd': some_set_2,
'e': some_set_2,
'h': some_set_3,
'i': some_set_3,
'q': some_set_4,
'w': some_set_4,
}
some_set['ref'].update(
some_set_2['ref']
)
some_set_2['ref'] = some_set['ref']
some_set_3['ref'].update(
some_set_4['ref']
)
some_set_4['ref'] = some_set_3['ref']
some_set['ref'].update(
some_set_4['ref']
)
some_set_4['ref'] = some_set['ref']
for key, value in ptr.items():
print(key, value, id(value["ref"]))
# a {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
# d {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
# b {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
# q {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
# h {'ref': {'q', 'h', 'i', 'w'}} 2036214697768
# i {'ref': {'q', 'h', 'i', 'w'}} 2036214697768
# e {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
# w {'ref': {'a', 'w', 'q', 'e', 'i', 'd', 'b', 'h'}} 2036214559912
some_set_4['ref'] = some_set_3['ref']
W jakiej sytuacji miałoby dojść do czegoś takiego? Jeśli coś takiego miałoby zachodzić to raczej:
some_set_4 = some_set_3
No przecież tak łączysz sety? Analogicznie zrobiłem do poprzednich łączeń. Chcę połączyć set 3 i set 4
To ja też :D
import itertools
class Node:
def __init__(self, identity):
self.parent = self
self.identity = identity
self.rank = 0
def link_parent(self, parent):
assert self.parent is self
self.parent = parent
if self.rank == parent.rank:
parent.rank += 1
def __repr__(self):
return str(self.__dict__)
class MagicSets:
def __init__(self):
self.id_generator = itertools.count(start=0, step=1)
self.sets = dict()
self.rev_index = dict()
def add(self, val):
if val not in self.rev_index:
identity = next(self.id_generator)
self.rev_index[val] = Node(identity)
self.sets[identity] = set(val)
def set_of(self, val):
root = self.find_root(val)
if root:
return self.sets[root.identity]
return None
def find_root(self, val):
node = self.rev_index.get(val)
while node and node.parent and node != node.parent:
next_node = node.parent
node.parent = next_node.parent
node = next_node
return node
def join(self, val1, val2):
root1 = self.find_root(val1)
root2 = self.find_root(val2)
if root1 != root2:
if root1.rank < root2.rank:
root1, root2 = root2, root1
root2.link_parent(root1)
self.sets[root1.identity].update(self.sets[root2.identity])
del self.sets[root2.identity]
def main():
m = MagicSets()
m.add("a")
m.add("b")
print(m.set_of("a"))
print(m.set_of("b"))
m.join("a", "b")
print(m.set_of("a"))
print(m.set_of("b"))
m.add("e")
m.add("f")
m.join("e", "f")
print(m.set_of("e"))
m.join("b", "f")
print(m.set_of("a"))
print(m.set_of("b"))
print(m.set_of("e"))
print(m.set_of("f"))
main()