SETT编程竞赛：最快的设置< T>履行 [英] The SETT Programming Contest: The fastest set<T> implementation
问题描述
SETT编程竞赛：最快的设置< Timplementation
编写最快的设置<仅使用标准C ++ / C进行实现。
理想情况下应该有与std :: set相同的接口。
至少必须实现以下方法：
insert（），find（），begin（），end（）， erase（），size（），operator<（），
和至少前向迭代器。
这里，速度和正确性是最重要的2因素。
从功能上看，它应该与std :: set类似，
几乎没有限制物品的数量，
并且显着更快，总是或在指定的情况下
条件（例如随机项目等）。
该类应放在自己的命名空间中。 />
还提供了一个基准程序例程，它将您的
实现与std :: set的实现进行比较，并简要记录
并对这些结果进行评论。
提示：由于集合中的项目总是按顺序排列
（由运算符<（）确定）你需要使用一些树
例程（AVL） ，红黑，展开等）或使用你自己的树
方法在你的实施的核心。
另见本文：
Ben Pfaff，斯坦福大学系统软件中的BST性能分析
http://www.stanford.edu/~blp/papers/libavl.pdf
在某处发布完成的项目在网上
（例如在您自己的主页或 http：// sourceforge .net / ）
并在comp.lang.c ++中公布。
本次比赛没有截止日期。最快的方法
将成为SETT编程竞赛的赢家，
，直到有人提出更快的方法。
祝你好运！
" SETT Programming Contest" < se ** @ sett.programming.contest.org.invalidwrote
消息新闻中的
：g2 ********** @ aioe.org ...
< blockquote class =post_quotes>
SETT编程竞赛：最快的设置< Timplementation
什么是奖品？
[...]
SETT Programming Contest写道：
SETT编程竞赛：最快的设置< Timplementation
通过简单地使用默认的
std :: set，可以实现相当大的加速自定义内存分配器。我在这里完成了以下工作：
http：// warp。 povusers.org/FSBAllocator/
我想这可能是我的参赛作品。
6月3日，4日：55 pm，SETT编程竞赛
< s ... @ sett.programming.contest.org.invalidwrote：
SETT编程竞赛：最快的设置< Timplementation
写出最快的设置<仅使用标准C ++ / C进行实现。
理想情况下它应该具有相同的功能接口如std :: set。
至少必须实现以下方法：
insert（），find（），begin（），end（），erase（ ），size（），operator<（），
和至少前向迭代器。
这里，速度和正确性是最重要的两个因素。
从功能上来说它应该与std :: set类似，
实际上没有l模仿物品的数量，
并且明显更快，无论是总是还是指定的
条件（例如随机物品等）。
该类应该放在一个自己的命名空间中。
还提供一个基准程序例程，它将你的
实现与std :: set的实现进行比较，并且简要记录
并评论这些结果。
提示：由于集合中的项目总是按顺序排列
（如由运算符<（）确定你需要使用一些树
例程（AVL，红黑，splay等）或使用你自己的树
方法实施的核心。
另见本文：
Ben Pfaff，系统软件中BST的性能分析，斯坦福大学，http：// www .stanford.edu / ~bpp / papers / libavl.pdf
在Web上的某个地方发布已完成的项目
（例如在您自己的主页或者http：// ：// sourceforge上。 net /）
并在comp.lang.c ++中公布。
此比赛没有截止日期。最快的方法
将成为SETT编程竞赛的赢家，
，直到有人提出更快的方法。
祝好运！
有趣的比赛。但是，对项目数量应该没有
限制的假设意味着底层内存管理模型将类似于std :: set使用的模型。 。它显示对这种内存模型的更改（特别是在现代的多线程环境中）可能会对
性能产生更大的影响基准测试，然后选择基础数据
结构，由字符串库演示
（参见： http://strinx.sourceforge.net/docs/strinx.html) 。
ShacharS。
The SETT Programming Contest: The fastest set<Timplementation
Write the fastest set<Timplementation 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.
Functionally it should behave similar to std::set,
have practically no limitation on the number of items,
and be significantly faster, either always or under specified
conditions (for example for random items etc.).
The class should be placed in an own namespace.
Supply also a benchmark routine which compares your
implementation with that of std::set, and briefly document
and comment these results.
Hint: Since items in a set are always in an ordered sequence
(as determined by operator<()) you need to use some tree
routines (AVL, red-black, splay, etc.) or use your own tree
method in the heart of your implementation.
See also this paper:
Ben Pfaff, "Performance Analysis of BST in System Software", Stanford University
http://www.stanford.edu/~blp/papers/libavl.pdf
Publish your finished project somewhere on the Web
(for example at your own homepage or at http://sourceforge.net/ )
and announce it in comp.lang.c++ .
There is no deadline on this contest. The fastest method
will be the winner of the SETT Programming Contest,
until someone comes up with a faster method.
Good Luck!
"SETT Programming Contest" <se**@sett.programming.contest.org.invalidwrote
in message news:g2**********@aioe.org...The SETT Programming Contest: The fastest set<TimplementationWhat''s the prize?
[...]
SETT Programming Contest wrote:The SETT Programming Contest: The fastest set<TimplementationConsiderable speedups can be achieved by simply using the default
std::set with a custom memory allocator. I have done exactly that here:
http://warp.povusers.org/FSBAllocator/
I suppose that could be my entry.
On Jun 3, 4:55 pm, "SETT Programming Contest"
<s...@sett.programming.contest.org.invalidwrote:The SETT Programming Contest: The fastest set<Timplementation
Write the fastest set<Timplementation 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.
Functionally it should behave similar to std::set,
have practically no limitation on the number of items,
and be significantly faster, either always or under specified
conditions (for example for random items etc.).
The class should be placed in an own namespace.
Supply also a benchmark routine which compares your
implementation with that of std::set, and briefly document
and comment these results.
Hint: Since items in a set are always in an ordered sequence
(as determined by operator<()) you need to use some tree
routines (AVL, red-black, splay, etc.) or use your own tree
method in the heart of your implementation.
See also this paper:
Ben Pfaff, "Performance Analysis of BST in System Software", Stanford Universityhttp://www.stanford.edu/~blp/papers/libavl.pdf
Publish your finished project somewhere on the Web
(for example at your own homepage or athttp://sourceforge.net/)
and announce it in comp.lang.c++ .
There is no deadline on this contest. The fastest method
will be the winner of the SETT Programming Contest,
until someone comes up with a faster method.
Good Luck!Interesting contest. However, the assumption that there should be no
limitation on the number of items implies that the underlying memory
management model will be similar to the one used by std::set. It
appears that a change to this memory model (particularly within modern
multi-threaded environments) may have a more dramatic affect on
performance benchmarks, then the selection of the underlying data
structure, as demonstrated by the String library
(see: http://strinx.sourceforge.net/docs/strinx.html).
ShacharS.
这篇关于SETT编程竞赛：最快的设置< T>履行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
