встроенный метод для объединения двух отсортированных списков в ruby

Question

У меня есть два списка объектов Foo. Каждый объект Foo имеет метку времени Foo.timestamp. Оба списка изначально отсортированы по отметке времени в порядке убывания.

Я хочу объединить оба списка объектов Foo таким образом, чтобы окончательный список также сортировался по отметке времени в порядке убывания.

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

Спасибо.

Answer 1

Это будет работать, но не даст большой производительности, поскольку не будет использовать преимущества уже отсортированных списков:

list = (list1 + list2).sort_by(&:timestamp)

Я не знаю ни одной встроенной функции, котораяделает что хочешь.

Answer 2

Вонючий императивный процесс слияния двух ...

a = [1,3,7,11]
b = [2,4,6,14]

c = merge_sorted_arrays(a,b)

def merge_sorted_arrays(a,b)
  a.reverse!
  b.reverse!
  output = []

  loop do
    break if a.empty? || b.empty?
    output << (a.last < b.last ? a.pop : b.pop)
  end
  return output + a.reverse + b.reverse
end

Возможно, с помощью .slice!взять первый элемент было бы лучше, чем вспять и всплыть?

====================

отредактировано послечетвертый комментарий:

Правильно ... У меня была еще одна пьеса, но мне нужно заняться реальной работой, или меня уволят; -)

На большоммассив целых чисел, мой оригинальный метод работает быстрее, чем использование sort_by, но после заполнения массивов 100 000 объектов OpenStruct и сортировки по атрибуту sort_by был в 100 раз быстрее.

Вот мои результаты бенчмаркинга:

def pop_merge_sorted_arrays(array1,array2)
  array1.reverse!
  array2.reverse!
  output = []

  loop do
    break if array1.empty? || array2.empty?
    output << (array1.last.my_field < array2.last.my_field ? array1.pop : array2.pop)
  end
  return output + array1.reverse + array2.reverse
end

def shift_merge_sorted_arrays(array1,array2)
  output = []
  loop do
    break if array1.empty? || array2.empty?
    output << (array1.first.my_field < array2.first.my_field ? array1.shift : array2.shift)
  end
  return output + array1 + array2
end

def slice_merge_sorted_arrays(array1,array2)
  output = []
  loop do
    break if array1.empty? || array2.empty?
    output << (array1.first.my_field < array2.first.my_field ? array1.slice!(0) : array2.slice!(0))
  end
  return output + array1 + array2
end

a=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field)
b=(1..100000).map{|x|OpenStruct.new(:my_field => rand)}.sort_by(:my_field)

# method 1
t=Time.now;w=pop_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t
# average of five runs: 185.96seconds

# method 2
t=Time.now;x=shift_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t
# average of five runs: 0.77seconds

# method 3
t=Time.now;y=slice_merge_sorted_arrays(a.clone,b.clone);puts Time.now-t
# average of five runs: 8.46seconds

# method 4
t=Time.now;z=(a.clone + b.clone).sort_by(&:my_field);puts Time.now-t
# average of five runs: 2.13seconds

Таким образом, в результате вы можете написать метод, который будет перетасовывать их при сохранении порядка, который будет выполняться довольно быстро (и, вероятно, есть еще несколько способов выжать из метода shift_merge, но для дополнительноговыгода, действительно ли это стоит не , просто объединяя их вместе и используя sort_by для простоты этого?: -)

Надеюсь, это не считается отступлением ...

Answer 3

Я быстро взглянул на реализации Array#sort и Enumerable#sort, и обе, похоже, используют быструю сортировку . Таким образом, они могут быть не такими эффективными, как вы вручную, используя сортировку слиянием , которая выбирает, какой из двух потенциальных элементов вывести по очереди в новый список.

Тем не менее, хорошая статья о самореализуемых алгоритмах сортировки показывает, что усилия одного программиста сделать лучше, чем базовая быстрая сортировка, потерпели неудачу - он напрямую не подошел к вашей проблеме, но его цифры достаточно утомительно, что я сначала попробую сортировку по умолчанию Enumerable#sort_by, и только если она будет слишком медленной, я вернусь к попытке самописной сортировки слиянием.