From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0 ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id GI/cNbvYVWHNiQAAgWs5BA (envelope-from ) for ; Thu, 30 Sep 2021 17:33:15 +0200 Received: from aspmx1.migadu.com ([2001:41d0:8:6d80::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0 with LMTPS id CMyQMbvYVWHFXgAA1q6Kng (envelope-from ) for ; Thu, 30 Sep 2021 15:33:15 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id F023123FD2 for ; Thu, 30 Sep 2021 17:33:14 +0200 (CEST) Received: from localhost ([::1]:43458 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mVy3d-0007TB-HG for larch@yhetil.org; Thu, 30 Sep 2021 11:33:13 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:34576) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mVxpw-0002bL-Nw for guix-patches@gnu.org; Thu, 30 Sep 2021 11:19:04 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:42155) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mVxpv-0000tl-4L for guix-patches@gnu.org; Thu, 30 Sep 2021 11:19:03 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mVxpv-00035v-2I for guix-patches@gnu.org; Thu, 30 Sep 2021 11:19:03 -0400 X-Loop: help-debbugs@gnu.org Subject: [bug#50878] [PATCH] union: Resolve collisions by stable-sort'ing them. Resent-From: Maxime Devos Original-Sender: "Debbugs-submit" Resent-CC: guix-patches@gnu.org Resent-Date: Thu, 30 Sep 2021 15:19:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 50878 X-GNU-PR-Package: guix-patches X-GNU-PR-Keywords: patch To: Attila Lendvai Cc: Liliana Marie Prikler , 50878@debbugs.gnu.org Received: via spool by 50878-submit@debbugs.gnu.org id=B50878.163301509511794 (code B ref 50878); Thu, 30 Sep 2021 15:19:03 +0000 Received: (at 50878) by debbugs.gnu.org; 30 Sep 2021 15:18:15 +0000 Received: from localhost ([127.0.0.1]:53697 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mVxp9-00034A-8S for submit@debbugs.gnu.org; Thu, 30 Sep 2021 11:18:15 -0400 Received: from laurent.telenet-ops.be ([195.130.137.89]:43168) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mVxp5-00033v-Nt for 50878@debbugs.gnu.org; Thu, 30 Sep 2021 11:18:13 -0400 Received: from ptr-bvsjgyjmffd7q9timvx.18120a2.ip6.access.telenet.be ([IPv6:2a02:1811:8c09:9d00:aaf1:9810:a0b8:a55d]) by laurent.telenet-ops.be with bizsmtp id 0FJ72600T0mfAB401FJ71K; Thu, 30 Sep 2021 17:18:08 +0200 Message-ID: <57b644a0b8accceed5d390cd82b2f69d427c464d.camel@telenet.be> From: Maxime Devos Date: Thu, 30 Sep 2021 17:18:01 +0200 In-Reply-To: References: <20210928214044.437-1-attila@lendvai.name> <57f1435fd83da8c0e0acaef64d5f08e4ca7b3404.camel@gmail.com> <9ab183637e8cd645267a37ba0f05319f8b3c72ff.camel@telenet.be> Content-Type: multipart/signed; micalg="pgp-sha512"; protocol="application/pgp-signature"; boundary="=-Tb+QToDZe9NWCxyVSq+H" User-Agent: Evolution 3.34.2 MIME-Version: 1.0 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=telenet.be; s=r21; t=1633015088; bh=7cEcr6W7Xkd82MyN3gwMKBA8g7Bs/FzS1HoC3O3T18M=; h=Subject:From:To:Cc:Date:In-Reply-To:References; b=roaJpoY0OsyHSNhN/cNP7ATgflN1zZn9y+Zs3IkAzOvyBZKnK88eixQe9zT8LhRpn ywmwzccU/Lq/WKxUyNXjU0zw37s8B4+lx+Uf984uKiuK3WUPZ63NJQMii5B0jFInVA 9603TC4rtg4zv8xloSCPBCSMPfIO99krqhYfhZGX8t2vb9BZs14Jb+TvLW0hx9XErM OPsOPTtBiVCVW94djriN9rbyaSdq4l1lMhn1YWm5yYPUVuZUfojrD9c07xgkD2trpl 3TeMtFB7p2+xnxRq0ZjYFPYq7FRzdpp5Wqd50Om1CD6KAsTwMtKz3jwUIOl16pX4n2 gavEI3SWhV6Sw== X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: guix-patches@gnu.org List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+larch=yhetil.org@gnu.org Sender: "Guix-patches" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1633015995; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:resent-cc:resent-from:resent-sender: resent-message-id:in-reply-to:in-reply-to:references:references: list-id:list-help:list-unsubscribe:list-subscribe:list-post: dkim-signature; bh=7cEcr6W7Xkd82MyN3gwMKBA8g7Bs/FzS1HoC3O3T18M=; b=YbyvbgvxQBkiW8xVlqCrrBSiaEf4u23E7M8az471Pc+sCRxWFjtayoqtdC8L4FaypBu7Tc uVaQdw8nQz6gGPL0sDmJuLp4Qb3rmymB61iCzfPls9VRG/A3bBmn/w/N0OQgXkeozKjW3j IcPk0+3OqWgGD2VQBEI0RXmco3webJE1m/ZDQaYyGlxCRAd9AcHaf6+B42ZKkPp0IXO9ds H05VbN8o4Mt5sELvyv95sY5UNXMAKY4a/0odgYTjdwPp0PZv7tt9Hqzp6OOqhXbjge87zQ louwxQeQRd8vssUlF0x9shL/XfXjsQneiWonOd/M4w4ZgJGOJtV8uzciSN5kLQ== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1633015995; a=rsa-sha256; cv=none; b=JGuLuhdROVwlsmiNwSfvXzDHv2ADls+03d62y4AyO0sBD0SN/orN1emPxB1GBnJOxwOFXR WmsA7YV4tU8xa+S+G6VAlk+qT9ytCCSGW8O5vTQhvEQvoI3kQ5JcYJ+o4VeQ7/w2fPKM3a /ESp28HRRgmywcwLWRqsWFSuhECyKcL4rlrCp92natqGATtxjxAz0+bhM2zhD/c9QAadVJ xb9iFJxacj3NGjsmTNnwFYiG9Pii1icmiFGFFE0BFK7MEUX0WE//d/1wH/u/ftYr3vBnij p5uwAfEgcqOAbYo80E7eiRGWXHSFMkh5Ju5was7wBVIrUHmpUyynAcXlI5c4CA== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=telenet.be header.s=r21 header.b=roaJpoY0; dmarc=fail reason="SPF not aligned (relaxed)" header.from=telenet.be (policy=none); spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Spam-Score: -3.40 Authentication-Results: aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=telenet.be header.s=r21 header.b=roaJpoY0; dmarc=fail reason="SPF not aligned (relaxed)" header.from=telenet.be (policy=none); spf=pass (aspmx1.migadu.com: domain of guix-patches-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=guix-patches-bounces@gnu.org X-Migadu-Queue-Id: F023123FD2 X-Spam-Score: -3.40 X-Migadu-Scanner: scn0.migadu.com X-TUID: 08p9d9GFiJPu --=-Tb+QToDZe9NWCxyVSq+H Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Attila Lendvai schreef op do 30-09-2021 om 14:12 [+0000]: > > > the hash also needs to be dropped from the path for sorting to be > > > useful, but the return value must be the full path, hence the > > > complexity with sorting the indices, pointing both to the full paths > > > and the cut parts. > >=20 > > You can replace the 'less' argument of 'stable-sort'. > > Example sorting by the second character of a string: > >=20 > > (sort '("za" "yb" "xc") (lambda (x y) > > (char>? (string-ref x 1) > > (string-ref y 1))))) >=20 > i don't know about the expected size of the collision list here, but > that would cons much more, because that would cons up two substrings > at each comparison, i.e. O(n^2) vs O(n) at least in GC load, probably > in time also. I don't see any consing here, or any increase in complexity? > i think it's not worth it, but let me know, and then i can simplify > the code somewhat at the cost of more consing. >=20 > sorting lists is probably also much slower than sorting vectors, but > there may be some tricks i don't know about. I was suggesting replacing the 'less' procedure with a procedure like (lambda (x y) (char>? (string-ref x 1) (string-ref y 1))) instead of doing the sorting in two steps. I wasn't suggesting using lists. The '("za" "yb" "xc") was only for demonstration, a vector should work as well. Greetings, Maxime. --=-Tb+QToDZe9NWCxyVSq+H Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- iI0EABYKADUWIQTB8z7iDFKP233XAR9J4+4iGRcl7gUCYVXVKRccbWF4aW1lZGV2 b3NAdGVsZW5ldC5iZQAKCRBJ4+4iGRcl7rNpAPkBGWGqP2ymoSNiKlKJoulyD6Xg Q7oOtq5wD8Vl66WSBgD+Nv17xzGCSTdKpY0nRg+mxye2gatFPRikpgIwMdAZUg0= =8wo9 -----END PGP SIGNATURE----- --=-Tb+QToDZe9NWCxyVSq+H--