Как отсортировать буквенно-цифровой массив в ruby

Question

Как я могу отсортировать данные массива в алфавитном порядке в рубине?

Предположим, мой массив a = [test_0_1, test_0_2, test_0_3, test_0_4, test_0_5, test_0_6, test_0_7, test_0_8, test_0_9, test_1_0, test_1_1, test_1_2, test_1_3, test_1_4, test_1_5, test_1_6, test_1_7, test_1_8, test_1_9, test_1_10, test_1_11, test_1_12, test_1_13, test_1_14, ...........test_1_121...............]

Я хочу, чтобы мой вывод был:

.
.
.
test_1_121
.
.
.
test_1_14
test_1_13
test_1_12
test_1_11
test_1_10
test_1_9
test_1_8
test_1_7
test_1_6
test_1_5
test_1_4
test_1_3
test_1_2
test_1_1
test_0_10
test_0_9
test_0_8
test_0_7
test_0_6
test_0_5
test_0_4
test_0_3
test_0_2
test_0_1

Answer 1

Общий алгоритм для сортировки строк, которые содержат произвольные порядковые номера в произвольных позициях.

padding = 4
list.sort{|a,b|
  a,b = [a,b].map{|s| s.gsub(/\d+/){|m| "0"*(padding - m.size) + m } }
  a<=>b
}

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

Чтобы получить запрошенный результатпользователем682932, просто добавьте .reverse после блока сортировки, который перевернет естественный порядок (по возрастанию) в порядке убывания.

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

padding = list.reduce(0){|max,s| 
  x = s.scan(/\d+/).map{|m|m.size}.max
  (x||0) > max ? x : max
}

Answer 2

Если вы просто сортируете как строку, вы не получите правильный порядок, например, между «test_2» и «test_10».Так же:

sort_by{|s| s.scan(/\d+/).map{|s| s.to_i}}.reverse

Answer 3

Размещение здесь более общего способа выполнения естественной десятичной сортировки в Ruby.Следующее основано на моем коде для сортировки "как Xcode" из https://github.com/CocoaPods/Xcodeproj/blob/ca7b41deb38f43c14d066f62a55edcd53876cd07/lib/xcodeproj/project/object/helpers/sort_helper.rb,, который сам по себе слабо вдохновлен https://rosettacode.org/wiki/Natural_sorting#Ruby.

Даже если ясно, что мы хотим, чтобы "10" было после "2" дляестественная десятичная сортировка, есть и другие аспекты, которые необходимо учитывать при желании нескольких возможных альтернативных поведений:

• Как мы относимся к равенству как «001» / «01»: сохраняем ли мы исходный порядок массива или делаему нас есть запасная логика?(Ниже сделан выбор второго прохода со строгой логикой упорядочения в случае равенства во время первого прохода)
• Мы игнорируем последовательные пробелы для сортировки или каждый символ пробела считается?(Ниже сделан выбор игнорировать последовательные пробелы при первом проходе и проводить строгое сравнение на проходе равенства)
• Тот же вопрос для других специальных символов.(Ниже делается выбор, чтобы любой не пробельный и нецифровый символ подсчитывался отдельно)
• Мы игнорируем регистр или нет;такое «а» до или после «А»?(Ниже сделан выбор игнорировать регистр при первом проходе, и мы имеем «a» перед «A» на проходе равенства)

С учетом этих соображений:

• Это означает, что мы почти наверняка должны использовать scan вместо split, потому что у нас будет потенциально три вида подстрок для сравнения (цифры, пробелы, все остальные).
• Itозначает, что мы почти наверняка должны работать с классом Comparable и def <=>(other), потому что невозможно просто map каждую подстроку к чему-то другому, что будет иметь два различных поведения в зависимости от контекста (первый проход и проход равенства).

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

  # Wrapper for a string that performs a natural decimal sort (alphanumeric).
  # @example
  #   arrayOfFilenames.sort_by { |s| NaturalSortString.new(s) }
  class NaturalSortString
    include Comparable
    attr_reader :str_fallback, :ints_and_strings, :ints_and_strings_fallback, :str_pattern

    def initialize(str)
      # fallback pass: case is inverted
      @str_fallback = str.swapcase
      # first pass: digits are used as integers, spaces are compacted, case is ignored
      @ints_and_strings = str.scan(/\d+|\s+|[^\d\s]+/).map do |s|
        case s
        when /\d/ then Integer(s, 10)
        when /\s/ then ' '
        else s.downcase
        end
      end
      # second pass: digits are inverted, case is inverted
      @ints_and_strings_fallback = @str_fallback.scan(/\d+|\D+/).map do |s|
        case s
        when /\d/ then Integer(s.reverse, 10)
        else s
        end
      end
      # comparing patterns
      @str_pattern = @ints_and_strings.map { |el| el.is_a?(Integer) ? :i : :s }.join
    end

    def <=>(other)
      if str_pattern.start_with?(other.str_pattern) || other.str_pattern.start_with?(str_pattern)
        compare = ints_and_strings <=> other.ints_and_strings
        if compare != 0
          # we sort naturally (literal ints, spaces simplified, case ignored)
          compare
        else
          # natural equality, we use the fallback sort (int reversed, case swapped)
          ints_and_strings_fallback <=> other.ints_and_strings_fallback
        end
      else
        # type mismatch, we sort alphabetically (case swapped)
        str_fallback <=> other.str_fallback
      end
    end
  end

Использование

Пример 1:

arrayOfFilenames.sort_by { |s| NaturalSortString.new(s) }

Пример 2:

arrayOfFilenames.sort! do |x, y|
  NaturalSortString.new(x) <=> NaturalSortString.new(y)
end

Мой тестовый пример вы можете найти в https://github.com/CocoaPods/Xcodeproj/blob/ca7b41deb38f43c14d066f62a55edcd53876cd07/spec/project/object/helpers/sort_helper_spec.rb,, где я использовал эту ссылку для заказа: ['a', 'a', '0.1.1',' 0.1.01 ',' 0.1.2 ',' 0.1.10 ',' 1 ',' 01 ',' 1a ',' 2 ',' 2 a ',' 10 ',' a ','A»,'a', 'a 2', 'a1', 'A1B001', 'A01B1',]

Конечно, не стесняйтесь настраивать свою собственную логику сортировки сейчас.

Answer 4

Процедуры сортировки могут иметь очень разное время обработки.Сравнительные варианты сортировки могут быстро найти самый быстрый способ сделать что-то:

#!/usr/bin/env ruby

ary = %w[
    test_0_1  test_0_2   test_0_3 test_0_4 test_0_5  test_0_6  test_0_7
    test_0_8  test_0_9   test_1_0 test_1_1 test_1_2  test_1_3  test_1_4  test_1_5
    test_1_6  test_1_7   test_1_8 test_1_9 test_1_10 test_1_11 test_1_12 test_1_13
    test_1_14 test_1_121
]

require 'ap'
ap ary.sort_by { |v| a,b,c = v.split(/_+/); [a, b.to_i, c.to_i] }.reverse

И его вывод:

>> [
>>     [ 0] "test_1_121",
>>     [ 1] "test_1_14",
>>     [ 2] "test_1_13",
>>     [ 3] "test_1_12",
>>     [ 4] "test_1_11",
>>     [ 5] "test_1_10",
>>     [ 6] "test_1_9",
>>     [ 7] "test_1_8",
>>     [ 8] "test_1_7",
>>     [ 9] "test_1_6",
>>     [10] "test_1_5",
>>     [11] "test_1_4",
>>     [12] "test_1_3",
>>     [13] "test_1_2",
>>     [14] "test_1_1",
>>     [15] "test_1_0",
>>     [16] "test_0_9",
>>     [17] "test_0_8",
>>     [18] "test_0_7",
>>     [19] "test_0_6",
>>     [20] "test_0_5",
>>     [21] "test_0_4",
>>     [22] "test_0_3",
>>     [23] "test_0_2",
>>     [24] "test_0_1"
>> ]

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

require 'benchmark'

n = 50_000
Benchmark.bm(8) do |x|
  x.report('sort1') { n.times { ary.sort { |a,b| b <=> a }         } }
  x.report('sort2') { n.times { ary.sort { |a,b| a <=> b }.reverse } }
  x.report('sort3') { n.times { ary.sort { |a,b|
                                  ap = a.split('_')
                                  a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
                                  bp = b.split('_')
                                  b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
                                  b <=> a
                                } } }

  x.report('sort_by1') { n.times { ary.sort_by { |s| s                                               }         } }
  x.report('sort_by2') { n.times { ary.sort_by { |s| s                                               }.reverse } }
  x.report('sort_by3') { n.times { ary.sort_by { |s| s.scan(/\d+/).map{ |s| s.to_i }                 }.reverse } }
  x.report('sort_by4') { n.times { ary.sort_by { |v| a = v.split(/_+/); [a[0], a[1].to_i, a[2].to_i] }.reverse } }
  x.report('sort_by5') { n.times { ary.sort_by { |v| a,b,c = v.split(/_+/); [a, b.to_i, c.to_i]      }.reverse } }
end


>>               user     system      total        real
>> sort1     0.900000   0.010000   0.910000 (  0.919115)
>> sort2     0.880000   0.000000   0.880000 (  0.893920)
>> sort3    43.840000   0.070000  43.910000 ( 45.970928)
>> sort_by1  0.870000   0.010000   0.880000 (  1.077598)
>> sort_by2  0.820000   0.000000   0.820000 (  0.858309)
>> sort_by3  7.060000   0.020000   7.080000 (  7.623183)
>> sort_by4  6.800000   0.000000   6.800000 (  6.827472)
>> sort_by5  6.730000   0.000000   6.730000 (  6.762403)
>> 

Sort1 и sort2, а также sort_by1 и sort_by2 помогают установить базовые показатели для sort, sort_by, и оба с reverse.

Сортировки sort3 и sort_by3 - два других ответа на этой странице.Sort_by4 и sort_by5 - это два варианта того, как я это сделаю, причем sort_by5 - самый быстрый из всех, что я придумала после нескольких минут работы.

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

Answer 5

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

a.sort { |a,b|
  ap = a.split('_')
  a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
  bp = b.split('_')
  b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
  b <=> a
}

Answer 6

Аналогично ответу @ctcherry, но быстрее:

a.sort_by {|s| "%s%05i%05i" % s.split('_') }.reverse

РЕДАКТИРОВАТЬ: Мои тесты:

require 'benchmark'
ary = []
100_000.times { ary << "test_#{rand(1000)}_#{rand(1000)}" }
ary.uniq!; puts "Size: #{ary.size}"

Benchmark.bm(5) do |x|
  x.report("sort1") do
    ary.sort_by {|e| "%s%05i%05i" % e.split('_') }.reverse
  end
  x.report("sort2") do
    ary.sort { |a,b|
      ap = a.split('_')
      a = ap[0] + "%05d" % ap[1] + "%05d" % ap[2]
      bp = b.split('_')
      b = bp[0] + "%05d" % bp[1] + "%05d" % bp[2]
      b <=> a
    } 
  end
  x.report("sort3") do
    ary.sort_by { |v| a, b, c = v.split(/_+/); [a, b.to_i, c.to_i] }.reverse
  end
end

Выход:

Size: 95166

           user     system      total        real
sort1  3.401000   0.000000   3.401000 (  3.394194)
sort2 94.880000   0.624000  95.504000 ( 95.722475)
sort3  3.494000   0.000000   3.494000 (  3.501201)

Answer 7

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

a.reverse

Answer 8

Судя по всему, вы хотите использовать функцию сортировки и / или функцию реверса .

ruby-1.9.2-p136 :009 > a = ["abc_1", "abc_11", "abc_2", "abc_3", "abc_22"]
 => ["abc_1", "abc_11", "abc_2", "abc_3", "abc_22"] 

ruby-1.9.2-p136 :010 > a.sort
 => ["abc_1", "abc_11", "abc_2", "abc_22", "abc_3"] 
ruby-1.9.2-p136 :011 > a.sort.reverse
 => ["abc_3", "abc_22", "abc_2", "abc_11", "abc_1"]