Блог

Главная - Вопросы по программированию - Сортировка структуры на основе ссылочного массива в ruby

Сортировка структуры на основе ссылочного массива в ruby

#arrays #ruby

#массивы #ruby

Вопрос:

У меня есть определение структуры как

 Player = Struct.new(:name, :level)

И образец массива

 levels = [ 'level-1','level-2','beta','alpha','level4','level7']

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

 [#<struct Player name="Ryan", level="beta">,
 #<struct Player name="Chris", level="alpha">,
  #<struct Player name="Tom", level="level4">,
 #<struct Player name="Edward", level="level1">,
  #<struct Player name="Drew", level="level7">]

становится

  #[<struct Player name="Edward", level="level1">,
 #<struct Player name="Ryan", level="beta">,
 #<struct Player name="Chris", level="alpha">,
  #<struct Player name="Tom", level="level4">,
  #<struct Player name="Drew", level="level7">]

Как мне это сделать в ruby.

Я пытался

 arr.sort_by { |e| [ levels.index(e.level)] }

ArgumentError: comparison of Array with Array failed
from (pry):79:in `sort_by'

Ответ №1:

У вас почти получилось. Результатом sort_by блока должно быть то, с чем вы хотите сравнить. Вы хотите использовать индекс в уровнях, а не массив, содержащий индекс в уровнях.

 arr.sort_by { |e| levels.index(e.level) }

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

Комментарии:

1. Просто хочу отметить, что вы можете оптимизировать временную сложность здесь, предварительно индексируя массив уровней, например, превратив его в { <level> => <index> } хэш, чтобы вам не приходилось вызывать .index повторно

2. Чтобы дополнить предложение @maxpleaner: for arr = [["Tom", "level4"], ["Ryan", "beta"], ["Chris", "alpha"]].map { |a| Player.new(*a) } #=> [#<struct Player name="Tom", level="level4">, #<struct Player name="Ryan", level="beta">, #<struct Player name="Chris", level="alpha">] , construct level_to_idx = levels.each_with_index.to_a.to_h #=> {"level-1"=>0, "level-2"=>1, "beta"=>2, "alpha"=>3, "level4"=>4, "level7"=>5} ,…

3. @CarySwoveland Я уже задавал этот вопрос в интервью раньше, и я всегда говорю, что он переходит от O (N ^ 2) к O (N), но мне просто пришло в голову спросить, действительно ли это так? Является ли временная сложность sort_by O (N)?

4. …затем arr.sort_by { |i| level_to_idx[i.level] } #=> [#<struct Player name="Ryan", level="beta">, #<struct Player name="Chris", level="alpha">, #<struct Player name="Tom", level="level4">] . Это снижает вычислительную сложность с O (n ** 2) до O (nlog (n)).

5. @maxpleaner, о чем ты говоришь? Я сказал O(nlog(n)) . (Признание: я сказал O (n) в удаленном комментарии.)

Ответ №2:

Вот решение, которое имеет вычислительную сложность, близкую к O (n), «close», потому что хэш-запросы не совсем постоянны по времени.

Нам дается:

 Player = Struct.new(:name, :level)

arr = [["Tom", "level4"], ["Ryan", "beta"], ["Chris", "alpha"],
       ["Drew", "level4"]].map { |a| Player.new(*a) }
  #=> [#<struct Player name="Tom",   level="level4">,
  #    #<struct Player name="Ryan",  level="beta">,
  #    #<struct Player name="Chris", level="alpha">,
  #    #<struct Player name="Drew",  level="level4">]

Обратите внимание, что у Тома и Дрю одинаковый уровень.

 levels = ['level-1','level-2','beta','alpha','level4','level7']

Затем

     arr.group_by(amp;:level).values_at(*levels).flatten.compact
  #=>[#<struct Player name="Ryan",  level="beta">,
  #   #<struct Player name="Chris", level="alpha">,
  #   #<struct Player name="Tom",   level="level4">,
  #   #<struct Player name="Drew",  level="level4">]

Шаги следующие:

 h = arr.group_by(amp;:level)
  #=> {"level4"=>[#<struct Player name="Tom",   level="level4">,
  #               #<struct Player name="Drew",  level="level4">],
  #    "beta"  =>[#<struct Player name="Ryan",  level="beta">],
  #    "alpha" =>[#<struct Player name="Chris", level="alpha">]}
 
 a = h.values_at(*levels)
  #=> [nil,
  #    nil,
  #    [#<struct Player name="Ryan",  level="beta">],
  #    [#<struct Player name="Chris", level="alpha">],
  #    [#<struct Player name="Tom",   level="level4">,
  #     #<struct Player name="Drew",  level="level4">],
  #    nil]
 
 b = a.compact
  #=>  [[#<struct Player name="Ryan",  level="beta">],
  #     [#<struct Player name="Chris", level="alpha">],
  #     [#<struct Player name="Tom",   level="level4">,
  #      #<struct Player name="Drew",  level="level4">]]
 
 c = b.flatten
  #=>  [#<struct Player name="Ryan",  level="beta">,
  #     #<struct Player name="Chris", level="alpha">,
  #     #<struct Player name="Tom",   level="level4">,
  #     #<struct Player name="Drew",  level="level4">]
Метки: