From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Joel Reicher Newsgroups: gmane.emacs.help Subject: Re: Which Elisp data structure is fastest for searching? Date: Thu, 26 Dec 2024 17:24:54 +1100 Message-ID: <86wmfnc66h.fsf@gmail.com> References: Mime-Version: 1.0 Content-Type: text/plain; format=flowed Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="6587"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Help GNU Emacs To: Jean Louis Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Thu Dec 26 07:25:26 2024 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1tQhJG-0001ZV-Tm for geh-help-gnu-emacs@m.gmane-mx.org; Thu, 26 Dec 2024 07:25:26 +0100 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1tQhIw-0007y2-Dw; Thu, 26 Dec 2024 01:25:06 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1tQhIs-0007xh-VM for help-gnu-emacs@gnu.org; Thu, 26 Dec 2024 01:25:02 -0500 Original-Received: from mail-pj1-x1036.google.com ([2607:f8b0:4864:20::1036]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1tQhIr-00050h-GD for help-gnu-emacs@gnu.org; Thu, 26 Dec 2024 01:25:02 -0500 Original-Received: by mail-pj1-x1036.google.com with SMTP id 98e67ed59e1d1-2ef6c56032eso5156160a91.2 for ; Wed, 25 Dec 2024 22:25:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1735194299; x=1735799099; darn=gnu.org; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=csEBnZYE/NWBqqtgb+oIYzepu6vSg9qGOMffT40tVec=; b=QGn37GFfGcstQcV8DgjgvLoUmbUL4031j1b3fygzvaY0C90fCknXWwRtPznkMkKGXH ggAM+tuzM0ihChyQgLcgOTLtFwZj5Io4m2mnFcBIz7ha0aXlFnvxyTPwxY8IEcNosoEO a/j4tAsoUnFCbSDpcc66CvpoxwZ6mKujdyJAF3hIhZRfVnahjxQRLrWufp055HoPxUyB mkeXVGSVWzhRYzsrqsLxq6eTs5uCS+cm1OCD+gn6Mtyqki1Mjkh2rGyNY0NidNAZm0km OHMr894meoBKNchLlylh19IJgKKTqr0sKlhpgTRBdG2FEuFPBUBKrf1QzD/8nhsyhZc0 MHyg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1735194299; x=1735799099; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=csEBnZYE/NWBqqtgb+oIYzepu6vSg9qGOMffT40tVec=; b=YPEk8kjcC7Kw6K8WCU/CXvlIIq0gh+hizb4/7WvEDuI14/dnmoeIwBF/DzC3AHH7Si Gg5tYGvYGjU/hhl+1CQeOdM2q0/i281onbmuegBah4+WGhnTb9JzeBbomscwGxkImCt6 +oe2pl2sdC4q7UXxm5nMSyJSBYMAl/c+maEcFlGxtxKU+v6eVzW4JNLX1Dx4KeNkgtxz ePNMby9xWaWhkOnhNUkAW8F+/p28DnEXsFtsm9aUlZBH8DSYAP792aA7cqmubmrRuC+K 59f/7VqTFSQY0YiXnJFQs7Togmjv7ZJaT64Rzcgj2zhVCfJZvLf6tf7Z/qsAk9GuqZCs qMhQ== X-Gm-Message-State: AOJu0YzVFtysuID4l02j+Wz433HNi3oA4r9X9CbDbhTvjqBt3TySDK5S PP1W6dVFFShus4JJC9DrGEP2GwbaEvA4kS2YkMBXRdLWVZ8PE8oZxWOyiw== X-Gm-Gg: ASbGncuxAi/kf2i3y/uoGp3iPA1JjjXflpm46r70U/vmrqQLYc9WNmNUJpTP2bDGpHk fuRtY0cPmjCnoPLhVN1p7YjGdYpHODj1bjnqwetbypDTEwM/plXIIuSxQG0zgL23k/oJxiyZ3wR YWTs9g36Gqv5GwSRcEoIl4ioAwEGg/KkjKr/85bW4xIvKdcSiIZm/ZCvNTb4Cklejz6rRda6vXR gX9e7/D5ay3L94HrcHHDzcJHPVwQMx3LtRi2DhZIYgDXiHQpTnySsGqveHMiZGy0F9UR8++GYYo f19F2dXKDKN2tJvIJibDgWXmO1iN3+kPcubo5+LF2eTa X-Google-Smtp-Source: AGHT+IFeKvHvwNvfUBM2r3f91aPiloQoRLrNdRX+w371IBNxYMxLLdUCAlHLHiNbf4gbPmEz5JHCCw== X-Received: by 2002:a17:90b:538b:b0:2ee:5bc9:75b5 with SMTP id 98e67ed59e1d1-2f452dfccf6mr32462309a91.4.1735194299524; Wed, 25 Dec 2024 22:24:59 -0800 (PST) Original-Received: from LAPTOP-ACR66VVN (139-218-25-158.sta.wbroadband.net.au. [139.218.25.158]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-219dca025d1sm113087245ad.254.2024.12.25.22.24.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 25 Dec 2024 22:24:59 -0800 (PST) In-Reply-To: (Jean Louis's message of "Wed, 25 Dec 2024 12:33:08 +0300") Received-SPF: pass client-ip=2607:f8b0:4864:20::1036; envelope-from=joel.reicher@gmail.com; helo=mail-pj1-x1036.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.help:148985 Archived-At: Jean Louis writes: [...] > A hash table is a very fast kind of lookup table, somewhat like > an alist (*note Association Lists::) in that it maps keys to > corresponding values. > > The above is not so conclusive and I have not done measurements. > > It says "somewhat like an alist", but is the alist faster in > searching through elements or the hash table? It depends on the kind of search you are doing. As an extreme example, imagine your search was not based on the hash table key; you might have to go through every entry in the table to find what you're looking for. This is why different data structures exist. There is no "best"; only "best for..." Regards, - Joel