Как объяснить несоответствие производительности этого рубинового кода? - PullRequest
Новая
       6

Как объяснить несоответствие производительности этого рубинового кода?

0 голосов
/ 29 апреля 2018

Я выполняю некоторые тесты скорости для следующей задачи:

Учитывая 2 строки, s1 и s2, которые содержат только строчные буквы, выводятся, если буквы s1 можно переставить так, чтобы s2 стала подстрокой s1.

Я получил 2 решения в рубине:

Версия 1: 

def scramble(s1,s2)
  if s1.length < s2.length
    return false
  end

  a = Array.new(26) { 0 }
  b = Array.new(26) { 0 }

  t1 = Time.now

  (0 ... s1.length).each do |x|
    a[s1[x].ord - 97] += 1
  end

  (0 ... s2.length).each do |x|
    b[s2[x].ord - 97] += 1
  end

  t2 = Time.now

  (0 ... 26).each do |x|
    if a[x] < b[x]
      return false
    end
  end

  puts t2 - t1

  return true
end

Эта версия сохраняет количество символов в s1 и s2 в таблице прямой адресации и сравнивает количество каждого символа. Должно быть понятно, что этот код выполняет приблизительно 2 * (N + M) операций, где N - это длина s1, а M - это длина s2.

Версия 2: 

def scramble(s1,s2)
  t1 = Time.now

  c = s2.chars
  c.uniq!
  t = c.all?{|x| s2.count(x)<=s1.count(x)}

  t2 = Time.now

  puts t2 - t1

  return t
end

Эта версия также использует количество символов в s1 и s2, но не использует таблицу прямой адресации. Из того, что я понимаю, эта версия должна выполнять приблизительно 26 * (N + M) операций, поскольку сложность метода count () линейна по количеству символов в строке и вызывается для каждого отдельного символа в строке.

Когда я выполняю 

scramble('abcdefghijklmnopqrstuvwxyz'*500000, 'abcdefghijklmnopqrstuvwxyz'*500000)

Первая версия занимает 4.424207s, а вторая - только 2.574269s. Я провел тест несколько раз с разными длинами s1 и s2, и результаты были согласованы (версия 2 намного быстрее, чем версия 1). Из-за их различных констант, я действительно запутался. Почему код в версии 2 работает намного быстрее, чем версия 1, несмотря на то, что его константа намного выше?

Может кто-нибудь, пожалуйста, посоветуйте мне?

1 Ответ

0 голосов
/ 29 апреля 2018

Я думаю, это потому, что стандартные методы библиотеки, такие как String#count, реализованы в C, что требует гораздо меньше затрат, чем выполнение сложного выражения Ruby a[s1[x].ord - 97] += 1 500000 раз в цикле.

Чтобы понять, что я имею в виду, попробуйте заменить эти циклы: 

(0 ... s1.length).each do |x|
  a[s1[x].ord - 97] += 1
end

(0 ... s2.length).each do |x|
  b[s2[x].ord - 97] += 1
end

с звонками на String#count: 

(0 ... 26).each do |x|
  a[x] = s1.count((x + 97).chr)
  b[x] = s2.count((x + 97).chr)
end

С этим изменением он запускается на моей машине за 0,4 секунды (по сравнению с 6,3 с ранее)!

...