Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > The SETT Programming Contest: The fastest set<T> implementation

Reply
Thread Tools

The SETT Programming Contest: The fastest set<T> implementation

 
 
James Kanze
Guest
Posts: n/a
 
      06-04-2008
On Jun 3, 3:55 pm, "SETT Programming Contest"
<(E-Mail Removed)> wrote:
> The SETT Programming Contest: The fastest set<T> implementation


> Write the fastest set<T> implementation using only standard
> C++/C.


Fastest at what? On what machine? With which implementation of
C++?

[...]
> See also this paper:
> Ben Pfaff, "Performance Analysis of BST in System Software", Stanford Universityhttp://www.stanford.edu/~blp/papers/libavl.pdf


Which more or less establishes that "fastest" is meaningless
unless you define at what?

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
 
Reply With Quote
 
 
 
 
Bartc
Guest
Posts: n/a
 
      06-04-2008

"SETT Programming Contest" <(E-Mail Removed)> wrote
in message news:g23kml$ld8$(E-Mail Removed)...
> The SETT Programming Contest: The fastest set<T> implementation
>
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.
> At least the following methods must be implemented:
> insert(), find(), begin(), end(), erase(), size(), operator<(),
> and at least the forward iterator.


I'm not going to enter this (since, until today, I'd never heard of set<T>
or BST).

But I'm interested in clearing up what the task is.

A set<T> is just an arbitrary collection of values (each unique) of type T?
Like a Pascal set? (OK a Pascal set is limited to scalars and has a pre-set
range).

And T can be anything at all, provided operator < is meaningful for it?

In this case it all sounds pretty straightforward, so why limit the contest
to C++ only? Is it to eliminate languages that already have very fast
implementations built-in?

--
Bartc


 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      06-04-2008
"SETT Programming Contest" <(E-Mail Removed)>
writes:
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.
> At least the following methods must be implemented:
> insert(), find(), begin(), end(), erase(), size(), operator<(),
> and at least the forward iterator.


Wouldn't it be easier to compare the implementations if you
required them to meet all the requirements placed on std::set by
the C++ standard?

> See also this paper:
> Ben Pfaff, "Performance Analysis of BST in System Software", Stanford University
> http://www.stanford.edu/~blp/papers/libavl.pdf


How amusing.
--
Ben Pfaff
http://benpfaff.org
 
Reply With Quote
 
Mike
Guest
Posts: n/a
 
      06-04-2008
In article <g23kml$ld8$(E-Mail Removed)>, http://www.velocityreviews.com/forums/(E-Mail Removed)lid says...
> The SETT Programming Contest: The fastest set<T> implementation
>
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.
> At least the following methods must be implemented:
> insert(), find(), begin(), end(), erase(), size(), operator<(),
> and at least the forward iterator.
>
> Here, speed and correctness are the 2 most important factors.


Does this mean that a totally incorect but exceedingly fast implementation can still get a 50% pass mark?
 
Reply With Quote
 
shablool
Guest
Posts: n/a
 
      06-05-2008
On Jun 4, 7:56 pm, Ben Pfaff <(E-Mail Removed)> wrote:
> "SETT Programming Contest" <(E-Mail Removed)>
> writes:
>
> > Write the fastest set<T> implementation using only standard C++/C.
> > Ideally it should have the same interface like std::set.
> > At least the following methods must be implemented:
> > insert(), find(), begin(), end(), erase(), size(), operator<(),
> > and at least the forward iterator.

>
> Wouldn't it be easier to compare the implementations if you
> required them to meet all the requirements placed on std::set by
> the C++ standard?
>
> > See also this paper:
> > Ben Pfaff, "Performance Analysis of BST in System Software", Stanford University
> >http://www.stanford.edu/~blp/papers/libavl.pdf

>
> How amusing.
> --
> Ben Pfaffhttp://benpfaff.org



As stated in previous post, this requirement alone assumes certain
memory model, which may affect the actual performance. Nevertheless, I
would like propose the following code fragment as possible candidate
for the actual test (after-all, we should start somewhere):


template <typename SetT>
void sett_contest(SetT& s, int n)
{
typedef typename SetT::value_type value_type;

int i;
std::vector<value_type> v(n);

for (i = 0; i < n; ++i)
{
v[i] = value_type(i);
}

std::random_shuffle(v.begin(), v.end());
s.insert(v.begin(), v.end());

std::random_shuffle(v.begin(), v.end());
for (i = 0; i < n; ++i)
{
s.erase(s.find(v[i]));
}
}

ShacharS.
 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      06-05-2008
shablool <(E-Mail Removed)> writes:

>> "SETT Programming Contest" <(E-Mail Removed)>
>> writes:
>>
>> > Write the fastest set<T> implementation using only standard C++/C.
>> > Ideally it should have the same interface like std::set.
>> > At least the following methods must be implemented:
>> > insert(), find(), begin(), end(), erase(), size(), operator<(),
>> > and at least the forward iterator.


> I would like propose the following code fragment as possible
> candidate for the actual test (after-all, we should start
> somewhere):


[...]

> std::random_shuffle(v.begin(), v.end());
> s.insert(v.begin(), v.end());
>
> std::random_shuffle(v.begin(), v.end());
> for (i = 0; i < n; ++i)
> {
> s.erase(s.find(v[i]));
> }


That fragment is going to strongly favor implementations that do
little or no balancing of the tree, because balancing is just a
waste of time when you know that insertions and deletions occur
in random order. Is that your intention?

I don't see any specifications on iterator invalidation in the
original post. Perhaps a hash table implementation would be
acceptable. If so, that's probably going to beat any tree-based
implementation, especially as the sets grow larger. I wonder
whether that is the intention, too.
--
"While the Melissa license is a bit unclear, Melissa aggressively
encourages free distribution of its source code."
--Kevin Dalley <(E-Mail Removed)>
 
Reply With Quote
 
shablool
Guest
Posts: n/a
 
      06-05-2008
On Jun 5, 3:38 pm, Ben Pfaff <(E-Mail Removed)> wrote:
> shablool <(E-Mail Removed)> writes:
> >> "SETT Programming Contest" <(E-Mail Removed)>
> >> writes:

>
> >> > Write the fastest set<T> implementation using only standard C++/C.
> >> > Ideally it should have the same interface like std::set.
> >> > At least the following methods must be implemented:
> >> > insert(), find(), begin(), end(), erase(), size(), operator<(),
> >> > and at least the forward iterator.

> > I would like propose the following code fragment as possible
> > candidate for the actual test (after-all, we should start
> > somewhere):

>
> [...]
>
> > std::random_shuffle(v.begin(), v.end());
> > s.insert(v.begin(), v.end());

>
> > std::random_shuffle(v.begin(), v.end());
> > for (i = 0; i < n; ++i)
> > {
> > s.erase(s.find(v[i]));
> > }

>
> That fragment is going to strongly favor implementations that do
> little or no balancing of the tree, because balancing is just a
> waste of time when you know that insertions and deletions occur
> in random order. Is that your intention?
>
> I don't see any specifications on iterator invalidation in the
> original post. Perhaps a hash table implementation would be
> acceptable. If so, that's probably going to beat any tree-based
> implementation, especially as the sets grow larger. I wonder
> whether that is the intention, too.
> --
> "While the Melissa license is a bit unclear, Melissa aggressively
> encourages free distribution of its source code."
> --Kevin Dalley <(E-Mail Removed)>


The original post said nothing about the underlying data-structure
representation. In particular, it did not assume usage of self
balancing binary search trees. The above code fragment is merely a
proposal for the actual test, which implicitly defines the interface
requirements. If you think it is incompatible with the spirit of the
original post, why don't you propose an alternative one?

ShacharS.
 
Reply With Quote
 
Anders Dalvander
Guest
Posts: n/a
 
      06-05-2008
On Jun 3, 3:55 pm, "SETT Programming Contest"
<(E-Mail Removed)> wrote:
> Write the fastest set<T> implementation using only standard C++/C.
> Ideally it should have the same interface like std::set.
> At least the following methods must be implemented:
> insert(), find(), begin(), end(), erase(), size(), operator<(),
> and at least the forward iterator.


Is that you Razii? What are you trying to prove?

Regards,
Anders
 
Reply With Quote
 
Ben Pfaff
Guest
Posts: n/a
 
      06-05-2008
shablool <(E-Mail Removed)> writes:

> On Jun 5, 3:38 pm, Ben Pfaff <(E-Mail Removed)> wrote:
>> shablool <(E-Mail Removed)> writes:
>> >> "SETT Programming Contest" <(E-Mail Removed)>
>> >> writes:

>>
>> >> > Write the fastest set<T> implementation using only standard C++/C.
>> >> > Ideally it should have the same interface like std::set.
>> >> > At least the following methods must be implemented:
>> >> > insert(), find(), begin(), end(), erase(), size(), operator<(),
>> >> > and at least the forward iterator.
>> > I would like propose the following code fragment as possible
>> > candidate for the actual test (after-all, we should start
>> > somewhere):

>> That fragment is going to strongly favor implementations that do
>> little or no balancing of the tree, because balancing is just a
>> waste of time when you know that insertions and deletions occur
>> in random order. Is that your intention?

>
> The original post said nothing about the underlying data-structure
> representation. In particular, it did not assume usage of self
> balancing binary search trees.


What non-tree-like data structures fulfill the asymptotic
requirements for std::set?

> The above code fragment is merely a proposal for the actual
> test, which implicitly defines the interface requirements.


The interface requirements were defined by the OP.

> If you think it is incompatible with the spirit of the original
> post, why don't you propose an alternative one?


I already proposed an alternative for the interface requirements,
in a direct followup to the OP.
--
Ben Pfaff
http://benpfaff.org
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C++ 32 03-01-2010 09:15 PM
Current Fastest Python Implementation? samuraisam Python 4 02-20-2008 10:11 AM
Sett absolute path problem Pumkin ASP .Net 9 10-12-2006 12:33 PM
Fastest 5 mp Digital Camera ? Fastest 4 mp Digital Camera? photoguysept102004@yahoo.com Digital Photography 6 10-28-2004 11:33 AM
Fastest ip address searching method/implementation Jonathan C++ 6 11-29-2003 06:19 AM



Advertisments