[M3devel] STL algorithms? sort/unique?
Jay K
jay.krell at cornell.edu
Fri Sep 28 12:26:19 CEST 2012
The following is very efficient:
run through a bunch of records, picking out one number from some of themappend those numbers to a growing vectorsort the vectorunique the vector
sequence allows for random access..but only via a function...or maybe an iterator
STL has this wonderful separation of algorithms from containers, via iterators.I suspect very few other libraries do.And it could be that most languages don't support it.It doesn't appear I can easily sort a sequence, unless I copy the data out into an array -- gross inefficiency.
I've hacked something very manual together..and it is taking forever to get it to work. It turns out I can reasonably well bound the size of the data, so I'm using an open array...and I have to keep track of my position instead of using addhi/push_back.Not happy.At some point I might give up and write the backend in C++..at which point I might as well write a C++ frontend anywa.
I absolutely do not want a sorted table and unique upon insert.That is much less efficient.What I'm describing uses temporarily larger working set but vastly less CPU.An array that gets sorted/uniqued occasionally, like just once.And not ongoing maintainence for every single add.
- Jay
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] STL algorithms? sort/unique?
> Date: Fri, 28 Sep 2012 01:04:48 -0700
> From: mika at async.caltech.edu
>
>
> BTW I had the same experience when I first started using Modula-3.
> It was painful to jump through all its hoops, coming from C, where you
> can do whatever you want to whatever bits happen to be sloshing around
> your machine. C++ from what I have seen mainly lets you do that to
> more bits in fewer lines of code.
>
> But after a while I really came to appreciate the value of things like the
> language's telling me I'm using the wrong data structure instead of
> just letting me use the same "nice, terse, efficient" syntax to write
> a crappy program :-)
>
> mika writes:
> >You're using the wrong (abstract) data structure if you want sort and unique.
> >
> >A "sequence" is meant to be accessed sequentially...
> >
> >Not knowing precisely what you're doing it sounds like you might want a
> >SortedTable... you can get unique on insert and access it in increasing
> >or decreasing order.
> >
> > Mika
> >
> >Jay K writes:
> >>--_d2a02ece-d492-410e-88fb-fb53737d7219_
> >>Content-Type: text/plain; charset="iso-8859-1"
> >>Content-Transfer-Encoding: quoted-printable
> >>
> >> I have an IntSeq.T with a bunch of integers. =20
> >> What is a good terse efficient idiom for sort and unique? =20
> >>
> >> In C++ I would say: vector<int> a=3B a.push_back(...)=3B =
> >> a.push_back(...)=3B std::sort(a.begin()=2C a.end())=3B =
> >> a.resize(std::unique(a.begin()=2C a.end()) - a.begin())=3B for (aut=
> >>o i =3D a.begin()=3B i !=3D a.end()=3B ++i) {
> >> do stuff with *i }=20
> >> Nice=2C terse=2C efficient. In Modula-3? =20
> >>
> >>I know that unique is one of the easiest algorithms to manually write inlin=
> >>e=2Cbut I shouldn't have to.
> >>
> >>(I'm really trying to stay in Modula-3 here=2C but it is definitely a strug=
> >>gle. :( )
> >>
> >>Thank you=2C - Jay
> >>
> >> =
> >>
> >>--_d2a02ece-d492-410e-88fb-fb53737d7219_
> >>Content-Type: text/html; charset="iso-8859-1"
> >>Content-Transfer-Encoding: quoted-printable
> >>
> >><html>
> >><head>
> >><style><!--
> >>.hmmessage P
> >>{
> >>margin:0px=3B
> >>padding:0px
> >>}
> >>body.hmmessage
> >>{
> >>font-size: 12pt=3B
> >>font-family:Calibri
> >>}
> >>--></style></head>
> >><body class=3D'hmmessage'><div dir=3D'ltr'> =3B  =3B =3BI have =
> >>an IntSeq.T with a bunch of integers. =3B  =3B =3B<br><div><spa=
> >>n style=3D"font-size: 12pt=3B "> =3B  =3B</span><span style=3D"font=
> >>-size: 12pt=3B "> =3B</span>What is a good terse efficient idiom for so=
> >>rt and unique?<span style=3D"font-size: 12pt=3B "> =3B  =3B</span><=
> >>span style=3D"font-size: 12pt=3B "> =3B</span></div><div><br></div><div=
> >>><br></div><div> =3B  =3B In C++ I would say:<span style=3D"font-si=
> >>ze: 12pt=3B "> =3B  =3B</span><span style=3D"font-size: 12pt=3B ">&=
> >>nbsp=3B</span></div><div><span style=3D"font-size: 12pt=3B "> =3B  =
> >>=3B</span><span style=3D"font-size: 12pt=3B "> =3B</span>vector<=3Bin=
> >>t>=3B a=3B<span style=3D"font-size: 12pt=3B "> =3B  =3B</span><sp=
> >>an style=3D"font-size: 12pt=3B "> =3B</span></div><div><span style=3D"f=
> >>ont-size: 12pt=3B "> =3B  =3B</span><span style=3D"font-size: 12pt=
> >>=3B "> =3B</span>a.push_back(...)=3B<span style=3D"font-size: 12pt=3B "=
> >>> =3B  =3B</span><span style=3D"font-size: 12pt=3B "> =3B</span=
> >>></div><div><div><span style=3D"font-size: 12pt=3B "> =3B  =3B</spa=
> >>n><span style=3D"font-size: 12pt=3B "> =3B</span>a.push_back(...)=3B<sp=
> >>an style=3D"font-size: 12pt=3B "> =3B  =3B</span><span style=3D"fon=
> >>t-size: 12pt=3B "> =3B</span></div><div><span style=3D"font-size: 12pt=
> >>=3B "> =3B  =3B</span><span style=3D"font-size: 12pt=3B "> =3B<=
> >>/span>std::sort(a.begin()=2C a.end())=3B<span style=3D"font-size: 12pt=3B "=
> >>> =3B  =3B</span><span style=3D"font-size: 12pt=3B "> =3B</span=
> >>></div><div><span style=3D"font-size: 12pt=3B "> =3B  =3B</span><sp=
> >>an style=3D"font-size: 12pt=3B "> =3B</span>a.resize(std::unique(a.begi=
> >>n()=2C a.end()) - a.begin())=3B<span style=3D"font-size: 12pt=3B "> =3B=
> >>  =3B</span><span style=3D"font-size: 12pt=3B "> =3B</span></div><d=
> >>iv><span style=3D"font-size: 12pt=3B "> =3B  =3B for (auto i =3D a.=
> >>begin()=3B i !=3D a.end()=3B ++i)</span></div><div><span style=3D"font-size=
> >>: 12pt=3B "> =3B  =3B {<br> =3B  =3B  =3B do stuff with=
> >> *i</span></div><div><span style=3D"font-size: 12pt=3B "> =3B  =3B =
> >>}</span></div><div> =3B</div><div><br></div><div><span style=3D"font-si=
> >>ze: 12pt=3B "> =3B  =3B</span><span style=3D"font-size: 12pt=3B ">&=
> >>nbsp=3B</span>Nice=2C terse=2C efficient.<span style=3D"font-size: 12pt=3B =
> >>"> =3B  =3B</span><span style=3D"font-size: 12pt=3B "> =3B</spa=
> >>n></div><div><span style=3D"font-size: 12pt=3B "> =3B  =3B</span><s=
> >>pan style=3D"font-size: 12pt=3B "> =3B</span>In Modula-3?<span style=3D=
> >>"font-size: 12pt=3B "> =3B  =3B</span><span style=3D"font-size: 12p=
> >>t=3B "> =3B</span></div><div><br></div><div><br></div><div>I know that =
> >>unique is one of the easiest algorithms to manually write inline=2C</div><d=
> >>iv>but I shouldn't have to.</div><div><br></div><div><br></div><div>(I'm re=
> >>ally trying to stay in Modula-3 here=2C but it is definitely a struggle. :(=
> >> )</div><div><br></div><div><br></div><div>Thank you=2C</div><div> =3B-=
> >> Jay</div><br><br></div> </div></body>
> >></html>=
> >>
> >>--_d2a02ece-d492-410e-88fb-fb53737d7219_--
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20120928/e8d2cbd3/attachment-0002.html>
More information about the M3devel
mailing list