From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Artur Malabarba Newsgroups: gmane.emacs.devel Subject: Re: What to do for faster `remove-duplicates'? Date: Wed, 6 May 2015 20:24:42 +0100 Message-ID: References: <87383atb2p.fsf@gmail.com> <873839ltoa.fsf@gmail.com> <87bnhxeh4j.fsf@gmail.com> <87lhh1zgyn.fsf@gmail.com> Reply-To: bruce.connor.am@gmail.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 X-Trace: ger.gmane.org 1430940304 4319 80.91.229.3 (6 May 2015 19:25:04 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 6 May 2015 19:25:04 +0000 (UTC) Cc: emacs-devel , Thierry Volpiatto To: Oleh Krehel Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 06 21:24:58 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 1Yq4wD-0000RB-3K for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 21:24:57 +0200 Original-Received: from localhost ([::1]:46863 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4wC-0005IT-FJ for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 15:24:56 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:49151) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4vz-0005IB-Ug for emacs-devel@gnu.org; Wed, 06 May 2015 15:24:44 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yq4vz-0002Rb-4I for emacs-devel@gnu.org; Wed, 06 May 2015 15:24:43 -0400 Original-Received: from mail-la0-x234.google.com ([2a00:1450:4010:c03::234]:35729) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq4vy-0002RP-Rt for emacs-devel@gnu.org; Wed, 06 May 2015 15:24:43 -0400 Original-Received: by labbd9 with SMTP id bd9so14918909lab.2 for ; Wed, 06 May 2015 12:24:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:reply-to:sender:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=ElX5pJ9HOPJRXuVT+NQr6HqLQlMR9/UboH6iVHn6zzk=; b=KIXAKooqiXNXv2a8j0pCTWxkR6iJNVeVgAxMAAEw+JVaRByp7VEs2qvdD0wMylKT0u owjKvFHbxRTkY4veSDL1SA9KYyZxxtZ2fG2/EUBBCJbBbuzm51499draIh2iWXsr676D Xh9Y6h/JAWKeHDm4mGoXMkwVpD8H6+W8oiWvbHQpjLRAMCc36yaVhq/RXXyOmyzfWvc4 cmCDhVI6OGSdoqFh1yZn4VSn+x31LJJoa1Btgdlxogi0tAGhXRAMUHCw1Knno2lEHmO0 5CKZNEPH1DgaVDcFkxXefRYdZgyfrN4I18Zmp70dCu6RNawDMdO83mofRqedJUIMdQMi 2n5w== X-Received: by 10.152.7.239 with SMTP id m15mr167162laa.95.1430940282110; Wed, 06 May 2015 12:24:42 -0700 (PDT) Original-Received: by 10.25.150.1 with HTTP; Wed, 6 May 2015 12:24:42 -0700 (PDT) In-Reply-To: <87lhh1zgyn.fsf@gmail.com> X-Google-Sender-Auth: Nym34cBRMG1qMfDpwxf9L3X4hF4 X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:4010:c03::234 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:186298 Archived-At: 2015-05-06 19:41 GMT+01:00 Oleh Krehel : > 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) I may be wrong, but it looks like it's completely skipping the car of the list.