Здравствуйте, Silver_s, Вы писали:
U>>Объясни каким образом рефакторинг поможет избавиться от этих промежуточных состояний?
S_>Если для написавшего ее, она легко читается и ее не прийдется менять, то никаких проблем. Если нет то ее лучше было бы как-то измельчить, порубать на более мелкие. Неважно в функциональном стиле или нет. Для алгоритмов как правило всегда существует много вариантов реализации.
Объясни каким образом измельчение позволит из императивного кода сделать функциональный?
S_>Например:Тут вот похоже два потока данных rawArrivals, rawDepartures, каждый оборот внутреннего цикла выдергивает и обрабатывает один элемент либо из первого либо из второго потока. Это уже можно вынести, в отдельную функцию возвращающую перечисление currentInterval, и если надо информацию откуда выдернуто.Небольшая но все-таки декомпозиция. Не факт что это сильно улучшит, остального кода я не видел (да и не стал бы разбираться с пол-тысячей строк).
И в чем после этого код станет менее императивным?
S_> Всю задачу я не понимаю. Но есть опасения что приведенный кусок кода выдернут из функции которая раз в 5 больше этого куска.
Приведенный кусок кода это практически функция целиком, единственно показана обработка только первой возможной ситуации (транспорт движется запланированно), а обработка двух других возможных ситуаций (неожиданная остановка и транспорт пропустил несколько остановок, но дальше поехал запланированно) поскипана, т.к. не суть.
S_> Интересно было бы только время жизни этих данных.
Время жизни от нуля (если на момент вызова функции у нас были данные на конец расписания) до бесконечности (если данные на конец расписания нам еще не пришли).
S_> И есть ли какая-то топ-функция у который вполне конкретный вход и выход, которая вызывает остальные функции, и которая скрывает какие-то промежуточные данные(время жизни которых не выходит за пределы этой функции).
Это и есть топ-функция. На вход она принимает въезды и выъезды на остановки, на выходе возвращает остановки с временем их прохождения.
Здравствуйте, AndrewVK, Вы писали:
U>>Можно пример сложного алгоритма без сложного промежуточного состояния?
AVK>В каком виде пример? Форматтер исходников в ешарпере сгодится?
Здравствуйте, gandjustas, Вы писали:
U>>Главная проблема чисто функционального подхода, что на нем непонятно как писать сложные алгоритмы. U>>Вот к примеру алгоритм определения прохождения расписания: G>По человечески объясни что код делает, уверен что моментально напишут функциональное решение.
Контроль расписания транспорта(например, автобуса). Т.е. есть набор остановок с временами когда автобус должен на них находиться (например, остановка А-выезд 7:45, остановка B-прибытие 8:34, остановка B-выезд 8:40, остановка А-прибытие 9:05, остановка А-выезд 9:12 и т.д.). Остановки могут накладываться друг друга. Нужно получить отклонения автобуса от расписания.
Здравствуйте, Undying, Вы писали:
U>Здравствуйте, gandjustas, Вы писали:
U>>>Главная проблема чисто функционального подхода, что на нем непонятно как писать сложные алгоритмы. U>>>Вот к примеру алгоритм определения прохождения расписания: G>>По человечески объясни что код делает, уверен что моментально напишут функциональное решение.
U>Контроль расписания транспорта(например, автобуса). Т.е. есть набор остановок с временами когда автобус должен на них находиться (например, остановка А-выезд 7:45, остановка B-прибытие 8:34, остановка B-выезд 8:40, остановка А-прибытие 9:05, остановка А-выезд 9:12 и т.д.).
Так уже лучше.
Какие входные данные? Как определять нахождение автобуса на остановке? В случае непопадания во время прибытия автобус должен простоять положенное время или должен уехать вовремя?
U>Остановки могут накладываться друг друга.
Это как
U>Нужно получить отклонения автобуса от расписания.
В каком виде?
Здравствуйте, gandjustas, Вы писали:
U>>Контроль расписания транспорта(например, автобуса). Т.е. есть набор остановок с временами когда автобус должен на них находиться (например, остановка А-прямая 7:45, остановка B-прямая 8:34, остановка B-обратная 8:40, остановка А-обратная 9:05, остановка А-прямая 9:12 и т.д.).
G>Какие входные данные?
Исходные, то что выше + геокоординаты автобуса во времени. В том алгоритме который я приводил, вместо геокоординат автобуса во времени, алгоритм работает с интервалами времен нахождения в пределах остановки (подготавливаемых из геокоординат автобуса во времени другой функцией).
G>Как определять нахождение автобуса на остановке?
Остановка это геокоордината + радиус. Попадание в этот радиус есть признак нахождения автобуса в пределах остановки. Соответственно алгоритм должен отбрасывать ложные проезды остановок (например, двигаясь по прямому маршруту автобус зацепил остановку обратного маршрута), а также определять к какому времени расписания проезд остановки относился.
G>В случае непопадания во время прибытия автобус должен простоять положенное время или должен уехать вовремя?
Это водителю решать. Задача алгоритма честно показать все отклонения автобуса от расписания.
U>>Остановки могут накладываться друг друга. G>Это как
Есть остановка Победы прямого маршрута, есть остановка Победы обратного маршрута, они могут накладываться друг на друга частично или даже полностью.
U>>Нужно получить отклонения автобуса от расписания. G>В каком виде?
В приведенном алгоритме, у нас есть коллекция остановок расписания с планируемыми временами (описанная вверху), итогом работы алгоритма является выставление для каждой остановки реального времени прибытия и отправления.
ps
Я не требую реализовывать функционально конкретно этот алгоритм (это просто пример задачи со сложным промежуточным состоянием), но мне было бы интересно увидеть решение любой вашей задачи со сложным промежуточным состоянием в чисто функциональном стиле.
Здравствуйте, Undying, Вы писали:
U>Объясни каким образом измельчение позволит из императивного кода сделать функциональный? U>И в чем после этого код станет менее императивным?
Ну так чтобы на низком уровне остались лямбды и цепочки функций из Enumerable, то сомнительно что любой алгоритм можно было так реализовать не ухудшив читабельность.
Но все же когда одна функция заменяется на несколько более маленьких(каждая проще и понятнее исходной), которые последовательно вызываются и передают результат на вход следующей. Это декомпозиция в стиле функциональной.
При этом для функций/алгоритмов плохо поддающихся такой декомпозиции может возникнуть оверхед — некоторые излишества, которые могут только ухудшить ситуацию.
Вот была тема "Закон сохранения сложности", один из моментов там был примерно такой(очень грубо): Когда сложность не превышает какой-то критический уровень, лишние абстракции и какие-то трюки разделения обязанностей,декомпозиции могут только его усложнить и увеличить объем кода. А когда сложность непосильная, на такие трюки,декомпозиции можно пойти, оверхед тоже будет, но общий выигрыш уже положительный. Нелинейные эффекты. Так что для каждого случая индивидуально, в зависимости от конкретных метрик.
Тут кстати приводили небольшие излишества(черезмерное дробление), вроде каждая функция упрощается а общая сложность скорее увеличивается: http://www.rsdn.ru/forum/philosophy/3761260.1.aspx
А так чтобы большой и сложный императивный код (который нельзя уже упростить императивно) превращался в маленький и понятный чисто функциональный, таких примеров не так много(по крайней мере не большинство). Мне бы тоже было интересно посмотреть на их список.
Здравствуйте, Undying, Вы писали:
U>Я не требую реализовывать функционально конкретно этот алгоритм (это просто пример задачи со сложным промежуточным состоянием), но мне было бы интересно увидеть решение любой вашей задачи со сложным промежуточным состоянием в чисто функциональном стиле.
на haskell.
import Data.Time
type Pos = (Double,Double)
dist :: Pos -> Pos -> Double
dist (x1,y1) (x2,y2) = sqrt (x' * x' + y' * y')
where x' = x1 - x2
y' = y1 - y2
type ScheduleItem = (Int, DiffTime)
type Schedule = [ScheduleItem]
type Track = [(Pos, DiffTime)]
type Stations = [Pos]
stations = [...]::Stations
getTrackSegmentWithinRadius :: Double -> Pos -> Track -> (Track, Track)
getTrackSegmentWithinRadius radius pos track =
span (\(p,_) -> dist pos p < radius) $ dropWhile (\(p,_) -> dist pos p > radius) track
data StationPassStatus = InTime | Late | Early | NotPassed
deriving(Eq,Show)
getStationPassStatus :: DiffTime -> Track -> StationPassStatus
getStationPassStatus stationTime segment =
if null segment
then NotPassed
else
--Super complex logic
InTime
where times = map snd segment
min = minimum times
max = maximum times
getScheduleDiff :: Double -> Schedule -> Track -> [(Int, StationPassStatus)]
getScheduleDiff radius s track =
drop 1 $
map (\(_,a,b) -> (a,b)) $
scanr (\(stationId, t) -> \(track,_,_) ->
let (seg, track') = getTrackSegmentWithinRadius radius (stations!!stationId) track
status = getStationPassStatus t seg
in (track', stationId, status)) (track, 0, NotPassed) s
не очень сложное состояние.
Вся передача состояния делается явно через параметры или неявно с помощью монад.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, Undying, Вы писали:
U>>Я не требую реализовывать функционально конкретно этот алгоритм (это просто пример задачи со сложным промежуточным состоянием), но мне было бы интересно увидеть решение любой вашей задачи со сложным промежуточным состоянием в чисто функциональном стиле.
G>на haskell.
Haskell я к сожалению не понимаю, поэтому мне сложно что-то сказать по этому коду. А на шарп это легко переписывается?
Здравствуйте, Undying, Вы писали:
U>Здравствуйте, gandjustas, Вы писали:
G>>Здравствуйте, Undying, Вы писали:
U>>>Я не требую реализовывать функционально конкретно этот алгоритм (это просто пример задачи со сложным промежуточным состоянием), но мне было бы интересно увидеть решение любой вашей задачи со сложным промежуточным состоянием в чисто функциональном стиле.
G>>на haskell.
U>Haskell я к сожалению не понимаю, поэтому мне сложно что-то сказать по этому коду. А на шарп это легко переписывается?
Если забить на ленивость, то в 2 раза по объему больше будет.
public class Pos
{
public double X { get; set; }
public double Y { get; set; }
}
public class TrackItem
{
public Pos Pos { get; set; }
public DateTime Time { get; set; }
}
public enum StationPassStatus
{
InTime, Late, Early, NotPassed
}
public static class EnumeraleExtensions
{
public static Tuple<IEnumerable<T>, IEnumerable<T>> Span<T>(this IEnumerable<T> seq, Func<T, bool> pred)
{
return Tuple.Create(seq.TakeWhile(pred), seq.SkipWhile(pred));
}
public static IEnumerable<S> Scan<T, S>(this IEnumerable<T> seq, S seed, Func<T, S, S> f)
{
var state = seed; //Вот тут происходит передача состоянияforeach (var e in seq)
{
yield return state;
state = f(e, state);
}
}
}
public static class TrackExtensions
{
public static double Dist(Pos p1, Pos p2)
{
var x = p1.X - p2.X;
var y = p1.Y - p2.Y;
return Math.Sqrt(x * x - y * y);
}
public static Tuple<IEnumerable<TrackItem>, IEnumerable<TrackItem>>
GetTrackSegmentWithinRadius(this IEnumerable<TrackItem> track, Pos pos, double radius)
{
return track.SkipWhile(t => Dist(t.Pos, pos) > radius)
.Span(t => Dist(t.Pos, pos) <= radius);
}
public static StationPassStatus GetStationPassStatus
(this IEnumerable<TrackItem> track, DateTime stationTime)
{
if (!track.Any())
{
return StationPassStatus.NotPassed;
}
else
{
var times = track.Select(t => t.Time);
var min = times.Min();
var max = times.Max();
//Супер-логикаreturn StationPassStatus.InTime;
}
}
}
class Program
{
static Pos[] stations = new Pos[] { ... };
static IEnumerable<Tuple<int, StationPassStatus>> GetScheduleDiff
(IEnumerable<Tuple<int,DateTime>> schedule,
IEnumerable<TrackItem> track,
double radius)
{
return schedule.Scan(new { Track = track, StationId = 0, Status = StationPassStatus.NotPassed},
(st, s) =>
{
var r = s.Track.GetTrackSegmentWithinRadius(stations[st.Item1], radius);
var status = r.Item1.GetStationPassStatus(st.Item2);
return new { Track = r.Item2, StationId = st.Item1, Status = status };
})
.Select(t => Tuple.Create(t.StationId, t.Status))
.Skip(1);
}
}
