Tag: 数据结构

从C＃中的大型数据结构中释放内存

我的模拟代码中有一些SortedList和SortedDictionary结构，随着时间的推移，我会在其中添加数百万个项目。 问题是垃圾收集器没有快速释放足够的内存，因此应用程序的性能受到很大影响。 我的最后一个选择是使用GC.Collect()方法，以便我可以回收那个内存。 有没有人有不同的想法？ 我知道Flyweight模式是另一种选择，但我希望其他建议不需要对我的代码进行大量重构。

三角网格的良好数据结构

我正在为三维网格或由三角形组成的面集寻找一种节省内存且方便的数据结构。 目前我正在使用这种“经典”结构： 点列表和三角形列表。 每个点都有X，Y和Z值。 每个三角形有三个索引i0，i1，i2，它们指的是点列表中的一个点。 这是我能想到的最紧凑的布局。 如果我想做的就是绘制网格，并且永远不会修改或过滤它，这是完美的。 但是，它确实使大多数操作修改网格或生成新的部分网格非常麻烦，例如： 删除三角形是非常低效的。 仅生成少于3个邻居的三角形的新网格 查找并删除在给定边界框内具有一个或所有点的所有三角形 找到具有一定角度的所有边缘 去除短于一定长度的所有边缘 基本上任何需要修改网格，或迭代边缘或找到相邻面/边缘的东西，都需要生成和丢弃几个临时字典和散列集。 没有简单的方法可以迭代单个面的点或边，或单个点周围的边/面。 删除一个点意味着从每个三角形中删除它，然后更改所有三角形中所有其他点的索引值等。 是否有规范的数据结构没有这些缺点，但是内存效率高？ 我不是在寻找一个完整的库，只是一个我自己可以实现的结构（尽管了解特定库如何解决这个问题可能很有趣）

二进制搜索和哈希表搜索

我想找出一个字典查找和一个数组的二进制搜索查找之间的权衡点。 我期待着字典的恒定时间查找，以及二进制搜索的对数时间查找，具体取决于集合的大小，二进制搜索对于较小的集合表现更好。 但是，当我看到以下结果时，我感到很惊讶： 我很惊讶：1。二进制搜索首先以对数方式增长，然后增长得更快。 哈希起初非常一致，但随后开始慢慢增长。 3.二进制搜索永远不会比哈希查找更好。 以下是我的代码。 我做错了什么？ class Program { static void Main(string[] args) { var r = new Random(); var targets = Enumerable.Range(0, 1000 * 1000).Select(_ => r.Next(int.MaxValue)).ToList(); for (int totalCount = 1; totalCount r.Next(int.MaxValue)).Distinct().Select(v => new thing(v)).OrderBy(t => t.value).ToArray(); var d = a.ToDictionary(t => t.value); var watch = new System.Diagnostics.Stopwatch(); { watch.Start(); […]

我的示例中使用什么数据结构

我想创建一个组件，它由一块板和它的周围角落组成。 板的大小（因此也是边界的大小）在运行时定义。 一些例子（板子很亮，边框很暗）： 替代文字http://img340.imageshack.us/img340/3862/examplegw.png 该板由BoardCell类型的对象组成，边界由BorderCell类型的对象组成。 电路板的数据结构是BoardCell [，] – 一个简单的二维数组。 我怎样才能代表边界？ 我从这样的事情开始： public BorderCell TopLeft // top left corner cell public BorderCell TopRight // top right corner cell public BorderCell BottomRight // bottom right corner cell public BorderCell BottomLeft // bottom left corner cell public BorderCell[] Top // top border (without corners) public BorderCell[] Bottom // […]

在C＃中为数组分配新结构时会发生什么？

假设我有一个C＃结构： struct Foo{ int mA; public int A {get {return mA;}} int mB; public int B {get {return mB;}} public Foo(int a, int b) { mA = a; mB = b; } } 然后我创建了Foo的数组： Foo[] foos = new Foo[10]; 我这样做会发生什么？ foos[1] = new Foo(20, 10); 如果Foo是一个类，Foo []会在堆上保存一个指向Foo对象的指针，并且该指针将被更改为新的Foo对象（旧的对象被留下来进行回收）。 但由于结构是值类型，新的Foo（20,10）是否会物理覆盖以前由foos [1]持有的相同内存位置？

C＃：避免if（x为Foo）{…} else if（x is Bar）{…}用于数据结构

我有一系列数据结构，如： abstract class Base {…} class Foo : Base {…} class Bar : Base {…} 以及一个接受Base并根据它的子类转换它的方法： void Convert(Base b) { if (b is Foo) // Do the Foo conversion else if (b is Bar) // Do the Bar conversion … 显然这是一个糟糕的面向对象 – 转换方法必须知道Base的每个派生类，并且必须在每次扩展Base时进行更改。 解决这个问题的“正常”OO方法是使每个派生类的Base负责转换自身，例如 abstract class Base { abstract Converted Convert(); …} class Foo : […]

如何建立一个和 – 或树？

我需要一个支持“和”和“或”的树结构。 例如，给定像ab|c(d|e)这样的正则表达式，我想将其转换为树。 所以，起初我们有两个“或”分支……它可以向下走，也可以向下走c(d|e) 。 如果你沿着ab分支ab ，你会得到两个节点， a 和 b （或者a后跟b ，无论如何）。 然后，如果你去c(d|e)分支，你得到c 和 (d|e) ，然后(d|e)被分成d 或 e 。 制作树形结构很容易，你只需要类似的东西 class Node { string element; Node[] children; } 但那么你怎么知道这些孩子应该“得到”还是“”？ 我想树的每个级别应该在“anding”和“oring”之间交替 那有意义吗？ 任何人都可以为此建议一个结构吗？ 有些人建议在节点上存储“操作员”，这很好，但是没有办法利用每个级别总是交替的事实，或者，和，和……？ 编辑：不太确定为什么人们会认为这是一棵二叉树。 事实并非如此 。 我希望这个小小的代码片段会让你失望。 这个例子碰巧只有2个分支。 目前倾向于： abstract class Node { } class DataNode : Node { string data; } abstract class OpNode : […]

C＃数组还是字典？

我想知道C＃数组是否具有恒定的访问速度？ 我需要在静态数组中存储1000个项目，这些项目将在服务器启动期间初始化。 此数组将以只读方式使用，因此不会对数组进行任何更改。 我应该使用简单的C＃数组（新的MyClass []）或字典。 我是C＃的新手，并试图了解C＃数组访问是如何工作的。 它们可以通过速度与c ++数组进行比较吗？

交叉索引引用

对不起，如果标题令人困惑，我不确定我应该如何标记这个，我试过了。 我正在编写一个程序来进行一些交叉索引搜索，该程序是使用Visual Studio 2010用C＃编写的。 我有一个包含3列的表： Category ， Type和Item 。 该表从excel电子表格中读入并存储在某种数据结构中（稍后将对此进行说明）。 以下是该表的简短示例。 | CATEGORY | TYPE | ITEM | <<header row | categoryA | typeA | itemA | <<first entry | categoryA | typeB | N/A | | categoryA | typeC | itemB | | categoryA | typeD | N/A | 我将读取两个用户输入字符串，我希望程序确定它们是否匹配。 [假设用户输入没有拼写错误，我写了一个函数来处理这个并规范化两个字符串] 确定两个字符串是否匹配的逻辑如下： 1）如果字符串是CATEGORY ，则具有相同CATEGORY每个TYPE和ITEM都是匹配的。 […]

用于代码的元语言为ANSI-C和C＃Structs生成打包的结构

我正在尝试找到一种“元语言”，可用于定义结构和获取/设置成员的代码。 问题在于结构已经存在于代码中，并且这种“元语言”将用作原始手工编码结构的逐位替换，以允许生成描述结构的头部。 关键是这些结构被用作C＃应用程序和嵌入式设备之间的协议的一部分（不是基于Linux，认为更小，更像PIC或CM0那样受限制。）元语言将充当 结构成员的文档 为get / set操作生成C＃结构和实现 生成打包的ANSI-C结构和get / set函数 元语言需要支持 枚举定义（指定大小 – 即uint16_t，uint8_t或更小的多位枚举） 位数组（指定大小 – 即48位数组打包成6个字节） 位结构/枚举数组（指定大小 – 即48位索引的2位结构为12个字节） 字节序和位序的规范， 生成二进制结构，可以通过生成的ANSI-C代码或C-sharp代码直接读取，以便通过网络发送。 收到数据时对数据进行有限的validation也是很好的。 到目前为止，我已经看过了 BSON 蚀刻 Hessian Avro 冰 MessagePack 协议缓冲区 节约 所有这些都非常适合文档和构建新协议，但是试图保持与现有协议的兼容性，并且由于数据封送中固有的类型编码而导致这些协议不足。 我还查看了ASN.1的ECN编码，但这似乎太难以理解，导致文档出现问题。 我从C结构看了Generating C＃结构，但那里没有一个好的选择。 有什么建议？