From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Oleh Krehel Newsgroups: gmane.emacs.devel Subject: Re: What to do for faster `remove-duplicates'? Date: Wed, 06 May 2015 20:41:36 +0200 Message-ID: <87lhh1zgyn.fsf@gmail.com> References: <87383atb2p.fsf@gmail.com> <873839ltoa.fsf@gmail.com> <87bnhxeh4j.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1430938092 32217 80.91.229.3 (6 May 2015 18:48:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 6 May 2015 18:48:12 +0000 (UTC) Cc: emacs-devel , Thierry Volpiatto To: Artur Malabarba Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 06 20:48:05 2015 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Yq4MW-00029L-Pe for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 20:48:04 +0200 Original-Received: from localhost ([::1]:46749 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4MV-0002VE-Ut for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 14:48:03 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:40802) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4MF-0002Tr-F2 for emacs-devel@gnu.org; Wed, 06 May 2015 14:47:52 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yq4MC-0003Ho-8y for emacs-devel@gnu.org; Wed, 06 May 2015 14:47:47 -0400 Original-Received: from mail-wg0-x22e.google.com ([2a00:1450:400c:c00::22e]:34491) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4MC-0003HT-29 for emacs-devel@gnu.org; Wed, 06 May 2015 14:47:44 -0400 Original-Received: by wgso17 with SMTP id o17so21393275wgs.1 for ; Wed, 06 May 2015 11:47:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=OHKcD8dWVmUCCUvhGTkSY5VwgqJgWnPH4A9JpC0S6ME=; b=foVwDiIfeC8LWrHmwvibtxoe33sc7Y6RpDrFO9dP2CUcXIxfSlcPn7L5jfoEYKG+mn AKfcLhdrAPkNPEwXZR1mfF2pSG9gvcII3g74INJ6soNVmLYPSyhs0u81sdITU5KcRMF4 Xohws2gtjYbTbUqCEbMP5o7xFjlOs701kwf7qqSS5/v4h83hnSQUuZrF8VwJnO2f7P+j RoYFiCWfD31FUI9tLzroS9veLaiO22M9WlcL4btBLdZ1Igj+IHqZxRVoTaqNOY6rJWgz xhnarzksm69eAK21q8C2FjJsJpkrSAMR+PkgP5yCw4mzdXDR0u335y9Pde5nATIvv3HR e8lg== X-Received: by 10.180.231.4 with SMTP id tc4mr7656775wic.27.1430938063382; Wed, 06 May 2015 11:47:43 -0700 (PDT) Original-Received: from firefly (dyn069045.nbw.tue.nl. [131.155.69.45]) by mx.google.com with ESMTPSA id k2sm21780wix.4.2015.05.06.11.47.42 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Wed, 06 May 2015 11:47:42 -0700 (PDT) In-Reply-To: (Artur Malabarba's message of "Wed, 6 May 2015 19:33:07 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.5 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c00::22e X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:186296 Archived-At: Artur Malabarba writes: > But that nreverse could be optimized out if the first loop followed a > `while'+`setcdr' strategy like the second. Please check the optimized version: (defun delete-dups (list) "Destructively remove `equal' duplicates from LIST. Store the result in LIST and return it. LIST must be a proper list. Of several `equal' occurrences of an element in LIST, the first one is kept." (if (> (length list) 100) (let ((hash (make-hash-table :test #'equal))) (let ((tail list) elt retail) (while (setq retail (cdr tail)) (setq elt (car retail)) (if (gethash elt hash) (setcdr tail (cdr retail)) (puthash elt t hash)) (setq tail retail)))) (let ((tail list)) (while tail (setcdr tail (delete (car tail) (cdr tail))) (setq tail (cdr tail))))) list) Oleh