logo
Redian新闻
>未名空间
>Programming - 葵花宝典
>
【C++算法求助】有个O(n*n)的算法不知道该怎么优化并且并行化计算
avatar
【C++算法求助】有个O(n*n)的算法不知道该怎么优化并且并行化计算# Programming - 葵花宝典
m*c
1 楼
需要系里的人填的表上有两个问题：
Positions minimum required experience. Please quantify in number of years.
Positions minimum required training other than which would or could haven
benn obtained during the normal course of the degree program listed above.
Please quantify.
跟国际办公室的人谈过，说是不能按我的情况填，应该按照一般打广告的要求。问题是
招我时并没有工
作经验的的要求。我觉得第一个问题应该含读博士的阶段，选4年或5年， 第二个问题
是工作经验，选1
年或两年是不是比较合理的？
系主任和小米都是新的， 对H-1b申请不熟。发e-mail问国际办公室以前办的H-1b大约
是几年，不
回。HR的人推皮球到国际办公室。这两个问题可能不是很重要， 不过还是稳妥点好。
谢谢了。
avatar
m*u
2 楼
第一次玩印度B, 裸币不会看品相, 不知道乔五的王冠上到底是弱打还是wear.
咬咬牙用克劳斯上BU的目录价拿下了.
第一个猜对分数的给包子...
avatar
m*a
3 楼
这个是比较新的相声版本，配上皮影戏更有看头了
avatar
m*d
4 楼
北京广仁宫[西顶庙] - 国家纵容的骗子[社会]
刚和男友从国内回来，与父母在北京跟着旅游团玩了几天。 www.6park.com
在北京第3天的时候， 小导游带着我们这个团32人来到了广仁宫，也叫西顶庙，说是北
京的第一财位，国家领导人及各位富裕人士必去的求神宝地，他还在车上教我们如何祭
拜。 www.6park.com
刚一下车，就看到大概有4-5个旅游团已经在那等候着入庙， 我们等了将近5分钟，有
个穿制服的人领着我们入了庙，并介绍了这座庙的历史。不久我们进了一间很普通的屋
子，有个中年妇女自称是玄学研究院的院长向我们介绍了墙上摆设的建筑图片和风水的
应用。然后又领着我们摸了貔貅，说是一定要把财气摸回家。 紧接着她就带着我们进
了房间，里面摆放着各式各样的貔貅，价格从￥100 到上万元不等，另外还有一男一女
分别自称是玄学的教授和资深的道士， 同时再次介绍了貔貅。 www.6park.com
我男友对貔貅不感兴趣，我老爸又在宾馆休息，只有我和我妈就跟着大队伍一起看待售
的貔貅，突然那个道士对我说我的面相很好，但今年我有大灾，我爸生意不会顺等，得
请个貔貅回家消灾启福，而且小的还不
avatar
c*n
5 楼
说来比较悲催 非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都还没下载配置呢！
不知道从你们的经验看来，这样做是否可行？或者哪里我还遗漏了没考虑到
avatar
l*6
6 楼
64
avatar
o*l
7 楼
jp:怎么说那是国家的寺庙
avatar
N*K
8 楼
没看懂你说的啥 你计算的部分有没有可以解耦和的？
先从计算角度分析 再考虑编程
比如 水文的模拟，计算流域面积 是否可以分区计算 ？

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的指针，遍
avatar
f*n
9 楼
猜65
不过两面好像都有划痕啊
avatar
m*l
10 楼
有钱人还是多阿
avatar
N*t
11 楼
就是计算每个节点的流域面积吗？如果是，这实际上是个很简单的问题，接近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的指针，遍
avatar
i*t
12 楼
搭车做广告，给大家推荐5d兔，拍照效果老好了
avatar
d*a
13 楼
我也觉得是这样。简单地说，就是有向无环图的广度优先搜索吧。

【在 N*******t 的大作中提到】
: 就是计算每个节点的流域面积吗？如果是，这实际上是个很简单的问题，接近O(n)复杂
: 性吧。简单地说就是，把那些节点连成有向图，然后先历遍所有叶子节点（最上游节点
: ），计算它们的流域面积（就是节点面积），然后历遍那些已计算流域面积的节点的下
: 游节点，对那些它们所有上游节点都已计算流域面积的节点计算流域面积（就是把上有
: 节点的流域面积加起来再加上它自己的节点面积）。然后按这个方法依次历遍下游节点
: ，计算流域面积。希望没理解错楼主的问题。
:
: node
avatar
m*u
14 楼
多少钱啊?

【在 i******t 的大作中提到】
: 搭车做广告，给大家推荐5d兔，拍照效果老好了
avatar
m*u
15 楼
包子发了!

【在 l*******6 的大作中提到】
: 64
avatar
i*t
16 楼
今天的deal啊，2500块

【在 m*****u 的大作中提到】
: 多少钱啊?
avatar
m*u
17 楼
太贵了, 55555555555

【在 i******t 的大作中提到】
: 今天的deal啊，2500块
avatar
i*t
18 楼
你的九牛一毛啦

【在 m*****u 的大作中提到】
: 太贵了, 55555555555
avatar
p*u
19 楼
顶!
avatar
g*n
20 楼
印度B都开始搞了，生意红火
avatar
m*u
21 楼
今年的印度B就是去年的中国B啊. 补过印度B确实要比中国币稀少很多很多.

【在 g******n 的大作中提到】
: 印度B都开始搞了，生意红火
avatar
g*n
22 楼
你这个B商太不专一了，哪里有利润往哪里跑，跟我们收藏家一点不一样

【在 m*****u 的大作中提到】
: 今年的印度B就是去年的中国B啊. 补过印度B确实要比中国币稀少很多很多.
avatar
N*7
23 楼
美凤没有送你一个？

【在 i******t 的大作中提到】
: 你的九牛一毛啦
avatar
a*o
24 楼
66

【在 m*****u 的大作中提到】
: 第一次玩印度B, 裸币不会看品相, 不知道乔五的王冠上到底是弱打还是wear.
: 咬咬牙用克劳斯上BU的目录价拿下了.
: 第一个猜对分数的给包子...
avatar
g*n
25 楼
上面那个说64的都领包子了。

【在 a*o 的大作中提到】
: 66
avatar
a*o
26 楼
5555

【在 g******n 的大作中提到】
: 上面那个说64的都领包子了。
avatar
w*o
27 楼
你这个66太不靠谱

【在 a*o 的大作中提到】
: 5555
avatar
m*u
28 楼
第一次玩印度B, 裸币不会看品相, 不知道乔五的王冠上到底是弱打还是wear.
咬咬牙用克劳斯上BU的目录价拿下了.
第一个猜对分数的给包子...
avatar
l*6
29 楼
64
avatar
f*n
30 楼
猜65
不过两面好像都有划痕啊
avatar
i*t
31 楼
搭车做广告，给大家推荐5d兔，拍照效果老好了
avatar
m*u
32 楼
多少钱啊?

【在 i******t 的大作中提到】
: 搭车做广告，给大家推荐5d兔，拍照效果老好了
avatar
m*u
33 楼
包子发了!

【在 l*******6 的大作中提到】
: 64
avatar
i*t
34 楼
今天的deal啊，2500块

【在 m*****u 的大作中提到】
: 多少钱啊?
avatar
m*u
35 楼
太贵了, 55555555555

【在 i******t 的大作中提到】
: 今天的deal啊，2500块
avatar
i*t
36 楼
你的九牛一毛啦

【在 m*****u 的大作中提到】
: 太贵了, 55555555555
avatar
p*u
37 楼
顶!
avatar
g*n
38 楼
印度B都开始搞了，生意红火
avatar
m*u
39 楼
今年的印度B就是去年的中国B啊. 补过印度B确实要比中国币稀少很多很多.

【在 g******n 的大作中提到】
: 印度B都开始搞了，生意红火
avatar
g*n
40 楼
你这个B商太不专一了，哪里有利润往哪里跑，跟我们收藏家一点不一样

【在 m*****u 的大作中提到】
: 今年的印度B就是去年的中国B啊. 补过印度B确实要比中国币稀少很多很多.
avatar
N*7
41 楼
美凤没有送你一个？

【在 i******t 的大作中提到】
: 你的九牛一毛啦
avatar
a*o
42 楼
66

【在 m*****u 的大作中提到】
: 第一次玩印度B, 裸币不会看品相, 不知道乔五的王冠上到底是弱打还是wear.
: 咬咬牙用克劳斯上BU的目录价拿下了.
: 第一个猜对分数的给包子...
avatar
g*n
43 楼
上面那个说64的都领包子了。

【在 a*o 的大作中提到】
: 66
avatar
a*o
44 楼
5555

【在 g******n 的大作中提到】
: 上面那个说64的都领包子了。
avatar
w*o
45 楼
你这个66太不靠谱

【在 a*o 的大作中提到】
: 5555
相关阅读
big data讲究四个v科技日新月异，知识淘汰如换衣履，微软说自己是良b，所有人都笑了请教 一个c++ lambda function 的问题你妈用VS写个helloworld真难啊。A家一个system designe, 求大牛指点求建议：商业数据使用看最近的争论,深深感到大家对C++还是不熟悉啊ood和oop在概念上有什么区别？没有大牛去开个FP版吗Hacker news 有人在污蔑中国 made routerC++怎么定义1列random number generatorsword真他妈的坑爹一般操作很多的数据用什么数据结构？专访Mozilla宫力--这个大叔也满嘴跑火车啊开源要牛人，老型笑了discussion: why do we need entry_points in python (setup_t (转载)有什么好的histogram算法吗？苹果的OS X为什么从Mach内核转用BSD内核？吐槽MS Visual Studio
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。