帮酷LOGO
  • 显示原文与译文双语对照的内容
文章标签:算法  SCA  Implementation  COM  IMP  implementations  Connections  
Compare various implementations of the contractions scan algorithm

  • 源代码名称:csa-challenge
  • 源代码网址:http://www.github.com/trainline-eu/csa-challenge
  • csa-challenge源代码文档
  • csa-challenge源代码下载
  • Git URL:
    git://www.github.com/trainline-eu/csa-challenge.git
  • Git Clone代码到本地:
    git clone http://www.github.com/trainline-eu/csa-challenge
  • Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/trainline-eu/csa-challenge
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
  • CSA挑战

    在 Captain,我们需要计算火车路线,以找出与不同列车运营商最佳组合的。

    我们的核心路由引擎是用 C++ 编写的,它基于连接扫描算法。

    我们有很多交谈,trolls和真正的好奇心是如何工作的。

    所以我们决定了一个非常简单的挑战: 实现你自己的路由引擎。 这是学习算法工作方式的最好方法,证明你的语言最具表达力,最最快速。最安全。

    数据

    时间表是用 Collection的( 出发站,到达站,出发时间,到达时间) 表示的。

    这些站由一个索引标识。 时间戳是unix时间戳。不要担心时区,有效日期 等等,我们在前处理数据。 它不是最有效的内存实现,但它是最简单的( 有人认为最好的性能) 。

    每个 tuple 都称为连接 。 connection ( 1,2,3600,) 意味着你可以从 1车站take到 1,在车站的stop,火车在车站 2: 。

    数据将作为分隔值提供。

    tuple 按存储在索引 array 中的离开时间戳排序。

    算法

    CSA很简单。 对于每个站 s,我们保持最佳到达时间和到达连接。 我们将这两个连接称为 arrival_timestamp[s]in_connection[s]

    我们想从 od,在时间戳 t0 中离开

    初始化初始化

    For each station s
     arrival_timestamp[s] = infinite
     in_connection[s] = invalid_value
    arrival_timestamp[o] = t0

    主循环

    我们遍历所有连接,看看是否能改进任何连接。

    一旦我们探索了所有的连接,我们计算出所有的最早到达路线从 o 到任何其他站。

    For each connection c
     if arrival_timestamp[c.departure_station] <c.departure_timestamp and arrival_timestamp[c.arrival_station]> c.arrival_timestamp
     arrival_timestamp[c.arrival_station] ← c.arrival_timestamp
     in_connection[c.arrival_station] = c

    正在获取实际路径

    我们只需要从 d 开始查找所有的in_connections直到到达 o,我们有路径和时间表。

    立即优化

    不需要查看所有的连接。 我们先从 c.departure_timestamp> = t0 开始,然后我们马上停止 c.departure_timestamp> arrival_timestamp

    限制

    这里算法查找路由时,需要注意以下限制:

    • 它计算出最早到达的。 然而,一个更好的解决方案可能会在稍后到达并到达
    • 连接最少的路由将不会被计算
    • 不考虑连接时间: 你可能得跑到下一列火车。
    • 像巴黎这样一个城市的多个站不被视为

    输入/输出

    你的程序应该从标准输入中读取。

    每一行都有一个连接,tuple的每一个值都是分开的。

    空行表示输入已经完成。 以下各行是一个由三个值分隔的路由请求: departure_station arrival_station departure_timestamp 。一行指示程序应该停止。

    下面是一个输入示例

    1 2 3600 7200
    2 3 7800 9000
    1 3 3000

    输出应该是standart输出上每个连接的一行。 一个空行表示输出的结束。 所以答案应该是

    1 2 3600 7200
    2 3 7800 9000

    参考实现

    C++11中的一个实现可用。

    它可以用 g++ $CPPFLAGS --std=c++11 -O3 -o csa_cpp csa.cc

    使用 ruby test.rb./csa_cpp 运行测试

    实现

    Debian软件包:

    • haskell
    • utils

    生成: ghc -o csa_hs -Wall -O3 csa.hs && strip csa_hs

    使用 ruby test.rb./csa_hs 运行测试

    Java实现

    构建:javac CSA.java

    运行测试 ruby test.rb"java CSA"

    实现

    运行测试 ruby test.rb"luajit csa.lua"

    Rust 实现

    构建:cargo build --release

    运行测试 ruby test.rb./target/release/csa_rs

    挑战

    尝试写入:

    • 第一个通过测试的实现
    • 最小源代码( 以字节为单位的度量) 。 在 Debian 。Ubuntu 。Archlinux上没有外部存储库的任何库都被接受
    • 最小可执行文件( 考虑依赖关系的相同规则)
    • 最不可读
    • 最少字母数字字符
    • 最有创意的算法实现

    基准测试

    我们在欧洲建立了 48小时的列车连接,start 1st 年 1970月。 数据不是真实的,但非常接近。

    你可以使用 ruby bench.rb./csa_cpp 运行基准测试



    文章标签:COM  IMP  Implementation  SCA  算法  Connections  implementations  

    Copyright © 2011 HelpLib All rights reserved.    知识分享协议 京ICP备05059198号-3  |  如果智培  |  酷兔英语