Article View: pl.comp.lang.python
Article #27186Re: Python a hashmapa
From: wodzik
Date: Sat, 09 Jan 2010 20:45
Date: Sat, 09 Jan 2010 20:45
18 lines
2023 bytes
2023 bytes
On 2010-01-09 13:03, Stachu 'Dozzie' K. wrote: >> czyli rozumiem, że operacje wstawiania - wyszukiwania mają złożoność >> obliczeniową równą 1? > > A widziałeś kiedyś strukturę spełniającą te kryteria? Z wyjątkiem > tablicy indeksowanej liczbami. Oczywiście że widziałem. Nazywa się to hashmapa. Działa to tak, że rezerwujemy sobie pamięć, a potem na podstawie jakiejś funkcji mieszającej określamy gdzie dany element powinien znajdować się w tablicy i tam go wstawiamy. Jeśli dla różnych obiektów mamy taki sam adres wyszukujemy mu nowy, albo robimy listę w tym miejscu. Tyle z szkoły. Ale link który podał Rob Wolfe chyba wyjaśnia sprawę dostatecznie. Przy zastosowaniu słownika średnia złożoność pobrania elementu wynosi O(1). Teraz pozostaje mi tylko napisać funkcje która w jakiś sensowny sposób będzie tworzyła klucz na podstawie mojej klasy. Pozdrawiam wodzik
Technical Details
Message-ID:
<hiapsg$4mg$1@zeus.man.szczecin.pl>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.pionier.net.pl!news.man.szczecin.pl!not-for-mailReferences:
<hi9a48$c1b$1@zeus.man.szczecin.pl> <20100109102348.d563af8e.natural-born-killer@dontmailme.com> <hi9nmc$iqv$1@zeus.man.szczecin.pl> <hi9rbf$1ke$2@solani.org>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!newsfeed.gazeta.pl!newsfeed.pionier.net.pl!news.man.szczecin.pl!not-for-mail From: wodzik <wodzik@noreply.com> Newsgroups: pl.comp.lang.python Subject: Re: Python a hashmapa Date: Sat, 09 Jan 2010 21:45:12 +0100 Organization: ACI - http://www.aci.com.pl Lines: 18 Message-ID: <hiapsg$4mg$1@zeus.man.szczecin.pl> References: <hi9a48$c1b$1@zeus.man.szczecin.pl> <20100109102348.d563af8e.natural-born-killer@dontmailme.com> <hi9nmc$iqv$1@zeus.man.szczecin.pl> <hi9rbf$1ke$2@solani.org> NNTP-Posting-Host: 212.14.0.154 Mime-Version: 1.0 X-Trace: zeus.man.szczecin.pl 1263069905 4816 212.14.0.154 (9 Jan 2010 20:45:05 GMT) X-Complaints-To: usenet@news.man.szczecin.pl NNTP-Posting-Date: Sat, 9 Jan 2010 20:45:05 +0000 (UTC) User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.5) Gecko/20091204 Thunderbird/3.0 In-Reply-To: <hi9rbf$1ke$2@solani.org> X-Antivirus: avast! (VPS 100109-0, 2010-01-09), Outbound message X-Antivirus-Status: Clean Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit