-
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
- 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??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-06-27 Re: Prywatny parking? Pierwsze 10 minut bezplatnie
- 2024-06-27 A co mnie to koooorwa obchodzi?
- 2024-06-28 nawigacja satelitarna
- 2024-06-28 SmartLife/Tuya i osuszanie -- mordowanie z zimną krwią...
- 2024-06-27 położyłem kafelki
- 2024-06-28 Łódź => International Freight Forwarder <=
- 2024-06-28 Łódź => Spedytor Międzynarodowy <=
- 2024-06-28 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-06-28 Sopot => Team Leader E-Commerce for Foreign Markets <=
- 2024-06-28 Warszawa => Senior React Native Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Software .Net Developer <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=
- 2024-06-28 Warszawa => Programista Full Stack .Net <=
- 2024-06-28 Warszawa => Frontend Developer (React) <=