Массив Ruby расположен в порядке возрастания - PullRequest
Новая
       2

Массив Ruby расположен в порядке возрастания

0 голосов
/ 11 ноября 2018

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

В методе Лагранжа используются X, F (X) и X0, где X0 должен находиться в диапазоне X, если нет, то вы не можете решить проблему

Пока это мой код 

xn = []
#i is a random number selected from a list
i.times do
    value=rand(0.1..15.1)
    xn<<value 
end
#ordena el arreglo de manera ascendente
xn.sort!

Редактировать: обновлен код

Ответы [ 2 ]

0 голосов
/ 14 ноября 2018

Как указал Сид, когда вы спрашиваете, «есть ли более простой способ сделать это», многое зависит от контекста.Если «проще» вы ищете эффективность, то ответ не только в количестве строк кода.

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

Однако, если у вас очень большие N иобрабатывают значения последовательно, вы можете предпочесть генераторный подход.Реализация, представленная ниже как ordered_random_generator, - это O (1) вычислений и хранилищ для каждого элемента, что дает O (N) для генерации всего набора, но O (1) для хранения, если вы отбрасываете каждый элемент после его использования.Если вы сохраняете элементы, на практике это медленнее, чем подход, основанный на сортировке, из-за высокой стоимости вычисления k th корней в расчете.

Другая возможность заключается в том, что вы не 'на самом деле интересует весь набор значений, но использует его для получения определенных квантилей или статистики порядка, например, 10-го из 100 упорядоченных элементов.В этом случае вы можете напрямую сгенерировать случайное значение с правильным распределением статистики порядка k th из N за O (1) время с O (1) хранилищем.

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

# Your original.
# O(N log N) time due to sort, O(N) storage.
def ordered_random1(n, range_spec = 1.0..n)
  ary = []
  n.times do
    value = rand(range_spec)
    ary << value
  end
  ary.sort!
end

# Same sort-based algorithm using Ruby's Array constructor with a block.
# O(N log N) time due to sort, O(N) storage.
def ordered_random2(n, range_spec = 1.0..n)
  Array.new(n) { rand(range_spec) }.sort!
end

# Generator which uses distributional properties to generate the minimum of
# k uniforms from k = N down to 1, scaling the result down to the remaining
# sub-range of the original range.
# O(1) time per element, O(1) storage.  However, computation time has a very
# large constant due to the transcendental function evaluation for kth root.
def ordered_random_generator(n, range_spec = 1.0..n)
  x = range_spec.first
  upper = range_spec.last
  Enumerator.new do |yielder|
    n.times do |i|
      range = upper - x
      u_min = 1.0 - rand ** (1.0 / (n - i))
      x += range * u_min
      yielder.yield x
    end
  end
end

# Use generator to fill array of size N.
# O(N) time and storage.
def ordered_random3(n, range_spec = 1.0..n)
  gen = ordered_random_generator(n, range_spec)
  Array.new(n) { gen.next }
end

require 'random_variates'   # 'gem install random_variates' to get from rubygems

# Use distributional properties of uniform order statistics to directly
# generate instances of the kth of N values.
# O(1) time, O(1) storage.
def kth_of_n_generator(k:, n:, range_spec: 0.0..1.0)
  # Uniform order stats have a beta distribution. Beta is a ratio of Gammas.
  x = Gamma.new(alpha: k).next
  y = Gamma.new(alpha: n - k + 1).next
  beta = x / (x + y)
  (range_spec.last - range_spec.first) * beta + range_spec.first
end

# Time for Demos!
my_range = 0.1..15.1
puts "SAMPLE OUTPUT FOR RANGE = #{my_range}:"
puts " original: #{ordered_random1(5, my_range)}"
puts "one-liner: #{ordered_random2(5, my_range)}"
puts "generator: #{ordered_random3(5, my_range)}"
puts "direct generation of min & max using kth_of_n_generator: #{
  kth_of_n_generator(k: 1, n: 5, range_spec: my_range)
}, #{
  kth_of_n_generator(k: 5, n: 5, range_spec: my_range)
}"

REPS = 10_000
n = 9
puts "\nDEMO DISTRIBUTIONAL CORRECTNESS OF SINGLETON GENERATOR (range = 0.0..1.0)"
(1..n).each do |k|
  total = Array.new(REPS) { kth_of_n_generator(k: k, n: n) }.inject(:+)
  quantile = k.to_f / (n + 1)
  suffix = case k
    when 1
      "st"
    when 2
      "nd"
    when 3
      "rd"
    else
      "th"
  end
  print "Average of #{REPS} values of #{k}#{suffix} of #{n}: #{total / REPS} "
  puts "[Expected value is #{quantile}]"
end

require 'benchmark/ips'
[100, 10_000].each do |n|
  puts "\nBENCHMARKING ARRAYS OF SIZE #{n}"
  Benchmark.ips do |b|
    b.report(' original:') { ordered_random1(n, my_range) }
    b.report('one-liner:') { ordered_random2(n, my_range) }
    b.report('generator:') { ordered_random3(n, my_range) }
    b.compare!
  end
end

Вот пример вывода на моеммашина.Время зависит от вашего оборудования, операционной системы и версии Ruby, которую вы используете.Конкретные значения будут варьироваться от прогона к прогоне из-за случайности, но они непротиворечивы. 

SAMPLE OUTPUT FOR RANGE = 0.1..15.1:
 original: [3.2143763318277223, 3.424117583339602, 4.98763316107166, 7.67915049946293, 13.002051529711663]
one-liner: [3.698584735327408, 3.7940473868424713, 8.133265097991108, 10.797493427133121, 13.519291528088747]
generator: [1.379949057529254, 3.330310564043854, 14.175279996588, 14.187770450655005, 14.747374304212487]
direct generation of min & max using kth_of_n_generator: 2.3844682728553956, 14.093371351681753

DEMO DISTRIBUTIONAL CORRECTNESS OF SINGLETON GENERATOR (range = 0.0..1.0)
Average of 10000 values of 1st of 9: 0.10061353514079374 [Expected value is 0.1]
Average of 10000 values of 2nd of 9: 0.19841217568287062 [Expected value is 0.2]
Average of 10000 values of 3rd of 9: 0.3018753486695847 [Expected value is 0.3]
Average of 10000 values of 4th of 9: 0.40002514960574265 [Expected value is 0.4]
Average of 10000 values of 5th of 9: 0.5003591617651723 [Expected value is 0.5]
Average of 10000 values of 6th of 9: 0.5974291957317844 [Expected value is 0.6]
Average of 10000 values of 7th of 9: 0.6980418879340753 [Expected value is 0.7]
Average of 10000 values of 8th of 9: 0.8012294219961899 [Expected value is 0.8]
Average of 10000 values of 9th of 9: 0.9002379495094114 [Expected value is 0.9]

BENCHMARKING ARRAYS OF SIZE 100
Warming up --------------------------------------
           original:     4.037k i/100ms
          one-liner:     4.242k i/100ms
          generator:   773.000  i/100ms
Calculating -------------------------------------
           original:     40.412k (± 2.0%) i/s -    205.887k in   5.096825s
          one-liner:     41.852k (± 2.3%) i/s -    212.100k in   5.070662s
          generator:      7.676k (± 4.2%) i/s -     38.650k in   5.045488s

Comparison:
          one-liner::    41852.1 i/s
           original::    40412.3 i/s - same-ish: difference falls within error
          generator::     7675.6 i/s - 5.45x  slower


BENCHMARKING ARRAYS OF SIZE 10000
Warming up --------------------------------------
           original:    29.000  i/100ms
          one-liner:    30.000  i/100ms
          generator:     7.000  i/100ms
Calculating -------------------------------------
           original:    295.387  (± 2.0%) i/s -      1.479k in   5.009243s
          one-liner:    304.406  (± 2.0%) i/s -      1.530k in   5.028485s
          generator:     78.104  (± 2.6%) i/s -    392.000  in   5.020934s

Comparison:
          one-liner::      304.4 i/s
           original::      295.4 i/s - same-ish: difference falls within error
          generator::       78.1 i/s - 3.90x  slower

Обратите внимание, что генераторный подход медленнее, чем два подхода на основе сортировки для обоих протестированных здесь размеров массивов.Разрыв закрывается для массивов больших размеров из-за асимптотики O (N) и O (N log N), но, вероятно, недостаточно, чтобы представлять интерес, если вы в первую очередь фокусируете на скорости.

0 голосов
/ 11 ноября 2018

Сам код выглядит нормально и служит вашей цели. Есть ли контекст вокруг того, где это будет использоваться? Потому что «простота» может быть обусловлена ​​контекстом кода.

Например,

  1. Вы можете настроить необходимое количество случайных чисел и диапазон случайных чисел. Вы можете настроить внешне порядок сортировки.

  2. Вы можете инкапсулировать это в служебный класс и предоставлять его как API другим классам.

  3. Если требуется миллион случайных отсортированных чисел, хотите ли вы, чтобы числа были в потоковом режиме? Если так, то есть библиотеки Ruby.

... и многое другое. Контекст будет полезен. Надеюсь это поможет.

...