c# - 读取文本文件并从中创建多维数组
问题描述
我想读取一个 txt 文件并以下列形式创建一个多维 int 数组：
var graph = new[,]
{
// 0 1 2 3 4 5 6 7 8 9 10 11...n
{ 0, 0, 0, 0, 0, 0, 10, 0, 12, 0, 0, 0 }, // 0
{ 0, 0, 0, 0, 20, 0, 0, 26, 0, 5, 0, 6 }, // 1
{ 0, 0, 0, 0, 0, 0, 0, 15, 14, 0, 0, 9 }, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0 }, // 3
{ 0, 20, 0, 0, 0, 5, 17, 0, 0, 0, 0, 11 }, // 4
{ 0, 0, 0, 0, 5, 0, 6, 0, 3, 0, 0, 33 }, // 5
{10, 0, 0, 0, 17, 6, 0, 0, 0, 0, 0, 0 }, // 6
{ 0, 26, 15, 0, 0, 0, 0, 0, 0, 3, 0, 20 }, // 7
{12, 0, 14, 0, 0, 3, 0, 0, 0, 0, 0, 0 }, // 8
{ 0, 5, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 }, // 9
{ 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0 }, // 10
{ 0, 6, 9, 0, 11, 33, 0, 20, 0, 0, 0, 0 }, // 11..n
};
这应该表示图中的节点并且彼此之间存在距离。我的 txt 文件看起来像这样（图片和图形值不匹配）：
第一个值是开始节点，第二个值是结束节点，第三个值应该是距离。所以表中行的索引是现有的起始节点，如果节点之间没有直接连接，则字段中的值应该是0，或者如果存在直接连接，它应该与txt文件有距离。列的索引应该是所有结束节点。
我是这样开始的：
using (var reader = new StreamReader(@"USA-road-d.CAL.gr"))
{
while (!reader.EndOfStream)
{
var lineCount = File.ReadLines(@"USA-road-d.CAL.gr").Count();
var pre_graph = new int[lineCount];
//initialize array with 0s
Array.Clear(pre_graph, 0, pre_graph.Length);
string new_line;
while ((new_line = reader.ReadLine()) != null)
{
var values = new_line.Split(null);
pre_graph[int.Parse(values[2])] = int.Parse(values[3]);
}
}
}
var pre_graph = new int[lineCount];是错误的，因为有多个边。我只想将不同起始节点的计数作为数组长度。
我不知道如何得到这个。有人可以帮忙吗？
最后我想用这个图来实现dijkstra算法：
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
public static class DijkstraWithoutQueue
{
public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
{
var n = graph.GetLength(0);
var distance = new int[n];
for (int i = 0; i < n; i++)
{
distance[i] = int.MaxValue;
}
distance[sourceNode] = 0;
var used = new bool[n];
var previous = new int?[n];
while (true)
{
var minDistance = int.MaxValue;
var minNode = 0;
for (int i = 0; i < n; i++)
{
if (!used[i] && minDistance > distance[i])
{
minDistance = distance[i];
minNode = i;
}
}
if (minDistance == int.MaxValue)
{
break;
}
used[minNode] = true;
for (int i = 0; i < n; i++)
{
if (graph[minNode, i] > 0)
{
var shortestToMinNode = distance[minNode];
var distanceToNextNode = graph[minNode, i];
var totalDistance = shortestToMinNode + distanceToNextNode;
if (totalDistance < distance[i])
{
distance[i] = totalDistance;
previous[i] = minNode;
}
}
}
}
if (distance[destinationNode] == int.MaxValue)
{
return null;
}
var path = new LinkedList<int>();
int? currentNode = destinationNode;
while (currentNode != null)
{
path.AddFirst(currentNode.Value);
currentNode = previous[currentNode.Value];
}
return path.ToList();
}
public static void Main()
{
var graph = new[,]
{
// 0 1 2 3 4 5 6 7 8 9 10 11
{ 0, 0, 0, 0, 0, 0, 10, 0, 12, 0, 0, 0 }, // 0
{ 0, 0, 0, 0, 20, 0, 0, 26, 0, 5, 0, 6 }, // 1
{ 0, 0, 0, 0, 0, 0, 0, 15, 14, 0, 0, 9 }, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0 }, // 3
{ 0, 20, 0, 0, 0, 5, 17, 0, 0, 0, 0, 11 }, // 4
{ 0, 0, 0, 0, 5, 0, 6, 0, 3, 0, 0, 33 }, // 5
{10, 0, 0, 0, 17, 6, 0, 0, 0, 0, 0, 0 }, // 6
{ 0, 26, 15, 0, 0, 0, 0, 0, 0, 3, 0, 20 }, // 7
{12, 0, 14, 0, 0, 3, 0, 0, 0, 0, 0, 0 }, // 8
{ 0, 5, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 }, // 9
{ 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0 }, // 10
{ 0, 6, 9, 0, 11, 33, 0, 20, 0, 0, 0, 0 }, // 11
};
PrintPath(graph, 0, 2);
PrintPath(graph, 0, 10);
PrintPath(graph, 0, 11);
PrintPath(graph, 0, 1);
}
public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
{
Console.Write(
"Shortest path [{0} -> {1}]: ",
sourceNode,
destinationNode);
var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);
if (path == null)
{
Console.WriteLine("no path");
}
else
{
int pathLength = 0;
for (int i = 0; i < path.Count - 1; i++)
{
pathLength += graph[path[i], path[i + 1]];
}
var formattedPath = string.Join("->", path);
Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
}
}
}
解决方案
我在 GitHub 上为你准备了一个解决方案，
使用 1890815x1890815 矩阵的数组联机不是一个好主意。表示这样一个数组 (1890815x1890815x4x2) 大约需要 28 601 450 MB，或者您需要使用 28 PB 内存的解决方案。
我想您将永远无法为美国路线图创建实体矩阵，因为您可能需要大约 1T 的 DDR 内存（经过优化）或 28 PB（包括零），我为您准备了 Visual Studio 解决方案（需要 VS2019 预览版）打开项目）：
这是一个好消息，如果忘记了 28 PB 的要求，您可以创建和使用连接矩阵 (C# 8.0) 从文件加载数据并在大约 5 秒内创建节点和边的树结构。
5.6 秒从内存中的档案加载所有美国道路，并验证结构
static class Program
{
static async Task Main(string[] args)
{
using (var archive = ZipFile.OpenRead(args[0]))
{
var entry = archive.Entries.Where(_ => _.FullName.Equals("USA-road-d.CAL.gr", StringComparison.OrdinalIgnoreCase)).FirstOrDefault();
if (entry != null)
{
var stopwatch = new Stopwatch();
stopwatch.Start();
var data = new List<string>(Decompress(entry.Open()));
var graph = new Graph(data);
stopwatch.Watch();
Console.ReadLine();
}
}
}
public static IEnumerable<string> Decompress(Stream stream)
{
using (var reader = new StreamReader(stream, Encoding.ASCII))
{
string line;
while ((line = reader.ReadLine()) != null)
{
yield return line;
}
}
}
public class Edge
{
public Edge(Graph graph, Node v1, Node v2, int distance, bool isDirectional = false)
{
Graph = graph;
V1 = v1;
V2 = v2;
Distance = distance;
v1.AddEdge(this);
if (!IsDirectional)
v2.AddEdge(this);
}
internal Graph Graph { get; }
public Node V1 { get; }
public Node V2 { get; }
public int Distance { get; }
public bool IsDirectional { get; }
}
public class Node
{
static int counter = 0;
readonly List<Edge> _edges = new List<Edge>();
public Node(Graph graph, int index)
{
Graph = graph;
Index = index;
Number = counter++;
}
internal Graph Graph { get; }
public int Index { get; }
public int Number { get; }
public IEnumerable<Edge> Edges => _edges;
public void AddEdge(Edge edge) => _edges.Add(edge);
}
public class Graph
{
Dictionary<int, Node> _nodes { get; } = new Dictionary<int, Node>();
readonly Parameters _parameters;
readonly List<Edge> _edges;
readonly List<string> _comments;
public IParameters Parameters => _parameters;
public IEnumerable<Edge> Edges => _edges;
public IEnumerable<string> Comments => _comments;
public Node GetNode(int index) => _nodes.ContainsKey(index) ? _nodes[index] : (_nodes[index] = new Node(this, index));
public Graph(IEnumerable<string> lines, bool isDirectional = false)
{
IEnumerable<string> parameters = new List<string>(lines.Where(_ => _[0] == 'p'));
IEnumerable<string> edges = new List<string>(lines.Where(_ => _[0] == 'a'));
IEnumerable<string> comments = new List<string>(lines.Where(_ => _[0] == 'c'));
_parameters =
parameters
.Select(_ => _.Split(' '))
.Select(_ => _[1] == "sp" ? new Parameters(int.Parse(_[2]), int.Parse(_[3])) : null).FirstOrDefault();
_edges =
edges
.Select(_ => _.Split(' '))
.Select(_ => new Edge(this, GetNode(int.Parse(_[1])), GetNode(int.Parse(_[2])), int.Parse(_[3]), isDirectional))
.ToList();
_comments =
comments
.Select(_ => _.Substring(1)).ToList();
if (_parameters.Nodes != _nodes.Keys.Count)
{
throw new Exception("invalid nodes count");
}
if (_parameters.Edges != _edges.Count)
{
throw new Exception("invalid edges count");
}
}
}
public interface IParameters
{
int Nodes { get; }
int Edges { get; }
}
public class Parameters: IParameters
{
public int Nodes { get; }
public int Edges { get; }
public Parameters(int nodes, int edges)
{
Nodes = nodes;
Edges = edges;
}
}
}
public static class StopwatchExtensions
{
public static void Watch(this Stopwatch stopwatch, string message = "",
[CallerMemberName] string memberName = "",
[CallerFilePath] string sourceFilePath = "",
[CallerLineNumber] int sourceLineNumber = 0) =>
Console.WriteLine(
$"{stopwatch.Elapsed} " +
$"{message} " +
$"{memberName} " +
$"{sourceFilePath}:{sourceLineNumber}");
}
推荐阅读
- rest - 如何过滤不存在属性的 OData 集合？
- python-3.x - Atom 找不到 discord 和 asyncio
- java - 对 Spring Boot 的 Angular HTTP POST 请求导致空值
- javascript - Node.js - 收到 Promise 后渲染
- mysql - 线程未返回所有订阅用户
- javascript - LobiPanel 不会从 localStorage 加载引导面板位置
- google-apps-script - 在 Google Apps 脚本中，有没有办法根据表单数据创建新选项卡，然后将数据从多个工作表复制到新创建的选项卡中？
- vue.js - 从 jQuery 转换为 Vue？
- go - 使用 Gmail API 检索邮件正文
- android - 将 sqlite 数据从一个活动发送到另一个活动