Здравствуйте, Lloyd, Вы писали:
G>>Ну, по мелочи — двоеточие пропустил. Вот здесь.
G>>for i, val := range x {
L>И это еще не конец. Эх, Gaperton, вроде и язык простой и задача простая, а столько ошибок на пустом месте. L>Как же так?
Компилятора нет, пишу на бумажке. Кроме того, это одна из моих первых программ на Go, и я постоянно сверяюсь с мануалом.
Удовлетворен? Или будут еще не относящиеся к делу вопросы?
Здравствуйте, Gaperton, Вы писали:
G>Тяжело, когда под рукой нет компилятора. Впрочем, наши коллеги линкеры также свой код не тестили. Иначе бы заметили, что их результаты с твоими примерами не совпадают.
Можно гипотетически прикинуть. Уменя получилось что-то вроде такого (предположим для простоты, что канал бесконечен):
func (c chan int, o chan int) {
var va int <- c
var vb int := 0
for {
vb <- c
if vb - a = 1 {
o <- vb
va <- c
}
else va := vb
}
}
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
func (c chan int, o chan int) {
var va int <- c
var vb int := 0
for {
vb <- c
if vb - va = 1 {
o <- vb
va <- c
}
else va := vb
}
}
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Lloyd, Вы писали:
L>Там два условия: L>1) елемент на единицу больше предыдущего. L>2) L>
L>при этом извлечённый элемент не должен принимать участия в последующем сравнении
L>Ты же заменил 2-е условие на другое: L>
L>при этом предшествующий элемент не должен удовлетворять первому условию
L>А такая замена некорректна.
?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию. Это можно строго доказать при желании. Утверждение "извлеченный элемент не принимает участия в последующем сравнении" относится к критерию фильтра, а не к алгоритму, который является решением задачи.
L>>при этом извлечённый элемент не должен принимать участия в последующем сравнении
L>>Ты же заменил 2-е условие на другое: L>>
L>>при этом предшествующий элемент не должен удовлетворять первому условию
L>>А такая замена некорректна.
G> ?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию.
Нет, он не удовлетворяет условию. Возьми последовательность {1, 2, 3, 4} и убедись.
G> Это можно строго доказать при желании.
Ты че такой упертый? Сам же видишь, что не прав, но продолжаешь упираться. Твой алгоритм даже на тестовом примере, что был изначально приведен, даст ответ, отличный от ожидаемого. О чем тут спорить?
Здравствуйте, Lloyd, Вы писали:
G>>От чего твоему коду сильно легчает, и становится заметно, что это простейшая императивная реализация.
G>>Вот тебе еще один пример с циклом, который проще чем твой вариант с линком.
L>Ну вот, превратил занятную головоломку для последующих supporter-ов в какое-то банальное унылое г**но.
Виноват, привычка, доведенная до автоматизма годами практики. Видишь-ли, я на саппорте 6 лет отработал.
Здравствуйте, Gaperton, Вы писали:
L>>Ты же заменил 2-е условие на другое: L>>
L>>при этом предшествующий элемент не должен удовлетворять первому условию
L>>А такая замена некорректна.
G> ?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию. Это можно строго доказать при желании. Утверждение "извлеченный элемент не принимает участия в последующем сравнении" относится к критерию фильтра, а не к алгоритму, который является решением задачи.
Не. Lloyd прав — твой алгоритм на монотонно возрастающей последовательности {1, 2, 3, 4, 5} выдаст {2}, а не {2, 4}.
Вот экивалент на шарпе:
static bool p(int[] x, int i)
{
return i > 0 && x[i - 1] == (x[i] - 1);
}
static List<int> gena_1(int[] x){
var res = new List<int>();
for(int i = 0; i < x.Length; ++i)
{
if (p(x, i) && !p(x, i - 1))
res.Add(x[i]);
}
return res;
}
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
func loop( c, o chan int ) // два раза типы писать не надо.
{
prev := <- c // := позволяет не писать мусора при объявлении+инициализации
for val := range с //читать из потока идиоматично в нашем случае так.
{
if val != prev + 1 // это у нас типо фильтр входных значений, мы его четко отделили
{
prev = val
continue
}
o <- val //а здесь обработка результата
prev = <- c //и как положено, пропускаем один шаг.
//Да, операция чтения - унарная, и надо писать "равно".
}
}
Вообще красота получилась. Не ожидал. Возьму на заметку.
Здравствуйте, Lloyd, Вы писали:
G>> ?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию.
L>Нет, он не удовлетворяет условию. Возьми последовательность {1, 2, 3, 4} и убедись.
Ага, теперь вижу. Блин, и правда бага . Непорядок. Ща схожу за сигаретами, и что-нибудь придумаю.
G>> Это можно строго доказать при желании.
L>Ты че такой упертый? Сам же видишь, что не прав, но продолжаешь упираться.
Не видел, пока ты не привел теста, на котором оно ломается. Че, не знаешь как баги репортить штоли?
Здравствуйте, Gaperton, Вы писали:
G>Вообще красота получилась. Не ожидал. Возьму на заметку.
Это CSP.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Здравствуйте, Gaperton, Вы писали:
L>>>Ты же заменил 2-е условие на другое: L>>>
L>>>при этом предшествующий элемент не должен удовлетворять первому условию
L>>>А такая замена некорректна.
G>> ?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию. Это можно строго доказать при желании. Утверждение "извлеченный элемент не принимает участия в последующем сравнении" относится к критерию фильтра, а не к алгоритму, который является решением задачи.
ГВ>Не. Lloyd прав — твой алгоритм на монотонно возрастающей последовательности {1, 2, 3, 4, 5} выдаст {2}, а не {2, 4}.
Так. По-ходу, как фиксить багу я кажется понял. Удивительно, но похоже эту задачку все-таки можно решить через компрехеншнс (в чем и была моя изначальная идея — решить в компрехеншнс, и перевести в цикл). Получается, правда, уже не так красиво, как я написал... Но все-таки, похоже задача решается без протягивания состояния с итерации на итерацию. Что далеко не очевидно.
Предлагается примерно следующая схема:
собираем индексы начал монотонного возрастания с единицей
starts = [ i | i <- 0..N, x.p(i), !x.p(i-1) ]
и индексы концов.
ends = [ i | i <- 0..N, !x.p(i), x.p(i-1) ]
p — предикат из моего решения, надо его профиксить чтобы он работал при превышении границы массива (выдавал false).
Элементов в обоих списках должно получиться равное количество, если правильно подобрать границы.
Потом, мы пробегаемся по обоим одновременно, и для каждой пары s и e генерируем последовательность индексов с шагом 2, делая выборку индекса уже из нее. Так в компрехеншнсах можно.
res = [ x[n] | ( s <- start & e <- ends ), n <- seq( s, e, 2 ) ]
где
seq — это функция, генерирующая последовательность чисел начиная с s, с шагом в третьем аргументе, и не более чем e.
& для генераторов обозначает параллельную выборку.
Как-то так. Решение вполне реляционно, и должно получиться примерно 4-5 строк кода на языках с компрехеншнсами (если я опять чего-нибудь не пропустил). Естественно, это достаточно компактно (если сравнивать с компрехеншнсами) переводится в циклы. Сейчас уже делать не буду, да и смысла особого нет — обычный вариант с циклом и форсированием пропуска следующей итерации очевидно проще.
Но вообще — жесть. Повезло, что удалось зацепиться за особенности задачи. Небольшая вариация условия — и все, досвидос.
Здравствуйте, Gaperton, Вы писали:
ГВ>>Не. Lloyd прав — твой алгоритм на монотонно возрастающей последовательности {1, 2, 3, 4, 5} выдаст {2}, а не {2, 4}.
G>Так. По-ходу, как фиксить багу я кажется понял. Удивительно, но похоже эту задачку все-таки можно решить через компрехеншнс (в чем и была моя изначальная идея — решить в компрехеншнс, и перевести в цикл). Получается, правда, уже не так красиво, как я написал... Но все-таки, похоже задача решается без протягивания состояния с итерации на итерацию. Что далеко не очевидно.
Она решается без протягивания состояния исключительно потому, что в твоем решении сосотояние глобально.
В случае, когда у тебя будет только курсор, который можно прокрутить только вперед (IEnumerable) без состояния уже не обойтись, как минимум придется сохранять значение предиката на предыдущем элементе.
Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>Вообще, знаешь, ты прав, пожалуй. Можно ввести требование, например, "отбирать запись, отстоящую от заданной не более, чем на -30 минут", или вообще — связанную с какой-то отдельной меткой события.
А можно уточнить, какие сложности при этом возникают. Не втыкаю как-то.
Здравствуйте, Gaperton, Вы писали:
G>Как-то так. Решение вполне реляционно, и должно получиться примерно 4-5 строк кода на языках с компрехеншнсами (если я опять чего-нибудь не пропустил). Естественно, это достаточно компактно (если сравнивать с компрехеншнсами) переводится в циклы. Сейчас уже делать не буду, да и смысла особого нет — обычный вариант с циклом и форсированием пропуска следующей итерации очевидно проще.
Ещё можно поиграть с возвратом замыканий. Тоже, кажется, должно компактно получиться.
G>Но вообще — жесть. Повезло, что удалось зацепиться за особенности задачи. Небольшая вариация условия — и все, досвидос. G>Геннадий, спасибо за задачку . Это был фан .
Всегда пожалуйста.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, Геннадий Васильев, Вы писали:
ГВ>>Вообще, знаешь, ты прав, пожалуй. Можно ввести требование, например, "отбирать запись, отстоящую от заданной не более, чем на -30 минут", или вообще — связанную с какой-то отдельной меткой события.
L>А можно уточнить, какие сложности при этом возникают. Не втыкаю как-то.
Не так просто привязаться к позиции. Например, у нас идут вот такие записи:
struct R {
DateTime time;
int value;
bool mark;
...
};
...в порядке возрастания time. Некоторые содержат true в mark. Когда на вход поступает очередная запись с mark=true (обозначим её r0), нужно выдать на выход "самую старую" запись, пришедшую не ранее, чем за 30 минут. Задача усложняется тем, что совершенно не обязательно, что time будет выравнен по границе минуты, т.е. к индексу уже не привяжешься.
Вот такой пример, скажем:
time mark
------------
0:14:00 f
0:15:28 f
0:18:20 f
0:27:37 f < ...а вернуть надо вот эту
0:29:59 f
0:32:28 f
0:55:32 t < mark = true, теперь см. выше...
Или, например, так. Та же структура, только на входе два потока — один "чаще", второй "реже". Теперь нужно выдавать на выход те записи первого потока, временнАя метка которых лежит в пределах [время-в-записи-второго-потока...+2 часа].
Ну то есть:
Stream 2, "редкий"
time mark
-------------
3:00:00 f
4:15:00 t <- опорное время
Stream 1, "частый"
time mark
------------
4:14:00 f
4:15:28 f <- начать нужно отсюда...
4:18:20 f
4:27:37 f
4:35:32 f
...
5:14:30 f <- ...а закончить здесь
5:15:32 f
Для Stream 1 тоже может быть добавлено какое-то условие, скажем, вычленять записи, находящиеся в диапазоне [-10 минут ... +2 часа].
Ну и дополнительную прелесть задаче придаёт то, что такие серии могут быть в десятки мегабайт размером.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Несколько опечаток:
ГВ>Или, например, так. Та же структура, только на входе два потока — один "чаще", второй "реже". Теперь нужно выдавать на выход те записи первого потока, временнАя метка которых лежит в пределах [время-в-записи-второго-потока...+1 час].
ГВ>Для Stream 1 тоже может быть добавлено какое-то условие, скажем, вычленять записи, находящиеся в диапазоне [-10 минут ... +1 час].
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Lloyd, Вы писали:
L>Здравствуйте, Gaperton, Вы писали:
ГВ>>>Не. Lloyd прав — твой алгоритм на монотонно возрастающей последовательности {1, 2, 3, 4, 5} выдаст {2}, а не {2, 4}.
G>>Так. По-ходу, как фиксить багу я кажется понял. Удивительно, но похоже эту задачку все-таки можно решить через компрехеншнс (в чем и была моя изначальная идея — решить в компрехеншнс, и перевести в цикл). Получается, правда, уже не так красиво, как я написал... Но все-таки, похоже задача решается без протягивания состояния с итерации на итерацию. Что далеко не очевидно.
L>Она решается без протягивания состояния исключительно потому, что в твоем решении сосотояние глобально.
В этом решении нет состояния вообще, потому, что в нем нет мутабельных операций. Все абсолютно чисто. Я нигде не изменяю состояния создаваемых объектов, и ничего помнить между итерациями не требуется.
L>В случае, когда у тебя будет только курсор, который можно прокрутить только вперед (IEnumerable) без состояния уже не обойтись, как минимум придется сохранять значение предиката на предыдущем элементе.
Ты имеешь в виду, при невозможности обращения к исходному массиву по индексу, штоли? Да вроде и этого можно избежать, при желании. Все должно ложиться на однопроходные операции, а обращение по индексу может быть решено через джойны.
Интерес, правда, в этом скорее академический. Уж больно через жопу как-то получается. Но надо на всякий случай запомнить, может пригодится когда-нибудь.
Здравствуйте, Геннадий Васильев, Вы писали:
G>>Как-то так. Решение вполне реляционно, и должно получиться примерно 4-5 строк кода на языках с компрехеншнсами (если я опять чего-нибудь не пропустил). Естественно, это достаточно компактно (если сравнивать с компрехеншнсами) переводится в циклы. Сейчас уже делать не буду, да и смысла особого нет — обычный вариант с циклом и форсированием пропуска следующей итерации очевидно проще.
ГВ>Ещё можно поиграть с возвратом замыканий. Тоже, кажется, должно компактно получиться.
Возврат замыкания принципиально не отличается от алгоритмов, выраженных через foldl, с явным состоянием, и от "объектного" стиля, где состояние завернуто в объект, и от простых циклов. Во всех этих случаях так или иначе состояние протягивается с одной итерации на другую, только разными способами. Работая с Go, я бы предпочел, вероятно, завернуть состояние в объект, ибо объекты там очень легко делаются. Может быть, ты что-то другое имеешь в виду, правда.
Здравствуйте, Gaperton, Вы писали:
ГВ>>Ещё можно поиграть с возвратом замыканий. Тоже, кажется, должно компактно получиться.
G>Возврат замыкания принципиально не отличается от алгоритмов, выраженных через foldl, с явным состоянием, и от "объектного" стиля, где состояние завернуто в объект, и от простых циклов. Во всех этих случаях так или иначе состояние протягивается с одной итерации на другую, только разными способами. Работая с Go, я бы предпочел, вероятно, завернуть состояние в объект, ибо объекты там очень легко делаются. Может быть, ты что-то другое имеешь в виду, правда.
Да нет, я как раз именно протягивание состояния имею в виду. А в случае Go, кстати, состояние неплохо заворачивается в горутину. Что ты думаешь, я тут крыльями машу?
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Впрочем, наши коллеги линкеры также свой код не тестили. Иначе бы заметили, что их результаты с твоими примерами не совпадают.
Твою двадцать...
?! Такая "замена" абсолютно корректна, ибо никакой "замены" по сути нет. Алгоритм удовлетворяет условию. Это можно строго доказать при желании. Утверждение "извлеченный элемент не принимает участия в последующем сравнении" относится к критерию фильтра, а не к алгоритму, который является решением задачи.
