Ruby: sort! и uniq! Что нужно запустить первым?

Ответ 1

Я сделал небольшой тест с различными комбинациями uniq uniq! сортировать и сортировать! Нет существенных различий:

                user     system      total        real
sort!.uniq!103.547000   0.172000 103.719000 (104.093750)
uniq!.sort!100.437000   0.093000 100.530000 (100.859375)
uniq.sort 100.516000   0.157000 100.673000 (101.031250)
sort.uniq 103.563000   0.062000 103.625000 (103.843750)

То, что вы не можете использовать, выглядит примерно так:

array = [1]
array.uniq!.sort!

уник! приведет к нулю и сортировке! выдает исключение.

Тест, который я использовал:

require 'benchmark'
require 'date'

TEST_LOOPS = 10_000
ARRAY = []
1000.times{ 
  ARRAY << Date.new(1900 + rand(100), rand(11)+1, rand(27) + 1 ) 
}
Benchmark.bm(10) {|b|

  b.report('sort!.uniq!') {
   TEST_LOOPS.times { 
      a = ARRAY.dup
      a.sort!
      a.uniq!
   }            #Testloops
  }             #b.report

  b.report('uniq!.sort!') {
   TEST_LOOPS.times { 
      a = ARRAY.dup
      # uniq!.sort! not possible. uniq! may get nil
      a.uniq!
      a.sort!
   }            #Testloops
  }             #b.report

  b.report('uniq.sort') {
   TEST_LOOPS.times { 
      a = ARRAY.dup.uniq.sort
   }            #Testloops
  }             #b.report

  b.report('sort.uniq') {
   TEST_LOOPS.times { 
      a = ARRAY.dup.sort.uniq
   }            #Testloops
  }             #b.report

} #Benchmark

Ответ 2

Фактически, это зависит от количества уникальных значений. В примере knut стартовый набор может включать в себя не более 365 уникальных значений из 1000, а порядок операций - без влияния.

если "uniq" значительно уменьшает размер массива, есть явное преимущество при его первом запуске.

A=[]
10_000.times do
  A << rand(80)
end

Benchmark.bm(10) do |b|
  b.report "sort.uniq" do
    10_000.times {A.sort.uniq}
  end
  b.report "uniq.sort" do
    10_000.times {A.uniq.sort}
  end
end

                 user     system      total        real
sort.uniq   20.202000   0.281000  20.483000 ( 20.978098)
uniq.sort    9.298000   0.000000   9.298000 (  9.355936)

Я не тестировал ".uniq!.sort!" перестановки, но я считаю, что они должны следовать приведенному выше результату.

Этот пример может быть немного экстремальным, но я не понимаю, почему нельзя всегда запускать '.uniq' first

Ответ 3

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

 a=[3,3,3,3,6,7,1,1,1,1,3]
 a.uniq!
 a.sort!

Ответ 4

Запуск одного или другого сначала зависит от потребностей вашего приложения.

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

2) Если у вас огромные массивы, и я имею в виду огромный, основанный на реальном измеренном определении того, что ваш код слишком долго работает при запуске array.sort!.uniq!, тогда вы можете попробовать другой порядок и посмотреть. Если у вас много дубликатов, array.uniq!.sort! может быть немного быстрее.

3) Если вас беспокоит скорость, вы, вероятно, захотите использовать sort_by. См. Например, https://github.com/JuanitoFatas/fast-ruby/blob/master/code/enumerable/sort-vs-sort_by.rb