jjzjj

c# - 高级 : How to optimize my complex O(n²) algorithm

coder 2024-06-03 原文

我有以下人员和地点数据:

  • Person实体有
    • IList<DateRangePlaces>每个都有
      • IList<Place>可能的地方
    • Schedule即日模式。 10 天可用 4 天不可用

在特定的 DateRangePlaces 内日期范围必须遵守 Schedule人是否可以去特定地方的模式。

  • Place实体有
    • IList<DateRangeTiming>每个定义每个日期范围内的开始/结束时间

重叠的日期范围作为 LIFO。因此，对于之前已经定义的每一天，新的时间定义优先。

问题

现在我需要做这样的事情(用伪代码):

for each Place
{
    for each Day between minimum and maximum date in IList<DateRangeTiming>
    {
        get a set of People applicable for Place and on Day
    }
}

这意味着执行我的任务的步骤数约为:

∑(places)( ∑(days) × ∑(people) )

我的理解是

O(x × yx × z)

<罢工> 并且可能近似于该算法的复杂度:

O(n3)

我不是理论专家，所以您可以随意纠正我的假设。事实是，这种复杂性绝对是 Not Acceptable ，特别是考虑到我将在很长的日期范围内与很多地方和很多人一起工作。

从公式近似可以看出people set会被迭代很多次。因此，我想至少优化这一部分。为了让事情变得简单一些，我改变了

Person.IList<DateRangePlaces>.IList<Place>

到

Person.IList<DateRangePlaces>.IDictionary<int, Place>

这会让我更快地知道一个人是否可以在特定日期去某个地方，因为我只会检查是否 Place.Id出现在字典中与 IList.Where()每次都必须扫描整个列表的 LINQ 子句。

问题

  1. 您能否建议我可以在我的算法中实现任何其他优化，以使其在大 O 表示法方面更快，甚至更不复杂？

  2. 您会在何处以及为什么使用哪些内存结构类型(列表、字典、堆栈、队列...)来提高性能？

附录:整个问题更加复杂

还有一些其他的复杂性我没有提到，因为我想简化我的问题以使其更清楚。所以。还有:

Place.IList<Permission>
Person.IList<DateRangePermission>

因此，地方需要特定的权限，而人们的权限授予会在有限的时间内到期。

除此之外，还有

Person.IList<DateRangeTimingRestriction>

它只告诉人们在特定日期范围内可以去某个地方的特定时间。和

Person.IList<DateRangePlacePriorities>

它定义了特定日期范围内的地点优先顺序。

在这个寻找合适人选的过程中，我还必须计算每个人每个地方的特定因素，这些因素与:

  • 一个人在特定的一天可以去的地方的数量
  • 人在那一天的位置优先因素

所有这些都是我决定宁愿在内存中操作这些数据，也不愿使用非常复杂的存储过程的原因，后者也会进行多表扫描以获取每个人、地点和日期的因素。

我认为这样的存储过程处理和维护起来会很复杂。所以我宁愿先获取所有数据(将其放入适当的内存结构以提高性能)，然后在内存中对其进行处理。

最佳答案

我建议使用关系数据库并编写存储过程来检索“适用于地点和日期的人员集”。

如果模型的架构设计得当，存储过程方法将不会复杂也不会难以维护。此外，关系数据库具有主键和索引以避免表扫描。

使用集合加快速度的唯一方法是:

  1. 更改集合类型。您可以使用 KeyedCollection、IDictionary<> 甚至断开连接的记录集。断开连接的记录集还使您能够为子记录集设置外键，但我认为这将是一个使用起来相当复杂的模式。

  2. 维护集合中的集合 - 与使用外键的父/子关系的概念基本相同。对象引用将只是指向原始对象内存空间的指针，或者，如果您使用键控集合，您可以简单地存储另一个集合的索引。

  3. 维护 bool 属性，如果为真或为假，这些属性可以让您跳过迭代。例如，在构建实体时，设置一个 bool 值“HasPlaceXPermission”。如果该值为 false，则您知道不会检索与地点 X 相关的信息。

  4. 维护标志 - 如果使用得当，标志可以成为一种非常好的优化技术。与#3 类似，标志可用于非常快速地确定权限，例如 if((person.PlacePermissions & (Place.Colorado | Place.Florida) > 0)//在科罗拉多州和佛罗里达州进行日期/时间扫描，否则不要't.

根据您提供的信息很难知道我会使用哪些集合类型，我需要更大范围的应用程序才能从架构上确定这一点。例如，数据存储在哪里、如何检索、如何准备以及如何呈现？了解应用程序的架构有助于确定其优化点。

关于c# - 高级 : How to optimize my complex O(n²) algorithm，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7485030/

c#algorithmcodeliIListiteratorbig-o

有关c# - 高级 : How to optimize my complex O(n²) algorithm的更多相关文章

  1. c# - 如何在 ruby​​ 中调用 C# dll？ - 2

    如何在ruby​​中调用C#dll？ 最佳答案 我能想到几种可能性:为您的DLL编写(或找人编写)一个COM包装器，如果它还没有，则使用Ruby的WIN32OLE库来调用它；看看RubyCLR,其中一位作者是JohnLam，他继续在Microsoft从事IronRuby方面的工作。(估计不会再维护了，可能不支持.Net2.0以上的版本)；正如其他地方已经提到的，看看使用IronRuby，如果这是您的技术选择。有一个主题是here.请注意，最后一篇文章实际上来自JohnLam(看起来像是2009年3月)，他似乎很自在地断言RubyCL

  2. C# 到 Ruby sha1 base64 编码 - 2

    我正在尝试在Ruby中复制Convert.ToBase64String()行为。这是我的C#代码:varsha1=newSHA1CryptoServiceProvider();varpasswordBytes=Encoding.UTF8.GetBytes("password");varpasswordHash=sha1.ComputeHash(passwordBytes);returnConvert.ToBase64String(passwordHash);//returns"W6ph5Mm5Pz8GgiULbPgzG37mj9g="当我在Ruby中尝试同样的事情时，我得到了相同sha

  3. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  4. c# - C# 中的 Flatten Ruby 方法 - 2

    我如何做Ruby方法"Flatten"RubyMethod在C#中。此方法将锯齿状数组展平为一维数组。例如:s=[1,2,3]#=>[1,2,3]t=[4,5,6,[7,8]]#=>[4,5,6,[7,8]]a=[s,t,9,10]#=>[[1,2,3],[4,5,6,[7,8]],9,10]a.flatten#=>[1,2,3,4,5,6,7,8,9,10 最佳答案 递归解决方案:IEnumerableFlatten(IEnumerablearray){foreach(variteminarray){if(itemisIEnume

  5. ruby - 可以像在 C# 中使用#region 一样在 Ruby 中使用 begin/end 吗？ - 2

    我最近从C#转向了Ruby，我发现自己无法制作可折叠的标记代码区域。我只是想到做这种事情应该没问题:classExamplebegin#agroupofmethodsdefmethod1..enddefmethod2..endenddefmethod3..endend...但是这样做真的可以吗？method1和method2最终与method3是同一种东西吗？还是有一些我还没有见过的用于执行此操作的Ruby惯用语？ 最佳答案 正如其他人所说，这不会改变方法定义。但是，如果要标记方法组，为什么不使用Ruby语义来标记它们呢？您可以使用

  6. c# - Ruby 等效于 C# Linq 聚合方法 - 2

    什么是Linq聚合方法的ruby​​等价物。它的工作原理是这样的varfactorial=new[]{1,2,3,4,5}.Aggregate((acc,i)=>acc*i);每次将数组序列中的值传递给lambda时，变量acc都会累积。 最佳答案 这在数学以及几乎所有编程语言中通常称为折叠。它是更普遍的变形概念的一个实例。Ruby从Smalltalk中继承了这个特性的名称，它被称为inject:into:(像aCollectioninject:aStartValueinto:aBlock一样使用。)所以，在Ruby中，它称为inj

  7. ruby - 高级语言是否使用数据结构？ - 2

    我目前还在上学，正在上一门关于用C++实现数据结构的类(class)。在业余时间，我喜欢使用“高级”语言(主要是Ruby和一些c#)进行编程。既然这些高级语言为你管理内存，你会用数据结构做什么？我可以理解对队列和堆栈的需求，但是您需要在Ruby中使用二叉树吗？还是2-3-4树？为什么？谢谢。 最佳答案 Sosincethesehigherlevellanguagesmanagethememoryforyou,whatwouldyouusedatastructuresfor?使用数据结构的主要原因与垃圾收集无关。但它是以某种方式有效的

  8. c# - 先学什么？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭8年前。Improvethisquestion几年前我去学校学习编程，毕业后我找到了一份系统管理方面的工作，这就是我职业生涯的方向。我想重新开始某种开发，并且一直在“玩”C#和ASP.NET，但我已经听到很多关于其他"new"语言的讨论(新的意思是它们是新的)我)喜欢Ruby和F#。我想我想知道我是否在浪费时间学习主要的MS语言，而不是成为一名通才。很长一段时间没有离开开发社区(如果我曾经离开过的话)让我在潮流中挣扎，我不想落在时代的

  9. c# - 在 C# 中重现 Ruby OpenSSL private_encrypt 输出 - 2

    我有一个简单的Ruby脚本，我用它在某些HTTPheader上执行private_encrypt以签署要发送到ruby​​RESTAPI的Web请求，该API会根据Base64编码字符串测试Base64编码字符串生成而不是解码Base64和解密数据然后测试原始字符串。我使用的脚本是require"openssl"require"base64"path_to_cert=ARGV[0].dupplain_text=Base64.decode64(ARGV[1].dup)private_key=OpenSSL::PKey::RSA.new(File.read(path_to_cert))pu

  10. C# 的 LINQ 用于在 ruby​​ 中等效的集合操作 - 2

    我是ruby​​开发的新手，我目前正在使用rails2.3.11在ruby​​1.8.7中开发一个项目，我想知道这种语言是否有与C#的linq等效的集合操作，例如where子句。谢谢。 最佳答案 Ruby中Linq的where等价于find_all检查documentationfortheEnumerableModule用于其他功能。 关于C#的LINQ用于在ruby​​中等效的集合操作，我们在StackOverflow上找到一个类似的问题： https://

随机推荐