range函数行为求解

[Ruiyun Wen]

在做4clojure #56的时候，遇到一个奇怪的问题

(keys (group-by identity (range 50))) 的结果竟然是(0 32 1 33 2 34  ...)！

初步分析应该是由于range函数用了一个容量为32的缓存，导致惰性求值时顺序错误。但以往出现类似问题，多是由于多线程访问，例如Oracle的序列。而本例中，应该没有引起并行求值的可能。

同时，我发现用(map identity (range 50))得到的结果就是正常顺序，我想也能初步证明应该不是由于惰性求值过程引起的问题。

PS：4clojure 的#56后来用reduce解决了，但希望能弄清上述问题的本质原因。

[Sun Ning]

group-by 得到的是一个map，这个顺序本身就不好说吧。。。
倒是有一个特殊的情况，似乎group-by会根据collection的类型返回不同的集合类型
user=> (class (group-by identity (range 50)))
clojure.lang.PersistentHashMap
user=> (class (group-by identity [1 2 3 4 5]))
clojure.lang.PersistentArrayMap

[dennis zhuang]

这个应该是range的chunked buffer引起的吧，一个chunk是32的长度。不过返回map本身就不保证顺序了吧。

--
庄晓丹
Email:        killm...@gmail.com xzh...@avos.com
Site:           http://fnil.net
Twitter:      @killme2008

[Ni HuaJie]

我实验了一下，应该是group-by的原因。。。。

你看我的笨办法：

(group-by identity '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35)) 

{32 [32], 1 [1], 33 [33], 2 [2], 34 [34], 3 [3], 35 [35], 4 [4], 5 [5], 6 [6], 7 [7], 8 [8], 9 [9], 10 [10], 11 [11], 12 [12], 13 [13], 14 [14], 15 [15], 16 [16], 17 [17], 18 [18], 19 [19], 20 [20], 21 [21], 22 [22], 23 [23], 24 [24], 25 [25], 26 [26], 27 [27], 28 [28], 29 [29], 30 [30], 31 [31]}

我扒了下源代码，确实没想通为什么会有这种奇怪但是又相对固定的顺序。。。。

坐等高手解释

[Sun Ning]

你说的这个顺序应该是恰好和哈希表的实现吻合上了
这个顺序是hashmap的实现导致的，我想恰好是32个bucket根据key取模，你看32，64所在的位置

貌似(vec (range 65))那个版本出来的依然是hashmap
要去了解一下实现才知道了

On Wed 16 May 2012 04:14:28 PM CST, Ruiyun Wen wrote:
> 一开始我也想可能是map排序的问题。于是我做了下面的实验
> (keys (group-by identity (range 32)))
> 结果是正常的，只有(range 33)及以上，才会出现问题。而32就是range的缓存
> 大小。
> 另外，谢谢Sun Ning的提示，于是我稍稍改动了一下进行测试，
> (keys (group-by identity (vec (range 50))))，
> 但结果与没有加vec相同。照理说，array-map就不会对元素顺序进行任何变动了。
> 所以我总觉得问题的根源应该更靠近range，而不是map。
>
> 另外，从大于32的结果上看。似乎有点像map函数传入2个集合参数时的那种交错
> 方式，不知道有否关联。
>
> 在 2012年5月16日 下午3:52，Sun Ning <class...@gmail.com
> <mailto:class...@gmail.com>>写道：
>
> group-by 得到的是一个map，这个顺序本身就不好说吧。。。
> 倒是有一个特殊的情况，似乎group-__by会根据collection的类型返回不同

> 的集合类型
> user=> (class (group-by identity (range 50)))
> clojure.lang.PersistentHashMap
> user=> (class (group-by identity [1 2 3 4 5]))

> clojure.lang.__PersistentArrayMap

>
>
> On Wed 16 May 2012 03:41:10 PM CST, Ruiyun Wen wrote:
>
> 在做4clojure #56的时候，遇到一个奇怪的问题
>
> (keys (group-by identity (range 50))) 的结果竟然是(0 32 1 33 2
> 34 ...)！

> 初步分析应该是由于range函数用了一个容量为32的缓存，__导致惰性
> 求值时顺序
> 错误。但以往出现类似问题，多是由于多线程访问，__例如Oracle的序

> 列。而本例
> 中，应该没有引起并行求值的可能。
>
> 同时，我发现用(map identity (range 50))得到的结果就是正常顺
> 序，我想也
> 能初步证明应该不是由于惰性求值过程引起的问题。
>

> PS：4clojure 的#56后来用reduce解决了，__但希望能弄清上述问题的
> 本质原因。
>
>
>
>

[dennis zhuang]

主要就是因为chunk buffer，group-by是用reduce实现的，而reduce的实现会对chunked buffer做特殊处理，看clojure.core.protocols:

  clojure.lang.IChunkedSeq

  (internal-reduce

   [s f val]

   (if-let [s (seq s)]

     (if (chunked-seq? s)

       (recur (chunk-next s)

              f

              (.reduce (chunk-first s) f val))

       (internal-reduce s f val))

     val))

结合group-by源码看就知道了。

[Ruiyun Wen]

我也觉得应该和这个chunked buffer有关，但从range函数的实现代码看，我确实找不出为什么顺序执行的代码会有这样奇怪的行为。

sorted-map是不保证的，但array-map和hash-map应该有保证

user=> (sorted-map :a "a" :c "c" :b "b")

{:a "a", :b "b", :c "c"}

user=> (array-map :a "a" :c "c" :b "b")

{:a "a", :c "c", :b "b"}

user=> (hash-map :a "a" :c "c" :b "b")

{:a "a", :c "c", :b "b"}

[Ruiyun Wen]

多谢大伙儿，。

[naitong Xiao]

返回类型跟长度有关
user> (class (group-by identity (range 8)))
clojure.lang.PersistentArrayMap

长度小于等于8的都是PersistentArrayMap， 属于性能优化吧
见PersistentArrayMap代码:
static final int HASHTABLE_THRESHOLD = 16;
.....
public IPersistentMap assocEx(Object key, Object val) {
        ....
        if(array.length > HASHTABLE_THRESHOLD)
            return createHT(array).assocEx(key, val);
        ....

[Sun Ning]

ԭ�����

On 05/16/2012 04:47 PM, naitong Xiao wrote:

�������͸���й�

user> (class (group-by identity (range 8)))
clojure.lang.PersistentArrayMap

����С�ڵ���8�Ķ���PersistentArrayMap�� ���������Ż���
��PersistentArrayMap����:

static final int HASHTABLE_THRESHOLD = 16;
.....
public IPersistentMap assocEx(Object key, Object val) {
        ....
        if(array.length > HASHTABLE_THRESHOLD)
            return createHT(array).assocEx(key, val);
        ....
}

�� 2012��5��16�� ����3:52��Sun Ning <class...@gmail.com>д ����

group-by �õ�����һ��map�����˳����Ͳ���˵�ɡ�����
������һ�������������ƺ�group-by����collection�����ͷ��ز�ͬ�ļ�������

user=> (class (group-by identity (range 50)))
clojure.lang.PersistentHashMap
user=> (class (group-by identity [1 2 3 4 5]))
clojure.lang.PersistentArrayMap

On Wed 16 May 2012 03:41:10 PM CST, Ruiyun Wen wrote:

����4clojure #56��ʱ������һ����ֵ�����

(keys (group-by identity (range 50))) �Ľ��Ȼ��(0 32 1 33 2 34 ...)��
��������Ӧ��������range��������һ������Ϊ32�Ļ��棬���¶�����ֵʱ˳��
���󡣵���������������⣬�������ڶ��̷߳��ʣ�����Oracle�����С�����
�У�Ӧ��û����������ֵ�Ŀ��ܡ�

ͬʱ���ҷ�����(map identity (range 50))�õ��Ľ�������˳������Ҳ
�ܳ���֤��Ӧ�ò������ڶ�����ֵ�����������⡣

PS��4clojure ��#56������reduce����ˣ���ϣ����Ū����������ı���ԭ��

[dennis zhuang]

恩，主要还是类型提升引起的，我误导大家了，32这个关键字太敏感了。hash-map里是，chunked buffer也是。这个问题貌似有人问过 

http://stackoverflow.com/questions/9160781/why-does-clojures-group-by-not-always-maintain-order

[Ruiyun Wen]

原来如此，此雷埋得不浅啊!

误导也不全是坏事，为了求证，刚才调试了一下internal-reduce， 基本弄明白其机制，也算另得一份收获了。

在 2012年5月16日 下午5:15，dennis zhuang <killm...@gmail.com>写道：