From debbugs-submit-bounces@debbugs.gnu.org Wed Jan 06 16:00:09 2021 Received: (at 45570) by debbugs.gnu.org; 6 Jan 2021 21:00:09 +0000 Received: from localhost ([127.0.0.1]:45728 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxFub-0003EX-6m for submit@debbugs.gnu.org; Wed, 06 Jan 2021 16:00:09 -0500 Received: from mailrelay.tugraz.at ([129.27.2.202]:38643) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1kxFuY-0003DN-Tt for 45570@debbugs.gnu.org; Wed, 06 Jan 2021 16:00:07 -0500 Received: from nijino.local (217-149-174-13.nat.highway.telekom.at [217.149.174.13]) by mailrelay.tugraz.at (Postfix) with ESMTPSA id 4DB1w41KLYz1LLyW; Wed, 6 Jan 2021 22:00:03 +0100 (CET) DKIM-Filter: OpenDKIM Filter v2.11.0 mailrelay.tugraz.at 4DB1w41KLYz1LLyW DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=tugraz.at; s=mailrelay; t=1609966804; bh=jd3gON0HPwX1p7XCwPPufT/Tgx4jwLi2L3nn+J2Y3mY=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=J6N+D9CoLPkG5fS4vh2LCMraDZOrmGPdkudzq6IFU24t2LLOWm6xuaLHM+gYvnkSX blTXYuyc48MW6QLz2fQbw87rfuut2CmXfPDUW5gBXe0SolzturwjfG3iYVg1vAkMD1 0N6V+xh2+41tYK76ou+sjLOSaxb9NleKGyCweHQo= Message-ID: Subject: Re: bug#45570: [PATCH] system: Assert, that user and group names are unique. From: Leo Prikler To: Ludovic =?ISO-8859-1?Q?Court=E8s?= Date: Wed, 06 Jan 2021 22:00:03 +0100 In-Reply-To: <87k0sqkx7p.fsf@gnu.org> References: <20210102055728.22594-1-leo.prikler@student.tugraz.at> <87v9cao0c8.fsf@gnu.org> <87k0sqkx7p.fsf@gnu.org> Content-Type: text/plain; charset="UTF-8" User-Agent: Evolution 3.34.2 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-TUG-Backscatter-control: bt4lQm5Tva3SBgCuw0EnZw X-Spam-Scanner: SpamAssassin 3.003001 X-Spam-Score-relay: -1.9 X-Scanned-By: MIMEDefang 2.74 on 129.27.10.116 X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 45570 Cc: 45570@debbugs.gnu.org, conjaroy@gmail.com X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Hi, Am Mittwoch, den 06.01.2021, 14:32 +0100 schrieb Ludovic Courtès: > Hi, > > Leo Prikler skribis: > > > > > + ((first . rest) > > > > + (if (member first rest =) ; (srfi srfi-1) member > > > > + (cons first (find-duplicates rest =)) > > > > + (find-duplicates rest =))))) > > > > > > Note that this is quadratic; it’s fine as long as we don’t have > > > “too > > > many” users, which may be the case in general. > > It is indeed quadratic, but would there even be an n log n > > solution? > > I've once done an n log n sort+delete-duplicates!, perhaps that'd > > be a > > nicer solution here? > > You could first build a hash table or vhash or set with all the > names, > then traverse again the list of names and check whether they’re in > that > table. That’d be linear (assuming the table is well balanced), but > the > constant factor would be higher. Yeah, I think the hash table solution would make the most sense here. Since VHashes are based on VLists, they're not actually purely functional, are they? > > > (define (assert-unique-account-names users) > > > (match (find-duplicates things …) > > > (() #t) > > > (lst > > > (raise (formatted-message (G_ "the following accounts > > > appear > > > more than once:~{ ~a~}~%" > > > lst)))))) > > > > > > ? > > That'd be weird for duplicate duplicates, hence just reporting the > > first. > > You could do (delete-duplicates lst) in the message above? Sure, but that'd be O(n^2) on top of O(n^2), which is less than ideal. I think I'll try working on a hash-based implementation for now. Regards, Leo