Article View: pl.comp.lang.c
Article #308449Re: kiedy używać listy, a kiedy wektora?
From: M.M.
Date: Mon, 18 Apr 2016 21:50
Date: Mon, 18 Apr 2016 21:50
18 lines
2153 bytes
2153 bytes
On Monday, April 18, 2016 at 10:16:40 PM UTC+2, Wiktor S. wrote: > > Główną wadą wektora jest to, że usuwanie elementu zachodzi w > > pesymistycznym czasie N, a nawet w średnim 0.5*N. > > I taką samą wadę ma lista podczas iterowania, więc jeśli chcesz z listy > usunąć N-ty element nie mając ustawionego nań iteratora, usuwanie elementu > będzie tak samo powolne jak w wektorze, bo trzeba będzie najpierw do > elementu dojechać. Jeśli przed usunięciem musimy wyszukać liniowo, to w obu strukturach wyszukujemy w średnim czasie 0.5*N, następnie w liście usuwamy w czasie stałym, a w wektorze w średnim czasie 0.5*N - więc i tu i tu czas liniowy, ale w liście 2 razy mniej operacji. Niestety w trakcie przeszukiwania listy nie zawsze działa cache, więc w praktyce w tym teście lista może być wolniejsza pomimo że wykonuje się na niej dwa razy mniej operacji. Pozdrawiam
Technical Details
Message-ID:
<aa6b8165-55dd-43a6-98bc-2a53b937f13e@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!fu-berlin.de!10no5053727qgg.1!news-out.google.com!u9ni382igk.0!nntp.google.com!g8no3837014igr.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mailReferences:
<117f9b9b-d150-440d-bee6-60eab4b1f360@googlegroups.com> <nf3fb5$stu$1@usenet.news.interia.pl>Show Full Headers
Complete Article Headers
X-Received: by 10.13.235.197 with SMTP id u188mr25404879ywe.4.1461016206786; Mon, 18 Apr 2016 14:50:06 -0700 (PDT) X-Received: by 10.50.60.164 with SMTP id i4mr366859igr.0.1461016206746; Mon, 18 Apr 2016 14:50:06 -0700 (PDT) Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!fu-berlin.de!10no5053727qgg.1!news-out.google.com!u9ni382igk.0!nntp.google.com!g8no3837014igr.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: pl.comp.lang.c Date: Mon, 18 Apr 2016 14:50:06 -0700 (PDT) In-Reply-To: <nf3fb5$stu$1@usenet.news.interia.pl> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.37.232.66; posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj NNTP-Posting-Host: 178.37.232.66 References: <117f9b9b-d150-440d-bee6-60eab4b1f360@googlegroups.com> <nf3fb5$stu$1@usenet.news.interia.pl> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <aa6b8165-55dd-43a6-98bc-2a53b937f13e@googlegroups.com> Subject: Re: kiedy używać listy, a kiedy wektora? From: "M.M." <mmarszik@gmail.com> Injection-Date: Mon, 18 Apr 2016 21:50:06 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit