-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: zadanie z netu
Date: Thu, 28 Mar 2013 20:14:35 +0100
Organization: ATMAN - ATM S.A.
Lines: 50
Message-ID: <kj24qt$mvr$1@node1.news.atman.pl>
References: <2...@g...com>
<0...@g...com>
<kj047e$kbo$1@node1.news.atman.pl>
<3...@g...com>
<5...@g...com>
<kj1qbt$bqv$1@node1.news.atman.pl>
<c...@g...com>
<kj23rb$2g9$1@node2.news.atman.pl>
NNTP-Posting-Host: 144-mi3-6.acn.waw.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1364498077 23547 85.222.69.144 (28 Mar 2013 19:14:37
GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Thu, 28 Mar 2013 19:14:37 +0000 (UTC)
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130307
Thunderbird/17.0.4
In-Reply-To: <kj23rb$2g9$1@node2.news.atman.pl>
Xref: news-archive.icm.edu.pl pl.comp.programming:202364
[ ukryj nagłówki ]W dniu 2013-03-28 19:57, bartekltg pisze:
> W dniu 2013-03-28 19:20, M.M. pisze:
>> W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg
>> napisał:
>>
>>> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
>>> pewnie tylko raz jeszcze musisz policzy.
>> Nie wiem jaki jest najsprytniejszy algorytm realokacji hash-table.
>> Naiwny wygląda mniej/więcej tak:
>> 1) Przydziel większą tablicę
>> 2) Dla każdego elementu z tablicy mniejszej:
>> a) policz funkcję hash
>> b) wrzuć do większej
>> 3) Zwolnij pamięć list
>> 4) Zwolni mniejszą tablicę
>>
>> W tym zadaniu faktycznie można dać tablicę 1.5 * ilosc_znaków i się
>> nie martwić. Ale w ogólnym przypadku (chyba) trochę czasu schodzi
>> na realokację.
>
>
> Tak jak w każdym tego typu kontenerze. Poszacuj sobie czas
> zamortyzowany. Dla czysto rosnącej tablicy i powiększania x2
> wychodzi 3 razy więcej niż wklejenie elementu (dodając element
> przydzielasz mu dodatkowe dwa kredyty na jego realokowanie w przyszlosci
> i realokowanie elementu z pierwszej połowy tablicy).
>
> Mała cena jak za możliwość nieprzejmowania się rozmiarem;)
OK, może za mętnie powiedziałem, trochę rozjaśnię.
Niech naszym bazowym kosztem będzie policzenie hasha,
wstawienie do tablicy i 1/n czasu zalkokowania tej tablicy
(czy tam tablicy list...) dlugosci n.
Koszt zamortyzowany pojedyńczego wstawiania jest
mniejszy niż 3*koszt podstawowy (będzie gdzieś pomiedzy x2 i x3).
Z grubsza tak samo jak w wektorze.
pzdr
bartekltg
Następne wpisy z tego wątku
- 28.03.13 20:18 M.M.
- 28.03.13 20:21 bartekltg
- 28.03.13 20:31 bartekltg
- 28.03.13 20:58 M.M.
- 28.03.13 21:50 Michoo
- 28.03.13 22:12 Michoo
- 28.03.13 23:55 bartekltg
- 29.03.13 11:41 firr kenobi
- 29.03.13 11:44 firr kenobi
- 29.03.13 12:21 M.M.
- 29.03.13 12:23 M.M.
- 29.03.13 13:07 firr kenobi
- 29.03.13 13:52 firr kenobi
- 29.03.13 15:33 M.M.
- 29.03.13 16:07 firr kenobi
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 przegląd za mną
- 2025-03-15 Na co komu okna
- 2025-03-15 Mój elektryk
- 2025-03-15 Fejk muzyczny czy nie fejk
- 2025-03-15 China-Kraków => Senior PHP Symfony Developer <=
- 2025-03-15 Wrocław => Konsultant wdrożeniowy Comarch XL (Logistyka, WMS, Produk
- 2025-03-15 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2025-03-15 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+ experience) <=
- 2025-03-15 Warszawa => Java Full Stack Developer (Angular2+) <=
- 2025-03-15 KOMU w RP3 pasuje "Rumuńska łatwość gmerania w wyborach" i dlaczego nie PO-Trzaskanym?
- 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 <=