English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: unordered_map a zba9i.in
Ktoś doszedł czemu większość rozwiązań opartych na unordered_map wywalała się na teście 9i ('a'*150k+'b'*150k)?
W rankingu nie ma informacji o tym, kto na jakich testach się wywalił...
Obstawiam, że problemem może być słaba funkcja haszująca generująca wiele kolizji. Standardowe funkcje hashujące zaimplementowane w gcc std::hash są słabe (powiedziałbym nawet mocniej, że błędne).
"How to pick a hash function" https://sortingsearching.com/2020/05/21/hashing.html
Obstawiam, że problemem może być słaba funkcja haszująca generująca wiele kolizji. Standardowe funkcje hashujące zaimplementowane w gcc std::hash są słabe (powiedziałbym nawet mocniej, że błędne).
"How to pick a hash function" https://sortingsearching.com/2020/05/21/hashing.html
> W rankingu nie ma informacji o tym, kto na jakich testach się wywalił...
No szkoda, ale są rozwiązania, można sobie sprawdzić. W szczególności wszystkie rozwiązania które dostały 9 punktów były oparte na unordered_map i wywalały się na teście 9i.
No szkoda, ale są rozwiązania, można sobie sprawdzić. W szczególności wszystkie rozwiązania które dostały 9 punktów były oparte na unordered_map i wywalały się na teście 9i.
> Obstawiam, że problemem może być słaba funkcja haszująca generująca wiele kolizji.
Jest to możliwy powód, jednak w ramach dzielenia się wiedzą zdradzę, że nie o to chodziło w większości rozwiązań, które miały problemy na tym teście. Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear(). Usuwa ona co prawda pary (klucz, wartość) z hashmapy, jednak nie zmniejsza zarezerwowanej pamięci, tzn. bucket_count() pozostaje bez zmian.
Dokładniej mówiąc, jeśli najpierw umieścimy w unordered_mapie dużo kluczy, a następnie dużo razy wyczyścimy ją w niewłaściwy sposób (tzn. jedynie używając metody clear()), to za każdym razem czas czyszczenia zależny będzie od rozmiaru zarezerwowanej pamięci, czyli liniowy, przez co całe rozwiązanie będzie kwadratowe.
Jest to możliwy powód, jednak w ramach dzielenia się wiedzą zdradzę, że nie o to chodziło w większości rozwiązań, które miały problemy na tym teście. Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear(). Usuwa ona co prawda pary (klucz, wartość) z hashmapy, jednak nie zmniejsza zarezerwowanej pamięci, tzn. bucket_count() pozostaje bez zmian.
Dokładniej mówiąc, jeśli najpierw umieścimy w unordered_mapie dużo kluczy, a następnie dużo razy wyczyścimy ją w niewłaściwy sposób (tzn. jedynie używając metody clear()), to za każdym razem czas czyszczenia zależny będzie od rozmiaru zarezerwowanej pamięci, czyli liniowy, przez co całe rozwiązanie będzie kwadratowe.
> Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear(). ...
O, dziękuję. Faktycznie o tym nie wiedziałem, a sprawdziłem, że w moim przypadku wystarczyło po wywołaniu clear() dodać rehash(2), żeby rozwiązać problem z zba9i. Chociaż równie dobrze i prościej można było zamienić unordered_map na map, chyba też by to przeszło.
O, dziękuję. Faktycznie o tym nie wiedziałem, a sprawdziłem, że w moim przypadku wystarczyło po wywołaniu clear() dodać rehash(2), żeby rozwiązać problem z zba9i. Chociaż równie dobrze i prościej można było zamienić unordered_map na map, chyba też by to przeszło.
Nie wiem czy warto zakładać nowy temat, więc może zapytam tu: jak wygląda rozwiązanie z unordered_map? To jest wzorcówka czy są inne podejścia?
"wzorcówka"? nie widziałem nigdzie żadnego oficjalnego rozwiązania, więc jak na razie chyba ciężko jakieś konkretne nazwać wzorcowym.
Ja robię tak, że robię DP[b-a][c-a] => liczba stringów kończących się na aktualnej pozycji, które mają liczby a,b,c takie, że te różnice są jakie są. Wtedy DP jest mapą z offsetem pomiędzy "logicznymi" a "fizycznymi" kluczami, żeby móc np. przesunąć wszystko o (-1, -1) jak wejdzie nowe a.
Ja robię tak, że robię DP[b-a][c-a] => liczba stringów kończących się na aktualnej pozycji, które mają liczby a,b,c takie, że te różnice są jakie są. Wtedy DP jest mapą z offsetem pomiędzy "logicznymi" a "fizycznymi" kluczami, żeby móc np. przesunąć wszystko o (-1, -1) jak wejdzie nowe a.
Ja inkrementowałem 7 map (7, bo było 7 możliwości podciągów zbalansowanych: zawierających tylko litery kolejno: a, b, c, ab, bc, ca i abc). Indeksem był balans pomiędzy literami zliczanymi przez daną mapę. Jednoliterowe mapy były 0-wymiarowe (1 element), dwuliterowe - jednowymiarowe (różnice ilości wystąpień tych dwóch liter), a trzyliterowa - dwuwymiarowa (2 z 3 indeksów map dwuliterowych). Jak wystąpiła litera nie zliczana przez daną mapę i na koniec, zliczałem dla każdego indeksu wartości v*(v-1)/2 z map i je czyściłem (gdybym miał unordered_map to też by mi się wywaliło na teście 9i). Dla abc konieczna była mapa, bo przestrzeń indeksów była O(n^2), co by się nie zmieściło w pamięci (natomiast różnych indeksów było max n).
Teraz widzę że zamiast czyścić mapy można było użyć nieużywanego wymiaru do zmiany koszyka i zliczać tylko na koniec.
Przy okazji: rozwiązania zniknęły :(
Teraz widzę że zamiast czyścić mapy można było użyć nieużywanego wymiaru do zmiany koszyka i zliczać tylko na koniec.
Przy okazji: rozwiązania zniknęły :(
> Problemem jest niewłaściwe używanie unordered_mapy, a dokładniej metody clear().
Najgorsze, że standard języka C++ mówi, że m.clear() musi mieć złożoność O(m.size()).
https://en.cppreference.com/w/cpp/container/unordered_map/clear
Tylko jak się wczytać dokładniej w specyfikację, to okazuje się, że liczą tutaj tylko operacje na elementach, a nie całkowity czas działania metody.
Najgorsze, że standard języka C++ mówi, że m.clear() musi mieć złożoność O(m.size()).
https://en.cppreference.com/w/cpp/container/unordered_map/clear
Tylko jak się wczytać dokładniej w specyfikację, to okazuje się, że liczą tutaj tylko operacje na elementach, a nie całkowity czas działania metody.
W takim razie kolejne czyszczenia powinny być już szybkie, bo m.size() po pierwszym się zeruje. To wygląda na niezgodność ze standardem, zwłaszcza że jest wprost napisane, że nie chodzi o ilość koszyków tylko ilość elementów:
> DR LWG 2550
> Applied to C++11
> Behavior as published for unordered associative containers, unclear if complexity is linear in the number of elements or buckets
> Correct behavior clarified that it's linear in the number of elements
> DR LWG 2550
> Applied to C++11
> Behavior as published for unordered associative containers, unclear if complexity is linear in the number of elements or buckets
> Correct behavior clarified that it's linear in the number of elements
Okazuje się, że jednak jest technicznie zgodne ze standardem, bo:
https://eel.is/c++draft/container.requirements.general#2
> All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
Jak mapa jest pusta, to clear() robi 0 operacji na elementach mapy -- ale ma prawo zrobić sobie ile chce innych obliczeń.
https://eel.is/c++draft/container.requirements.general#2
> All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
Jak mapa jest pusta, to clear() robi 0 operacji na elementach mapy -- ale ma prawo zrobić sobie ile chce innych obliczeń.
Rzeczywiście nie jest to powiedziane, a IMHO powinno, bo w ten sposób, to clear() mógłby robić sleepa na 5 sekund i też by było zgodne ze standardem :)
Łał, rzeczywiście paskudna pułapka, w życiu nie słyszałem o tym zachowaniu (i najwidoczniej ciężko je wyczytać z dokumentacji), a też się na to naciąłem.
Internally unordered map is implemented using Hash Table, the key provided to map are hashed into indices of a hash table that is why the performance of data structure depends on hash function a lot but on an average, the cost of search, insert and delete from the hash table is O.
http://www.indigocard.vip/
http://www.indigocard.vip/
https://www.vassouras.rj.gov.br/profile/fildena200/profile
https://www.fhwa.dot.gov/reauthorization/reauexit.cfm?link=www,genericvillage.com/product/vidalista-20-mg/
https://www.fhwa.dot.gov/reauthorization/reauexit.cfm?link=www.genericvillage.com/product/kamagra-oral-jelly/
http://ideate.xsead.cmu.edu/discussion/introduction-to-media-synthesis-and-analysis/topics/viro-valor-xl-pills-to-last-longer-and-get-stronger?page=1
https://www.northliberty.in.gov/profile/cenforce/profile
http://blogs.harvard.edu/stoptorture/about/comment-page-543/
https://www.fhwa.dot.gov/reauthorization/reauexit.cfm?link=www,genericvillage.com/product/vidalista-20-mg/
https://www.fhwa.dot.gov/reauthorization/reauexit.cfm?link=www.genericvillage.com/product/kamagra-oral-jelly/
http://ideate.xsead.cmu.edu/discussion/introduction-to-media-synthesis-and-analysis/topics/viro-valor-xl-pills-to-last-longer-and-get-stronger?page=1
https://www.northliberty.in.gov/profile/cenforce/profile
http://blogs.harvard.edu/stoptorture/about/comment-page-543/