P.J. Plauger wrote:
>
> James Kuyper <kuyper@wizard.net> wrote in article <359C0204.446B@wizard.net>...
> > AlanStokes@my-dejanews.com wrote:
> > Given that a standard containers can contain objects as small a 1 byte,
> > an upper limit of a few thousand is very tight. What is the smallest
> > memory space that anyone watching this newsgroup has written actual
> > practical C++ (or even EC++) code for?
>
> I can tell you what the envisioned marketplace for EC++ is. The following is
> cribbed from a slide I presented at the April '98 Embedded Systems Conference
> in Chicago. I stole it, in turn, from Hiroshi Monden of NEC Corporation:
>
> NEC Semiconductor Application Engineering Division
> reports the following typical embedded code sizes:
>
> Application       Current KB  Future KB
>
> camera            48-64       96-256
> rice cooker       16-48       64
> celluar phone     384+        768+
> printer           32-64       64-128
> television        16-48       32-96
> VCR               192-256     320+
> HDD               32-64       64-128
>

Therefore, assuming that the available space for data is a significant
fraction of the total space, you should be able to run conformance tests
using containers containing at least 10000 1-byte objects, and as many
as 5000 unique 2-byte objects.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <359A60F7.2781@wizard.net>,
  James Kuyper <kuyper@wizard.net> wrote:
>
> AlanStokes@my-dejanews.com wrote:
> > Are you sure? If the data sets are known to be small (say because the
address
> > space is so small that there can't be more than 256 or 64k elements) then
any
> > sort algorithm will be O(N log N) - indeed O(1) for sufficiently large
> > constant.
> >
> > (Because O(N) notation is all about limits for large N, and you're
preventing
> > N ever becoming large. Of course the same argument can be applied to any
> > finite system, i.e. every computer ever built, which is a bit of a shame.)

> In principle, the complexity requirements refer to the limit as N goes
> to infinity, which can be evaluated theoretically as a characteristic of
> the algorithm, regardless of the limits imposed by the system it is
> implemented on. In practice, the complexity requirement are for the case
> of large N, where 'large' is relative to the limits imposed by the
> system.

Agreed.

> Either way, you cannot simply ignore those requirements just
> because the maximum N for your implementation is small, if you wish to
> claim conformance.

Would you care to back up that assertion? How could a conforming program tell
that the algorithm used was technically N^2 rather than N log N if it couldn't
be run for N larger than a few hundred/thousand?

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <MPG.1004620c336564d1989b69@news.rmi.net>,
  jcoffin@taeus.com (Jerry Coffin) wrote:
> In fairness, I suppose they do give most users a reasonable guess at
> what's likely to happen on the majority of high-quality
> implementations, but that's a pretty weak statement, to put it mildly.

But it's all you'll get anywhere in the standard.  There are a number
of catch phrases which will allow an unscrupulous vendor off the hook,
like conformaty only being specified within resource units.  In practice,
serious vendors don't use them.

> I'm not sure it's any different from simply having put in a couple of
> footnotes like "sort is intended to be implemented with a quicksort or
> similar algorithm."

Just worded in a more precise manner:-).

--
James Kanze    +33 (0)1 39 23 84 71    mailto: kanze@gabi-soft.fr
        +49 (0)69 66 45 33 10    mailto: jkanze@otelo.ibmmail.com
GABI Software, 22 rue Jacques-Lemercier, 78000 Versailles, France
Conseils en informatique orient   e objet --
              -- Beratung in objektorientierter Datenverarbeitung

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:
>
> In article <359A60F7.2781@wizard.net>,
>   James Kuyper <kuyper@wizard.net> wrote:
...
> > In principle, the complexity requirements refer to the limit as N goes
> > to infinity, which can be evaluated theoretically as a characteristic of
> > the algorithm, regardless of the limits imposed by the system it is
> > implemented on. In practice, the complexity requirement are for the case
> > of large N, where 'large' is relative to the limits imposed by the
> > system.
>
> Agreed.
>
> > Either way, you cannot simply ignore those requirements just
> > because the maximum N for your implementation is small, if you wish to
> > claim conformance.
>
> Would you care to back up that assertion? How could a conforming program tell
> that the algorithm used was technically N^2 rather than N log N if it couldn't
> be run for N larger than a few hundred/thousand?

As a practical matter, it could use swap and compare functions that
count how often they were executed, and do counts at three large but
logarithmically well-seperated values of N that include the maximum
value, and make a log-log plot pf the results. If you can produce
results that look like N log N to such a program, your algorithm
effectively is N log N, in the only sense that matters for such a
program. Having N as large as 1000 is sufficient to rule out significant
contributions from lower order terms unless they have coefficients on
the order of 1000/log(1000) times larger than the coefficient of the
leading term.

However, for actual conformance verification, I wouldn't use a test
program, I'd inspect the actual algorithm used, and verify the behavior
in the limit as N goes to infinity. Conformance checking cannot be a
simple matter of running test programs. If that were the case, an
implementation that created programs which celebrated their millionth
execution by formatting your hard disk could likely get certified as
conforming. A serious conformance check should involve an examination of
at least a random sample of the compiler design documents and source
code. Obviously, this is something only the richest compiler clients
could afford to do.

Given that a standard containers can contain objects as small a 1 byte,
an upper limit of a few thousand is very tight. What is the smallest
memory space that anyone watching this newsgroup has written actual
practical C++ (or even EC++) code for?
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:

[...]

> If that were the case, an
> implementation that created programs which celebrated their millionth
> execution by formatting your hard disk could likely get certified as
> conforming.

Certainly: The implementation has the resource limit of 999999
executions
per compile ;-)

[...]
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper <kuyper@wizard.net> wrote in article <359C0204.446B@wizard.net>...
> AlanStokes@my-dejanews.com wrote:
> Given that a standard containers can contain objects as small a 1 byte,
> an upper limit of a few thousand is very tight. What is the smallest
> memory space that anyone watching this newsgroup has written actual
> practical C++ (or even EC++) code for?

I can tell you what the envisioned marketplace for EC++ is. The following is
cribbed from a slide I presented at the April '98 Embedded Systems Conference
in Chicago. I stole it, in turn, from Hiroshi Monden of NEC Corporation:

NEC Semiconductor Application Engineering Division
reports the following typical embedded code sizes:

Application       Current KB  Future KB

camera            48-64       96-256
rice cooker       16-48       64
celluar phone     384+        768+
printer           32-64       64-128
television        16-48       32-96
VCR               192-256     320+
HDD               32-64       64-128

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:

> Are you sure? If the data sets are known to be small (say because the address
> space is so small that there can't be more than 256 or 64k elements) then any
> sort algorithm will be O(N log N) - indeed O(1) for sufficiently large
> constant.
>
> (Because O(N) notation is all about limits for large N, and you're preventing
> N ever becoming large. Of course the same argument can be applied to any
> finite system, i.e. every computer ever built, which is a bit of a shame.)

This applies to computers. C++ are defined on abstract machines
which can be arbitrarilly big.

if (size() > 10000)
    sgi_stl_clearly_conforming_implementation();
else
    linear_implementation_doesnt_conform_on_a_PC();

This is conforming. You can optimise the first part away,
if max_size is 1000.

--

Valentin Bonnard                mailto:bonnardv@pratique.fr
info about C++/a propos du C++: http://pages.pratique.fr/~bonnardv/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

AlanStokes@my-dejanews.com wrote:
>
> In article <MPG.ff7a8d7f91c6b97989b30@news.rmi.net>,
>   jcoffin@taeus.com (Jerry Coffin) wrote:
> > IMO, this is another example of the specification of computational
> > complexity being overly constraining without serving a useful purpose.
> > On a system where it's known that data sets will always be relatively
> > small (e.g. because the system doesn't address a lot of memory) it
> > might be perfectly reasonable to implement sort() using a Shell-
> > Metzner sort.  Unfortunately, this doesn't meet the official
> > computational complexity requirements, even though on relatively small
> > collections it's often faster than most of the others, along with
> > typically using less memory.
>
> Are you sure? If the data sets are known to be small (say because the address
> space is so small that there can't be more than 256 or 64k elements) then any
> sort algorithm will be O(N log N) - indeed O(1) for sufficiently large
> constant.
>
> (Because O(N) notation is all about limits for large N, and you're preventing
> N ever becoming large. Of course the same argument can be applied to any
> finite system, i.e. every computer ever built, which is a bit of a shame.)
>
> So the requirements can be met by a linear search; and if that is what is best
> for the platform then that's what a good implementation should use.

In principle, the complexity requirements refer to the limit as N goes
to infinity, which can be evaluated theoretically as a characteristic of
the algorithm, regardless of the limits imposed by the system it is
implemented on. In practice, the complexity requirement are for the case
of large N, where 'large' is relative to the limits imposed by the
system. Either way, you cannot simply ignore those requirements just
because the maximum N for your implementation is small, if you wish to
claim conformance.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <6nb0ep$1hv$1@nnrp1.dejanews.com>, AlanStokes@my-
dejanews.com says...

[ ... ]

> Are you sure? If the data sets are known to be small (say because the address
> space is so small that there can't be more than 256 or 64k elements) then any
> sort algorithm will be O(N log N) - indeed O(1) for sufficiently large
> constant.

Yes -- in fact I've posted at least one other article pointing this
out.  However, even I'll admit that this seems to be directly contrary
to the intent of the standard, even though it appears to me that it is
technically in accordance with the requirements.

>
> (Because O(N) notation is all about limits for large N, and you're preventing
> N ever becoming large. Of course the same argument can be applied to any
> finite system, i.e. every computer ever built, which is a bit of a shame.)
>
> So the requirements can be met by a linear search; and if that is what is best
> for the platform then that's what a good implementation should use.

In short, the "requirements" as they stand, are (as I believe I've
said previously) not useful to much of anybody: they give the user no
guarantee of much of anything, but are likely to mislead many (most?)
vendors into believing they have to use particular algorithms, even
when they're not going to be optimal on the particular machine.

In fairness, I suppose they do give most users a reasonable guess at
what's likely to happen on the majority of high-quality
implementations, but that's a pretty weak statement, to put it mildly.
I'm not sure it's any different from simply having put in a couple of
footnotes like "sort is intended to be implemented with a quicksort or
similar algorithm."

--
    Later,
    Jerry.

The Universe is a figment of its own imagination.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <MPG.ff7a8d7f91c6b97989b30@news.rmi.net>,
  jcoffin@taeus.com (Jerry Coffin) wrote:
> IMO, this is another example of the specification of computational
> complexity being overly constraining without serving a useful purpose.
> On a system where it's known that data sets will always be relatively
> small (e.g. because the system doesn't address a lot of memory) it
> might be perfectly reasonable to implement sort() using a Shell-
> Metzner sort.  Unfortunately, this doesn't meet the official
> computational complexity requirements, even though on relatively small
> collections it's often faster than most of the others, along with
> typically using less memory.

Are you sure? If the data sets are known to be small (say because the address
space is so small that there can't be more than 256 or 64k elements) then any
sort algorithm will be O(N log N) - indeed O(1) for sufficiently large
constant.

(Because O(N) notation is all about limits for large N, and you're preventing
N ever becoming large. Of course the same argument can be applied to any
finite system, i.e. every computer ever built, which is a bit of a shame.)

So the requirements can be met by a linear search; and if that is what is best
for the platform then that's what a good implementation should use.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]