220 38475 article Path: news.gmane.org!.POSTED!not-for-mail From: florian.csdt@gmail.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Adding Sorting with suffix subordering for suffix arrays Date: Mon, 4 Jun 2018 09:02:48 -0700 (PDT) Lines: 210 Approved: news@gmane.org Message-ID: References: <57aff230-b879-4205-9cc6-dc3382c7d580@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_33993_1036016547.1528128168356" X-Trace: blaine.gmane.org 1528128046 25442 195.159.176.226 (4 Jun 2018 16:00:46 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 16:00:46 +0000 (UTC) To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBC26HM4V3MIRBKOF2XMAKGQEVVUXOLI@isocpp.org Mon Jun 04 18:00:42 2018 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-yw0-f198.google.com ([209.85.161.198]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1fPruR-0006U7-3I for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 18:00:39 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id g5-v6sf2747992ywk.10 for ; Mon, 04 Jun 2018 09:02:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=6faKc5lOzFDwtgpAWALWcu2DqXLmUVm3STMzsGPr2bo=; b=ntOSL/9pCcmW95m4M8LRYpdxZzOdQlPHXuYhB/h5UkpSDZ0z6SFNoJMqPux30X12hW 2OzDWRy3Kxy66cdiTl4Pfg09LkqpNynNVe1XP2sw/5KsIIg10EKq/w4FIfHiBo7jPFud wYSMJH0OUwFkuQ9txm1fuBYIVk2pjayIuFVfqR6f7+JWehWqJUuJHbv9OTsdZkzriMVj ftSKVKW12g599dhIgiBh0CdFwvOVf/FJBdJxAiadoZwxV6bNRZ7aWyHC1TkKPNo2+B// a5qQey4BbazqiwzvUlVyzQ3yltkNMVTS0hjPbt+O+NYW6rk+Eyv2ThpxDgBT1KNhMYFo /FlQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=6faKc5lOzFDwtgpAWALWcu2DqXLmUVm3STMzsGPr2bo=; b=eDxPycwjc5GBL46yRc9cVGTjv32p+qrnMMajheN6TqWyLJUGVfycTnTx+pnZ/MtF10 H1fKMEY/MnzJWAcboJcAt98UnklYdXvvmLxOQQ2REfFH+CrgVfv9M5E7E5mh804/ZOfY DvOPN764MocGyX8Wb33aOXfCb18h50/NHFbpVhmTWNfY1nYtzF6PhO1vlbTl5mer89h5 VVlWgqaFyofRHooAeR3eZEgsZ8OQLqT7i8TvquGqjHitYhaVNHFc6MuNFLgmCsp3uPCi Ei/sDDqHqpF/uF1Yk1Sv0TeMyv3MF/EoojSA5ep+axCJfSq8CTr3U7qHkPsbSVxFS9EY 8GdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version:x-original-sender:reply-to:precedence :mailing-list:list-id:x-spam-checked-in-group:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=6faKc5lOzFDwtgpAWALWcu2DqXLmUVm3STMzsGPr2bo=; b=KPNY+eTWuq3Con28lu1jQzRhmLwIxj4XPdVzhfYnh0dU199jyKZBuCRqBuuESGF7fR kyCGvD6Ld3pllq5Tg4HoHn7AzyViU+lAK0J3mh5VRGF0GfWTbLpl1AkF49kfEba/ec+u 1QqREyOndo5+BUpuroXC2eifF9OZbrhibuyCJGRA4aBUP38AYupWXWjh0lL2fGu/UvEz 3Na14k+P17UQUE7uk18DIHbp6x7VXp6rJu64sGV1koUkbbdVO7VOAbqpuWUKkKY0tn5q 1wt9oG9nhsi4BezQ345ot457jvyC0APQW3Orl8NroVh8ExVK0QQHBJgAFtESlx89Lrz8 yq9w== X-Gm-Message-State: ALKqPwfoWXjUNS13+x6yVvj2iK1oW2HD2g2nNXB0cXeMqxPrd3Y1SOjs skS8HHm+Si6HUQJnmvvkTF8ofA== X-Google-Smtp-Source: ADUXVKIZx5ogvvKDkP0F+LrJ5egi+mmnI2RvI7pBtEquYrclAc10CH/jtzQSNC/4cYuAV8gBX/GAxA== X-Received: by 2002:a81:7012:: with SMTP id l18-v6mr5957202ywc.59.1528128169955; Mon, 04 Jun 2018 09:02:49 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a25:ba83:: with SMTP id s3-v6ls1024075ybg.15.gmail; Mon, 04 Jun 2018 09:02:49 -0700 (PDT) X-Received: by 2002:a25:d68d:: with SMTP id n135-v6mr984318ybg.6.1528128168846; Mon, 04 Jun 2018 09:02:48 -0700 (PDT) In-Reply-To: X-Original-Sender: florian.csdt@gmail.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Spam-Checked-In-Group: std-proposals@isocpp.org X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:38475 Archived-At: ------=_Part_33993_1036016547.1528128168356 Content-Type: multipart/alternative; boundary="----=_Part_33994_1777521046.1528128168356" ------=_Part_33994_1777521046.1528128168356 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable How is it O(n=C2=B2 log n)? end - begin is O(1) (random access iterator) out_begin + n is O(1) (random access iterator) std::iota(out_begin, out_end, 0) is O(n) std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return=20 begin[lhs] < begin[rhs]; }) is O(n log n) ( begin[] is O(1)) In the end, this is O(n log n). Maybe I have assumed random access iterators where they are not, but=20 otherwise, it is O(n log n). Le lundi 4 juin 2018 17:51:49 UTC+2, joshua.r.ma...@gmail.com a =C3=A9crit = : > > Unfortunately, that approach computes and is correct but is not efficient= =20 > enough to be seriously considered in my area. That approach ends up bein= g=20 > something like O(n^2 log n). Naive tuned algorithms are still in the rea= lm=20 > on O(n^2) when using a normally linear sort. SACA-K is linear time and= =20 > constant workspace, and divsufsort is n log n time with some acceptable= =20 > workspace. > > > On Monday, June 4, 2018 at 11:36:49 AM UTC-4, floria...@gmail.com wrote: >> >> I have the feeling we don't a new interface for that: >> template< typename RandomAccess_Iterator, typename Output_Iterator > >> void get_suffix_array(RandomAccess_Iterator begin, RandomAccess_Iterator= =20 >> end, Output_Iterator out_begin) { >> // few preparations >> const auto n =3D end - begin; >> auto out_end =3D out_begin + n; >> >> // actual work >> std::iota(out_begin, out_end, 0); >> std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return= =20 >> begin[lhs] < begin[rhs]; }); >> } >> >> Would that be enough? >> >> Le lundi 4 juin 2018 17:14:52 UTC+2, joshua.r.ma...@gmail.com a =C3=A9cr= it : >>> >>> A more limited change to the sorts made available is adding a discrete= =20 >>> suffix array function. For the uninitiated, a suffix array is unlike a= =20 >>> typical sorting algorithm in two respects: the returned object is a=20 >>> sequence of indexes or reference into the original container, and in th= e=20 >>> case of ties, subordering is dictated by a comparison of each index's o= r=20 >>> reference's following value in the original container with the terminal= =20 >>> value being the global minimum value. >>> >>> The two significant algorithms for generating suffix arrays right now= =20 >>> are SACA-K and divsufsort. >>> >>> I think a good call interface for this would be as follows: >>> >>> template< typename _Bidirectional_Iterator, typename _Output_Iterator > >>> void get_suffix_array(_Bidirectional_Iterator begin,=20 >>> _Bidirectional_Iterator end, _Output_Iterator out); >>> >>> This would have applications in compression, text searching, and=20 >>> sequence alignment. >>> >> --=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. To view this discussion on the web visit https://groups.google.com/a/isocpp= ..org/d/msgid/std-proposals/ffee2e05-2287-4044-9947-f19f21a389b6%40isocpp.or= g. ------=_Part_33994_1777521046.1528128168356 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
How is it O(n=C2=B2 log n)?
end - begin is O(1) (random access iterato= r)
out_begin + n is O(1) (random access iterator)
std::iota(out_begin, out_end, 0) is O(n)
std::sort(out_begin, out_en= d, [&begin](auto lhs, auto rhs) { return begin[lhs] < begin[rhs]; })= is O(n log n)=C2=A0 ( begin[] is O(1))

In the end, this is O= (n log n).
Maybe I have assumed random access iterators where they are n= ot, but otherwise, it is O(n log n).

Le lundi 4 juin 2018 17:51:49 U= TC+2, joshua.r.ma...@gmail.com a =C3=A9crit=C2=A0:
Unfortunately, that approach comp= utes and is correct but is not efficient enough to be seriously considered = in my area.=C2=A0 That approach ends up being something like O(n^2 log n).= =C2=A0 Naive tuned algorithms are still in the realm on O(n^2) when using a= normally linear sort.=C2=A0 SACA-K is linear time and constant workspace, = and divsufsort is n log n time with some acceptable workspace.


On Monday, June 4, 2018 at 11:36:49 AM UTC-4, floria...@= gmail.com wrote:
I have the feeling we don't a new interface for that:
template<= typ= ename RandomAccess_Iterator, typename Output_Iterator >
void get_suffix_array(RandomAccess_Iterator begin= , RandomAccess_Iterator end,= Output= _Iterator out_begin) {
=C2=A0 =C2=A0<= span style=3D"color:#800">// few preparations
=C2=A0 =C2=A0const<= /span> auto n =3D end - be= gin;
=C2=A0 =C2=A0auto out_end =3D out_begin + n;
<= span style=3D"color:#000">=C2=A0 =C2=A0 // actual work
= =C2=A0 =C2=A0std:= :iota(out_begin, out_end, 0);
=C2=A0 =C2=A0std::sort(out_begin, out_end, [&a= mp;begin](auto lhs, auto rhs) { return begin[lhs] < begin[rhs]; });
}

Would that be enough?

Le lundi 4 juin = 2018 17:14:52 UTC+2, joshua.r.ma...@gmail.com a =C3=A9crit=C2=A0:
A more limited c= hange to the sorts made available is adding a discrete suffix array functio= n.=C2=A0 For the uninitiated, a suffix array is unlike a typical sorting al= gorithm in two respects: the returned object is a sequence of indexes or re= ference into the original container, and in the case of ties, subordering i= s dictated by a comparison of each index's or reference's following= value in the original container with the terminal value being the global m= inimum value.

The two significant algorithms for g= enerating suffix arrays right now are SACA-K and divsufsort.

=
I think a good call interface for this would be as follows:

template< typename _Bidirectional_Iterator, typenam= e _Output_Iterator >
void get_suffix_array(_Bidirectional= _Iterator begin, _Bidirectional_Iterator end, _Output_Iterator out);
<= div>
This would have applications in compression, text search= ing, and sequence alignment.

--
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.= com/a/isocpp.org/d/msgid/std-proposals/ffee2e05-2287-4044-9947-f19f21a389b6= %40isocpp.org.
------=_Part_33994_1777521046.1528128168356-- ------=_Part_33993_1036016547.1528128168356-- .