На основании анализа метода Group в list было установлено, что он правильно работает тогда и только тогда, когда функция cmp обладает свойством транзитивности и рефлективности для операции упорядочивания списка ( см. функцию sort).
Для самого метода Group это избыточно ( достаточно метода correct).
Вопрос – чем вызвано требование упорядочивания списка?
using System;
using System.Console;
using Nemerle;
using Nemerle.Utility;
[Record]
public class Point3D {
[Accessor]
x : int;
[Accessor]
y : int;
[Accessor]
z : int;
public override ToString() : string{
$"($(this.X),$(this.Y),$(this.Z))"
}
}
module Program
{
Main() : void
{
def l = [
Point3D(1,1,1),
Point3D(1,2,2),
Point3D(1,3,3),
Point3D(2,1,4),
Point3D(2,2,5),
Point3D(2,3,6),
Point3D(1,2,7)];
// То, что работает сейчас
def sort (a,b) {
def l_cmp = a.X.CompareTo ( b.X );
if ( l_cmp == 0 ) {
a.Y.CompareTo ( b.Y )
} else {
l_cmp
}
}
// То, чего достаточно
def correct(a,b) {
Math.Abs(a.X.CompareTo(b.X)) + Math.Abs(a.Y.CompareTo(b.Y))
}
WriteLine($"..$l");
WriteLine(" sort:");
WriteLine($"..$(l.Sort(sort))");
WriteLine($"..$(l.Group(sort))");
WriteLine(" correct:");
WriteLine($"..$(l.Sort(correct))");
WriteLine($"..$(l.Group(correct))");
_ = ReadLine();
}
}
Вывод:
(1,1,1), (1,2,2), (1,3,3), (2,1,4), (2,2,5), (2,3,6), (1,2,7)
sort:
(1,1,1), (1,2,2), (1,2,7), (1,3,3), (2,1,4), (2,2,5), (2,3,6)
[(1,1,1)], [(1,2,7), (1,2,2)], [(1,3,3)], [(2,1,4)], [(2,2,5)], [(2,3,6)]
correct:
(1,2,7), (2,3,6), (2,2,5), (2,1,4), (1,3,3), (1,2,2), (1,1,1)
[(1,2,7)], [(2,3,6)], [(2,2,5)], [(2,1,4)], [(1,3,3)], [(1,2,2)], [(1,1,1)]
... << RSDN@Home 1.2.0 alpha rev. 737>>
E>E> def sort (a,b)
E>
Для красоты sort можно написать так
def sort (a,b) {
match ( (a.X.CompareTo ( b.X ), lazy ( a.Y.CompareTo ( b.Y ) ) ) ) {
| ( 0, y ) => y.Value
| ( x, _ ) => x
}
}
только интересно, lazy сработает как надо?
... << RSDN@Home 1.2.0 alpha rev. 737>>
Здравствуйте, ecinunice, Вы писали:
E>Вопрос – чем вызвано требование упорядочивания списка?
Экономия памяти. Вместо накопления списка (массива, whatever) с промежуточными результатами группировки, можно предположить, что список отсортирован и считать, что группа сформирована, когда встретился отличный от предыдущего элемент. Если не ошибаюсь, то сейчас там всё равно создаются списки. Но зато переделка в ленивый вариант — это изменить возвращаемый тип на IEnumerable[IEnumerable['a]] да вставить yield в паре мест.
По идее, наверное, надо иметь оба варианта в штатной библиотеке и назвать их по разному.
... << RSDN@Home 1.2.0 alpha 4 rev. 1084>>
Здравствуйте, Сергей Туленцев, Вы писали:
Поставлю вопрос по другому — является ли существующая реализация метода Group верной, верной с умолчанием, не верной? Например реализаци на
haskell не сортирует список, в этом случае это перекладывается на разработчика — group sort
... << RSDN@Home 1.2.0 alpha rev. 737>>
Здравствуйте, ecinunice, Вы писали:
E>Здравствуйте, Сергей Туленцев, Вы писали:
E>Поставлю вопрос по другому — является ли существующая реализация метода Group верной, верной с умолчанием, не верной? Например реализаци на haskell не сортирует список, в этом случае это перекладывается на разработчика — group sort
Я бы сделал по другому, скажем так. Сортировка отдельно, группировка отдельно. Так же можно было иметь отдельный метод, который неленивый, жрет больше памяти, но не требует сортировки.
... << RSDN@Home 1.2.0 alpha 4 rev. 1084>>
Здравствуйте, Сергей Туленцев, Вы писали:
СТ>Я бы сделал по другому, скажем так. Сортировка отдельно, группировка отдельно. Так же можно было иметь отдельный метод, который неленивый, жрет больше памяти, но не требует сортировки.
А можно забить и использовать GropeBy из Linq-а.
Здравствуйте, Alex1911, Вы писали:
A>Про что здесь и хотели узнать. Просмотрев реализацию метода группировки, узнали, что он сам выполняет сортировку, и только после этого разбивает список на группы. Реализация на haskell просто пробегает по списку, ничего предварительно с ним не делая. А из-за этой неявной сортировки и получается ситуация, описанная в первом посте
А если хаскеллю подать несортированный список, то получим фигню какую-то, да?
... << RSDN@Home 1.2.0 alpha 4 rev. 1084>>
Здравствуйте, Сергей Туленцев, Вы писали:
СТ>А если хаскеллю подать несортированный список, то получим фигню какую-то, да?
Получим результат в соответствии с определением функции Group.
А если мы N подаем функцию, достаточную для группировки (см.
correctАвтор: ecinunice
Дата: 23.04.08
), то получаем тоже фигню какую-то
... << RSDN@Home 1.2.0 alpha rev. 737>>
