Javascript 的引擎设计在更坏的情况下如何影响用户数据结构的实现?
How does Javascript's engine design affect user data structure implementations on worse case?
举个例子,一个JS web引擎通过使用哈希表来实现关联数组(对象)。但正如我们所知,哈希表的情况更糟 O(n) 因为冲突是不可避免的。
假设我开始使用 Javascript 开发一种新的数据结构,这种数据结构例如 LinkedList 对于 insert/delete 的情况更糟 O(1)。但是因为我用 object/array 实现了它。那么我的实现也必须是最坏情况 O(n)。
我知道这个引擎优化得很好,一个好的散列函数平均生成 O(1)。然而,我只是想证实我的认识,即这并不像教科书所说的那么简单。还是?
我想所有数据结构的根都是用数组实现的,因为访问总是 O(1),那么不应该所有数据结构都用没有中间结构的数组构建吗?另外,动态数组仍然有 delete O(n) 不能像我之前的例子一样是可以滴下来的同一个问题吗?
这就是使用低级编程语言比使用高级语言的优势所在吗?这么低级就没有那么多抽象,教科书上的复杂度居然能匹配?
如果我的想法到处都是,请道歉。
But since I implement [my custom data structure] with object/array. Then it must be true that my implementation is also at minimum worse case O(n) as well.
没有。您的链接列表不会在任何地方使用带有 n
键的对象。你会得到一个
const linkedListNode = {
value: …,
next: null,
};
但即使此 是 使用具有 O(n)
最坏情况成员访问权限的哈希表实现的,在您的情况下 n=2
。您的对象中没有任意多个属性,只有两个。这就是你回到 O(1)
.
的方式
Is this where the benefit of using a low level programming language is better than using high level language? Such that low level there isn't so much abstraction and the textbook complexity numbers can actually match?
没有。即使在较低级别的编程语言中,您也可以开始质疑底层抽象。你认为在 C 中,内存中的索引数组访问是常数时间?不,因为页面错误和其他缓存恶作剧开始发挥作用。
这就是为什么教科书的复杂性总是用 machine model 来定义的原因。只要您将 JavaScript 执行模型中的对象 属性 访问定义为恒定时间(这样做是一个非常合理的假设!它与现实世界非常相似),您的数字确实适用于 JavaScript代码也是如此。当然,您可以尝试解开抽象并根据较低级别的原语分析您的高级算法,但这样做没有意义。这正是我们首先拥有这些抽象的原因。
“使用哈希表的关联数组(对象)”-> Javascript 对象很复杂并且不仅仅是“它是一个哈希映射”。我不知道确切的技术细节,但我认为它们会在存储一定数量的值后更改为哈希映射,同时它们还存储元数据,这些元数据用于 Object.keys
等其他算法以自动排序从哈希映射中拉出后的密钥。同样,我不知道技术细节,但我知道,这不是直截了当的。
“因为我们知道哈希表有更坏的情况 O(n) 因为冲突是不可避免的”-> 这取决于您使用的是什么哈希,但更重要的是,即使冲突是不可避免的,仅仅声明也是不正确的“更糟糕的情况是 O(n)”并保留它,因为它是 O(n) 的概率以对数方式下降到 0,它一次又一次地发现碰撞的机会是极不可能的,所以虽然它可以也许找到一个不能有效描述时间复杂度的碰撞。
“我的实现也至少是 O(n) 的最坏情况” -> 不正确,你说的是两件不同的事情。如果你构建一个链表,每个节点将使用堆引用连接到下一个节点,这与 javascript 对象无关。遍历整个链表将是 O(n),但这是因为必须遍历每个下一个节点,而不是因为任何对象或哈希。
"worse case O(1) for insert/delete" -> 仅当您有对要 insert/delete 的节点的引用时才为真,否则您将不得不在 insertion/deletion 之前搜索它。但这在 javascript.
中完全相同
“那么不应该所有数据结构都用没有中间结构的数组构建吗”-> 我知道的大多数数据结构(如列表、堆栈、队列)都是在普通数组之上实现的。那些不是的(比如二叉树、dictionary/map 或链表)没有在数组上实现,因为它实际上没有意义。例如,将对象引用与链表一起使用的全部意义在于,您可以直接 insert/delete 某些东西,而在幕后使用数组只会在您专门尝试时打败使用链表的全部意义提前获取对象引用。
“动态数组仍然有 delete O(n) 不能是同一个问题,它可以像我之前的例子一样滴入”-> 不一定,因为当你将东西包装在一个对象中并在其中使用一个内部数组时,您可以添加元数据、索引、散列、存储在数组外部的东西(对象私有)和各种其他东西来加速和跟踪该数组上的东西。因此,内部使用的复杂性不会自动溢出到在另一个对象中使用它。但是你确实需要小心,比如如果你使用一个列表,那么它在 C# 等语言中的内部工作原理是,当你尝试在它已满后向它添加更多元素时,它会使内部数组加倍,这可能会导致大量内存浪费。
据说 javascript 的用例在 99% 的情况下都不是“再优化 10 毫秒”,javascript 之所以被使用是因为它的非 IO 阻塞性质,流式传输,async/await 响应式编程,它的开发速度很快,它也有 90% 用于网络通信,而不是一些高度优化的图形引擎。因此,在极少数情况下,您需要超过 9000 项复杂性优化、功能开发、代码可读性、可维护性,这些在 JS 中通常是更重要的事情。除此之外,在大多数用例中,您不会使用 JS 从您的数据库中请求 1m 数据记录,通常是您想要在页面上显示的 50 条,为此您将使用数据库来优化您的查询,几乎没有在任何 JS 开发(或一般的 Web 开发)中都需要使用如此大的数据结构。提取您需要的东西并请求更多或不断地将您需要的东西流式传输给客户要好得多。所以很多数据结构(比如二叉树)与 JS 中的东西并不真正相关,除非它是一个非常具体的用例。
举个例子,一个JS web引擎通过使用哈希表来实现关联数组(对象)。但正如我们所知,哈希表的情况更糟 O(n) 因为冲突是不可避免的。
假设我开始使用 Javascript 开发一种新的数据结构,这种数据结构例如 LinkedList 对于 insert/delete 的情况更糟 O(1)。但是因为我用 object/array 实现了它。那么我的实现也必须是最坏情况 O(n)。
我知道这个引擎优化得很好,一个好的散列函数平均生成 O(1)。然而,我只是想证实我的认识,即这并不像教科书所说的那么简单。还是?
我想所有数据结构的根都是用数组实现的,因为访问总是 O(1),那么不应该所有数据结构都用没有中间结构的数组构建吗?另外,动态数组仍然有 delete O(n) 不能像我之前的例子一样是可以滴下来的同一个问题吗?
这就是使用低级编程语言比使用高级语言的优势所在吗?这么低级就没有那么多抽象,教科书上的复杂度居然能匹配?
如果我的想法到处都是,请道歉。
But since I implement [my custom data structure] with object/array. Then it must be true that my implementation is also at minimum worse case O(n) as well.
没有。您的链接列表不会在任何地方使用带有 n
键的对象。你会得到一个
const linkedListNode = {
value: …,
next: null,
};
但即使此 是 使用具有 O(n)
最坏情况成员访问权限的哈希表实现的,在您的情况下 n=2
。您的对象中没有任意多个属性,只有两个。这就是你回到 O(1)
.
Is this where the benefit of using a low level programming language is better than using high level language? Such that low level there isn't so much abstraction and the textbook complexity numbers can actually match?
没有。即使在较低级别的编程语言中,您也可以开始质疑底层抽象。你认为在 C 中,内存中的索引数组访问是常数时间?不,因为页面错误和其他缓存恶作剧开始发挥作用。
这就是为什么教科书的复杂性总是用 machine model 来定义的原因。只要您将 JavaScript 执行模型中的对象 属性 访问定义为恒定时间(这样做是一个非常合理的假设!它与现实世界非常相似),您的数字确实适用于 JavaScript代码也是如此。当然,您可以尝试解开抽象并根据较低级别的原语分析您的高级算法,但这样做没有意义。这正是我们首先拥有这些抽象的原因。
“使用哈希表的关联数组(对象)”-> Javascript 对象很复杂并且不仅仅是“它是一个哈希映射”。我不知道确切的技术细节,但我认为它们会在存储一定数量的值后更改为哈希映射,同时它们还存储元数据,这些元数据用于 Object.keys
等其他算法以自动排序从哈希映射中拉出后的密钥。同样,我不知道技术细节,但我知道,这不是直截了当的。
“因为我们知道哈希表有更坏的情况 O(n) 因为冲突是不可避免的”-> 这取决于您使用的是什么哈希,但更重要的是,即使冲突是不可避免的,仅仅声明也是不正确的“更糟糕的情况是 O(n)”并保留它,因为它是 O(n) 的概率以对数方式下降到 0,它一次又一次地发现碰撞的机会是极不可能的,所以虽然它可以也许找到一个不能有效描述时间复杂度的碰撞。
“我的实现也至少是 O(n) 的最坏情况” -> 不正确,你说的是两件不同的事情。如果你构建一个链表,每个节点将使用堆引用连接到下一个节点,这与 javascript 对象无关。遍历整个链表将是 O(n),但这是因为必须遍历每个下一个节点,而不是因为任何对象或哈希。
"worse case O(1) for insert/delete" -> 仅当您有对要 insert/delete 的节点的引用时才为真,否则您将不得不在 insertion/deletion 之前搜索它。但这在 javascript.
中完全相同“那么不应该所有数据结构都用没有中间结构的数组构建吗”-> 我知道的大多数数据结构(如列表、堆栈、队列)都是在普通数组之上实现的。那些不是的(比如二叉树、dictionary/map 或链表)没有在数组上实现,因为它实际上没有意义。例如,将对象引用与链表一起使用的全部意义在于,您可以直接 insert/delete 某些东西,而在幕后使用数组只会在您专门尝试时打败使用链表的全部意义提前获取对象引用。
“动态数组仍然有 delete O(n) 不能是同一个问题,它可以像我之前的例子一样滴入”-> 不一定,因为当你将东西包装在一个对象中并在其中使用一个内部数组时,您可以添加元数据、索引、散列、存储在数组外部的东西(对象私有)和各种其他东西来加速和跟踪该数组上的东西。因此,内部使用的复杂性不会自动溢出到在另一个对象中使用它。但是你确实需要小心,比如如果你使用一个列表,那么它在 C# 等语言中的内部工作原理是,当你尝试在它已满后向它添加更多元素时,它会使内部数组加倍,这可能会导致大量内存浪费。
据说 javascript 的用例在 99% 的情况下都不是“再优化 10 毫秒”,javascript 之所以被使用是因为它的非 IO 阻塞性质,流式传输,async/await 响应式编程,它的开发速度很快,它也有 90% 用于网络通信,而不是一些高度优化的图形引擎。因此,在极少数情况下,您需要超过 9000 项复杂性优化、功能开发、代码可读性、可维护性,这些在 JS 中通常是更重要的事情。除此之外,在大多数用例中,您不会使用 JS 从您的数据库中请求 1m 数据记录,通常是您想要在页面上显示的 50 条,为此您将使用数据库来优化您的查询,几乎没有在任何 JS 开发(或一般的 Web 开发)中都需要使用如此大的数据结构。提取您需要的东西并请求更多或不断地将您需要的东西流式传输给客户要好得多。所以很多数据结构(比如二叉树)与 JS 中的东西并不真正相关,除非它是一个非常具体的用例。