javascript 复杂度是O(1)还是O(2)?

brvekthn  于 2023-04-10  发布在  Java
关注(0)|答案(3)|浏览(151)

对于我最近写的一些算法,我认为散列会很好。我认为我可能只是使用对象中的成员变量作为键值对。我不确定这是否是最佳的,因为我真的不知道幕后发生了什么。我也假设V8与其他环境不同。然而,我确实想象查找成员变量会非常快(希望)?
这就是说,我想知道在JavaScript对象中写入,阅读,创建和删除成员变量的运行时复杂度是否都是O(1)。如果环境有差异(v8与其他),它们是什么?

r6hnlfcb

r6hnlfcb1#

性能方面,将它们视为哈希值似乎是安全的。历史上有很多文章说不要相信它。从我的经验来看,肯定有一些情况下,对象可能比Map更符合人体工程学。
基准测试-https://jsfiddle.net/soparrissays/Lt0znmxw/
你可以看到,无论对象的大小如何,每个CRUD操作都能够执行大约相同数量的ops/sec,这表明每个操作都是O(1)。下面是在Chrome中运行的:

100 keys (create) x 13,326,160 ops/sec ±9.42% (34 runs sampled)
1k Keys (create) x 13,757,260 ops/sec ±9.15% (34 runs sampled)
100k Keys (create) x 12,434,691 ops/sec ±7.91% (34 runs sampled)
1M Keys (create) x 12,678,435 ops/sec ±13.12% (38 runs sampled)
100 keys (read) x 80,126,804 ops/sec ±0.24% (101 runs sampled)
1k Keys (read) x 80,333,384 ops/sec ±0.14% (102 runs sampled)
100k Keys (read) x 80,154,201 ops/sec ±0.17% (103 runs sampled)
1M Keys (read) x 80,259,463 ops/sec ±0.13% (98 runs sampled)
100 keys (update) x 71,771,379 ops/sec ±0.19% (100 runs sampled)
1k Keys (update) x 71,851,829 ops/sec ±0.13% (103 runs sampled)
100k Keys (update) x 71,804,254 ops/sec ±0.13% (103 runs sampled)
1M Keys (update) x 71,770,332 ops/sec ±0.13% (98 runs sampled)
100 keys (destroy) x 22,673,628 ops/sec ±0.52% (100 runs sampled)
1k Keys (destroy) x 20,852,449 ops/sec ±0.60% (93 runs sampled)
100k Keys (destroy) x 21,137,940 ops/sec ±0.86% (97 runs sampled)
1M Keys (destroy) x 21,436,091 ops/sec ±0.56% (96 runs sampled)

在过去,我看到其他浏览器的行为类似。

2023更新

我应该只读源代码-如果我阅读这个权利,这是一个Map与更多的功能围绕它https://github.com/v8/v8/blob/2b79cfd81f6acdfec29661ce2b39d60f4a45b14f/src/objects/js-objects.cc#L2391

MaybeHandle<JSObject> JSObject::New(Handle<JSFunction> constructor,
                                    Handle<JSReceiver> new_target,
                                    Handle<AllocationSite> site) {
  // If called through new, new.target can be:
  // - a subclass of constructor,
  // - a proxy wrapper around constructor, or
  // - the constructor itself.
  // If called through Reflect.construct, it's guaranteed to be a constructor.
  Isolate* const isolate = constructor->GetIsolate();
  DCHECK(constructor->IsConstructor());
  DCHECK(new_target->IsConstructor());
  DCHECK(!constructor->has_initial_map() ||
         !InstanceTypeChecker::IsJSFunction(
             constructor->initial_map().instance_type()));

  Handle<Map> initial_map;
  ASSIGN_RETURN_ON_EXCEPTION(
      isolate, initial_map,
      JSFunction::GetDerivedMap(isolate, constructor, new_target), JSObject);
  constexpr int initial_capacity = V8_ENABLE_SWISS_NAME_DICTIONARY_BOOL
                                       ? SwissNameDictionary::kInitialCapacity
                                       : NameDictionary::kInitialCapacity;
  Handle<JSObject> result = isolate->factory()->NewFastOrSlowJSObjectFromMap(
      initial_map, initial_capacity, AllocationType::kYoung, site);
  return result;
}

我推测Map可能会给你带来一些性能,但是它的clear对象非常快,而且它们的属性看起来属于一个hash。所以当然要选择合适的工具来完成这项工作。如果你需要围绕Object构建的所有工具,使用它们仍然是安全的!

pu82cl6c

pu82cl6c2#

JavaScript对象 * 是 * 散列。我无法想象任何正常的实现不会对对象属性提供恒定时间的CRUD操作。
您是否发现这种方法存在特定的性能问题?

hc2pp10m

hc2pp10m3#

JavaScript中的对象是哈希表的一个例子,因为对象数据被表示为键和值。

相关问题