没有字典的快速多关键查找? -- c# 领域 和 linq 领域 和 search 领域 和 .net-4.0 领域 和 lookup 领域 相关 的问题

Fast multi-key lookup without Dictionary?


1
vote

问题

中文

我有一个映射缓存,它占用了太多的内存。它用于容纳3种不同类型的ID的ID的组合,并从表中读取它们的映射,并在6个不同的字典中缓存,用于从任何1个ID类型到另一个id类型的快速查找/翻译(性能对我的申请很重要)。

我想将它重写为具有较小内存占用空间的东西,因此我确实实现了一个综合的ID列表并使用了LINQ / Lambda表达式来拔出我想要的值。它现在看起来像这样。

  public struct IdMappings {      public int Id1;      public int Id2;      public int Id3; }  //new cache     private static List<IdMappings> AllIdMappings = null;  //current cache implementation private static Dictionary<int, int> Id1ToId2 = null; private static Dictionary<int, int> Id1ToId3 = null; //etc.  public static void FillCache(DataSet data) {      foreach (DataRow r in data.Tables[0].Rows)      {           //fill list and/or dictionaries with id's      } }   

示例查找将是:

  public static int GetId2FromId1(int id1) {     return AllIdMappings.FirstOrDefault(m => m.Id1 == id1).Id2;     //or     return Id1ToId2[id1]; }   

这是在减少内存使用情况方面所需要的,但查找的性能遭受了结果,因此我看到了如何实现不同的东西。有没有办法做多索引键,或者多关键查找,它比通过列表迭代相对较快的方法?

英文原文

I have an Id mapping cache that's taking up a bit too much memory. It's used to house a combination of 3 different types of Id's for an object and the mappings for them are read in from a table, and cached in 6 different dictionaries for quick look-up/translation from any 1 Id type to another (performance is important for my application).

I wanted to rewrite it to something that has a smaller memory footprint so I did implement a consolidated list of the Id's and used a linq/lambda expression to pull out the values I wanted. It looks like this for now.

public struct IdMappings {      public int Id1;      public int Id2;      public int Id3; }  //new cache     private static List<IdMappings> AllIdMappings = null;  //current cache implementation private static Dictionary<int, int> Id1ToId2 = null; private static Dictionary<int, int> Id1ToId3 = null; //etc.  public static void FillCache(DataSet data) {      foreach (DataRow r in data.Tables[0].Rows)      {           //fill list and/or dictionaries with id's      } } 

Example lookup would then be:

public static int GetId2FromId1(int id1) {     return AllIdMappings.FirstOrDefault(m => m.Id1 == id1).Id2;     //or     return Id1ToId2[id1]; } 

This does what I need in terms of reducing memory usage, but performance for lookups has suffered as a result so I'm seeing how to implement something different. Is there a way to do multi-indexing keys, or multi-key lookup that's relatively faster than iterating through a list?

              
   
   

回答列表

1
 
vote
vote
最佳答案
 

如果添加这三个词典:

  table(sapply(myList, paste, collapse = ",")) #  #     A,B A,B,B,C A,C,B,B     B,A  #       2       2       1       1  6  

并使字典值为相同的引用,它应该使用minimally更多的内存,而是将相同的查找速度保持为原始实现。

如果我在考虑这个权利,这应该使用6字典解决方案的一半内存,但两次 table(sapply(myList, paste, collapse = ",")) # # A,B A,B,B,C A,C,B,B B,A # 2 2 1 1 7 类型解决方案。

作为@sweko指出, table(sapply(myList, paste, collapse = ",")) # # A,B A,B,B,C A,C,B,B B,A # 2 2 1 1 8 需要是 table(sapply(myList, paste, collapse = ",")) # # A,B A,B,B,C A,C,B,B B,A # 2 2 1 1 9 不是 table(sapply(myList, function(x) paste(sort(x), collapse = ","))) # # A,B A,B,B,C # 3 3 0 ,以确保使用引用指针而不是副本它。

 

If you add these three dictionaries:

private static Dictionary<int, IdMappings> Id1Lookup = null; private static Dictionary<int, IdMappings> Id2Lookup = null; private static Dictionary<int, IdMappings> Id3Lookup = null; 

And have the dictionary values be the same references, it should use minimally more memory but retain the same lookup speed as your original implementation.

If I'm thinking about this right, this should use half the memory of your 6 dictionary solution, but twice a List<IdMappings> type solution.

As @SWeko points out, IdMappings needs to be a class not a struct to ensure the reference pointer is used rather than copies of it.

 
 
 
 
1
 
vote

是,对列表进行排序并使用二进制搜索(列表&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;已经在方法中为您实施) 然后在O(LOGN)中完成保持排序的列表和查找。

 

Yes, sort the list and use binary search (List<> already implements this for you in the method Find) Maintaining a sorted list and lookups is then done in O(logn).

 
 
1
 
vote

一个潜在的性能改进可能是使用 table(sapply(myList, function(x) paste(sort(x), collapse = ","))) # # A,B A,B,B,C # 3 3 1 而不是 9988876632 ,但这主要有助于直接查找,而不是 table(sapply(myList, function(x) paste(sort(x), collapse = ","))) # # A,B A,B,B,C # 3 3 3 哪个或多或少地迭代列表。

如果您的查找来自ID1 - &gt; ID2和ID3方向,您可以使用 table(sapply(myList, function(x) paste(sort(x), collapse = ","))) # # A,B A,B,B,C # 3 3 4 的键,这将从当前词典中消除ID1的额外值。

无论如何,缓存是根据定义的记忆交易,以便查找速度,所以我不认为可以提高内存消耗多少。

 

One potential performance improvement could be to use a Hashset<IdMappings> instead of a List<IdMappings>, but that would mostly help for direct look-up, and not for FirstOrDefault which, more or less, iterates the list sequentially.

If your lookups are all from the ID1 -> ID2 and ID3 direction, you could use a Dictionary<int, Tuple<int, int>> for the keys, and that would eliminate a extra value of ID1 from the current dictionaries.

Anyway, cache is by definition trade of memory for lookup speed, so I don't think you can improve the memory consumption by much.

 
 
     
     
1
 
vote

可能是您最好的选择是创建一个映射结构:

  struct Mapping: IComparable<Mapping> {     private readonly int FromId;     private readonly int ToId;     public Mapping(int fid, int tid);     // implement the IComparable.Compare method to compare FromId }   

然后,为每个索引创建 List<Mapping> ,并对列表进行排序。然后,您可以使用 99887662 查找所需的项目。

 

Probably your best bet is to create a mapping structure:

struct Mapping: IComparable<Mapping> {     private readonly int FromId;     private readonly int ToId;     public Mapping(int fid, int tid);     // implement the IComparable.Compare method to compare FromId } 

Then, create a List<Mapping> for each index, and sort the list. You can then use List.Find to find the item you want.

 
 

相关问题

1  由于调用来自子表单的函数而重复的父表单  ( Duplicate parent forms as a result of calling a function from a child form ) 
在我的应用程序中,我有一个父格式和弹出窗口表单。在POPUP表单中单击Button1时,应用程序应该调用函数,并且由于函数,标签必须更改其文本。虽然弹出按钮工作,但我有两个父母表格;一个带有标签的标签,其中一个带有标签的一个,因为单击弹出窗口中的按钮。有没有办法隐藏初始父母表格?这是我在弹出窗体中使用的代码: ...

-1  是否有一种方法可以使用BOOL来检测Foreach循环中的假值,以便我的方法无法执行?  ( Is there a way to use a bool to detect a false value in a foreach loop so that m ) 
我希望我的应用程序检查所有5个文本框是否为数字,如果值都是真的。显示塔利。如果没有,我不希望我的方法执行,现在是。我的方法是编码的方式,对我来说似乎应该有效。我想如果有人可以指向正确的方向,我相信有一种简单的方法可以做到这一点,但我还没有找到它。事先致谢,无论如何需要时间来看待这个。 我在这里尝试了若干例子的变化,但...

1  如何使用C#在Windows 10中的任务栏上创建工具栏工具  ( How to create toolbar tool on taskbar in windows 10 using c sharp ) 
我想在任务栏上使用Windows工具栏功能创建一个简单的Internet速度计,该仪表在任务栏上面在任务栏上面显示速度,但我不知道如何在C#或任何其他语言中执行此操作。请让我知道如何这样做。 工具栏在Windows 10 ...

0  使用实体框架核心同时更新来自多个客户端的记录  ( Update a record from multiple clients at the same time with entity framework cor ) 
我的数据 ID VALUE 1 100 我正在使用efcore和postgreSQL。我有2个请求在同一时间更新与 Id =1 的记录。 请求1:获取记录 Id = 1 ,收到 {Id =1, Value=100} ,然后我更新 Value = Value + 10 并更新到DB 请求2:当请...

1  C#如何制作表现得像可用的<t>  ( C sharp how to make a class that behave like nullablet ) 
给出代码: public class Filter<T> { private bool selected = false; public bool Selected { get { return selected; } } private T value; public T Va...

0  寻找httputility.parsequerystring替代品  ( Looking for a httputility parsequerystring alternative ) 
在Windows运行时是否存在此方法的替代方案? 如果没有任何优雅的方法可以从URL解析查询字符串? ...

0  C#条件语句不会返回true  ( C sharp condition statement doesnt return true ) 
我有一个比较两个整数的条件,但它也永远不会返回true,即使两个数字也是相等的。 foreach (TreeViewItem item in Categories.Items) { if (subCategory.Tag == item.Tag) ...

1  Visual Studio在线构建 - Web.config连接字符串ConfigSource  ( Visual studio online build web config connection strings configsource ) 
我的项目 web.config 在使用以下构造的单独文件中定义了连接字符串: ui-router2 在项目上协作或部署项目时是方便的。但是,我无法让VSO构建工作,因为它显示了以下错误: c: program文件 (x86) msbuild 14.0 bin microsoft.common.c...

0  尝试使用sqldataSource将数据插入数据库中,我收到此错误:ORA-01745无效的主机异常,为什么?  ( Trying to insert data into database with sqldatasource i get this error ora 01 ) 
我在我的aspx文件中有这个代码: <asp:SqlDataSource ID="RegisterUserSQL" runat="server" ConnectionString="<%$ ConnectionStrings:UserQueries %>" ProviderName="<%$ Connection...

0  .exe文件不包含在UWP最终包中  ( Exe file is not included in the uwp final package ) 
我目前正在尝试创建appxpackage。 可悲的是,其中一个资产是项目中可执行文件,不能在最终 998876612 中找到,即使这个文件/资产的构建操作 content < / strong>并且选择始终复制。 我还尝试过Xcopy,其中包含以下后构建脚本,但没有成功: MyDBHandler.java3 ...

0  在模型上进行一个字段并发送到视图  ( Substring one field on model and send to view ) 
我有一个模型,我在这个模型上发送子字段一个字段,并返回到gridview中的显示 我的模型是: public class News { public int ID { get; set; } [MaxLength(300)] public string Title { get; set...

-2  如何从C#程序创建Ubuntu计算机上的用户?  ( How to create a user on ubuntu machine from a c sharp program ) 
我从未使用过网络,我有一个任务: 在虚拟mashine上,我有一个ubuntu在真正的mashine上我有一个窗户; 我需要在Windows中编写一个程序,它在Ubuntu中创建一个用户。 网络连接已设置,Mashines正在ping。 我尝试使用nfs(netwerk文件系统),但我对此什么也不了...请帮忙,推我...

1  Visual Studio在线构建 - Visual Studio SDK和Modellng SDK  ( Visual studio online build visual studio sdk and modellng sdk ) 
我已包含 Visual Studio SDK 和建模sdk 在我的项目中,以便构建我的T4模板。它一直在正常工作,直到我想设置VSO构建,这给了我以下错误: 导入项目"C: Program Files (x86) msbuild microsoft VisualStudio v14.0 texttemp...

0  @ html.filefor返回null mvc4  ( Html filefor returns null mvc4 ) 
尝试使用mvc4上传文件,我在我的控制器中返回null以获取文件上传。能否看看为什么请? 查看模型 public class PostExtendedWithImage { public Post post { get; set; } public HttpPostedFileBase file...

0  从中从表中删除行后,无效值下一行具有不正确的“无效”CSS  ( After remove row from table with invalid value next row has incorrect invalid ) 
净核心3.1等,布拉泽服务器 我有一个少数行的表。我可以通过添加列表或从服务器端的列表中删除项目来添加和删除行。 我的输入字段使用Dataannotations [必需] 具有简单的验证 示例。 2行。当删除输入字段的第一个"无效" 时,因为它为空,第二行向上移动到第一行位置。填充数据的输入字段就像无效,因为有红色边...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有


Licensed under cc by-sa 3.0 with attribution required.