g*******y
发帖数: 1930 | 1 假设要做很多重循环，
比如有N个vector v1 v2...vN
要做的循环是：
for(v1.beg ... v1.end)
for(v2.beg ... v2.end)
....
for(vN.beg ... vN.end)
最佳的方式是怎么写好呢? | a**********s
发帖数: 588 | 2 一个方法是弄两个array, CurrentIndices[N], Sizes[N];
memset(CurrentIndices, 0, sizeof(CurrentIndices));
Sizes = {v1.size(), ..., vN.size()};
do {
....
} while(Next(CurrentIndices, Sizes, N));
bool Next(int CurrentIndices[], int Sizes[], int cnt)
{
int i = 0;
while (i < cnt && CurrentIndices[i] == Sizes[i]-1)
CurrentIndices[i++] = 0;
if (i == cnt)
return false;
CurrentIndices[i]++;
return true;
}
没有验证过, 不过我觉得这样也不怎么好 | g*******y
发帖数: 1930 | 3 for generality,假定不一样吧。
如果一样会更容易些吗？
每个单独的循环就是一个长度不等的数组的遍历吧。
一个简单常见的例子就是给一个手机号码，打印所有可能的string (假设每个数字有不
同数目的字母相对应)。
我的想法是，用单个整数循环， i = 1 ... product of all sizes, 然后对每个i，算
出一串indices，分别用于每个vector.
这样可以很简单写出来，但是效率不高。
【在 a**********s 的大作中提到】
: 一个方法是弄两个array, CurrentIndices[N], Sizes[N];
: memset(CurrentIndices, 0, sizeof(CurrentIndices));
: Sizes = {v1.size(), ..., vN.size()};
: do {
: ....
: } while(Next(CurrentIndices, Sizes, N));
: bool Next(int CurrentIndices[], int Sizes[], int cnt)
: {
: int i = 0;
: while (i < cnt && CurrentIndices[i] == Sizes[i]-1)
| p*********a
发帖数: 21 | 4 dfs
【在 g*******y 的大作中提到】
: 假设要做很多重循环，
: 比如有N个vector v1 v2...vN
: 要做的循环是：
: for(v1.beg ... v1.end)
: for(v2.beg ... v2.end)
: ....
: for(vN.beg ... vN.end)
: 最佳的方式是怎么写好呢?
| g*******y
发帖数: 1930 | 5 如果就是常规的DFS的话，树的大小 和 iteration的总数目成正比了吧？
【在 p*********a 的大作中提到】
: dfs
| a**********s
发帖数: 588 | 6 好像我上面的版本也不见得比你的版本快(少做了几次除法, 但是有很多branches), 不
过不用担心
overflow
这种是面试题的话, 大概就是面试管想看到的吧
【在 g*******y 的大作中提到】
: for generality,假定不一样吧。
: 如果一样会更容易些吗？
: 每个单独的循环就是一个长度不等的数组的遍历吧。
: 一个简单常见的例子就是给一个手机号码，打印所有可能的string (假设每个数字有不
: 同数目的字母相对应)。
: 我的想法是，用单个整数循环， i = 1 ... product of all sizes, 然后对每个i，算
: 出一串indices，分别用于每个vector.
: 这样可以很简单写出来，但是效率不高。
| g*******y
发帖数: 1930 | 7 如果就是常规的DFS的话，树的大小 和 iteration的总数目成正比了吧？
【在 p*********a 的大作中提到】
: dfs
| g*******y
发帖数: 1930 | 8 呵呵，你的方法正好是我想找的答案。
【在 a**********s 的大作中提到】
: 好像我上面的版本也不见得比你的版本快(少做了几次除法, 但是有很多branches), 不
: 过不用担心
: overflow
: 这种是面试题的话, 大概就是面试管想看到的吧
| p*********a
发帖数: 21 | 9 use stack to simulate the function call if you really care about overflow.
【在 g*******y 的大作中提到】
: 如果就是常规的DFS的话，树的大小 和 iteration的总数目成正比了吧？
|
|
