sort/2、keysort/2 与 samsort/3、predsort/3

2023-12-31

ISO-Prolog 提供sort/2 and keysort/2它依赖于术语顺序(7.2),通常称为“标准术语顺序”。 以不同顺序对列表进行排序的常见方法是映射每个元素El以某种方式将该列表转换为成对列表XKey-El然后对该列表进行排序,最后将键投射出去。作为一个例子,考虑如何keysort/2可以表示为sort/2 (请参阅注释以了解实现 http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#keysort).

在许多情况下,这种方法比使用依赖于用户定义顺序的通用实现特定排序谓词(如 SWI 的排序谓词)要快得多predsort(C_3, List, SortedList) http://www.swi-prolog.org/pldoc/doc_for?object=predsort/3或 SICStus 的samsort(O_2, List, SortedList) https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002dsamsort.html#index-samsort_002f_005b2_002c3_005d-_0028samsort_0029-1.

我的问题归结为:

Are there cases where a sorting using predsort/3 resp. samsort/3 cannot be replaced by some mapping, sort/2-ing and projecting?1

为了清楚起见,最好坚持使用有限的基本术语。因为,无限基本项不具有总的词典顺序,因为它需要作为有限情况的扩展;此外,尚不清楚在 ISO/IEC 13211-1:1995 的 7.2.1 中,变量与依赖于实现的两个不同变量的情况的比较结果如何:

7.2.1 变量

If X and Y是不相同的变量
X 术语先于 Y应依赖于实现
除了在创建排序列表期间(7.1.6.5,
8.10.3.1 j) 顺序应保持不变。

所以不清楚是否predsort/3仍然有资格作为 创建排序列表。显而易见的是,顺序保持不变during sort/2 and keysort/2.


1 感谢@WillNess,这个投影至少应该包括reverse/2- 或任何线性变换。这也意味着可以实现具有重复和唯一结果的结果(类似于keysort/2已实施)。


首先,您可以“否定”Prolog 原子。我们就这样称呼它吧atom_neg/2(这是一个愚蠢的名字,但无论如何它做了一些愚蠢的事情):

atom_neg(A, NK) :-
    atom_codes(A, Cs),
    maplist(negate, Cs, NCs),
    append(NCs, [0], NK).

negate(X, N) :- N is -X.

我并不是说这样做是可行的,但显然,这是可能的。

全排序是一种弱排序,也是一个关键函数f在一组上T连同总订购r在 的共域上f, define弱排序wr(x, y)r(f(x), f(y)).

(该上下文中函数的共域是函数返回值的域。)

我可能完全错了,但是关系的存在需要一个键的存在:你可以根据另一个关系来定义一个关系,但最终你必须比较也可以单独存在的东西:键。

这里的重点是,关键是不需要在同一个域中作为我们想要排序的东西,并且为对象定义了弱排序(关系)相同的域。 Prolog 在这里做了一些奇怪的事情:它定义了术语的标准顺序对于所有可能的条款。 Prolog 也没有正确的“类型”或“域”概念。我的直觉告诉我,对不属于同一域的东西进行排序根本没有多大用处,但 Prolog 显然不同意。

不能为以下两种情况定义关键函数:

  1. 比较谓词保持其自己的状态;
  2. 您有“不透明”对象(例如,在 C 中定义),它们提供比较函数,但不提供关键函数。

无论哪种方式,predsort可能有用:没有人愿意atom_neg/2威尔·尼斯的解决方案。然而,它目前有一个严重的缺陷:它不允许进行稳定的排序。 SWI-Prolog 已经可以这样使用 https://stackoverflow.com/questions/28076715/possible-behaviors-of-predsort-3,所需要做的就是将当前行为添加到规范和文档中predsort/3.

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

sort/2、keysort/2 与 samsort/3、predsort/3 的相关文章

  • 如何对“s3cmd ls”的输出进行排序

    Amazon s3cmd ls 的输出如下 2010 02 20 21 01 1458414588 s3 file1 tgz 00 br 2010 02 20 21 10 1458414527 s3 file1 tgz 01 br 2010
  • 根据 D3 中的属性值对对象进行排序

    我有一系列在 D3 中使用的对象 例如 var cities city London country United Kingdom index 280 city Geneva country Switzerland index 259 ci
  • 实体框架按枚举值按字母顺序排序

    我有一个名为Comment 其中有一个enum类型的属性CommentType public class Comment public virtual Guid Id get private set public virtual Comme
  • 什么是确定性快速排序?

    我一直在阅读有关快速排序的内容 发现有时它被称为 确定性快速排序 这是普通快速排序的替代版本吗 普通快速排序和确定性快速排序有什么区别 普通 确定性 快速排序在特定数据集上的行为可能非常差 例如 选择第一个未排序元素的实现在已排序数据上的时
  • Python:for 循环 - for i in range(0,len(list) 与 for i in list

    这是一个非常简单的Python 力学问题 为什么我不能只说 for i in range original list 而不是 for i in range 0 len original list 人们通常使用范围而不是前者吗 谢谢 If I
  • 用于基本要素匹配的最坏情况 NlogN 算法

    查找两个相同大小数组的元素之间的唯一映射 https stackoverflow com questions 4411940 find the unique mapping between elements of two same size
  • 当 docvalues=true 时,小写过滤器工厂不起作用

    我正在尝试使用 Solr 实现不区分大小写的排序并面临这个问题 https stackoverflow com questions 31745713 solr case insensitive sort not working Copied
  • WAM 中的扁平化形式

    WAM 教程重构指出查询 p Z h Z W f W 需要使用以下原则进行扁平化 话虽这么说 查询扁平化形式是 X3 h X2 X5 X4 f X5 X1 p X2 X3 X4 我对外部变量的定义感到困惑 请考虑以下内容 p Z h Y a
  • 如何在休眠中按条件对列表进行排序

    我是 Spring3 和 Hibernate 的新手 以下代码效果很好 但我试图找到一种方法让我的列表按日期字段排序返回 有人可以告诉我如何向此代码添加排序吗 To get list of all articles SuppressWarn
  • 有效地合并两个数组 - 一个已排序,另一个未排序

    我正在解决一个问题 该问题有一个由 n 个元素组成的排序数组 后跟一个未排序的长度数组 O logn O 平方 n 如何最有效地对整个列表进行排序 在上述两种情况下我应该使用哪种排序 由于将单个元素插入数组并保持其排序是O n 你不可能变得
  • javascript中的父子关系排序

    我有以下结构 category id 1 parent category null category id 2 parent category 1 category id 3 parent category 1 category id 4
  • 为什么 OS X 和 Linux 之间的 UTF-8 文本排序顺序不同?

    我有一个包含 UTF 8 编码文本行的文本文件 mac os x cat unsorted txt foo foo 津 如果它有助于重现问题 这里是文件中确切字节的校验和和转储 以及如何自己生成文件 在 Linux 上 使用base64 d
  • 使用 php 在多维数组中按键排序[重复]

    这个问题在这里已经有答案了 可能的重复 在 PHP 中对多维数组进行排序 https stackoverflow com questions 2059255 sorting multidimensional array in php 如何在
  • 按相反顺序对列表进行排序

    我有直接顺序的列表 list1 List
  • 按文件名对 $_FILES 进行排序 [关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 他俩 如您所知 在新的 HTML5 中 您可以非常轻松地上传多个文件 但我这里的问题是如何按列 名称 对 FILES 数组进行排序 这是
  • 删除近排序数组中未排序/离群元素

    给定一个像这样的数组 15 14 12 3 10 4 2 1 我如何确定哪些元素乱序并删除它们 在本例中为数字 3 我不想对列表进行排序 而是检测异常值并将其删除 另一个例子 13 12 4 9 8 6 7 3 2 我希望能够删除 4 和
  • Prolog,确定图是否是非循环的

    我需要定义一个谓词 acycling 1 它将一个图作为输入并确定该图是否是非循环的 所以根据我的理解 graph1 a b graph1 b c graph1 c a 将返回 no 和 graph2 a b graph2 b c 将返回是
  • Java 8 流排序字符串列表[重复]

    这个问题在这里已经有答案了 我正在流上调用排序方法 java 文档说 Sorted 方法返回一个由该流的元素组成的流 并根据自然顺序排序 但是当我运行下面的代码时 List
  • 从给定的项目列表创建子列表

    我首先要说的是以下问题不是为了家庭作业目的即使因为我几个月前就完成了软件工程师的工作 无论如何 今天我正在工作 一位朋友向我询问了这个奇怪的排序问题 我有一个包含 1000 行的列表 每行代表一个数字 我想创建 10 个子列表 每个子列表都
  • 对包含元组的元组进行排序[重复]

    这个问题在这里已经有答案了 我有以下元组 其中包含元组 MY TUPLE A Apple C Carrot B Banana 我想根据以下内容对这个元组进行排序second内部元组中包含的值 即 对 Apple Carrot Banana

随机推荐

  • 什么是数据库文件系统?

    我对什么是数据库文件系统知之甚少 有人可以向我解释一下数据库文件系统到底是什么 以及它的应用程序是什么吗 它与传统的文件系统有何不同 我怎样才能建造它 典型的文件系统 nix ms dos 等 按层次结构组织文件 例如 c 代表层次结构的顶
  • 如何防止 .htaccess 在特定目录中使用?

    我有一个网站 可以说 http www example com 我正在使用重写模块 但我有一个子文件夹forum example com 我不想要 htaccess要影响这个目录 我该怎么做 If your forum domain com
  • 将参数发送到 Web 服务

    开始之前 我正在使用 Objective C 为 Iphone 编程 我已经使用 NSURLRequest 和 NSURLConnection 实现了对 Web 服务函数的调用 然后该函数返回一个包含我需要的信息的 XML 代码如下 NSU
  • Rails 3,将局部变量传递给部分[重复]

    这个问题在这里已经有答案了 可能的重复 Rails 对将局部变量传递给局部变量的语法感到困惑 https stackoverflow com questions 4402556 rails confused about syntax for
  • 从图像中获取像素颜色[重复]

    这个问题在这里已经有答案了 我在浏览器上有一张图片 我想获取图像颜色的左上角像素 坐标 0 0 无论图像是否旋转 我该如何使用 javascript 或 php 代码来做到这一点 创建画布文档 createElement 获取二维上下文ca
  • 在 tmux 下使用 $TERM='screen-256color' 时,HOME 和 END 键不起作用。为什么?

    我已经设置了 tmux TERM被设置为screen 256color正确 这工作正常 并且颜色设置正确 但是它阻止我发送HOME and END终端的密钥 而是打印为F n and H n 我应该补充一点 home 似乎可以在 irssi
  • 支持 IE11 的 vue cli3 lib

    根据文档 https cli vuejs org guide build targets html library https cli vuejs org guide build targets html library 我不清楚如何集成
  • 在 Node WebKit 中启用触摸事件

    我使用自定义触摸屏 我想默认激活触摸事件节点 webkit https github com rogerwang node webkit 那可能吗 This one https github com rogerwang node webki
  • 如何在不看到控制台的情况下检测unity c#运行时是否有错误? [复制]

    这个问题在这里已经有答案了 是否可以在不读取控制台日志的情况下检测在 Unity 中运行的 C 脚本中的错误 当我必须构建游戏并在手机中测试它时 我需要这个 如果运行时出现错误 它将显示一个消息框来显示错误 据我了解 我们可以使用Unity
  • 如何在 .NET Core 的主布局视图中渲染特定控制器的操作?

    我正在打电话 TopNav 部分来自内部Layout主视图 I want TopNav要强类型化的视图和要在其中创建的模型TopNavController 有什么方法可以从主视图中渲染特定控制器的操作吗 所以在这种情况下我需要渲染TopNa
  • 覆盖后退按钮以充当主页按钮

    按下后退按钮后 我希望我的应用程序进入停止状态 而不是销毁状态 在安卓中docs http developer android com intl fr guide practices ui guidelines activity task
  • @WithUserDetails 似乎不起作用

    我有一个应用程序 其中使用 Spring Social Security 进行身份验证和授权 不幸的是 我在模拟 Spring Security 时遇到了一些问题 似乎根本不起作用 我有一个 REST 控制器 如果它应该返回的实体的标识符不
  • 如何使用MessageUI框架在iPhone上发送iMessage消息

    是否可以使用 iPhone 上的 MessageUI 框架从应用程序内部发送消息 或者 有 iMessage 的 URL 方案吗 使用 iOS 4 您可以从应用程序内部发送电子邮件和短信 使用 MessagUI 视图控制器 由于 iOS 5
  • 用于 Java 的 ANTLR4。如何显示词法分析中的错误

    如何在词法分析过程中显示错误列表 如果有 我尝试了以下方法 但我的输出是 org antlr v4 runtime ConsoleErrorListener 1026c84c 我写的代码 private static String erro
  • 开源 php docx 到 pdf 转换?

    是否有任何开源 PHP 工具可以用来将 doc docx 转换为 pdf 如果您有任何好的教程或工具 将不胜感激 我正在研究 phpLiveDocx 但看起来他们按月收费 或者也许是 php 或 linux 中的 odt 到 pdf 尝试
  • Oracle 10g 上的独占表(读)锁?

    有没有办法在 Oracle 10g 中独占锁定表以进行读取 我对Oracle不是很熟悉 所以我问了DBA 他说在Oracle中不可能锁定一个表来读取 我实际上正在寻找类似 SQL Server TABLOCKX HOLDLOCK 提示的内容
  • 单击标签不会单击 React 中的复选框?

    我创建了一个表单 用户可以在提交表单之前选择选项 我隐藏复选框display none我正在设计
  • Pandas:填充缺失日期的数据

    假设我有下表 ProdID Date Val1 Val2 Val3 Prod1 4 1 2019 1 3 4 Prod1 4 3 2019 2 3 54 Prod1 4 4 2019 3 4 54 Prod2 4 1 2019 1 3 3
  • 调用其他线程调用的函数时,线程未启动

    我正在使用线程来显示进度窗口 同时执行耗时的操作 for 循环 在该操作之后 我想停止线程 但是该方法 显示进度对话框 没有被调用 我在其他事件中使用相同的方法 效果很好 下面是代码 Private Sub TSBRSToLoc Click
  • sort/2、keysort/2 与 samsort/3、predsort/3

    ISO Prolog 提供sort 2 and keysort 2它依赖于术语顺序 7 2 通常称为 标准术语顺序 以不同顺序对列表进行排序的常见方法是映射每个元素El以某种方式将该列表转换为成对列表XKey El然后对该列表进行排序 最后