python - 如果用 Ruby 重写，Python 脚本变得非常慢的原因是什么？

Question

我一直在练习机器学习来恢复连接文本中的空格。由于我决定使用字典功能，所以我在网上搜索了一些基于字典拆分文本的想法，我偶然发现了this idea。 .基于它，我写了一个 script将没有空格的文本转换为 ML 工具所需的垂直形式:

#!/usr/bin/python
# -*- coding: UTF-8 -*-
from math import log
import string
import fileinput

words = open("dictionary.txt", encoding="utf8").read().split()
wordcost = dict((k, log((i+1)*log(len(words)))) for i,k in enumerate(words))
maxword = max(len(x) for x in words)

def infer_spaces(s):
    # Find the best match for the i first characters, assuming cost has
    # been built for the i-1 first characters.
    # Returns a pair (match_cost, match_length).
    def best_match(i):
        candidates = enumerate(reversed(cost[max(0, i-maxword):i]))
        return min((c + wordcost.get(s[i-k-1:i], 9e999), k+1) for k,c in candidates)

    # Build the cost array.
    cost = [0]
    for i in range(1,len(s)+1):
        #original script was pretty basic, so symbols\words not in dictionary
        #broke the processing completely. This fixed the problem.
        if s[i-1] not in wordcost:
            wordcost[s[i-1]] = log((len(words) + 1)*log(len(words)))
        c,k = best_match(i)
        cost.append(c)
        print(cost)

    # Backtrack to recover the minimal-cost string.
    out = []
    i = len(s)
    while i>0:
        c,k = best_match(i)
        assert c == cost[i]
        out.append(s[i-k:i])
        i -= k

    return " ".join(reversed(out))

def char_type(s):
    """ Character type function """
    if s in string.punctuation:
        return "P"
    elif s in string.digits:
        return "D"
    elif s in string.ascii_letters:
        return "F"
    elif s.isupper():
        return "U"
    else:
        return "R"


def test_to_vert(s):
    """
   Transforms regular text into a vertical form.
   """
    s = s.rstrip('\n')
    orig_sent = s
    a = s.lower().replace("ё", "е")
    a = infer_spaces(a)
    space_indices = []
    a = list(a)
    for i,k in enumerate(a):
        if k == " ":
            space_indices.append(i)

    orig_sent = list(orig_sent)
    for i in space_indices:
        orig_sent.insert(i, " ")

    orig_sent = "".join(orig_sent)
    orig_sent = orig_sent.split(" ")

    answer = []

    for word in orig_sent:
        i = 0
        for letter in word:
            answer.append(letter + "\t" + letter.lower() + "\t" + \
                  char_type(letter) + "\t" + str(i) + "|" + str(len(word)))                                                    
            i += 1
    return '\n'.join(answer)

testfile = open("head.txt", encoding="utf8")
output = open("test_python.txt", 'w', newline="\n", encoding="utf8")



for line in testfile:
    if line in ['\n', '\r\n']:
        output.write('\n')
    else:
        output.write(test_to_vert(line))
        output.write('\n\n')

output.write('\n\n\n')
testfile.close()
output.close()

到目前为止一切顺利，它有效。之后我决定练习我的 Ruby(我对编码还比较陌生)，所以我尝试重写脚本(Ruby version):

#!/usr/bin/ruby
#encoding: UTF-8
Encoding::default_internal = "UTF-8"
Encoding::default_external = "UTF-8"

require 'active_support/core_ext'

@wordcost = Hash.new
@count = %x{wc -l dictionary.txt}.split.first.to_i

i = 0

File.readlines("dictionary.txt").each do |line|
  line.chomp!

  @wordcost[line.mb_chars.downcase.to_s] ||= Math.log((i+1) * Math.log(@count))
  i += 1
end

def infer_spaces(s)

  @sent = s.chomp

  def best_match(i)
    result = []
    candidates = @cost[0, i].reverse
    candidates.each_index do |index|
      if @wordcost.has_key?(@sent[i-index-1...i].mb_chars.downcase.to_s)
        result << [(candidates[index] + @wordcost[@sent[i-index-1...i].mb_chars.downcase.to_s]), (index + 1)]
      else
        result << [(candidates[index] + Float::INFINITY), (index + 1)]
      end
    end
    result.sort!
    return result[0][0], result[0][1]
  end

  @cost = [0]
  for i in (1..@sent.length)
    @wordcost[@sent[i-1].mb_chars.downcase.to_s] ||= Math.log(@count * Math.log(@count))
    c, k = best_match(i)
    @cost << c
  end

  out = []
  i = @sent.length
  while i>0
    c, k = best_match(i)
    if c != @cost[i]
      raise "Something went wrong"
    end
    out << @sent[i-k...i]
    i -= k
  end

  return out.reverse.join(" ")

end

def char_type(string)
  case string
  when /[[:punct:]]/
    return "P"
  when /[[:digit:]]/
    return "D"
  when /[A-z]/
    return "F"
  when /[[:upper:]]/
    return "U"
  else
    return "R"
  end
end

def test_to_vert(s)
  s.chomp!
  orig_sent = s
  a = s.mb_chars.downcase.to_s
  a = infer_spaces(a)
  space_indices = []
  a = a.split("")
  a.each_index do |i|
    if a[i] == " "
      space_indices << i
    end
  end
  orig_sent = orig_sent.split("")
  space_indices.each do |x|
    orig_sent.insert(x, " ")
  end
  orig_sent = orig_sent.join
  orig_sent = orig_sent.split

  answer = []

  orig_sent.each do |word|
    letters = word.split("")
    letters.each_index do |i|
      answer << letters[i] + "\t" + letters[i].mb_chars.downcase.to_s + \
      "\t" + char_type(letters[i]) + "\t" + i.to_s + "|" + word.length.to_s
    end
  end

  return answer.join("\n")
end

file = File.open('test_ruby_vert.txt', 'w')

File.readlines("test.txt").each do |line|
  if line.chomp.empty?
    file.write("\n")
  else
    file.write(test_to_vert(line))
    file.write("\n\n")
  end
end

file.close

重写的脚本可以工作，但是，与 Python 版本相比它真的很慢(一个大约 40000 行的文本处理时间不超过一个小时，一个 Ruby 脚本现在可以工作几个小时，而且它只处理了占文本的 15%)。

我想知道是什么让它慢了这么多？难道是因为我需要使用“active_support/core_ext”来降低 Ruby 中的西里尔文字？难道是因为我没有使用maxword限制best_match中的处理？也许其他一些重写真的把脚本搞砸了？任何见解都会对我很有帮助。

Answer 1

我没有仔细查看(您的问题中的代码太多，无法进行详细检查，您确实需要将其缩减为 SSCCE )，但我突然想到了一些事情。

最重要的一点是，语言实现旨在使惯用的、结构良好的、设计良好的代码快速运行。但是，您的代码看起来更像 Fortran 而不是 Ruby，它绝对既不是惯用的 Ruby 也不是经过精心设计的。

一些较小的观察结果:

在这里你不必要地创建了很多字符串对象:

answer << letters[i] + "\t" + letters[i].mb_chars.downcase.to_s + \
  "\t" + char_type(letters[i]) + "\t" + i.to_s + "|" + word.length.to_s

您应该更喜欢使用 << 来改变单个字符串使用 + 创建许多临时字符串:

answer << ('' << letters[i] << "\t" << letters[i].mb_chars.downcase.to_s <<
  "\t" << char_type(letters[i]) << "\t" << i.to_s << "|" << word.length.to_s)

但实际上，字符串插值更为惯用(而且速度更快):

answer << "#{letters[i]}\t#{letters[i].mb_chars.downcase}\t#{char_type(letters[i])}\t#{i}|#{word.length}"

你有很多不必要的return在你的代码中。同样，这是非惯用的，而且速度也较慢。例如这里:

def char_type(string)
  case string
  when /[[:punct:]]/
    return "P"
  when /[[:digit:]]/
    return "D"
  when /[A-z]/
    return "F"
  when /[[:upper:]]/
    return "U"
  else
    return "R"
  end
end

应该这样写

def char_type(string)
  case string
  when /[[:punct:]]/
    "P"
  when /[[:digit:]]/
    "D"
  when /[A-z]/
    "F"
  when /[[:upper:]]/
    "U"
  else
    "R"
  end
end

还有其他不需要的地方return s也是。

在您的 infer_spaces 内方法，您定义另一个名为 best_match 的全局方法.自 infer_spaces由 test_to_vert 调用，这在你的内部被称为 readlines循环，该方法将被一遍又一遍地为文件中的每一行定义，这意味着(由于现在大多数 Ruby 实现都是编译的)，它必须被一遍又一遍地编译。每次重新定义也会使所有先前的优化失效，例如推测内联。只需将方法定义移到循环之外。

IO::readlines将整个文件作为数组读入内存。然后你遍历数组。您也可以使用 IO::foreach 直接遍历文件的行相反:

File.foreach("test.txt") do |line|

这将避免一次将整个文件加载到内存中。

您没有说明您使用的是哪种 Ruby 实现。由于你有一个相当热和紧密的循环，使用具有某种热点优化、多态内联缓存、推测内联、自适应优化等的实现，可能会产生很大的不同，特别是如果你修复了 best_match 的重新编译问题。 . Rubinius 和 JRuby 是不错的选择。例如，Rubinius 已被证明在某些情况下比手动优化的 C 更快!

注意:这些都只是微优化。我实际上并没有看你的算法。通过调整算法而不是微优化实现，您可能可以获得更高的性能。

例如:在 best_match 的 Python 实现中, 你使用 min找到最小元素，即 O(n)，而在 Ruby 中，你 sort然后返回第一个元素，即 O(n * log n)。