由“千万字母表问题”看多范式编程语言_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > 由“千万字母表问题”看多范式编程语言

由“千万字母表问题”看多范式编程语言

 2017/6/22 5:31:45  jywhltj  程序员俱乐部  我要评论(0)
  • 摘要:本也发在我的个人博客上:https://hltj.me/lang/2016/11/07/10m-letters.html。最近整理多范式编程语言共性及趋势,再次翻出今年夏天的时候瓜哥(@2gua)在微博上出的一个题目:【来做题】功能实现倒是很简单~用你熟悉的语言,统计一个字符串abcdefghijklmnopqrstuvwxyz…abcdefghijklmnopqrstuvwxyz(1千万个a-z,不可直接a=1千万……)中每个字母的个数,最后输出类似图示。要求除了更好的方式
  • 标签:问题 编程 编程语言

本也发在我的个人博客上:https://hltj.me/lang/2016/11/07/10m-letters.html?。

最近整理多范式编程语言共性及趋势,再次翻出今年夏天的时候瓜哥(@2gua)在微博上出的一个题目:

【来做题】功能实现倒是很简单~ 用你熟悉的语言,统计一个字符串abcdefghijklmnopqrstuvwxyz…abcdefghijklmnopqrstuvwxyz(1千万个a-z,不可直接a=1千万……) 中每个字母的个数,最后输出类似图示。要求除了更好的方式(如更加Pythonic的方式),还要计算越快越好,并打印出代码执行时间(打印效果类似图示)?

当时分别写了 Rust、Kotlin 和 Julia 版本,加上近期写的 Java 8 版,其速度分别与作为基准的 Ruby 代码做对比,在一台配置略低的虚拟机中运行多次取中位数如下:

Ruby 2.3.1 Rust 1.11.0 Kotlin 1.0.3 Java 1.8.0_112 Julia 0.4.6 class="highlighter-rouge">8.4s+ 6.4s+ 18.8s+ 5.8s+ 170s+

之所以用 Ruby 版代码作为基准,是因为它的速度非常快,而且其代码也很优雅,代码在 @mulder 的基础上改了一点,使其更合乎函数式编程风格:

require "benchmark"
time = Benchmark.realtime do
	s = (('a'..'z').to_a.join * 1000_0000)
	h = Hash[('a'..'z').collect {|c| [c, s.count(c)]}]
	puts h
end

puts time

Julia

从上面速度数据看,Julia 版代码最慢,但其代码最简洁:

function f()
       s = repeat(join('a':'z'), 1000_0000)
       [ c=>count(i->i==c, s) for c in 'a':'z' ]
end

@time println(f())

它与 Ruby 版的实现很类似,但从速率上看,它优化的并不是很好。

Rust

Rust 版的速度很快,但是其实多写了不少代码:

use std::time::SystemTime;

fn logarithmic_repeat(mergeable: &Vec<u8>, num: usize) -> Vec<u8> {
    let mut result: Vec<u8> = Vec::with_capacity(mergeable.len() * num);
    let mut mergeable: Vec<u8> = mergeable.clone();
    let mut num = num;

    while num != 0 {
        if num & 1 != 0 {
             result.extend(mergeable.as_slice().iter());
        }

        num >>= 1;

        if num == 0 {
            break;
        }
        let mergeable_clone: Vec<u8> = mergeable.clone();
        mergeable.extend(mergeable_clone.as_slice().iter());
    }
    result
}

fn main() {
    let now = SystemTime::now();
    let letters: Vec<u8> = (b'a'..b'z'+1).collect();
    let repeated: Vec<u8> = logarithmic_repeat(&letters, 1000_0000);
    for b in letters {
        print!("{}: {}, ", b as char, repeated.iter().filter(|&x| *x==b).count());
    }
    let elapsed = now.elapsed().unwrap();
    println!("\ntime: {}.{:09}s", elapsed.as_secs(), elapsed.subsec_nanos());
}

上述代码已经是比较简洁的了,Rust 语言因为独有的生命周期机制,写起来略显复杂。但是更多的代码是为避免速度输在起跑线上而实现对数级的重复(相当于 Ruby 的?*?和 Julia 的?repeat()?函数),这是 Rust 标准库所欠缺的地方。

Java 8

更快的就是近期写的 Java 8 版代码:

import java.util.Collections;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Z {
    public static void main(String[] args) {
	long startTime=System.currentTimeMillis();

        String letters = IntStream.rangeClosed('a', 'z')
                .mapToObj(c -> "" + (char)c)
                .collect(Collectors.joining());

        String repeated = Collections.nCopies(1000_0000, letters)
                .parallelStream()
                .collect(Collectors.joining());

        Map<String, Long> result = repeated.chars()
                .parallel()
                .mapToObj(c -> "" + (char)c)
                .collect(
                        Collectors.groupingBy(
                                Function.identity(),
                                Collectors.counting()
                        )
                );

	long endTime=System.currentTimeMillis();
        System.out.println(result);
	System.out.println("" + (endTime - startTime) / 1000.0 + "s");
    }
}

Java 8 版代码是最啰嗦的,它并不需要自己实现对数级重复,但是它的代码量已经与 Rust 版相当了;另一 Java 8 的不足是,尚未支持简单变量的类型推断,当然这也是其啰嗦的成因之一。 说完了缺点,现在看其优点:

  1. 丰富的 Collector:groupingBy()?与?counting()?的组合完美实现了此功能,从而避免了像 Rust 版、Ruby 版那样重复扫描巨大字符串 26 次。
  2. .parallelStream()?和?.parallel()?方法获得并行流,其后能够并行计算,这是它能够在速度上胜出的另一个因素。

Kotlin

Kotlin 版的实现与 Ruby 非常类似,只是没有 Ruby 那么多的语法糖:

import kotlin.system.measureTimeMillis

fun main(args : Array<String>) { 
    print(measureTimeMillis {
        val letters = ('a'..'z').joinToString(separator="")
        val repeated = letters.repeat(1000*10000)
        println(letters.map { x -> Pair(x, repeated.count {it == x}) })
    } / 1000.0)
    println('s')
}

Kotlin 代码对“1 千万”的表达与其他语言不同,它的数字字面值还未支持分隔符,这是有待改进的一小处。与 Java 相比缺少?groupingBy()?与?counting()?这样的 Collector,因此性能不及 Java 8,但是比 Java 8 要简洁很多倍,未来有取代 Java 的潜质。

小结

除了作为对照基准的 Ruby,其他的都是新兴语言(包括 Java 8,它相对于 Java 7 也是革命式的更新)。

  • Julia 是动态语言,其定位是统计与科学计算,从上文看简洁性不错,性能改进是关键。
  • Rust、Kotlin 与 Java 8 都是多范式静态类型语言。对于 Java 8 致命弱点是不够简洁;而 Rust 和 Kotlin 目前的不足是完善程度,但目前两门语言都在快速发展期,具有很大潜力。

参见

  • 微博:原题
  • 微博:Rust 版
  • 微博:Kotlin 版
  • 微博:Julia 版
灰蓝天际?灰蓝天际

转载请勿修改,并注明作者:灰蓝天际 及许可协议:署名-非商业性使用-禁止演绎。

发表评论
用户名: 匿名