快速查找字符串是否在数组中的方法

2024-02-17

在 Ruby 中,查找字符串是否在数组中 (.include? x)非常慢。如果将该数组更改为集合,则BAM,闪电般的快速查找。

在 JavaScript 中,没有集合,数组查找(.indexOf(x) >= 0)也是very很慢,但是我需要在脚本中执行数万次这样的查找。

我的 Ruby 版本(带集)运行于0.125秒,我的 JavaScript 版本(在 NodeJS 中)需要29!

是否有任何集合库或更好的方法来执行数组查找,可以使 Javascript 速度接近 Ruby?

Edit:将“对象”更改为“字符串”以消除任何混淆


首先,对于 JavaScript 中可用的数据结构存在一些基本的混淆。

TL;DR

  • 如果您想要对具有短原型继承链的对象进行最快的键查找,请使用in.

  • 如果您想要相同,但对于具有广泛继承链的对象,请使用Object.prototype.hasOwnProperty

  • 如果您想要最快的值查找,请使用Array.prototype.indexOf for Array.

  • 哈希表中没有用于查找值的内置函数。当然,您可以自己推出,但有许多库已经提供了这一功能。例如,Underscore 提供了一个(它称之为indexOf).

JavaScript 没有数组

从根本上来说,JavaScript 只有哈希表。标准Array函数构造哈希表(我将这些称为整数哈希表, or 整数哈希表) 其中键除了字符串键之外还可以是整数。它们的性能与数组类似,但它们在某些方面有所不同。有缺点也有优点。例如,从 int-hash-table 中删除一个元素是一个 O(1) 操作,而从数组中删除一个元素是一个 O(n) 操作(因为您需要将其余元素复制到新数组中)。这就是为什么Array.prototype.spliceJavaScript 中的函数非常快。缺点是实现的复杂性。

所以,当你说Array在 JavaScript 上下文中,它被理解为 int-hash-table,以及与之相关的所有渐近复杂性。这意味着如果你想找到一个字符串value在 int-hash-table 中,那么这将是一个 O(n) 操作。有一个标准函数可以做到这一点:Array.prototype.indexOf。但是,如果您想寻找key,则有两个函数:in and Object.prototype.hasOwnProperty.

有点违反直觉:

[1, 2, 3].hasOwnProperty(0); // true
0 in [1, 2, 3]; // true

两者的区别需要进一步解释。这与 JavaScript 中的所有事物都是对象这一事实有关,因此它们具有一些对象特性。其中之一的特点是prototype,对象与其原型之间的链接。它是哈希表的分层结构,每个哈希表都包含对象的属性。

  • in查找对象的直接哈希表,然后递归搜索该对象原型的哈希表。

  • Whereas Object.prototype.hasOwnProperty只查看直接哈希表。您可能认为它应该更快,但请等待一下得出结论。

由于 JavaScript 的动态特性,所有函数调用都是动态的,并且环境必须非常小心以确保故障安全的代码执行。这意味着 JavaScript 中的函数调用非常昂贵。所以,经过Object.prototype.hasOwnProperty可能比经历要贵很多in,尽管理论上应该是相反的。然而,如果有足够高的继承树和足够的继承属性,最终,Object.prototype.hasOwnProperty将接管。

一些获得更好直觉的例子:

>>> var array = [1, 2, 3];
undefined
>>> 3 in array;
false
>>> array.hasOwnProperty(3);
false
>>> 3 in array;
false
>>> array.__proto__ = [1, 2, 3, 4];
[1, 2, 3, 4]
>>> 3 in array;
true
>>> array.hasOwnProperty(3);
false
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

快速查找字符串是否在数组中的方法 的相关文章

  • “过滤”JSON 以获得唯一键并获取所有相关值

    找到一个组中所有可能的相关值的最佳方法是什么 var table group a stuff new group a stuff old group b stuff newOld group b stuff old group c stuf
  • 如何检查变量是否是生成器函数? (例如函数*产量)[重复]

    这个问题在这里已经有答案了 检查函数是否是生成器的可靠方法是什么 例如 let fn function yield 100 if fn instanceof for let value in fn 我能想到的唯一方法是fn toString
  • ExtJS 4 用于选择所选值的组合框事件

    由于某种原因 我需要知道用户何时从组合框中选择了值 即使它已经被选择 仅当用户选择未选择的项目时 选择 事件才起作用 我在组合框或选择器的文档中没有看到任何类似 itemclick 的事件 有任何想法吗 ComboBox uses 绑定列表
  • Angular 2 测试 ng-content

    我想知道是否有办法测试ng content不创建宿主元素 例如 如果我有警报组件 Component selector app alert template div div
  • 将 Javascript 正则表达式转换为 PHP

    我知道这个问题已经被问了大约十几次 但是从技术上讲 这个问题并不是一个骗局 如果您愿意 请检查其他问题 基本上 我有一个 Javascript 正则表达式来检查用于前端验证的电子邮件地址 并且我使用 CodeIgniter 在后端进行双重检
  • HTML5 游戏到本机应用程序 [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 我正在用 HTML5 制作游戏 我最熟悉 HTML5 并且比 C 等更高级的语言更喜欢它 HTML5
  • mongodb - 检索数组子集

    看似简单的任务对我来说是一个挑战 我有以下 mongodb 结构 services TCP80 data status 1 delay 3 87 ts 1308056460 status 1 delay 2 83 ts 1308058080
  • 采用 std::vector 或 std::array 的模板函数

    我有一个函数 当前接受 2 个向量 其中可以包含任何普通的旧数据 template
  • 如何用方向键移动div

    我想使用 jQuery 用箭头键移动 div 所以右 左 下 上 找到了我想要完成的演示here http atomicrobotdesign com blog htmlcss move objects around the canvas
  • Javascript 3d 绘图实用程序? [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 有谁知道有什么好的 javascript 3d 绘图实用程序吗 我知道每个网站都推荐过画布 3d 图
  • 单击 div 中的图像时如何翻转该 Div?

    好吧 我对编写 Javascript 知之甚少 我可以对其进行一些编辑 并且涉足了 CSS3 动画 我将向您展示我正在努力实现的目标 然后在下面进行解释 网站布局将是这样的 https i stack imgur com RMb4R jpg
  • 查找 JavaScript 中函数参数的数量[重复]

    这个问题在这里已经有答案了 可能的重复 获取函数的元数 https stackoverflow com questions 4848149 get a functions arity 假设我有 function a x function b
  • 通过API更新Twitter背景

    我在通过 Twitter 的 API 更新背景时遇到了一些问题 target url http www google com logos 11th birthday gif ch curl init curl setopt ch CURLO
  • NodeJS 错误堆栈未定义 [关闭]

    Closed 这个问题需要细节或清晰度 help closed questions 目前不接受答案 我正在使用节点检查器 我注意到new Error 有未定义的堆栈 如果我将此值分配给一个变量 该变量将显示堆栈未定义 有趣的是 跑步new
  • jQuery 更改为隐藏字段后触发重力表单中的表单更新

    简而言之 是否有 JavaScript 函数或挂钩来触发重力形式的更新 以便执行条件逻辑 原问题 我正在使用重力形式 并且创建了一个 变化时 事件 gform 1 find gfield date dropdown month select
  • ParseFromString 在 IE 中抛出错误,但在 Chrome 中不会抛出错误

    我正在使用传单的 KML 插件 该插件在 Google Chrome 中运行良好 然而 在 IE 中 它会在以下代码中引发错误 parser new DOMParser console log url outputs path to kml
  • 更改哈希值而不触发 hashchange 事件

    我使用哈希来动态加载内容 为了使后退按钮正常工作 我正在捕获哈希更改 然而 有时我需要更改哈希值而不触发哈希更改函数 例如 当页面重定向到服务器端时 我需要在内容返回后更新哈希值 我想出的最佳解决方案是取消绑定 hashchange 事件
  • 将数组数组的字符串转换为 Javascript 数组数组的优雅方法?

    我有一个 ajax 请求 它返回一个值列表 如下所示 5 5 5 6 15 15 7 13 12 我需要它是一个带有数字的 javascript 数组 5 5 5 6 15 15 7 13 12 我尝试将 和 替换为 然后用 分割和 for
  • 使用 JQueryUI Autocomplete 和 Meteor 的规范方法

    使用 Meteor 我想了解使用 JQuery UI 自动完成处理大量服务器端数据的最有效方法 我有两个工作提案 想听听关于差异的意见 以及是否有更好的方法来做同样的事情 使用发布 订阅 Server Meteor publish auto
  • ReactJS setState 仅在嵌套在 setState 中时才有效

    问题 当我使用 this setState 并在回调中输出状态时 它根本不会改变 但是当我将 setstate 嵌套在 setstate 中时 它将正常工作 例子 这不行 this setState data newData 这确实有效 t

随机推荐

  • 如何使用 R 中的 TSP 包指定起始城市

    我一直在尝试使用 R 中的 TSP 包来解决 TSP 问题 我创建了一个大型对称距离矩阵 沿前导对角线有 0 个条目 我希望能够将第一个城市指定为以下方法的起始城市nearest insertion 我已经成功使用了 nn 方法并使用以下代
  • 在 Android studio 中打开 Unity 项目时出现资源未找到异常

    由于 Google 警告我们提供对 64 位架构的支持 我正在从版本迁移现有的 Unity 项目统一5 6 6f to 统一 2018 4 1f 运行我的项目应用程序崩溃并显示日志 2019 06 02 20 08 27 869 14987
  • 如何从 SQL Server 中的值列表中进行选择

    我有一个非常简单的问题无法解决 我需要做这样的事情 select distinct from 1 1 1 2 5 1 6 有人可以帮忙吗 Edit 该数据以文本文件形式来自我们的一位客户 它完全没有格式化 它是一个很长的单行文本 但在 Ex
  • 如何告诉 springdoc-openapi-maven-plugin 生成 YAML 而不是 JSON?

    我正在使用springdoc maven openapi plugin这边走
  • libstdc++ 并行模式:谁在使用它?安全吗?有类似的项目吗? [关闭]

    Closed 这个问题是基于意见的 help closed questions 目前不接受答案 C 库的 GNU 实现支持并行模式 解释如下here http gcc gnu org onlinedocs libstdc manual pa
  • 在 Homestead 上运行 Laravel Dusk

    我用的是家园版本1 0 1 and Laravel 版本 5 4 16 我通过阅读来设置 Laravel dusk文档 https laravel com docs 5 4 dusk installation 但是 当我跑步时php art
  • 如何在 Rails 迁移中将可空列更改为不可空列?

    我在之前的迁移中创建了一个日期列并将其设置为可为空 现在我想将其更改为不可为空 假设该数据库中存在空行 我该如何执行此操作 如果这些列当前为空 我可以将它们设置为 Time now 如果您在迁移中执行此操作 那么您可能可以这样做 Make
  • SvelteKit 瞬间无样式 html

    我通过 sveltekit cli 命令创建了一个基本应用程序 我选择的选项是 scss 和 typescript 当我启动应用程序的一瞬间 我看到了无样式的 html 每次我创建的每个项目都会发生这种情况 我做了一些测试 看起来 css
  • Azure Function 给出错误:此平台不支持 System.Drawing

    如果这个问题措辞不好 有人可以帮我解决吗 我有一个 Azure Function 2 0 它依赖于一些 System Drawing 代码 我添加了对 System Drawing Common 4 5 0 的 NuGet 引用 然而 发布
  • 如何在Contact Form 7 WordPress中实施Google Adwords转换代码

    我想将 Google 转化 Adwords 代码集成到联系表7插件无需重定向到 谢谢 页面 如何在中实现 Google Adwords 转换代码联系表7插件 有人可以帮助我吗 我不喜欢重定向到另一个页面 我在联系表单 7 中找到了实施 Go
  • 如何遍历/迭代 STL 映射?

    我想遍历一张STL地图 我不想使用它的密钥 我不关心顺序 我只是寻找一种访问它包含的所有元素的方法 我怎样才能做到这一点 是的 您可以遍历标准库map 这是用于遍历的基本方法map 并作为遍历任何标准库集合的指导 C 03 C 11 inc
  • JavaScript 在某个索引后找到第一个正则表达式匹配

    我想找到第一个RegExp一定之后匹配index in a String在 JavaScript 中 JavaScriptString prototype indexOf在搜索开始处提供第二个参数限制 但indexOf只支持String n
  • CryptographicException:错误的 PKCS7 填充

    我看到一小部分生产用户随机报告与使用 Xamarin Android 加密 解密字符串相关的异常 但不幸的是我无法重现它 什么可能导致此问题和 或如何重现该异常 以便找到修复 解决方法 CryptographicException Bad
  • Swift 像闭包一样使用选择器参数

    我只是想知道是否可以将函数传递给按钮操作 通常是选择器 例如 通常我会说 UIBarButtonItem title Press style Done target self action functionToCall func funct
  • 当前拓扑不支持会话

    Hi 我收到错误 当前拓扑不支持会话 请参考附图 并编码为 async function insertBooking parking aFunction const session await BookingSchema startSess
  • 为什么我不能将此接口转换为具体类?

    我有一个界面IApiDataWithProperties 一个类叫做Event实现了这个接口 通常我可以投射一个对象IApiDataWithProperties to Event 假设它是一个 并且编译器让我这样做没有问题 在这种情况下 该
  • 在Oracle中的SQL查询中获取固定数量的行[重复]

    这个问题在这里已经有答案了 请帮我在Oracle数据库中编写一个SQL查询 有一个名为 tbl 的表 它有 12 行 我想先选择前 4 行 然后选择下 4 行和最后 4 行 谁能告诉我如何在 Informix 中做到这一点 编辑 现在应该通
  • PySpark 2.x:以编程方式将 Maven JAR 坐标添加到 Spark

    以下是我的 PySpark 启动片段 非常可靠 我已经使用它很长时间了 今天我添加了两个 Maven 坐标 如图所示spark jars packages选项 有效地 插入 Kafka 支持 现在通常会触发依赖项下载 由 Spark 自动执
  • 如何从 PHP 调用网站服务?

    我的问题如下 我的服务器上有一个 EmailReports php 我用它来发送邮件 例如 电子邮件受保护 cdn cgi l email protection 什么 123456 pdf 我无法修改 EmailReports php 因为
  • 快速查找字符串是否在数组中的方法

    在 Ruby 中 查找字符串是否在数组中 include x 非常慢 如果将该数组更改为集合 则BAM 闪电般的快速查找 在 JavaScript 中 没有集合 数组查找 indexOf x gt 0 也是very很慢 但是我需要在脚本中执