请问 node 有没有处理JSON 行列 转换的包?
发布于 6 年前 作者 bsspirit 4562 次浏览 最后一次编辑是 4 年前

比如:下面JSON, 从列转行 和 行转列,如何快速实现? 尽量保证在O(0)到O(n)的时间复杂度。

[
 {"field":"date","data":[20080102,20080103,20080104,20080105,20080106,20080107,20080108,20080109,20080110]},
 {"field":"x1","data":[1.5916,2.5916,3.5916,3.5916,3.9916,2.5916,9.5916,3.5916,3.5916]},
 {"field":"x2","data":[1.4916,7.5916,1.5916,2.5916,3.116,1.5916,7.5916,0.5916,3.5916]}
 ]

列转行

[
{"date":20080102,"x1":1.5916,"x2":1.4916},
{"date":20080103,"x1":1.5916,"x2":1.4916},
{"date":20080104,"x1":1.5916,"x2":1.4916},
{"date":20080105,"x1":1.5916,"x2":1.4916},
{"date":20080106,"x1":1.5916,"x2":1.4916}
]

评论就不单独回复了:

自己实现的算法 O(m+n),见文件中的 exports.col2row2 函数定义。 https://github.com/bsspirit/ape-algorithm/blob/master/rowcol.js

26 回复

这个自己写几句代码就搞定啊

@chloe 如果几句代码,就麻烦你来写几句吧!谢谢

trans = (data) ->
	results = []
	for item in data
		for value, index in item.data
			results[index] ?= {}
			results[index]["#{item.field}"] = value
	results

O(m*n)

@ravenwang O(m*n),这个有点慢了。 如果 field 和 data,分两次操作,而不是嵌套循环是O(m+n),我已经实现了。

我希望有小于 O(n) 的算法。谢谢。

@chloe O(m*n) 是不可接受的时间复杂度。

@bsspirit m应该是个常数,为什么不可接受

@bsspirit O(m+n)的发来看看

列转行转过来结果是不是应该是: [ {“date”:20080102,“x1”:1.5916,“x2”:1.4916}, {“date”:20080103,“x1”:2.5916,“x2”:7.4916}, {“date”:20080104,“x1”:3.5916,“x2”:1.4916}, {“date”:20080105,“x1”:3.5916,“x2”:3.4916}, {“date”:20080106,“x1”:2.5916,“x2”:1.4916}. … ]

m+n的怎么实现的?

@bsspirit 发下你的算法看看? @ravenwang 这个已经最快了吧?

@bsspirit 这个类似于矩阵转置,貌似没有低于O(n^2)的算法吧

理论上只能遍历硬转,m * n (field * row),那位 m+n 的不妨贴出来让咱学习学习~

看下lodash这个库,我记得这个库里有实现方法(没看源码),你可以看看

帖子已更新,就不单独回复了。

@bsspirit 亲,你这只是把本来用循环来执行的n个操作拍平了用eval来执行而已… 要这能算O(m+n)的话任何算法我都能搞个O(1)的版本出来:改成字符串eval一下就是了

你们用用大量数据来测试一下,你的这种写法比二楼的写法,花的时间更长,时间复杂度应该是一系统操作所谓的时间吧,eval这种操作的时间复杂度不是O(1)

@ravenwang 期待O(1)的大作,我是想不到怎么写。

@chloe 确实是要做个压力测试,看看效果。

@bsspirit 我的意思是你这还是个O(m*n),你拼那个字符串然后在底下的循环中eval相当于一个内层循环,没有任何意义,反而要增加字符串拼接和eval的代价

写了一个速度测试:idy/53eae4fff4b616a82f025533

其实从根本的角度考虑一下,你想做行列变换,几乎要把每个元素都移动一遍才可以,所以每个元素至少都要访问一遍,复杂度至少是 O(n*m) 的。就像你读书,不管你读的是电子书,还是纸质书,先读目录在读正文,或者从后面往前读,你总要每个字都看一遍才算读完的,复杂度最少就是字的个数。 用 eval 只是省去你写代码访问每行的元素,但是 eval 中包含了列数那么多行的赋值代码,如果你把 eval 里面的代码粘贴在 eval 那里,你再看看复杂度,还是 O(n*m) 么。

下面是测试结果:

Speed test
    Scale at: 800 x 800
      ✓ col2row (392ms)
      ✓ col2row2 (454ms)
      ✓ col2row should equal to col2row2 (1ms)
    Scale at: 400 x 1600
      ✓ col2row (315ms)
      ✓ col2row2 (337ms)
      ✓ col2row should equal to col2row2
    Scale at: 200 x 3200
      ✓ col2row (412ms)
      ✓ col2row2 (936ms)
      ✓ col2row should equal to col2row2
    Scale at: 100 x 6400
      ✓ col2row (387ms)
      ✓ col2row2 (264ms)
      ✓ col2row should equal to col2row2
    Scale at: 50 x 12800
      ✓ col2row (331ms)
      ✓ col2row2 (97ms)
      ✓ col2row should equal to col2row2

  Complexity test
    Scale at: 100 x 100
      ✓ linear
      ✓ col2row2 (3ms)
      ✓ col2row (5ms)
    Scale at: 200 x 200
      ✓ linear
      ✓ col2row2 (30ms)
      ✓ col2row (26ms)
    Scale at: 400 x 400
      ✓ linear (1ms)
      ✓ col2row2 (96ms)
      ✓ col2row (87ms)
    Scale at: 800 x 800
      ✓ linear
      ✓ col2row2 (552ms)
      ✓ col2row (722ms)
    Scale at: 1600 x 1600
      ✓ linear
      ✓ col2row2 (2672ms)
      ✓ col2row (1854ms)


  30 passing (10s)

楼主有点搞笑了, 掩耳盗铃.

@idy 棒! @ravenwang 来看楼主的回复

@idy 多谢回复,我找时间按你的程序测试一下!

@alsotang 楼主的回复在哪里……

@ravenwang 虽然不是O(n+m) 但是测试之后感觉 列数较小的时候 eval 会快很多,因为eval 执行的语句带缓存。 我的repo里解释了一下 ;) 下面这个case:

Scale at: 50 x 12800
      ✓ col2row (331ms)
      ✓ col2row2 (97ms)
      ✓ col2row should equal to col2row2
回到顶部