c******n
发帖数: 16666 | 1 说来比较悲催 非cs专业，搞了个小程序跑模拟，数据量小的时候还好，数据量一大先
是内存挂了。后来跑去ec2租了个大内存服务器发现跑得还是很慢，仔细一看，有个
function算得特别慢，因为是n*n的复杂度，数据量上去了计算时间马上跳了等量级上
升。自己又是一知半解的，不知道哪位能帮着改进下算法然后提示下OpenMP该怎么做。
简而言之，是个关于水文的模拟，计算流域面积，所以数据的基本单位/对象就是node
。 有两个linked-list（求别吐槽用这个而不用vector，摊子摊太大了 改起来不容易
，或者如果我现在添加一个vector，复制现有list行不？）里面存的都是node之间的指
针。
第一个linked-list存的所有node的指针，按照node的ID存放，方便遍历所有node
第二个linked-list，其实不止一个，存的是所有在当前node的下游的node的指针，遍
历的话可以从当前node一直走到当前mesh的边界
流域面积的具体计算，就是当前node自己的面积加上其所有上有点面积的总和
比如在下图中，
a b c d e
| / |
f g h i j
| | /
k p m n o
p点最后的流域面积是a.area+g.area+p.area
m点最后的流域面积的是b.area+c.area+d.area+h.area+m.area
我现在的计算方法是
========================================================================
for( curnode = nodIter.FirstP(); nodIter.IsActive();
curnode = nodIter.NextP() ) //对有所有的node的一个iterator，只要是
active的（IsActive返回一个bool），iterator对应的是一个linked list， linked
list里面包含了对应node的pointer。
{
RouteFlowArea( curnode, curnode->getVArea() ); /
}
----------------------------------------------------------------
然后这个调用的function具体是
void tStreamNet::RouteFlowArea( tLNode *curnode, double addedArea )
{
// 判断只要没出界然后还是有效地，就算下去
while( (curnode->getBoundaryFlag() == kNonBoundary) && //这边是while的
loop
(curnode->getFloodStatus()!=tLNode::kSink) )
{
curnode->AddDrArea( addedArea ); //AddDrArea是一个很简单的
inline function，返回“drarea +=value；
”
curnode = curnode->getDownstrmNbr(); // getDownstrmNbr()返回另一个
pointer，指向的是当前点 curnode下游的那个点
}
}
====================================================================
首先的问题就是现在的算法是n*n的，所以才会这么慢，
然后从我现在对多线程的理解，我觉得应该在第一个for loop那边就设置开始多线程，
然后分成几个线程来单独计算不同node的DrainageArea。
但是从图上就能看出，b-》h-》m和c-》h-》m 如果先后计算，因为DrArea + =
InputArea，应该没啥大问题。但是如果同时计算的话，数据肯定会乱掉。按照我刚才
填鸭看得文档，理论上处理这个应该用上OpenMP里面的 flush和lock，但是具体怎么用
还不知道，甚至我现在连openMP都还没下载配置呢！
不知道从你们的经验看来，这样做是否可行？或者哪里我还遗漏了没考虑到 |
N******K
发帖数: 10202 | 2 没看懂你说的啥 你计算的部分有没有可以解耦和的？
先从计算角度分析 再考虑编程
比如 水文的模拟，计算流域面积 是否可以分区计算 ？
node
【在 c******n 的大作中提到】
: 说来比较悲催 非cs专业，搞了个小程序跑模拟，数据量小的时候还好，数据量一大先
: 是内存挂了。后来跑去ec2租了个大内存服务器发现跑得还是很慢，仔细一看，有个
: function算得特别慢，因为是n*n的复杂度，数据量上去了计算时间马上跳了等量级上
: 升。自己又是一知半解的，不知道哪位能帮着改进下算法然后提示下OpenMP该怎么做。
: 简而言之，是个关于水文的模拟，计算流域面积，所以数据的基本单位/对象就是node
: 。 有两个linked-list（求别吐槽用这个而不用vector，摊子摊太大了 改起来不容易
: ，或者如果我现在添加一个vector，复制现有list行不？）里面存的都是node之间的指
: 针。
: 第一个linked-list存的所有node的指针，按照node的ID存放，方便遍历所有node
: 第二个linked-list，其实不止一个，存的是所有在当前node的下游的node的指针，遍
|
N*******t
发帖数: 66 | 3 就是计算每个节点的流域面积吗？如果是，这实际上是个很简单的问题，接近O(n)复杂
性吧。简单地说就是，把那些节点连成有向图，然后先历遍所有叶子节点（最上游节点
），计算它们的流域面积（就是节点面积），然后历遍那些已计算流域面积的节点的下
游节点，对那些它们所有上游节点都已计算流域面积的节点计算流域面积（就是把上有
节点的流域面积加起来再加上它自己的节点面积）。然后按这个方法依次历遍下游节点
，计算流域面积。希望没理解错楼主的问题。
node
【在 c******n 的大作中提到】
: 说来比较悲催 非cs专业，搞了个小程序跑模拟，数据量小的时候还好，数据量一大先
: 是内存挂了。后来跑去ec2租了个大内存服务器发现跑得还是很慢，仔细一看，有个
: function算得特别慢，因为是n*n的复杂度，数据量上去了计算时间马上跳了等量级上
: 升。自己又是一知半解的，不知道哪位能帮着改进下算法然后提示下OpenMP该怎么做。
: 简而言之，是个关于水文的模拟，计算流域面积，所以数据的基本单位/对象就是node
: 。 有两个linked-list（求别吐槽用这个而不用vector，摊子摊太大了 改起来不容易
: ，或者如果我现在添加一个vector，复制现有list行不？）里面存的都是node之间的指
: 针。
: 第一个linked-list存的所有node的指针，按照node的ID存放，方便遍历所有node
: 第二个linked-list，其实不止一个，存的是所有在当前node的下游的node的指针，遍
|
d***a
发帖数: 13752 | 4 我也觉得是这样。简单地说，就是有向无环图的广度优先搜索吧。
【在 N*******t 的大作中提到】
: 就是计算每个节点的流域面积吗？如果是，这实际上是个很简单的问题，接近O(n)复杂
: 性吧。简单地说就是，把那些节点连成有向图，然后先历遍所有叶子节点（最上游节点
: ），计算它们的流域面积（就是节点面积），然后历遍那些已计算流域面积的节点的下
: 游节点，对那些它们所有上游节点都已计算流域面积的节点计算流域面积（就是把上有
: 节点的流域面积加起来再加上它自己的节点面积）。然后按这个方法依次历遍下游节点
: ，计算流域面积。希望没理解错楼主的问题。
:
: node
|
