Сортировать список по более чем одному ограничению в Scala - PullRequest
Новая
       11

Сортировать список по более чем одному ограничению в Scala

1 голос
/ 19 марта 2012

Я отчаянно пытаюсь найти способ сортировки списка строк, где строки являются предопределенными идентификаторами следующего вида: a1.1, a1.2, ..., a1.100, a2.1, a2. 2, ...., a2.100, ..., b1.1, b1.2, .. и т. Д., Что уже соответствует правильному порядку. Таким образом, каждый идентификатор сначала упорядочен по своему первому символу (по убыванию в алфавитном порядке), а в этом порядке по убыванию упорядочен по порядковым номерам. Я пробовал sortWith, предоставив функцию сортировки, указав вышеуказанное правило для всех двух последовательных членов списка. 

scala> List("a1.102", "b2.2", "b2.1", "a1.1").sortWith((a: String, b: String) => a.take(1) < b.take(1) && a.drop(1).toDouble < b.drop(1).toDouble)
res2: List[java.lang.String] = List(a1.102, a1.1, b2.2, b2.1)

Это не тот порядок, который я ожидал. Однако, меняя порядок выражений как 

scala> List("a1.102", "b2.2", "b2.1", "a1.1").sortWith((a: String, b: String) => (a.drop(1).toDouble < b.drop(1).toDouble && a.take(1) < b.take(2)))
res3: List[java.lang.String] = List(a1.1, a1.102, b2.1, b2.2)

это действительно дает мне (по крайней мере, для этого примера) желаемый порядок, который я тоже не понимаю.

Я был бы очень благодарен, если бы кто-нибудь дал мне подсказку, что именно там происходит и как я могу сортировать списки по своему желанию (с более сложным логическим выражением, чем только сравнение <или>). Еще один вопрос: строки, которые я сортирую (в моем примере), на самом деле являются ключами из HashMap m. Любое решение повлияет на сортировку m по ключам в пределах 

m.toSeq.sortWith((a: (String, String), b: (String, String)) => a._1.drop(1).toDouble < b._1.drop(1).toDouble && a._1.take(1) < b._1.take(1))

Большое спасибо заранее!

Ответы [ 3 ]

6 голосов
/ 20 марта 2012

Обновление: я неверно истолковал ваш пример - вы хотите, чтобы a1.2 предшествовал a1.102, что в приведенных ниже версиях toDouble не будет правильным.Вместо этого я бы предложил следующее: 

items.sortBy { s =>
  val Array(x, y) = s.tail.split('.')
  (s.head, x.toInt, y.toInt)
}

Здесь мы используем Ordering экземпляр Scala для Tuple3[Char, Int, Int].

Похоже, у вас есть опечатка в секунду («правильная») версия: b.take(2) не имеет смысла и должно быть b.take(1), чтобы соответствовать первому.Как только вы исправите это, вы получите тот же (неправильный) порядок.

Реальная проблема заключается в том, что вам нужно только второе условие в случае совпадения чисел.Таким образом, следующее работает так, как нужно: 

val items = List("a1.102", "b2.2", "b2.1", "a1.1")
items.sortWith((a, b) =>
  a.head < b.head || (a.head == b.head && a.tail.toDouble < b.tail.toDouble)
)

Я бы на самом деле предложил следующее: 

items.sortBy(s => s.head -> s.tail.toDouble)

Здесь мы пользуемся тем фактом, что Scala предоставляет соответствующий Orderingэкземпляр для Tuple2[Char, Double], поэтому мы можем просто предоставить функцию преобразования, которая превращает ваши элементы в этот тип.

И чтобы ответить на ваш последний вопрос: да, любой из этих подходов должен прекрасно работать с вашим Mapпример.

0 голосов
/ 20 марта 2012

Создайте кортеж, содержащий строку перед ".", а затем целое число после ".".При этом будет использоваться лексикографический порядок для первой части и порядок по целому числу для второй части. 

scala> val order = Ordering.by((s:String) => (s.split("\\.")(0),s.split("\\.")(1).toInt))
order: scala.math.Ordering[String] = scala.math.Ordering$$anon$7@384eb259

scala> res2
res8: List[java.lang.String] = List(a1.5, a2.2, b1.11, b1.8, a1.10)


scala> res2.sorted(order)
res7: List[java.lang.String] = List(a1.5, a1.10, a2.2, b1.8, b1.11)
0 голосов
/ 20 марта 2012

Итак, рассмотрим, что происходит, когда передаются функции сортировки a="a1.1" и b="a1.102".Что бы вы хотели, чтобы функция возвращала true.Тем не менее, a.take(1) < b.take(1) возвращает false, поэтому функция возвращает false.

Подумайте о своих случаях чуть более осторожно

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

Поэтому попробуйте это вместо: 

(a: String, b: String) => if (a.take(1) == b.take(1)) a.drop(1).toDouble < b.drop(1).toDouble else a.take(1) < b.take(1)

И это возвращает правильный порядок: 

scala> List("a1.102", "b2.2", "b2.1", "a1.1").sortWith((a: String, b: String) => if (a.take(1) == b.take(1)) a.drop(1).toDouble < b.drop(1).toDouble else a.take(1) < b.take(1))
res8: List[java.lang.String] = List(a1.1, a1.102, b2.1, b2.2)

Причиной того, что он сработал для вас с обратным порядком, была удача.Рассмотрим дополнительный ввод "c0", чтобы увидеть, что происходит: 

scala> List("c0", "a1.102", "b2.2", "b2.1", "a1.1").sortWith((a: String, b: String) => (a.drop(1).toDouble < b.drop(1).toDouble && a.take(1) < b.take(2)))
res1: List[java.lang.String] = List(c0, a1.1, a1.102, b2.1, b2.2)

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

...