Tag: 数据结构

使用什么样的数据结构？: 我正在开展一个需要跟踪的项目： 5-6只是字符串名称的根项每个根项都需要具有不同标识符类型的多个子项（int，string，float等）。一个根的所有子节点都是相同类型，但每个根节点将具有不同的子类型用户需要能够从每个根添加/删除子项我稍后需要单独访问每个孩子，并在需要时执行字符串操作和解析我想过可能会使用一个字典，其中Key是一个字符串，而Values是对象列表。或者每个根项都有一个唯一的类，每个类都包含一个子列表。有没有人有任何好的建议？我对OOP还很新，请耐心等我:) 谢谢！

如何有效地搜索此层次结构？: 我有一个如下所示的数据结构： public class Node { public string Code { get; set; } public string Description { get; set; } … public List Children { get; set; } } 在给定指定的Code ，我想编写一个返回特定节点的方法。通常我会在层次结构中进行递归遍历以找到节点，但我关注性能。层次结构中将有数千个节点，并且此方法将被多次调用。如何构建它以使其更快？我是否可以使用现有的数据结构，可能在保留层次结构的同时对Code执行二进制搜索，而不是自己重新实现某种forms的二进制搜索？

.Net Dictionary 超出6,000,000个条目的内存不足exception: 我使用Dictionary来存储图像中颜色的频率，其中键是颜色（作为int），值是在图像中找到颜色的次数。当我处理更大/更彩色的图像时，这个字典会变得非常大。我在大约6,000,000个条目中得到了一个内存不足的例外。这是在32位模式下运行时的预期容量吗？如果是这样，我能做些什么吗？什么可能是一些跟踪这些不会耗尽内存的数据的替代方法？作为参考，这里的代码循环遍历位图中的像素并将频率保存在Dictionary ： Bitmap b; // = something… Dictionary count = new Dictionary(); System.Drawing.Color color; for (int i = 0; i < b.Width; i++) { for (int j = 0; j < b.Height; j++) { color = b.GetPixel(i, j); int colorString = color.ToArgb(); if (!count.Keys.Contains(color.ToArgb())) { count.Add(colorString, 0); } count[colorString] […]

这个无锁的.NET队列线程安全吗？: 我的问题是，下面包含的类对于单读者单作者队列类线程安全吗？这种队列称为无锁，即使队列已填满也会阻塞。数据结构的灵感来自Marc Gravell在StackOverflow 上实现的阻塞队列。结构的要点是允许单个线程将数据写入缓冲区，而另一个线程则读取数据。所有这些都需要尽快发生。 Herb Sutter在DDJ的文章中描述了类似的数据结构，但实现是在C ++中。另一个区别是我使用了一个vanilla链表，我使用了一个链表的数组。我不是仅仅包含一段代码，而是将所有内容与允许的开源许可证（MIT许可证1.0）一起包含，以防任何人发现它有用，并且想要使用它（原样或修改）。这与Stack Overflow上有关如何创建阻塞并发队列的其他问题有关（请参阅在.NET中创建blockinq队列和在.NET中创建线程安全阻塞队列）。这是代码： using System; using System.Collections.Generic; using System.Threading; using System.Diagnostics; namespace CollectionSandbox { /// This is a single reader / singler writer buffered queue implemented /// with (almost) no locks. This implementation will block only if filled /// up. […]

在C＃中使用一对（三重等）值作为一个值的最佳方法是什么？: 也就是说，我想要一个价值元组。我心中的用例： Dictionary<Pair, object> 要么 Dictionary<Triple, object> 是否有像Pair或Triple这样的内置类型？或者实施它的最佳方式是什么？更新答案中描述了一些通用元组实现，但对于在字典中用作键的元组，您应该另外validation哈希码的正确计算。在另一个问题中有关于此的更多信息。更新2我想也值得提醒一下，当你在字典中使用某个值作为键时，它应该是不可变的。

c＃中的Fibonacci，Binary或Binomial堆？: 是否存在任何堆数据结构实现，斐波那契，二进制或二项式？参考：这些是用于实现优先级队列的数据结构，而不是用于分配动态内存的数据结构。见http://en.wikipedia.org/wiki/Heap_(data_structure）谢谢，戴夫

在C＃中为信息检索应用程序编写反向索引: 我正在编写一个内部应用程序，其中包含几条文本信息以及有关这些文本的大量数据。这些数据将按入口顺序保存在数据库（SQL Server，尽管可能会更改）中。我希望能够搜索这些信息中最相关的信息，其中最相关的信息位于顶部。我最初考虑使用SQL Server全文搜索，但它不像我希望的那样灵活，以满足我的其他需求，所以我似乎需要开发自己的解决方案。根据我的理解，所需要的是倒排索引，然后根据所保存的附加信息的结果来恢复和修改所述倒排索引的内容（尽管现在这可以留待以后我想要的日期倒排索引从数据库表/字符串提供的索引主文本）。我在使用Hashtable在Java中编写此代码时遇到了一个问题，其中密钥作为单词，值作为单词出现的列表但是老实说我仍然是C＃的新手并且只是真正使用过处理信息时，如DataSet和DataTables。如果请求，我会在我清除这台病毒笔记本电脑后立即上传Java代码。如果从表或字符串列表中给出一组条目，那么如何在C＃中创建一个反向索引，最好保存到DataSet / DataTable中？编辑：我忘了提到我已经尝试过Lucene和Nutch，但是需要我自己的解决方案，因为修改Lucene以满足我的需求需要比编写倒置索引要长得多。我将处理大量的元数据，这些元数据在基本的反向索引完成后也需要处理，所以我现在需要的是使用反向索引在一个区域上进行基本的全文搜索。最后，制作倒排索引不是我每天都要做的事情，所以对它进行破解是很好的。

什么是应该使用链接列表的真实世界示例？: 另一位程序员提到他们在职业生涯中没有找到在任何专业软件中使用链表数据结构的用例。我想不出任何好的例子。他主要是C＃和Java开发人员任何人都可以提供一些例子来说明这是解决特定现实世界问题的正确数据结构吗？相关：链接列表的实际现实示例是什么？

为什么在排序输入上比随机输入更快插入我的树？: 现在我总是听说二进制搜索树比随机数据更快地构建，而不是有序数据，因为有序数据需要显式重新平衡以保持树高最小。最近我实现了一个不可变的treap ，一种特殊的二叉搜索树，它使用随机化来保持自己相对平衡。与我的预期相反，我发现我可以持续建立一个快速约2倍的treap，并且通常比有序数据更好地平衡 – 而且我不知道为什么。这是我的treap实现： http://pastebin.com/VAfSJRwZ 这是一个测试程序： using System; using System.Collections.Generic; using System.Linq; using System.Diagnostics; namespace ConsoleApplication1 { class Program { static Random rnd = new Random(); const int ITERATION_COUNT = 20; static void Main(string[] args) { List rndTimes = new List(); List orderedTimes = new List(); rndTimes.Add(TimeIt(50, RandomInsert)); rndTimes.Add(TimeIt(100, RandomInsert)); rndTimes.Add(TimeIt(200, RandomInsert)); […]

数据结构的最佳存储，以实现快速查找和持久性: 脚本我有以下方法： public void AddItemSecurity(int itemId, int[] userIds) public int[] GetValidItemIds(int userId) 最初我在思考表单上的存储： itemId -> userId, userId, userId 和 userId -> itemId, itemId, itemId AddItemSecurity基于我如何从第三方API获取数据， GetValidItemIds是我想在运行时使用它的方式。可能有2000个用户和1000万个项目。项目ID在表格上：2007123456,2010001234（10位数，前四位代表年份）。 AddItemSecurity不必执行超快速，但GetValidIds需要亚秒。此外，如果现有的itemId有更新，我需要删除列表中不再存在的用户的itemId。我正在考虑如何以最佳方式存储它。最好是在磁盘上（带缓存），但我希望代码可维护和清洁。如果项目id从0开始，我想为每个用户创建一个长度为MaxItemId / 8的字节数组，如果该项目存在与否则设置一个真/假位。这将限制每个用户的arrays长度超过1mb，并提供快速查找以及更新每个用户列表的简便方法。通过使用.Net 4框架将其保存为内存映射文件，我认为我也可以获得不错的缓存（如果机器有足够的RAM），而无需自己实现缓存逻辑。解析id，剥离年份，每年存储一个arrays可能是一个解决方案。 ItemId – > UserId []列表可以直接序列化到磁盘并使用普通的FileStream进行读/写，以便在发生更改时保留列表并进行区分。每次添加新用户时，所有列表也必须更新，但这可以在每晚完成。题我应该继续尝试这种方法，还是应该探索其他途径？我认为SQL服务器执行速度不够快，而且会产生开销（至少如果它托管在不同的服务器上），但我的假设可能是错误的。任何关于此事的想法或见解都表示赞赏。我想尝试解决它而不添加太多硬件:) [更新2010-03-31] 我现在已经在以下条件下使用SQL Server 2008进行了测试。 […]