我怎样才能加速这个图形算法？
完全公开:我写这篇文章是作为hackerrank.com挑战的一部分。
作为我算法的一部分，我必须获取一个对的列表，并生成一个集合列表。每一对表示两个节点之间的链接，每个集合表示相互链接(直接和间接)的所有节点。
这些对是以列表的形式出现的，因为它们就是这样生成的，我不想浪费时间在元组中对它们进行重装箱。此外，不可辩驳的模式消除了大部分这种开销。
import Data.List
import Data.Maybe
import qualified Data.IntSet as IS (fromList)
mkgroups :: [[Int]] -> [IntSet]
mkgroups = foldl' add2gc []
where
-- if a group is not found, create a new group
add2gc [] is = [IS.fromList is]
-- for the current group,
add2gc (g:gc) ~is@[i1, i2]
-- if either mates in group, add to group.
| i1 `IS.member` g = merge2gc i2 g gc
| i2 `IS.member` g = merge2gc i1 g gc
-- otherwise try next group
| otherwise = g : add2gc gc is
-- merge other inmate to appropriate group
merge2gc i g gc
-- in original group, return original group
| i `IS.member` g = g:gc
| otherwise = case part (IS.member i) gc of
-- in any other group, merge that group with this.
(Just g',gs) -> (IS.union g g') : gs
-- otherwise add innmate to this group
_ -> (IS.insert i g):gc我需要一个函数来返回第一个匹配和所有不匹配实体的列表，而不是partition。使用此函数而不是分区将算法从O(n^2)改为O(n*log n)，摊销(并使我的运行时减少了15%)。
part p as = go as []
where
go [] ps = (Nothing, ps)
go (a:as) ps = if p a
then (Just a, ps ++ as)
else go as (a:ps)我也尝试为这项工作选择最佳的数据结构。最初，这些组是[[Int]]，实际上工作得很好(迁移到[IntSet]只提高了30%的运行时)。
不过，我还是得让这件事更快些。我的最后一次测试是在8秒内超时，并且我对测试背后的输入数据没有可见性。这可能是一条最糟糕的道路，甚至只是一大团数据。我已经尝试了几乎所有我所知道的使这更快，即使使用我的知识，将始终有2个元素在内部输入列表，以使一个匹配无可辩驳。目前，我正在尝试让我的本地GHC安装和包重新使用分析数据来尝试并深入分析代码。
有什么我还没试过的Haskell大师们能看到或想到的东西吗？
编辑：--我认为我目前使用的算法是对我心目中目标的合理解释，尽管它在set insert上存在大量复制问题。因此，多亏了@fizruk et。我使用标准库中的Data.Graph进行了重新实现。
import Data.Tree as T
import Data.Graph as G
mkgroups :: Int -> [(Int,Int)] -> Forest Vertex
mkgroups n = filter ((>1) . length . T.flatten) . G.components . G.buildG (0,n)这很好地完成了这项工作，并且运行得更快(大约4倍)。感谢每一个帮忙的人。我决定将答案授予@phil_20686，因为在阅读了库源代码之后，他的回答似乎最接近于库的实际工作。
回答 2
Stack Overflow用户
发布于 2014-05-21 11:04:09
一旦构建了适当的数据结构，就可以使用广度优先或深度优先搜索在线性时间内解决这个问题。
然而，构造数据结构在时间或内存上都不一定是微不足道的。例如，您可以将任何元素放入一对多任务中(一个用于传入，一个用于传出)。然后，只需转到适当的键，并获取所有连接的节点，就可以实现BFS。如果你把它们从地图上删除，你就确保自己不会重复。
由于映射是在值(节点)数上以线性时间构造的，而BFS在边数上是线性的，因此性能将是O(E+V)。
Stack Overflow用户
发布于 2014-05-21 14:40:55
联合查找算法是针对一个密切相关的问题而设计的。黑客搜索建议有几个实现此算法的包，您可能有兴趣签出这些包。然而，正如在下面的注释中所讨论的，“密切相关”这个词实际上是负载--在本例中是: union-find解决了一个稍微困难的问题，因此实际上并不是最优的。也就是说，给定图中的两个节点，联合查找结构将能够最优地快速地告诉您它们是否是同一个连接组件的一部分。
https://stackoverflow.com/questions/23779696
复制相似问题
腾讯云开发者
