From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: "A. Soare" Newsgroups: gmane.emacs.devel Subject: Re: van Emde Boas hash. Date: Fri, 20 Nov 2009 07:41:15 +0100 (CET) Message-ID: <24670838.273241258699275844.JavaMail.www@wwinf4616> Reply-To: alinsoar@voila.fr NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1258699511 29192 80.91.229.12 (20 Nov 2009 06:45:11 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 20 Nov 2009 06:45:11 +0000 (UTC) Cc: Stefan Monnier , "Emacs Dev \[emacs-devel\]" To: Deniz Dogan Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Nov 20 07:45:03 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NBNEs-0004ku-Ax for ged-emacs-devel@m.gmane.org; Fri, 20 Nov 2009 07:45:02 +0100 Original-Received: from localhost ([127.0.0.1]:41116 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NBNEr-0008FL-RX for ged-emacs-devel@m.gmane.org; Fri, 20 Nov 2009 01:45:01 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NBNBJ-0006ko-0z for emacs-devel@gnu.org; Fri, 20 Nov 2009 01:41:21 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NBNBG-0006jo-1S for emacs-devel@gnu.org; Fri, 20 Nov 2009 01:41:20 -0500 Original-Received: from [199.232.76.173] (port=54012 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NBNBF-0006jk-FF for emacs-devel@gnu.org; Fri, 20 Nov 2009 01:41:17 -0500 Original-Received: from smtp3.voila.fr ([193.252.22.173]:13026 helo=smtp1.voila.fr) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1NBNBE-0001Aq-TN for emacs-devel@gnu.org; Fri, 20 Nov 2009 01:41:17 -0500 Original-Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf4928.voila.fr (SMTP Server) with ESMTP id EB19970000FD; Fri, 20 Nov 2009 07:41:15 +0100 (CET) Original-Received: from me-wanadoo.net (localhost [127.0.0.1]) by mwinf4928.voila.fr (SMTP Server) with ESMTP id DDEF37000173; Fri, 20 Nov 2009 07:41:15 +0100 (CET) Original-Received: from wwinf4616 (wwinf4616 [10.232.13.60]) by mwinf4928.voila.fr (SMTP Server) with ESMTP id CFC9470000FD; Fri, 20 Nov 2009 07:41:15 +0100 (CET) X-ME-UUID: 20091120064115851.CFC9470000FD@mwinf4928.voila.fr X-Originating-IP: [91.201.80.240] X-Wum-Nature: EMAIL-NATURE X-WUM-FROM: |~| X-WUM-TO: |~| X-WUM-CC: |~||~| X-WUM-REPLYTO: |~| X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:117326 Archived-At: Van Emde Boas arrays are hashed arrays (of numbers for example), which have= the property that all operations are realized into a constant number of st= eps. For example, for an array of length 2^32, the complexity is O(0), and the n= umber of steps is less than log_2 (32) =3D "maximum 5 steps" for every oper= ation. The operations are: * insert a new number * delete a number * seek for a number * find the successor of a number * find the predecessor of a number ____________________________________________________ Gagnez un s=C3=A9jour au Maroc=C2=A0en d=C3=A9couvrant les sketchs d=C3=A9s= opilants des ReVoila sur http://www.lesrevoila.fr/