Tag: 80年代

快速排序问题

好吧， 真的是一个小案例。 如果您要在上面烤我… 通过一系列不幸的事件，我最近意识到Swift的默认排序算法可能会产生不稳定的结果。 这不仅让我感到沮丧，而且令我非常恼火，即使从Swift 3开始 ，也没有默认的稳定类别可以使我们的生活更轻松。 通常，这样的事情不会打扰我。 实际上，在大多数情况下，我可能不太在乎这些事情。 但是，在这一特定的日子，这使我非常困扰。 时间压力和使数据排列不正确的费用高得离谱，这使我不得不迅速解决这个问题。 现在，我将假设许多阅读本文的人对“稳定”排序的含义没有丝毫的了解。 因此，我将以我理解的方式在下面进行说明： 仅当两个相等的待排序对象被算法单独处理时，排序才被认为是稳定的。 确实，开发人员只应关心排序列表的稳定性，前提是这样做的代价是不小的 。 老实说，我对自己感到有些失望。 我天真地认为sort（）对于我们所有的用例都可以完美地工作，并且我不需要对数据排序进行过多的关注。 假设是“所有操蛋之母”。 分类问题与山丘一样古老。 它们非常普遍，甚至可能导致代码中似乎无法完全解决的错误。 如果您使用Swift的时间超过大约四秒钟，那么您可能在Swift代码中使用了sort（）几次。 您是否对潜在的边缘案例足够重视？ 在与我的团队讨论了四个字母并进行了“您为什么认为此错误发生的原因”的讨论之后，粗略浏览一下sort（）的快速帮助面板会向我们发出警告，指出不稳定算法最有可能是我的问题的原因。 经过快速检查，我们一起证明了。 为什么要为我们吸？ 我们碰巧正在使用的应用程序在很大程度上依赖于向客户提供准确的数据。 基本上，用户可以订阅服务，并且每月向他们收费，这些订阅也可以停止。 每当我们去查询用户的订阅历史列表时，这个问题就变得很丑陋。 我们希望对数据进行排序，以便将给定订阅的历史记录和父列表本身从最旧到最新进行排序。 由于后端仅知道的原因，订阅的状态会在99.999％的时间内明显地发生变化，例如，从“ 请求”变为“活动”到“ 已停止 ”。 但是，在最小的0.001％的时间内，状态将立即更改。 问题就出在这里。 因为我是按日期排序的，所以列表最终混乱了，因为其中的某些项目被认为是相等的，并且Swift的排序算法不稳定。 我的解决方案 现在，虽然我可能已经能够为sort（）提供更多指标， 我选择立即使用更强力的解决方案。 由于Swift对我来说还是很新的东西，因此我选择了老旧的Objective-C解决方案。 让sortedArray =（parentList as NSArray）.sortedArrayWithOptions（.Stable，usingComparator：（{（lhs，rhs）-> NSComparisonResult在 let lhs =（lhs as！Record）//用您的数据类型替换 let rhs =（rhs as！Record）//与上面相同 如果lhs.date […]