From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 1083580211 for ; Mon, 2 Oct 2017 22:05:28 +0200 (CEST) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=chan.ngo2203@gmail.com; spf=Pass smtp.mailfrom=chan.ngo2203@gmail.com; spf=None smtp.helo=postmaster@mail-qt0-f173.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of chan.ngo2203@gmail.com) identity=pra; client-ip=209.85.216.173; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of chan.ngo2203@gmail.com designates 209.85.216.173 as permitted sender) identity=mailfrom; client-ip=209.85.216.173; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qt0-f173.google.com) identity=helo; client-ip=209.85.216.173; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="postmaster@mail-qt0-f173.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AVR/f4xY+W8mKzeSMQ1o54S3/LSx+4OfEezUN459i?= =?us-ascii?q?sYplN5qZpcy9bnLW6fgltlLVR4KTs6sC0LWG9f24EUU7or+/81k6OKRWUBEEjc?= =?us-ascii?q?hE1ycBO+WiTXPBEfjxciYhF95DXlI2t1uyMExSBdqsLwaK+i76xXcoFx7+LQt4?= =?us-ascii?q?IPjuUs6X1pzvlrP6x5qGSAVShSGhZqtyIV2MpAvfv80SgMM2IaYrywDVpWNIds?= =?us-ascii?q?xMzG1mLFaXnlDx+5Hj0oRk9nFusvRp3M5JV+3ccKNwGbdYBTJgNW8yvpez7jHM?= =?us-ascii?q?SAKO4j0XVWBAwUkAOBTM8ByvBsS5iSD9rOconXDCZcA=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AjAgB+m9JZf63YVdFcHQEFAQsBFwEBB?= =?us-ascii?q?AEBCgEBhQQnB4NygTaYTYF2iTOEQIpLCoU7AoQ6B0IVAQEBAQEBAQEBAQESAQE?= =?us-ascii?q?JCwsIJjGCMwUBHgEFgjsBAQEBAgEjHQEbEAoDAQMBCwYDAgQHNwICIgERAQUBH?= =?us-ascii?q?AYTCIoPAQMNCIddkRtAjAyCBQUBHIMKBYNpChknDVeDDQEBAQEBAQQBAQEBARs?= =?us-ascii?q?CBhKDG4IChmOIF4JhBYEtAQEBiGiXEAgBAYFWkw+EBY8ElUAUBR+BFTVkTFMlX?= =?us-ascii?q?hpchBWCLiQ2h3CBVAEBAQ?= X-IPAS-Result: =?us-ascii?q?A0AjAgB+m9JZf63YVdFcHQEFAQsBFwEBBAEBCgEBhQQnB4N?= =?us-ascii?q?ygTaYTYF2iTOEQIpLCoU7AoQ6B0IVAQEBAQEBAQEBAQESAQEJCwsIJjGCMwUBH?= =?us-ascii?q?gEFgjsBAQEBAgEjHQEbEAoDAQMBCwYDAgQHNwICIgERAQUBHAYTCIoPAQMNCId?= =?us-ascii?q?dkRtAjAyCBQUBHIMKBYNpChknDVeDDQEBAQEBAQQBAQEBARsCBhKDG4IChmOIF?= =?us-ascii?q?4JhBYEtAQEBiGiXEAgBAYFWkw+EBY8ElUAUBR+BFTVkTFMlXhpchBWCLiQ2h3C?= =?us-ascii?q?BVAEBAQ?= X-IronPort-AV: E=Sophos;i="5.42,470,1500933600"; d="scan'208,217";a="293819799" Received: from mail-qt0-f173.google.com ([209.85.216.173]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 02 Oct 2017 22:05:27 +0200 Received: by mail-qt0-f173.google.com with SMTP id o3so9131582qte.6 for ; Mon, 02 Oct 2017 13:05:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=8cPYKyd0R2eYTys6dMxKMtGS9d3cC+ImZiN+FmidYNk=; b=ehFZJIrHGZrfRq2dWk/x/ykWmTH/m1aJG7wgPvrZgmoAA6Z3K8er6UtoA+6QVBYidu stqAbSkufZ0zc/mwvWnXubU5ZOn5cgoyNM1kdRV2lIVqs6Xmwaf/q1dN3cQpRAGu9ThE 8i1MaAVSMG4SjNPahzZJSmytcdVQeqOHIhyq56PnbRYwA7hdkoCp/3Usv21wujECyamu uZ7O1Oj7YiDssk0Q/M7z8ArUkbpLOJpRL3mjXJ6kLQJ7VvzTUJ8cD7lzZ/b/4u6shyXM gFfCxTFMKE2wN/RLv4IkIrPYpS/bLQCoDgewZprw22x1egt4akBoiewwScEPGr+1hc23 PXKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=8cPYKyd0R2eYTys6dMxKMtGS9d3cC+ImZiN+FmidYNk=; b=FTUOUcsp14B3GdXCog1FpF95zU5V4nklVfuJrDTW5KRmJFXLZNZ+c+zA0cZFn5F1Cs Vqn+dFPWCysZozkoJYG1RseepT/o2Se5zo1GhTPv5oXfQkBkdUHx9e6xowkIKSwhCUig /G/sKKMHjNCk8SBwwNEx+kf5fz1VwR0fCJaXkADIzk91VYZ6d2FUDUsiJsp/30VcgUBF OS4wnlrPZ/g9xeLlFAUApXXFbhqfy0sKL8VoKUcAjwYjxHsVKpvTM9y5q+Mu6K0T3/5A n5gspcfTT/YP0+N3TEJRedGPK7CAoKkxCaSSKxD8QrNNhTFY0WgV5v8hKyd6Jbs8r3X0 ynAg== X-Gm-Message-State: AMCzsaV4h+iNVTRXiztAnUKSM12uDgBLtURrmpbo83WEyWuRXjH6A6Ey RMP6Syg9B7MRYMH0QUY/NVnyHIw2t8Rfe5EdPA== X-Google-Smtp-Source: AOwi7QBG9hsz8lBrTOJxByB+4KZwhSVmwXlID5RINxI9TtfgrfWbf6UkoIu7eYs6kFS0fBJ19bnjsv6O+Y7Qy1bq4ak= X-Received: by 10.200.8.166 with SMTP id v35mr21262120qth.306.1506974726086; Mon, 02 Oct 2017 13:05:26 -0700 (PDT) MIME-Version: 1.0 Received: by 10.237.54.228 with HTTP; Mon, 2 Oct 2017 13:05:25 -0700 (PDT) In-Reply-To: <20171002041115.x3g63rnyg53m7dor@delli7.univ-savoie.fr> References: <20171002041115.x3g63rnyg53m7dor@delli7.univ-savoie.fr> From: Van Chan Ngo Date: Mon, 2 Oct 2017 16:05:25 -0400 Message-ID: To: Christophe Raffalli Cc: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary="001a11c148da3be3ea055a95e50d" Subject: Re: [Caml-list] An interesting sorting algorithm for list --001a11c148da3be3ea055a95e50d Content-Type: text/plain; charset="UTF-8" Hi, It sounds interesting. However, I suppose they have the same worst-case complexity O(nlogn). Could we formally have the average complexity? Best, -Van Chan On Mon, Oct 2, 2017 at 12:11 AM, Christophe Raffalli wrote: > Hello, > > Here is an algorithm I found nice to sort lists. It is in O(n ln(k)) > where n is the size and k the number of changes of direction in the list. > > for [ 1; 5; 10; 15; 20; 10; 2; 3; 5; 7], k = 3. > > This implementation is a stable sort. > > It is "almost" as fast as List.sort in the bad cases (Random lists) > (when k ~ n) and can be much faster if k is small as expected... > > A challenge: find a similar algorithm, for lists, that is always > faster than List.sort ... I have tried a lot and I was always 5% slower > on the bas cases ... (Try to remain stable) > > Enjoy, > Christophe > > PS: the benchmark: > > Correctness test passed > Stability test passed > Random lists: > random: tf = 1.53, tg = 1.56, factor = 0.98x, gain = -2.33% > random small: tf = 1.37, tg = 1.44, factor = 0.95x, gain = -4.88% > Worst cases: > worst1: tf = 1.31, tg = 1.38, factor = 0.95x, gain = -5.18% > worst2: tf = 1.32, tg = 1.36, factor = 0.98x, gain = -2.49% > Sorted (partially) lists: > sorted: tf = 1.28, tg = 0.01, factor = 97.21x, gain = 98.97% > reversed: tf = 1.31, tg = 0.17, factor = 7.76x, gain = 87.11% > sorted@rev: tf = 1.33, tg = 0.37, factor = 3.60x, gain = 72.23% > rev@sorted: tf = 1.30, tg = 0.38, factor = 3.44x, gain = 70.94% > Shuffled lists (permute k times 2 elements in a sorted list): > shuffle 10: tf = 1.35, tg = 0.80, factor = 1.68x, gain = 40.64% > shuffle 100: tf = 1.36, tg = 1.07, factor = 1.27x, gain = 21.56% > shuffle 1000: tf = 1.38, tg = 1.20, factor = 1.15x, gain = 13.17% > shuffle 10000: tf = 1.41, tg = 1.25, factor = 1.13x, gain = 11.45% > --001a11c148da3be3ea055a95e50d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi,

It sounds interesting. However, I s= uppose they have the same worst-case complexity O(nlogn).
Could w= e formally have the average complexity?

Best,
-Van Chan


On Mon, Oct 2, 2017 at 12:11 AM, Christophe Raffal= li <christophe@raffalli.eu> wrote:
Hello,

Here is an algorithm I found nice to sort lists.=C2=A0 It is in O(n ln(k))<= br> where n is the size and k the number of changes of direction in the list.
for [ 1; 5; 10; 15; 20; 10; 2; 3; 5; 7], k =3D 3.

This implementation is a stable sort.

It is "almost" as fast as List.sort in the bad cases (Random list= s)
(when k ~ n) and can be much faster if k is small as expected...

A challenge: find a similar algorithm, for lists, that is always
faster than List.sort ... I have tried a lot and I was always 5% slower
on the bas cases ... (Try to remain stable)

Enjoy,
Christophe

PS: the benchmark:

Correctness test passed
Stability test passed
Random lists:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 random: tf =3D 1.53, tg =3D 1.56, factor= =3D 0.98x, gain =3D -2.33%
=C2=A0 =C2=A0 random small: tf =3D 1.37, tg =3D 1.44, factor =3D 0.95x, gai= n =3D -4.88%
Worst cases:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 worst1: tf =3D 1.31, tg =3D 1.38, factor= =3D 0.95x, gain =3D -5.18%
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 worst2: tf =3D 1.32, tg =3D 1.36, factor= =3D 0.98x, gain =3D -2.49%
Sorted (partially) lists:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 sorted: tf =3D 1.28, tg =3D 0.01, factor= =3D 97.21x, gain =3D 98.97%
=C2=A0 =C2=A0 =C2=A0 =C2=A0 reversed: tf =3D 1.31, tg =3D 0.17, factor =3D = 7.76x, gain =3D 87.11%
=C2=A0 =C2=A0 =C2=A0 sorted@rev: tf =3D 1.33, tg =3D 0.37, factor =3D 3.60x= , gain =3D 72.23%
=C2=A0 =C2=A0 =C2=A0 rev@sorted: tf =3D 1.30, tg =3D 0.38, factor =3D 3.44x= , gain =3D 70.94%
Shuffled lists (permute k times 2 elements in a sorted list):
=C2=A0 =C2=A0 =C2=A0 shuffle 10: tf =3D 1.35, tg =3D 0.80, factor =3D 1.68x= , gain =3D 40.64%
=C2=A0 =C2=A0 =C2=A0shuffle 100: tf =3D 1.36, tg =3D 1.07, factor =3D 1.27x= , gain =3D 21.56%
=C2=A0 =C2=A0 shuffle 1000: tf =3D 1.38, tg =3D 1.20, factor =3D 1.15x, gai= n =3D 13.17%
=C2=A0 =C2=A0shuffle 10000: tf =3D 1.41, tg =3D 1.25, factor =3D 1.13x, gai= n =3D 11.45%

--001a11c148da3be3ea055a95e50d--