0

R でグラフ オブジェクト (igraph パ​​ッケージ) を使用しています。特定の頂点からグラフ内の他のすべての頂点への最短パスを提供する「get.shortest.paths()」という関数を適用します。このアルゴリズムは、リストの各要素がターゲット頂点に対応するリストを返し、ソースとターゲット間の最短パス上のすべての頂点の頂点インデックスを含みます。例えば;

head(get.shortest.paths(graph, from = V(graph)[1], to = V(graph), mode = "out"))
[[1]]
[1] 0 (source and target are the same)
[[2]]
[1]     0 91835 38405 89704     1
[[3]]
[1]     0 91835 12104 39002 22670     2
[[4]]
[1]     0 62386 36754 89246 31045     3

問題は、頂点インデックスから頂点名に移動したい場合です。このようなもの;

[[1]]
[1] "gene 1"
[[2]]
[1]     "gene 1"  "protein 45" "protein 83" "protein 70"     "gene 2"
[[3]]
[1]     "gene 1" "protein 45" "protein 30"  "reaction 2" "protein 404"     "gene 3"
[[4]]
[1]     "gene 1" "protein 4" "reaction 12" "protein 19"  "protein 494"   "gene 4"

lapply() を使用してこれを実行しようとしています

path.index.list <-  get.shortest.paths(graph, from = V(graph)[1], to = V(cn), mode = "out")
path.name.list <- lapply(path.index.list, FUN = function(path) V(graph)[path]$name)

...しかし、これには非常に長い時間がかかります。"for" ループも同様に長くかかります。実際、1 つのソース頂点から他の 100,000 以上の頂点すべてのインデックスから名前に変換するのに必要な正確な時間は...

system.time(lapply(path.index.list, FUN = function(path) V(graph)[path]$name))
  user  system elapsed
608.62  152.69  761.66

...グラフ全体で約900日になります。

これは「参照渡し」と「値渡し」の問題の 1 つですか? もしそうなら、誰かがそれを解決する方法を理解するのを手伝ってくれますか? このような問題を解決するために R でハッシュまたは環境関数を使用することを聞いたことがありますが、それについてコメントできますか? これに対処するのに役立つRのパッケージについても聞いたことがありますか?

基本的に、C でコーディングせずにこれを解決するにはどうすればよいでしょうか。

4

2 に答える 2

0

はい、私はもともと「Tamás」を使用して説明したlapplyメソッドを使用しました。反復ごとに約230秒（1000アイテムごとに約2秒）を取得しています。「fastmatch」パッケージをマトリックスを使用したメモリ割り当てと組み合わせて使用​​してみましたが、実際には速度が低下しました。私はこれを、Rがアイテムを検索してからメモリを検索する速度の問題であると解釈しました。これが実際に実用的であるためには、これを反復ごとに6秒未満に短縮する必要があります。私はCに行くと思います...

于 2012-06-18T19:53:20.087 に答える
0

事前に頂点の名前を照会し、次のようにインデックスを付けますlapply。

names <- V(graph)$name
lapply(path.index.list, FUN = function(path) names[path])

サブリストを選択するために毎回名前リストlapplyを作成する必要がないため、これははるかに高速になると思います。V(graph)

于 2012-06-16T08:14:01.133 に答える