从递归到迭代的翻译 [英] Translation from recursive to iterative
问题描述
由于缺乏资源，我必须以迭代的形式翻译以下递归
函数。
这是一种二分法搜索。 />
void SearchSlaves（unsigned long start_uid，unsigned long end_uid）
{
char ret;
/ / ping一系列地址（所有带有uid的奴隶在
start_uid到end_uid的范围内都会回复）
ret = PingSlave（start_uid，end_uid）;
if（start_uid == end_uid）//单项
{
if（ret == VALID_PING_REPLY）
AddUidToSlaveList（start_uid）;
return;
}
if（ret == VALID_PING_REPLY）
{
SearchSlaves（start_uid，（（start_uid + end_uid + 1）>> 1） - 1）;
//左子树
SearchSlaves（（（start_uid + end_uid + 1）>> 1），end_uid）; //对吧
子树
}
}
我们将非常感谢任何帮助！ :-)
问候，
Marco
BQ< ba *** *******************@libero.invalid>写道：
由于缺乏资源，我必须以迭代的形式翻译以下递归
函数。
这是一种二分法搜索._
void SearchSlaves（unsigned long start_uid，unsigned long end_uid）
{zh_cn} zh_cn //
// ping一系列地址（所有带有uid的从站）从
start_uid到end_uid的范围将回复）
ret = PingSlave（start_uid，end_uid）;
if（start_uid == end_uid）//单项
{
if（ret == VALID_PING_REPLY）
AddUidToSlaveList（start_uid）;
return;
}
if（ret == VALID_PING_REPLY）
{
SearchSlaves（start_uid，（（start_uid + end_uid + 1）>> 1） - 1）;
// left subtree
SearchSlaves（（（start_uid + end_uid + 1）>> 1 ），end_uid）; //右边
子树
[BTW，在新闻组中使用C ++风格的评论_和_标签不是一个好的
的想法。 ]
}
}
首先想到：摆脱过早的优化，摆脱
不必要的对象（是的，我确实看到了讽刺）：
void SearchSlaves（unsigned long start_uid，unsigned long end_uid）
{
if（PingSlave（start_uid，end_uid）== VALID_PING_REPLY）{
if（start_uid == end_uid）{
AddUidToSlaveList（start_uid）;
返回;
}
SearchSlaves（start_uid，（start_uid + end_uid + 1）/ 2） - 1）;
SearchSlaves（（start_uid + end_uid + 1）/ 2，end_uid）;
}
}
第二个想法：虽然这个算法是有效的，如果奴隶非常稀疏，或相对稀疏和聚集在范围内，这可能是一个有效的算法。每个奴隶都被多次ping，
虽然（log2（end_uid-start_uid）次数，大约），所以如果有很多
的奴隶，这个效率不高。如果在该范围内有一个合理数量的奴隶，那也不是最佳选择。如果您怀疑
其中一个可能就是这种情况，那么直接的线性搜索可能会打败这个算法。
事实上，如果PingSlave使用用于搜索范围的明显，天真的算法，这已经是一次线性搜索 - 已经好几次了。另一种可能性是提高PingSlave的效率，也许是通过
给它一个（可重置的）内存。
Richard
Richard Bos写道：
[BTW，在新闻组中使用C ++风格的注释_和_标签不是一个好消息
想法。 ]
ehr，对不起...... :-)
首先想到：摆脱过早的优化，摆脱不必要的对象（是的，我确实看到了讽刺）：
void SearchSlaves（unsigned long start_uid，unsigned long end_uid）
{
if（PingSlave（start_uid，end_uid）== VALID_PING_REPLY ）{
if（start_uid == end_uid）{
AddUidToSlaveList（start_uid）;
返回;
}
SearchSlaves（start_uid，（start_uid + end_uid + 1）/ 2） - 1）;
SearchSlaves（（start_uid + end_uid + 1）/ 2，end_uid）;
}
第二个想法：这个算法是如果奴隶非常稀疏，那么效率很高，而且情况就是这样：max.20 / 30''奴隶''，稀疏范围2 ^ 16宽
或相对稀疏且聚集在该范围内，这可能是一种有效的算法。每个奴隶都被多次ping，但是（log2（end_uid-start_uid）次数，大约），所以如果有很多
奴隶，这是无效的。如果在该范围内有合理数量的奴隶，也不是最佳的。如果您怀疑其中一个可能就是这种情况，那么简单的线性搜索可能会打败这个算法。
在我的情况下，无法进行简单的线性搜索。
每个ping都有150毫秒的超时，不能减少，并且
搜索空间非常大。
事实上，如果PingSlave使用明显的，天真的算法搜索其范围，这已经是一个线性搜索 - 几个时间结束。
如果他们的uid是start_uid< = uid< = end_uid，奴隶会回答ping。
所以搜索10/20奴隶最多需要大约2-3秒
无论如何，这个代码是针对一个微处理器进行编译的，资源非常有限
资源我有一个堆栈问题把我推向
搜索这个算法的迭代版本：我最多可以进行32个子程序调用，而SearchSlave自己调用至少16次
2 ^ 16空间。由于SearchSlave不是0级，我有时会获得一个
堆栈溢出。
顺便提一下，理论确保递归算法总是可以
以迭代方式重写。如果有人有想法...
问候，
Marco
BQ写道：< blockquote class =post_quotes>
由于缺乏资源，我必须以迭代的形式翻译以下递归
函数。
这是一种二分法搜索。 />
void SearchSlaves（unsigned long start_uid，unsigned long end_uid）
{zh_cn}查询;
// ping一系列地址（所有从站的uid都在
start_uid到end_uid将回复）
ret = PingSlave（start_uid，end_uid）;
if（start_uid == end_uid）//单项
{
if（ret == VALID_PING_REPLY）
AddUidToSlaveList（start_uid）;
return;
}
if（ret == VALID_PING_REPLY）
{SearchSlaves（ start_uid，（（start_uid + end_uid + 1）>> 1） - 1）;
//左子树
SearchSlaves（（（start_uid + end_uid + 1）>> 1），end_uid）; //
子树
}
}
任何帮助将不胜感激！ :-)
问候，
Marco
您可以从让人们轻松帮助您开始。 8个字符
缩进过多，//评论不能生存线包好
好，任何超过72的线长都可能导致问题
新闻组上
。不要使用制表符，使用空格。为未定义的东西包含虚拟的
函数，以便人们可以立即编译它/ b
。因为它是SearchSlaves操作看起来很奇怪
没用，因为它什么都不返回。
-
我的结论是有两种构建软件的方法
设计：一种方法是使它变得如此简单以至于显然没有缺陷，而另一种方法是使它变得如此复杂
没有明显的缺陷。 - C. A. R. Hoare
Due to a lack of resources, I have to translate the following recursive
function in its iterative form.
It''s a kind of dichotomic search.
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
char ret;
//ping over a range of addresses (all slaves with uid in the range from
start_uid to end_uid will reply)
ret = PingSlave(start_uid,end_uid);
if (start_uid == end_uid) //single item
{
if (ret == VALID_PING_REPLY)
AddUidToSlaveList(start_uid);
return;
}
if (ret == VALID_PING_REPLY)
{
SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
//left subtree
SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
subtree
}
}
Any help will be greatly appreciated! :-)
Regards,
Marco
BQ <ba**********************@libero.invalid> wrote:
Due to a lack of resources, I have to translate the following recursive
function in its iterative form.
It''s a kind of dichotomic search.
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
char ret;
//ping over a range of addresses (all slaves with uid in the range from
start_uid to end_uid will reply)
ret = PingSlave(start_uid,end_uid);
if (start_uid == end_uid) //single item
{
if (ret == VALID_PING_REPLY)
AddUidToSlaveList(start_uid);
return;
}
if (ret == VALID_PING_REPLY)
{
SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
//left subtree
SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
subtree
[ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good
idea. ]
}
}
First thought: get rid of the premature optimisation, get rid of the
unnecessary object (yes, I do see the irony):
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
if (start_uid == end_uid) {
AddUidToSlaveList(start_uid);
return;
}
SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
SearchSlaves((start_uid+end_uid+1)/2, end_uid);
}
}
Second thought: while this algorithm is efficient if slaves are very
sparse, or relatively sparse and clustered within the range, this is
probably an efficient algorithm. Every slave is pinged several times,
though (log2(end_uid-start_uid) times, circa), so if there are many
slaves, this is not efficient. Nor is it optimal if there are a
reasonable number of slaves peppered through the range. If you suspect
one of those may be the case, a straightforward linear search may beat
this algorithm.
In fact, if PingSlave uses the obvious, naive algorithm for searching
its range, this already _is_ a linear search - several times over. One
other possibility would be to improve PingSlave''s efficiency, perhaps by
giving it a (resettable) memory.
Richard
Richard Bos wrote:
[ BTW, using C++-style comments _and_ tabs in a newsgroup is not a good
idea. ]
ehr, sorry.... :-)
First thought: get rid of the premature optimisation, get rid of the
unnecessary object (yes, I do see the irony):
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
if (PingSlave(start_uid,end_uid)==VALID_PING_REPLY) {
if (start_uid == end_uid) {
AddUidToSlaveList(start_uid);
return;
}
SearchSlaves(start_uid, (start_uid+end_uid+1)/2) - 1);
SearchSlaves((start_uid+end_uid+1)/2, end_uid);
}
}
Second thought: while this algorithm is efficient if slaves are very
sparse,
-- and this is the case: max.20/30 ''slaves'', sparse over a range 2^16 wide
or relatively sparse and clustered within the range, this is
probably an efficient algorithm. Every slave is pinged several times,
though (log2(end_uid-start_uid) times, circa), so if there are many
slaves, this is not efficient. Nor is it optimal if there are a
reasonable number of slaves peppered through the range. If you suspect
one of those may be the case, a straightforward linear search may beat
this algorithm.
in my situation, a straightforward linear search can''t be made.
Every ping has a 150ms timeout that can''t be reduced, and the
searchspace is very large.
In fact, if PingSlave uses the obvious, naive algorithm for searching
its range, this already _is_ a linear search - several times over.
Slaves answer to the ping if their uid is start_uid<= uid <= end_uid.
So searching 10/20 slaves requires about 2-3 seconds at most
Anyway, this code is compiled against a microprocessor with very limited
resources and I have a problem with stack that pushes me toward
searching an iterative version of this algorithm: I can make at most 32
subroutine calls, and SearchSlave calls itself at least 16 times in a
2^16 space. Since SearchSlave is not at level 0, I sometime obtain a
stack overflow.
By the way, theory assures that a recursive algorithm can always be
rewritten in an iterative way. If anyone has an idea...
Regards,
Marco
BQ wrote:
Due to a lack of resources, I have to translate the following recursive
function in its iterative form.
It''s a kind of dichotomic search.
void SearchSlaves(unsigned long start_uid, unsigned long end_uid)
{
char ret;
//ping over a range of addresses (all slaves with uid in the range from
start_uid to end_uid will reply)
ret = PingSlave(start_uid,end_uid);
if (start_uid == end_uid) //single item
{
if (ret == VALID_PING_REPLY)
AddUidToSlaveList(start_uid);
return;
}
if (ret == VALID_PING_REPLY)
{
SearchSlaves( start_uid , ( (start_uid + end_uid + 1) >> 1) - 1 );
//left subtree
SearchSlaves( ( (start_uid + end_uid + 1) >> 1) , end_uid); //right
subtree
}
}
Any help will be greatly appreciated! :-)
Regards,
Marco
You might start by making it easy for people to help you. 8 char
indents are excessive, // comments don''t survive line wrapping
well, and any linelength over about 72 is likely to cause a problem
on newsgroups. Do not use tabs, use spaces. Include dummy
functions for the undefined things, so that people can compile it
immediately. As it is the SearchSlaves operation seems singularly
useless, since it returns nothing.
--
"I conclude that there are two ways of constructing a software
design: One way is to make it so simple that there are obviously
no deficiencies and the other way is to make it so complicated
that there are no obvious deficiencies." -- C. A. R. Hoare
这篇关于从递归到迭代的翻译的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
