Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Funkcja hash() - ryzyko kolizji



 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Python
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Luke



Dołączył: 17 Cze 2007
Posty: 1893
Skąd: Szczecin

PostWysłany: Czw Gru 17, 2015 10:16 am  OP    Temat postu: Funkcja hash() - ryzyko kolizji Odpowiedz z cytatem Pisownia

W programie potrzebuję przechowywać informacje powiązane z wieloma (setkami tysięcy, milionami) stanami planszy. Do tego celu wykorzystuję słownik (dict).

Kod:
class BoardState(object):
    def __init__(self, ...):
        # ...
        self.board = [ [ None ] * self.cols for _ in xrange(self.rows) ]

    def __hash__(self):
        board_tuple = tuple([ tuple(row) for row in self.board ])
        return hash(board_tuple)

    # ...


Pierwszym pomysłem było indeksowanie słownika obiekami BoardState. Jednak obiektów BoardState przechowywanych w słowniku nie wykorzystuję do innych celów, niż późniejsze wyciągnięcie danych. Doszedłem więc do wniosku, że mogę oszczędzić pamięć indeksując słownik za pomocą hasha z obiektu BoardState hash(board_state) (tworzonego wyżej zdefiniowaną metodą __hash__).

Ta druga wersja zużywa 4 razy mniej pamięci, jednak zastanawiam się, jakie jest ryzyko wystąpienia kolizji - że dwa różne obiekty BoardState (z różnymi planszami w środku) otrzymają ten sam hasz.

_________________
Moje projekty | Endless Horse Run game
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Czw Sty 07, 2016 10:58 pm      Temat postu: Odpowiedz z cytatem Pisownia

Ja chyba bym zrobił inaczej, o ile to możliwe (pomysł rzucam ot tak, nie znam dobrze Twojego zagadnienia)... Skoro tych stanów jest dużo tak jak piszesz, to może lepiej przechowywać stany (lub pewną ich część) w jakiejś lokalnej (a może nawet mniej lokalnej) bazie danych współpracującej z Pythonem, z tego co wiem, to Python ma moduł umożliwiający łączenie z SQlite... Pracuje to całkiem nieźle... Testowałem to nawet, ale tylko na niewielkiej ilości danych... Miałem testować na większej, ale udało mi się rozwiązać problem prościej... :) Pozdrawiam :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Luke



Dołączył: 17 Cze 2007
Posty: 1893
Skąd: Szczecin

PostWysłany: Sro Sty 13, 2016 12:44 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Dawno i nie prawda, ale komuś może się przydać informacja, jak to, przynajmniej częściowo, rozwiązałem.
A mianowicie - skorzystałem z ZODB, obiektowej bazy danych dla Pythona.
Ostatecznie i tak okazała się zbyt mało wydajna (operacje zwalniały przy jeszcze większej ilości danych, ale proszę sobie nie myśleć, że to wina bazy - możliwe, że to np. dysk twardy był wąskim gardłem albo sama ogromna ilość danych).
Zdecydowałem się więc na aproksymację siecią neuronową.

_________________
Moje projekty | Endless Horse Run game
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Sro Sty 13, 2016 5:25 pm      Temat postu: Odpowiedz z cytatem Pisownia

Ciekawe :) Miałem co nieco wspólnego z AI, najbardziej ciekawi mnie logika rozmyta (ciut też algorytmy genetyczne i systemy hybrydowe), widzę w niej potencjał... logika zerojedynkowa mnie niestety nie przekonuje, w życiu nie ma logiki zerojedynkowej, w logice standardowej nie ma kluczowego pojęcia "nie wiem" oraz innych pośrednich stanów PRAWDY i FAŁSZU... :) nawet kiedyś miałem pomysł implementacji pewnych rozmytych układów, ale poszedł do kosza... na razie uczę się programować i implementować algorytmy w różnych językach... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Python Wszystkie czasy w strefie CET (Europa)

Strona 1 z 1

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.17955 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |