-
Data: 2015-09-22 13:43:04
Temat: Re: Tablica int i usuwanie duplikatów
Od: "M.M." <m...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On Saturday, September 19, 2015 at 8:44:44 PM UTC+2, bartekltg wrote:
> Aj!
> Racja.
> Na szczęśćie dla wyników, na które patrzyłem, czyli najdłuższych,
> i tak była jedna pętla, te wyniki wiec się nie znieniły.
Tak
> >> Nagmatwałeś troche z różną ilośćią zer;-)
> > Był błąd, powinno być tak:
> > for( int i=0 ; i<size ; i++ ) {
> > if( t[i] != 0 ) {
> > if( ! exist_mm( t[i] , u , s2) )
> > t[size2++] = t[i];
> > } else if( !zero ) {
> > t[size2++] = 0;
> > zero = true;
> > }
> > }
>
> Tak, teraz działą.
>
> Hackerstwo ;-)
> Ale ładne.
Dziękuję :)
> TEraz tylko osobny kubełek dla zer i mamy
> szybką hastablicę (bez usuwania).
To jest tylko głupia hash-table, a ile można usprawnień i wersji
zaimplementować. Do konkretnych danych można lepiej funkcję hash
dopasować. Do losowych faktycznie nie ma sensu. Można wyzbyć się
operacji modulo, na rzecz bitowego and. Można testować na 64
pozycje w przód w jednym ifie lub jednej pętli.
> >> i wtedy nie musimy co chwila robić realokacji i rehashowania,
> >> gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
> >> wynik,
> > Hmmm ja bym się spodziewał się max 1.5 raza.
>
> Pamiętaj, żę nie napisałeś ogolnej tablicy hashującej,
Mimo to powinno być 1.5 raza. Nie mam czasu na zabawę, ale
coś czuję, żebym napisał ogólną ze współczynnikiem 1.5.
> tylko
> uży<=eś jednej specyficznej wartości do oznaczenia pustego pola
> w tablicy (i jakbyś tworzył pełną tablicę hashującą, miałbyś
> osobny kubełek na zera) Zrobienie tego w ogolności (dla dowolnego typu)
> jest dość trudne.
> Nie masz usuwania z tablicy - dopisane w tej wersji byłoby
> kosztowne.
Jest jeszcze jedna sztuczka, czasami się opłaca. Zamiast kubełka na
wartość zero, robi się tablicę bitów z info o zajętych pozycjach.
W trakcie dodawania, zliczasz ile maksymalnie było przeskoczonych
zapełnionych pozycji. Potem, w trakcie usuwania i wyszukiwania, tyle
samo wykonujesz iteracji. Ilość iteracji może wzrosnąć do
dużej wartości przy złym rozproszeniu i małym zapełnieniu. Ale można
takich wartości zapamiętać wiele, np. jedna dla każdych 1-10tys
entry point w hash-table... niby to tylko głupia hash-table ;-)
> Jak się buduje pałną talicę hashującą, aż takiej poprawy nie ma:
> http://incise.org/hash-table-benchmarks.html
>
> Googlowa jest neicałe 2 razy szybsza od unordered set.
>
> I teraz pytanie, na ile użycie własnej konstrukcji opłaca się
> w strosunku do gotowca. Przyszpieszenie ejst bardzo wyraźne, ale
> musiałeś to napsiać i jeszczer błąd się wkradł.
Cóż, albo bierzemy gotowca, albo rzeźbimy sami, narażając się na
błędy i stratę czasu. Każdy wyboru musi dokonać sam.
> >> bo tamta hashmapa rozwiązuje kolizje tworząc listę,
> >> a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
> >> o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.
> > Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa
> > tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej
> > tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.
>
> W przypadku hashmapy bardzon ważne jest cache. Jak masz dwie tablice,
> to masz dwa razy więcej dostępów.
Teoretycznie tak, ponieważ są dwa strzały w losowe miejsce RAM. Jednak z
tego co pamiętam z pomiarów własnych, to nie spowalniało wyraźnie.
> Stadndard nie precyzuje, gcc implementuje... identyczność ;-)
> Tu nie będzie miało to znaczenia, bo dane sa losowe.
Racja.
Pozdrawiam
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-03-15 China-Kraków => Key Account Manager IT <=
- 2025-03-14 Spalił się autobus :-)
- 2025-03-14 Policjanci z Piątku
- 2025-03-14 Lublin => JavaScript / Node / Fullstack Developer <=
- 2025-03-14 Warszawa => Account Manager - Sprzedaż Usług Rekrutacyjnych <=
- 2025-03-14 Gliwice => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-03-14 VAT-R Umowa najmu na adres zamieszkania
- 2025-03-14 Gliwice => IT Expert (Network Systems area) <=
- 2025-03-14 Warszawa => Junior Rekruter <=
- 2025-03-14 Wrocław => Konsultant wdrożeniowy Comarch XL/Optima (Księgowość i
- 2025-03-14 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-14 Żerniki => Dyspozytor Międzynarodowy <=
- 2025-03-13 Raspberry Pi 3 Model B+
- 2025-03-13 Kuchenka elektryczna
- 2025-03-12 test