グラフ間のいくつかの接続をランダムに生成する小さなプログラムを開発しました（カウントの値もランダムにすることができますが、テストの目的のためにconst valueを定義しました。いつでもランダム値で再定義できます）。
コードは C# です: http://ideone.com/FDCtT0
( 結果: 成功時間: 0.04 秒 メモリ: 36968 kB 戻り値: 0 )
隣接行列がわからない場合は、ここにアクセスしてください: http://en.wikipedia.org/wiki/Adjacency_matrix
私のコードのバージョンはかなり最適化されていないと思います。サイズが10k x 10kの大きな行列で作業する場合。
あなたの提案は何ですか?このタスクで計算を並列化するにはどうすればよいですか? 大規模な行列でのマルチスレッド計算には、セマフォなどのロッカー モデルを使用する必要があります。
プログラムのアーキテクチャを再設計するための提案は何ですか。大規模なマトリックス用にどのように準備すればよいですか?
ご覧のとおり、上のideoneでは、time 実行パラメーターと RAM に割り当てられたメモリを示しています。私のプログラムの実行の漸近値は何ですか? O(n^2)ですか？
だから私はあなたのアドバイスを聞きたいです漸近マーク、セマフォを使用した並列計算（またはスレッドのより良いロッカーモデル）を増やす方法。
ありがとうございました！
PS: SO では、フォーマットされたコードなしでトピックを投稿することは許可されていないため、最後に投稿しています (完全なプログラム):
/*
Oleg Orlov, 2012(c), generating randomly adjacency matrix and graph connections
*/
using System;
using System.Collections.Generic;
class Graph
{
internal int id;
private int value;
internal Graph[] links;
public Graph(int inc_id, int inc_value)
{
this.id = inc_id;
this.value = inc_value;
links = new Graph[Program.random_generator.Next(0, 4)];
}
}
class Program
{
private const int graphs_count = 10;
private static List<Graph> list;
public static Random random_generator;
private static void Init()
{
random_generator = new Random();
list = new List<Graph>(graphs_count);
for (int i = 0; i < list.Capacity; i++)
{
list.Add(new Graph(i, random_generator.Next(100, 255) * i + random_generator.Next(0, 32)));
}
}
private static void InitGraphs()
{
for (int i = 0; i < list.Count; i++)
{
Graph graph = list[i] as Graph;
graph.links = new Graph[random_generator.Next(1, 4)];
for (int j = 0; j < graph.links.Length; j++)
{
graph.links[j] = list[random_generator.Next(0, 10)];
}
list[i] = graph;
}
}
private static bool[,] ParseAdjectiveMatrix()
{
bool[,] matrix = new bool[list.Count, list.Count];
foreach (Graph graph in list)
{
int[] links = new int[graph.links.Length];
for (int i = 0; i < links.Length; i++)
{
links[i] = graph.links[i].id;
matrix[graph.id, links[i]] = matrix[links[i], graph.id] = true;
}
}
return matrix;
}
private static void PrintMatrix(ref bool[,] matrix)
{
for (int i = 0; i < list.Count; i++)
{
Console.Write("{0} | [ ", i);
for (int j = 0; j < list.Count; j++)
{
Console.Write(" {0},", Convert.ToInt32(matrix[i, j]));
}
Console.Write(" ]\r\n");
}
Console.Write("{0}", new string(' ', 7));
for (int i = 0; i < list.Count; i++)
{
Console.Write("---");
}
Console.Write("\r\n{0}", new string(' ', 7));
for (int i = 0; i < list.Count; i++)
{
Console.Write("{0} ", i);
}
Console.Write("\r\n");
}
private static void PrintGraphs()
{
foreach (Graph graph in list)
{
Console.Write("\r\nGraph id: {0}. It references to the graphs: ", graph.id);
for (int i = 0; i < graph.links.Length; i++)
{
Console.Write(" {0}", graph.links[i].id);
}
}
}
[STAThread]
static void Main()
{
try
{
Init();
InitGraphs();
bool[,] matrix = ParseAdjectiveMatrix();
PrintMatrix(ref matrix);
PrintGraphs();
}
catch (Exception exc)
{
Console.WriteLine(exc.Message);
}
Console.Write("\r\n\r\nPress enter to exit this program...");
Console.ReadLine();
}
}