尝试改善 Julia 代码的执行时间

Question

我需要编写代码来使用只有一个规则的语法生成字符串。例如，如果规则是"G -> [G+G]"，我们将规则应用到"G"，结果是字符串“[G+G]”；如果我们将它应用到之前的结果，我们得到“[[G+G]+[G+G]]”等等。换句话说，它是关于将公理（规则的左侧）重写给定次数，遵循规则。

我得到了一段用 Octave 编写的实现此操作的代码（我不会包含代码，因为它有点长，但如果有必要理解或回答问题，我会包含）。我需要做的是在 Julia 中编写一个等效的函数；所以我写了这个

    function generate_developedstring(axiom::ASCIIString, genome::ASCIIString, iterations::Int8)
        tic()
        developedstring = axiom
        for i=1:iterations
            developedstring = replace(developedstring, axiom, genome)
        end
        toc()
        return developedstring
    end

在我之前写的例子中，公理是"G"，基因组是“[G+G]”。

根据发布的基准时间 julialang.org，Julia 应该比 Octave 快得多，但在这种情况下，Octave 是 Julia 的两倍（我对两个代码使用了相同的公理、基因组和迭代，并且我用 tic toc 函数测量了时间）。

有什么方法可以使 Julia 代码更快？

编辑：首先，非常感谢大家的评论。我会告诉你我得到的八度代码（我没有写）：

function axiom = ls(genome)
  tic
  ProductionSystem = ['[=>[ ]=>] +=>+ -=>- G=>',genome];
  rule = extract(ProductionSystem);

  n_Rules = length(rule);

  % starting string
  axiom = 'G';

  % iterations (choose only from 1 to 7, >= 8 critical,
  % depends on the string and on the computer !!
  n_Repeats = 3;

%CALCULATE THE STRING
%=================================

for i = 1:n_Repeats
    % a single letter (axiom)
    axiomINcells = cellstr(axiom);
    for j = 1:n_Rules
        % find all occurrences of that axiom
        hit = strfind(axiom, rule(j).pre);
        if (length(hit) >= 1)
            for k = hit
                % perform the rule
                % (replace 'pre' by 'post')
                axiomINcells{k} = rule(j).pos;
            end
        end
    end
    axiom = [];
    for j = 1:length(axiomINcells)
        % put all strings together
        axiom = [axiom, axiomINcells{j}];
    end
end
toc

function rule = extract(ProductionSystem)
% rules are separated by space character, and pre and post sides are
% separtated by '->'
% e.g. F->FF G->F[+G][-G]F[+G][-G]FG

i=0;
while (~isempty(ProductionSystem))
    i=i+1;
    [rule1,ProductionSystem] = strtok(ProductionSystem,' ');
    [rule(i).pre,post] = strtok(rule1,'=>');
    rule(i).pos = post(3:end);
    if (~isempty(ProductionSystem)) ProductionSystem=ProductionSystem(2:end);   % delete separator
    end
end

关于我使用的 Julia 版本，它是 0.4.7。你还问我需要多快运行；我只需要尽可能快地编写代码，而 Octave 更快的事实让我觉得我做错了什么。再次感谢。

Answer 1

您可以将 genome 指定为规则而不是模式吗？我的意思是，例如 genome = ax -> "[$ax,$ax]".

比较这两个实现，第一个和你的一样：

function genstring(axiom::String, genome::String, iter::Int)
    str = axiom
    for i in 1:iter
        str = replace(str, axiom, genome)
    end
    return str
end

然后用一个匿名函数：

genome = ax -> "[$ax,$ax]"

function genstring_(axiom::String, genome, n::Int)
    if n < 1
        return axiom
    end
    return genstring_(genome(axiom), genome, n-1)
end

在版本 0.5 上，BenchmarkTools:

julia> @benchmark genstring("G", "[G,G]", 2)
BenchmarkTools.Trial: 
  memory estimate:  752.00 bytes
  allocs estimate:  15
  --------------
  minimum time:     745.950 ns (0.00% GC)
  median time:      801.067 ns (0.00% GC)
  mean time:        1.006 μs (14.30% GC)
  maximum time:     50.271 μs (96.63% GC)
  --------------
  samples:          10000
  evals/sample:     119
  time tolerance:   5.00%
  memory tolerance: 1.00%

julia> @benchmark genstring_("G", genome, 2)
BenchmarkTools.Trial: 
  memory estimate:  352.00 bytes
  allocs estimate:  9
  --------------
  minimum time:     397.562 ns (0.00% GC)
  median time:      414.149 ns (0.00% GC)
  mean time:        496.511 ns (13.06% GC)
  maximum time:     24.410 μs (97.18% GC)
  --------------
  samples:          10000
  evals/sample:     201
  time tolerance:   5.00%
  memory tolerance: 1.00%

扩展性更好：

julia> @benchmark genstring("G", "[G,G]", 10)
BenchmarkTools.Trial: 
  memory estimate:  18.00 kb
  allocs estimate:  71
  --------------
  minimum time:     93.569 μs (0.00% GC)
  median time:      95.959 μs (0.00% GC)
  mean time:        103.429 μs (3.05% GC)
  maximum time:     4.216 ms (97.14% GC)
  --------------
  samples:          10000
  evals/sample:     1
  time tolerance:   5.00%
  memory tolerance: 1.00%

julia> @benchmark genstring_("G", genome, 10)
BenchmarkTools.Trial: 
  memory estimate:  14.13 kb
  allocs estimate:  49
  --------------
  minimum time:     3.072 μs (0.00% GC)
  median time:      3.597 μs (0.00% GC)
  mean time:        5.703 μs (29.78% GC)
  maximum time:     441.515 μs (98.24% GC)
  --------------
  samples:          10000
  evals/sample:     8
  time tolerance:   5.00%
  memory tolerance: 1.00%

据我所知，字符串插值速度不是很快，因此可以进一步优化。

尝试改善 Julia 代码的执行时间

Trying to improve execution time of Julia code

grammar

octave

julia