Tag: 排序算法

Curiosity.letsGetSwift.sorted（）

问：如何在Swift中实现排序。 它使用哪种算法？ Google —如何在Swift中实现排序 单击解释它的stackOverflow链接。 单击答案中的源代码链接以转到实现排序的确切文件。 想知道.gyb是什么东西？ 以及文件中的所有％是什么？ Google什么是gyb 找到这个很棒的帖子 了解什么是gyb以及如何使用它。 cd您最喜欢的代码实验目录 mkdir和swift-stdlib一起玩&& cd和swift-stdlib一起玩 curl -O https://raw.githubusercontent.com/apple/swift/master/utils/gyb.py 触摸swift.sort.gyb 打开-a Sublime \文本swift.sort.gyb 复制第3点中文件的粘贴内容 python ./gyb.py — line-directive = -o sort.swift sort.swift.gyb 打开sort.swift 花费剩下的时间理解700余行代码 有一些☕️

快速排序问题

好吧， 真的是一个小案例。 如果您要在上面烤我… 通过一系列不幸的事件，我最近意识到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 […]

探索一些标准库排序功能

在今天的文章中，我们将探讨一些排序功能。 这些是我们作为开发人员在几乎所有日常任务中使用的非常常见的功能。 我们将探索clang libc ++的一些函数，例如std :: sort，std :: stable_sort和std :: partial_sort。 另外，我们将研究其中一些函数的算法，并尝试了解它们的工作原理。 另外，我们将讨论Swift Collection排序方法\ o /。 使用排序算法时，我们要了解的最重要的事情之一就是时间复杂度。 幸运的是，此信息始终是这些方法文档的一部分，因此在调用标准库排序方法时，我们具有此保证。 分类 std :: sort是使用Introsort算法的排序函数，其复杂度为O（N log（N）），其中N = std :: distance（first，last）自C ++ 11起，且元素顺序相等不能保证保留[3]。 gcc-libstdc ++也使用Introsort算法。 Introsort是一种混合算法，基本上使用两种（或在某些实现中为三种）算法来优化运行时复杂性。 它开始使用Quicksort，并且如果递归深度超出接近O（N log（N））[1]的阈值，它将切换到Heapsort算法，以避免Quicksort最坏情况下具有O（N²）的情况。时间复杂度。 在某些实现中，它使用InsertionSort在排序过程中对小区域进行排序，因为在这种情况下，它的处理效率更高。 我们没有详细介绍Introsort算法的实现细节，但是您可以在[7]上看到伪代码，该伪代码显示了其背后的逻辑。 在下面，我们可以看到一个非常简单的示例，说明如何使用std :: sort对int向量进行升序和降序排序。 这就是本文的全部，希望您喜欢🙂 如果我有问题或您有任何意见或疑问，请告诉我。 我很高兴收到您的反馈feedback 您可以在Twitter上@ LucianoPassos11找到我。 感谢您阅读🙂 参考文献 2017年LLVM开发人员会议：A.基于Kumar Introsort的libc ++排序功能。 https://www.youtube.com/watch?v=Lcz0ZHewkHs “ libc ++” C ++标准库。 […]

所以我想在Swift中快速将项目分组

介绍 在我们的编程生涯中，有时需要对数据集合进行分类和分组。 排序本身是一个简单的概念-列出未排序的数据列表，并根据一组规则对其进行排序。 是您执行或使您感到沮丧的实现。 以手机中的联系人列表为例。 根据您的情况，该列表可能很小，也可能很长（有时不合理）。 这就是为什么在大多数操作系统上都可以导航到列表中所需位置的方法，而不必花太多时间浏览。 这可以通过排序和分组来实现。 您设置了一些规则，应用程序将进行相应排序。 该实现需要能够快速处理大量数据，否则打开“​​联系人”应用会变得很麻烦。 假设我向互联网机器查询了过去二十年来发行的所有电影的列表。 如果要在iOS应用中显示该图片，则需要按字母顺序对其进行排序，因为我们每年要谈论成千上万部电影。 我想要的UI很简单，将UITableView分组为AZ部分，并且在右侧有一个部分索引标题栏，这使我可以像rolodex一样向下滑动列表。 我已经多次看到类似的实现： 令u = u中的v表示“ ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789” var x = [Movies]（）for电影中的y { 如果让z = y.name.prefix（1），则z == v { 临时附加（y） } } indexedList.append（（v，x））} 松散地，正在做的是遍历字母和每个匹配的电影，使数据结构如下： [（“ A”：[电影，电影，电影]），（“ B”：[电影，电影]），（“ C” …）] 该算法的时间复杂度可能为O（n²） ，因为每次外循环运行N次 ，内循环运行M次。 换句话说，电影列表越长，实现就越需要时间来完成。 将其与iPhone 6配合使用，几乎要花整整两秒钟的时间才能对15,000件物品进行排序。 令人沮丧的缓慢。 让我们使用字典分组 通过在Swift中使用字典分组，我们可以在某种程度上克服这一问题。 我拿了电影清单，写了一个谓词： 让谓词：（电影）->字符串{ 警卫让c =字符串（$ 0.title.prefix（1））否则{fatalError（）} 让字母=“ ABCDEFGHIJKLMNOPQRSTUVWXYZ” […]