`
mlzboy
  • 浏览: 726505 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

ordered hash in ruby 1.9 embedded wow!

阅读更多

Talk Like A Duck

In Ruby, it's not the dog, it's the tricks!

<!-- end header -->
<!-- sidebar components -->
Click here to lend your support to: Help me give my Ruby Conf Talk and make a donation at www.pledgie.com !

I'm an old Smalltalker to whom Ruby looks like an old friend. To get a perspective on my perspective and credentials, have a look at my mini-memoirs


Click here to lend your support to: ri_cal and make a donation at www.pledgie.com !

If you like my blog, you might consider recommending me on Working With Rails.

Recommend Me

Rails Core Contributor

Rails Hackfest Winner

Categories

Syndicate

Archives

Spinner-blue <script></script>

Tags

agile agility C ducks git implementation inheritance java kentbeck performance rails rical Rspec ruby rubyconf self smalltalk testing types ubuntu

<!-- -->

Ordered Hashes, In Ruby 1.9 and Javascript

Posted by Rick DeNatale on 2009年04月15日

My “evil twin,” Patrick Mueller, recently opined about a possible change in the Javascript (officially called ECMAScript) specification to make Javascript objects have a defined enumeration order for their properties. In Javascript, every object is basically a Hash which maps property names to property values.

The existing ECMAScript spec says that an object is an “unordered collection of properties.” But apparently recent drafts have omitted the word unordered.

It turns out that MOST existing JavaScript implementations enumerate object properties in the order in which those properties were added to the object. This was pointed out in an article by John Resig about the JavaScript engine in Google’s Chrome browser. The Chrome JavaScript VM had a few cases for which this was not the case. Despite the fact that the ECMAScript standard doesn’t/didn’t require a standard order, the Chrome team decided that the incompatibility with the other “major browsers” constituted a bug.

Patrick is not happy about this.

There’s an interesting parallel here with changes in Ruby Hashes between Ruby 1.8 and Ruby 1.9.

A few years back there were heated discussions on the Ruby-talk forum about the “need” for an ordered hash. One aspect of this is what the ordering should be. Some advocated that a Hash should be enumerated by the sorted order of the keys (assuming that the keys were all comparable) This would mean that a Hash with integer keys would enumerate similarly to an Array. Another camp wanted ordering by insertion order.

At the time my reaction to this was similar to Patrick’s Hashes are all about speed, and the whole notion of a Hash was based on what I’d learned about hashing in my computer science classes years ago. Hashes are inherently unordered, and adding ordering would introduce unnecessary overhead.

Then Matz snuck ordered hashes into Ruby 1.9.

Ruby 1.9 hashes enumerate in the order in which their elements were inserted. This is nice, but at what cost.

It turns out that this is mostly a space cost. In Ruby 1.8, each hash entry needs 4 things, the hash value, a reference to the key, a reference to the data, and a pointer to the next hash entry with the same hash value should there be a hash collision. Depending on the platform each of this is roughly a word.

Ruby 1.9 adds two more pointers to each entry, forward and backward pointers which allow the entries to be chained together in a doubly linked list. There are also two pointers to the first and last entries in the whole hash. So besides the space cost, there is a small additional cost for element insertion and deletion.

When an element is inserted (which is always at the end of the list), either the first entry pointer (if this is the first element) or the forward pointer in the last element needs to be updated, and the backward pointer in the new element gets set to the old last element, (or 0).

When an element is deleted, the forward pointer of the previous element (or the first pointer if we are deleting the last element) and the backward pointer of the next element (or the last pointer if we are deleting the last element) need to be updated.

The performance of looking up an element is unaffected, as long as the hash is just being read, the linked list will remain unchanged.

And what about enumerating.

It turns out that enumerating Ruby 1.9 hashes is slightly faster than enumerating Ruby 1.8 hashes, even though one might think that preserving enumeration order would be a burden.

In Ruby 1.8 enumerating a hash is done by visiting each entry in an array of entries, and checking whether or not it actually contains a value. Empty hash entries have a special value ‘reference’ indicating that the value is undefined.

In Ruby 1.9 enumerating a hash is done by starting with the first entry pointer and following the forward pointers. Every entry on the list is actually a defined element.

All in all the speed difference is rather minimal, and there are certainly cases where having a fixed enumeration order is nice.

In the case of JavaScript, since the major implementations all have fixed property enumeration orders, there are undoubtedly applications which rely on it, and Chrome’s decision, to go with the pragmatics of compatibility, rather than appealing to the lack of a specified ordering makes sense, at least to me.

分享到:
评论

相关推荐

    ORDERED Hint in Complex Searches

    Subject: ORDERED Hint in Complex Searches Doc ID: 408049.1 Type: PROBLEM Modified Date : 08-JUL-2009 Status: PUBLISHED

    java ordered接口应用

    Java中的`Ordered`接口主要用在需要定义顺序或者排列规则的场景,特别是在Spring框架中,它在Bean的初始化和销毁顺序、AOP切面的执行顺序等方面起到关键作用。`Ordered`接口仅包含一个方法`getOrder()`,返回一个...

    sas hash简介与实例.pdf

    其中,hashexp: 4 指定 Hash 表的大小为 2 的 4 次方,dataset: 'work.sales' 指定需要映射到 Hash 表的数据集,ordered: 'yes' 指定在 Hash 表中根据关键字升序排序。 Hash 表提供了多种操作,例如: * FIND:...

    PyPI 官网下载 | orderedset-1.2.tar.gz

    标题中的"PyPI 官网下载 | orderedset-1.2.tar.gz"表明这是一个在Python Package Index (PyPI)上发布的软件包,名为`orderedset-1.2`,并且是以`.tar.gz`格式提供的。PyPI是Python社区用于分发、发现和安装第三方...

    hash table spell checking

    3. Next, complete the hash function encapsulated in class hash_function in dictionary.h. 4. Then, finish the implementation of function check_spelling. This function already contains code that reads ...

    数据结构作业Hash表

    3. Next, complete the hash function encapsulated in class hash_function in dictionary.h. 4. Then, finish the implementation of function check_spelling. This function already contains code that reads ...

    北大POJ2533-Longest Ordered Subsequence【O(nlogn)】

    北大POJ2533-Longest Ordered Subsequence【O(nlogn)】

    Laravel开发-ordered-eloquent

    "Laravel开发-ordered-eloquent"这个项目则是针对Eloquent ORM的一个扩展,旨在实现自动排序查询结果的功能。 这个扩展名为Ordered Eloquent,其主要目标是让开发者在使用Eloquent查询时,能够更加方便地对结果进行...

    Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释

    Pku acm 第2533题 Longest Ordered Subsequence 代码,有详细的注释,动态规划

    M13OrderedDictionary, 带有有序对象和键的NSDictionary.zip

    M13OrderedDictionary, 带有有序对象和键的NSDictionary M13OrderedDictionaryM13OrderedDictionary是NSArray和NSDictionary之间的交叉。 它包含一个有序的对象和键列表。 所有这些都可以通过索引或者键访问。 这里...

    ordered-set:定义自定义迭代顺序的高性能 ES6 Set 子类

    有序集 ordered-set是一个高性能的 ES6 Set 子类,它允许控制迭代顺序。... // iterates in order defined by mySortingFunction } 安装 npm install ordered-set 用法 const OrderedSet = require

    POJ2533-Longest Ordered Subsequence

    标题“POJ2533-Longest Ordered Subsequence”是指北京大学在线判题系统POJ上的一道编程题目,其核心任务是寻找一个序列中最长的有序子序列。描述中的“解题报告+AC代码”表明这个压缩包包含了对这道问题的解答思路...

    OrderedDictionary, 这里库提供OrderedDictionary和MutableOrderedDictionary子类.zip

    OrderedDictionary, 这里库提供OrderedDictionary和MutableOrderedDictionary子类 命令行目存储在NSDictionary中的对象的顺序未定义。 通常,可以以通过一组键/值对循环,并按照插入的顺序返回对象。 这个库提供了两...

    oracle的hint函数

    介绍了oracle中的hint,常用的 ordered、use_nl、use_hash、index、full 五种, 给出使用实例和适用场景

    OrderedSet:具有定义顺序的集合

    OrderedSet 静态的,有序的唯一对象集合。 关于 简而言之, OrderedSet是Array和Set的混合体。 像Array一样,它的元素具有定义的顺序,但是它像Set一样在其成员上强制唯一性。 在以下情况下,可以使用OrderedSet...

    OrderedList:OrderedList(与JDK1.7一起编译)

    在Java编程语言中,`OrderedList`是一种特殊的集合类,它不仅提供了集合的基本操作,如添加、删除和查找元素,还特别强调了元素的顺序。标题"OrderedList:OrderedList(与JDK1.7一起编译)"暗示了这个项目或者库是...

    ordered-map:保留插入顺序的C ++哈希映射和哈希集

    "ordered-map"是一个库,它提供了一种特殊的哈希映射(HashMap)和哈希集(HashSet)实现,特点是它们能保留元素的插入顺序。这对于需要同时保持键值对排序和高效查找的场景非常有用。在C++标准库中,`std::map`和`...

    ordered-set:记住条目顺序的可变集。 Python缺少的数据类型之一

    OrderedSet是一种可变数据结构,它是列表和集合的混合体。 它会记住其条目的顺序,并且每个条目都有一个可以查找的索引号。 用法示例 一个OrderedSet被创建并像一个set一样使用: &gt;&gt;&gt; from ordered_set import ...

Global site tag (gtag.js) - Google Analytics