Этот скрипт работает, но держит время с больше входов. Как я могу улучшить свою скорость? [Рубиновый]


Скрипт принимает строку типа этой: (15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37) и разбивает ее в массив массивов. Затем он вычисляет как можно большее количество вариантов, с основного положения, что для каждого массива должны иметь оба числа меньше предыдущего выбора. На строку выше, правильный выход будет 4.

people = File.read(ARGV[0])
people = people.sub("\(", '').sub(/\)$/, '').split("\) \(")
people.map! { |p| p.split(', ') }

count = 0
test = people.permutation.to_a
test.each do |perm|
  test_count = 0
  perm.each_with_index do |item, i|
    test_case = perm[i+1]
    unless test_case == nil 
    test_count += 1 if item[0] > test_case[0] && item[1] > test_case[1]
    end
  count = [count, test_count].max
  end
end

p count

В любом случае, это работает, но это sloooow, особенно с длинными строками. Как я могу ускорить этот процесс? Я знаю вложенных циклов может быть проблематичным и, как строку, растет число перестановок растет. Любые советы будут высоко ценится.

Редактировать: я использую это на Ruby 1.8.7.


Редактирования: новая попытка на проблему/сценария:

people = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)'
#people = File.read(ARGV[0]).chomp
people = people.sub("\(", '').sub(/\)$/, '').split("\) \(")
people.map! { |p| p.split(', ').map {|a| a.to_i } }

ht = people.sort_by { |h| h[0] }
wt = people.sort_by { |w| w[1] }
a_i = []

ht.each do |item|
  a_i << wt.index(item)
end

def subgen( array, count=1, t=(array.length+1) )
  if array.length == 1
    return count
  end
  without = subgen(array[0..-2], count, t)
  if array[0] > array[-1] || array[-1] > t
    return without
  else
    with = subgen(array[0..-2], count+=1, t = array[-1])
    return [with, without].max
  end
end

current = 0
a_i.each_with_index do |item, j|
  test = a_i[j..-1]
  current = [current, subgen(test)].max
end

p current

Это была тщательно протестирована и работает, но там должен быть способ сделать это быстрее. Любые идеи?



257
4
задан 15 декабря 2011 в 06:12 Источник Поделиться
Комментарии
3 ответа

Итак, вы создаете все возможные перестановки массива, который является О(Н!) операция. Это огромный.

Я думаю, что это можно сделать с O(Н2) алгоритм. Я бы сделал :


  • создать массив, содержащий пары, заказали по первому значению

  • создать еще одну запись, содержащую пар, заказанных на второе значение

  • создать третий массив, содержащий для каждого индекс первого массива, индекс второго массива, где можно найти соответствующее значение.

  • найти все подмножества этого третьего массива, значения которых упорядочены по возрастанию.

Результатом является длина самого большого подмножества.

Пример

first array | second array | third array
------------+--------------+------------
15,176 | 102,6 | 7
39,47 | 123,37 | 3
44,168 | 72,43 | 6
65,97 | 39,47 | 4
72,43 | 65,97 | 2
90,163 | 90,163 | 5
102,6 | 44,168 | 0
123,37 | 15,176 | 1
191,189 | 191,189 | 8

Восходящий подмножества :


  • 7 8

  • 3 6 8

  • 3 4 5 8

  • 6 8

  • 4 5 8

  • 2 5 8

  • 5 8

  • 0 1 8

  • 1 8

  • 8

Самая большая подгруппа (3 4 5 8), и ее размер составляет 4.

Сложности

Сорта можно сделать с O(N записей N)
Создать третий массив за o(П2)
Чтобы найти подмножество, я думаю, что мы можем сделать это за o(П2) (я не уверен)

Итак, все это должно быть o(Н2).

Алгоритм нахождения восходящих подмножеств не является тривиальным. Я уверен, что это будет интересно реализовать !

4
ответ дан 15 декабря 2011 в 01:12 Источник Поделиться

Приведенный ниже код следует известное правило: используйте максимально простой алгоритм, если некоторый код-зондирование узким местом анализа (с ваших данных) доказывает это недостаточно быстро.

Так, он в основном использует алгоритм сначала дали, а также индексами @barjak, и его выводы, как то, что вы делаете, и в том, что комбинации так же хорошо, как перестановки, после того, как они являются отсортированными. Также:


  • Поскольку находить самую большую цель, он начинает с самой крупной и работы меньше, поэтому он может остановить, как только он находит первый.

  • Он преобразует цифры, поэтому он может работать с быстрее двоичном вместо струн.

  • Он не преобразовывает в огромный перечисли (комбинаций или даже перестановки) в массив, который хранит все в памяти и может привести к замедлению подкачки, но индивидуально проверяет свои записи.

  • Используя методы из Ruby библиотек, когда это возможно (в основном, написанные на C), а не наш собственный код Руби, ускоряет выполнение.

Рубин библиотека 'не дает никаких гарантий по поводу порядка, в котором они были получены, поэтому сначала я не доверяла его, чтобы сохранить порядок индексов при предоставлении их комбинаций, но я в таком дальнейшей алгоритмической оптимизации, чтобы избежать сортировки по высоте для каждой комбинации.

Кроме того, я выручать как только найду весы вышли из строя, а не сортировать всю комбинацию стоит. Но все равно это будет о(n!) ведь практически N раз, он проверяет почти Н!/(н-к)!к! комбинаций, каждая из длины k. И, он по-прежнему занимает длительное время: 16 секунд всего 22 пары (с мои установки). 19 пар занимает 2 секунды.

Я нашел вашего описания, 'как можно большее количество вариантов, с указаниями, что для каждого массива должны иметь обе цифры меньше, чем предыдущий выбор довольно трудно интерпретировать. Итак, я прочитал свой код вместо этого, и придумал:

Проблема: рисунок из набора целых 2-кортежей, найти длину самой длинной поднабора, который может строго увеличение обеих переменных.

Для ваших тестовых данных, я получил 4 также.

def print_time
p Time.new.sec
end

def increasing?(array, indices)
f = array.at indices.first
skip_first = 1
# Compare adjacent pairs.
(skip_first...indices.length).reduce(f) do |memo,i|
each = array.at indices.at i
return false unless memo < each # Bail out quickly.
each # Slide the pair.
end
true
end

def search
# Get filename.
##fn = ARGV.at 0

# Read string containing parenthesized pairs of numbers.
##paren = File.read fn
# Or, use test string.
##paren = '(15, 176) (65, 97) (72, 43) (102, 6) (191, 189) (90, 163) (44, 168) (39, 47) (123, 37)'
# Or, generate repeatable random numbers.
srand 0
n, max = 22, 100000
paren=(0...n).map{(0..1).map{rand max}}.map{|a,b| "(#{a}, #{b})"}.join ' '
print_time

# Translate to array syntax.
# Add commas.
commas = paren.gsub ') (', '),('

# Convert parentheses to brackets.
brack = commas.tr '()', '[]'
s = "[ #{brack} ]"

# Convert into pairs of numbers in binary.
people = eval s

# Pre-sort people by height then weight, which may speed sorting the combinations.
people = people.sort

# Remove duplicates, which could reduce the length considerably, depending on the data.
people = people.uniq

# Get single numbers in binary.
ht = people.map{|e| e.first} # Height.
wt = people.map{|e| e.last } # Weight.

# Set up indices.
pl = people.length
p "N after removing duplicates is #{pl}."
indices = (0...pl).to_a

result = 0 # Preserve the result after the block.

# Start from the largest size of subset and go downward.
decreasing_sizes = (1..pl).to_a.reverse
decreasing_sizes.each do |size|

# Use combinations instead of permutations.
# Don't produce a big array of combinations, because
# it could be causing slow virtual-memory paging.
# Instead, check each combination when it is supplied.

indices.combination(size).each do |comb|

# Each combination is sorted already in increasing order by height.
## comb = comb.sort{|i,k| (ht.at i) <=> (ht.at k)}

# Check whether the weights are also in increasing order.
next unless increasing? wt, comb
w = wt.values_at *comb # Double check.
next unless w.sort==w

# We have found our first subset, which is increasing in both
# height and weight.
# Therefore, its size is the largest good subset size.
# Report this size and stop.
result = [size, comb.map{|i| people.at i}]
throw :result, result
end
end
end

length, pairs = catch(:result){ search}
p "One of the longest subsets has length #{length}: #{pairs.inspect}, length #{length}."
print_time

1
ответ дан 23 января 2012 в 11:01 Источник Поделиться

Лучшим для этого является алгоритм, похожий на сортировку терпение. Я написал некоторый код на Ruby, который обрабатывает десятки тысяч пар в нечто вроде нескольких секунд. Ты можешь написать мне, если вы все еще заинтересованы.

0
ответ дан 20 марта 2012 в 08:03 Источник Поделиться