220 38476 <65056fa4-3634-4430-9ca3-ca2254eb308b@isocpp.org> article Path: news.gmane.org!.POSTED!not-for-mail From: joshua.r.marshall.1991@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:15:03 -0700 (PDT) Lines: 228 Approved: news@gmane.org Message-ID: <65056fa4-3634-4430-9ca3-ca2254eb308b@isocpp.org> 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_33998_398333938.1528128903915" X-Trace: blaine.gmane.org 1528128781 13514 195.159.176.226 (4 Jun 2018 16:13:01 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Mon, 4 Jun 2018 16:13:01 +0000 (UTC) Cc: florian.csdt@gmail.com To: ISO C++ Standard - Future Proposals Original-X-From: std-proposals+bncBCFIZIPVQEORBCGL2XMAKGQEIY6YDGI@isocpp.org Mon Jun 04 18:12:57 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 1fPs6I-0003Ku-Oy for gclcip-std-proposals@m.gmane.org; Mon, 04 Jun 2018 18:12:55 +0200 Original-Received: by mail-yw0-f198.google.com with SMTP id z195-v6sf23452077ywa.0 for ; Mon, 04 Jun 2018 09:15:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=isocpp-org.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc: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=znk7qm4p3KsFovzi37BDrDw4z2b6R/cf8X9sTE5F8Ns=; b=iMgkH3ui6nZ92XR3J6IA86wMZV4tOwKXO9A+y1vcAzANTC8Seq6zhAklfwULfso09P G66zrdt/zMC0iBjr67ghtnfQKwpjUSYGKZJWdr1VaWTEIEAIGUJP/TmX6hW6/8qyrqGQ nqjTzcc+JmfXtgvfkspHIRarGDodFuSKfR6ChFo60qSVjXVZEclv+Ij6muShId26WFew Qi708h+3X6GoB9Oz4eym9wzalVwHZQn3wgG3mfWhYFG/3dj7V2JEzKlZuzFQTljzE6om H9ZrxYyrjBnoI69YvastC2sZag7mdLXd9tLsosMw+CRhfnvZ6Ch1Y8Dm2IGqO48teui3 myCw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:cc: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=znk7qm4p3KsFovzi37BDrDw4z2b6R/cf8X9sTE5F8Ns=; b=tFOXLInlQUdbCkPa6ESExcNmMc0gaqYDg0IgM6olhjIZk8agZt3/oNI9erhjf4U60g CAWKFELsMdl7iyL1ulCrRJkdBYW5JuKIAk/bD52NySe83uXCcL8vvnL7l12ZzR2Od6lb Ra9vMnTJIvQCR6U2UYSayeqJVXcZPr2JUEutdRlqpdl+/6KSZv9vv1g90pKjZfqmwaeW 4tHGx5vtMm+/EyDwwayZQcqTjqFRLvpGk8Cqxk+Z3uEvbYbkwbBHpLksHZPBDRU5DLAB h6mD/PamCBdZPg0Wcr8FcsWCEW3TZ70OLIwEYZHnoMBakG/h8SL8ysU9pqAsAg20uVB8 Dh/w== 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:cc: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=znk7qm4p3KsFovzi37BDrDw4z2b6R/cf8X9sTE5F8Ns=; b=uH/+ivx2hAiRTQY6YddnThXQcG2hPOcnxIJy35OtwQbcq96GMJeKWxbrP39GszToXo JzXZHMW01wFLKzf9b2YMQmJ/QLTAn92OEX1sUkLBo7+OvzGWk+Qx/d0wiRfwtM2djiGG jO2UOm3bIMo2cBguvWmYW+vN+90frvMtEpbhevz6FZw+ZOrZ5P2/yy4DcXf/zT0Gogmq Mu4OSN4miYjCo1aqrdJ4ftmpDOaLt1pPwO3SQvOzPscHbHEFHhx+zD9U81zMfaMPyyGS NuvgHzd7viDmjgoygcBK1H3gFCiq4liFUNISuNhTx3pizS1woHuK40DTwJgCd+CevYQ2 brKA== X-Gm-Message-State: ALKqPwfMPIFPNAKEuFH4fAWo9JUE+KY9u21BRZD/EYB/IFdSZp4E8rdh MeikCph4APGRwSkmVFxG7Q+v3A== X-Google-Smtp-Source: ADUXVKINCecoN/RPsk4WhvL8wkbaHJOXEVSuZ4djT3LlYuUatSRSAnCWDDCyct5D1frnQJ0Ylfi3LA== X-Received: by 2002:a81:6ca:: with SMTP id 193-v6mr5718357ywg.170.1528128905595; Mon, 04 Jun 2018 09:15:05 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 2002:a81:52c1:: with SMTP id g184-v6ls685784ywb.33.gmail; Mon, 04 Jun 2018 09:15:04 -0700 (PDT) X-Received: by 2002:a81:9b0f:: with SMTP id s15-v6mr698805ywg.11.1528128904327; Mon, 04 Jun 2018 09:15:04 -0700 (PDT) In-Reply-To: X-Original-Sender: joshua.r.marshall.1991@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:38476 Archived-At: ------=_Part_33998_398333938.1528128903915 Content-Type: multipart/alternative; boundary="----=_Part_33999_1984808436.1528128903916" ------=_Part_33999_1984808436.1528128903916 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Not quite. Because these have to track backwards from the each starting=20 point, there are many successive comparisons, especially over the common=20 case of small alphabets. So take your expected length before mismatch of= =20 strings, O(n/2) worst case, O(log(n)/log(|alphabet|))) best case, and=20 multiply each comparison by that. Comparisons are not O(1). On Monday, June 4, 2018 at 12:02:48 PM UTC-4, floria...@gmail.com wrote: > > 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=A9cri= t : >> >> Unfortunately, that approach computes and is correct but is not efficien= t=20 >> enough to be seriously considered in my area. That approach ends up bei= ng=20 >> something like O(n^2 log n). Naive tuned algorithms are still in the re= alm=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_Iterato= r=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=A9c= rit : >>>> >>>> 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 t= he=20 >>>> case of ties, subordering is dictated by a comparison of each index's = or=20 >>>> reference's following value in the original container with the termina= l=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/65056fa4-3634-4430-9ca3-ca2254eb308b%40isocpp.or= g. ------=_Part_33999_1984808436.1528128903916 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Not quite.=C2=A0 Because these have to track backwards fro= m the each starting point, there are many successive comparisons, especiall= y over the common case of small alphabets.=C2=A0 So take your expected leng= th before mismatch of strings, O(n/2) worst case, O(log(n)/log(|alphabet|))= ) best case, and multiply each comparison by that.=C2=A0 Comparisons are no= t O(1).

On Monday, June 4, 2018 at 12:02:48 PM UTC-4, floria...@gmai= l.com wrote:
H= ow is it O(n=C2=B2 log n)?
end - begin is O(1) (random access iterator)
out_begin + n is O(1) (random acc= ess iterator)
std::iot= a(out_begin, out_end, 0) is O(n)
std::sort(out_begin, out_end, [&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 ass= umed random access iterators where they are not, but otherwise, it is O(n l= og n).

Le lundi 4 juin 2018 17:51:49 UTC+2, joshua.r.ma...@gmail.= com a =C3=A9crit=C2=A0:
Unfortunately, that approach computes and is correct but is n= ot efficient enough to be seriously considered in my area.=C2=A0 That appro= ach 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 tim= e with some acceptable workspace.


On Monday, Ju= ne 4, 2018 at 11:36:49 AM UTC-4, floria...@gmail.com wrote:
I have the feeling we don&#= 39;t a new interface for that:
<= code>
template< typename RandomAccess_Iterator, typename Output_Iterator >
void get_suffix_array(RandomAccess_Iterator <= /span>begin, RandomAc= cess_Iterator end, Output_Iterator out_begin) {
=C2=A0 =C2=A0<= /span>// fe= w preparations
=C2=A0 =C2=A0const auto n =3D end - begin;
=C2=A0 =C2=A0auto o= ut_end =3D out_begin + n;
=C2= =A0 =C2=A0 // actual work
=C2=A0 =C2=A0std::iota(out_begin, out_end, 0);<= /span>
= =C2=A0 =C2=A0std::sort(out_begin, out_end, [&begin](auto lhs, auto rhs) { return begin[lhs] <= ; begin[rhs]; });
}

W= ould 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 change to the sorts made availab= le is adding a discrete suffix array function.=C2=A0 For the uninitiated, a= suffix array is unlike a typical sorting algorithm in two respects: the re= turned object is a sequence of indexes or reference into the original conta= iner, and in the case of ties, subordering is dictated by a comparison of e= ach index's or reference's following value in the original containe= r with the terminal value being the global minimum value.

The two significant algorithms for generating suffix arrays right n= ow are SACA-K and divsufsort.

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

template&l= t; typename _Bidirectional_Iterator, typename _Output_Iterator >
void get_suffix_array(_Bidirectional_Iterator begin, _Bidirectional= _Iterator end, _Output_Iterator out);

This would h= ave applications in compression, text searching, 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/65056fa4-3634-4430-9ca3-ca2254eb308b= %40isocpp.org.
------=_Part_33999_1984808436.1528128903916-- ------=_Part_33998_398333938.1528128903915-- .