Objective Caml - Вторник, 19 марта 2013

Objective Caml

ocaml@conference.jabber.ru

Вторник, 19 марта 2013< ^ >

Конфигурация комнаты

Участники комнаты

GMT+4
[00:30:08] Sun][ вышел(а) из комнаты
[00:47:10] Typhon вышел(а) из комнаты
[00:49:02] Zbroyar вышел(а) из комнаты
[00:49:02] Typhon вошёл(а) в комнату
[00:49:48] Zbroyar вошёл(а) в комнату
[00:53:02] akovbovich вошёл(а) в комнату
[01:13:42] Typhon вышел(а) из комнаты
[01:17:00] Kakadu вышел(а) из комнаты
[01:18:40] Zbroyar вышел(а) из комнаты
[01:44:22] Typhon вошёл(а) в комнату
[02:01:21] tilarids вошёл(а) в комнату
[02:05:54] Typhon вышел(а) из комнаты
[03:26:18] tilarids вышел(а) из комнаты
[03:29:36] tilarids вошёл(а) в комнату
[04:57:09] f[x] вошёл(а) в комнату
[05:32:20] f[x] вышел(а) из комнаты
[05:50:34] tilarids вышел(а) из комнаты: Machine going to sleep
[06:04:18] f[x] вошёл(а) в комнату
[08:04:24] tilarids вошёл(а) в комнату
[09:14:36] tilarids вышел(а) из комнаты
[10:17:55] komar вошёл(а) в комнату
[10:25:42] komar вышел(а) из комнаты: Logged out
[10:39:22] ermine вошёл(а) в комнату
[11:32:58] Typhon вошёл(а) в комнату
[11:45:13] Sun][ вошёл(а) в комнату
[12:16:30] komar вошёл(а) в комнату
[12:41:07] komar вышел(а) из комнаты: Logged out
[12:46:22] zinid вошёл(а) в комнату
[12:54:39] komar вошёл(а) в комнату
[13:12:19] <ermine> хех, опам переставляет уже поставленные пакеты, если ставишь пакет, который является их опциональным депеденсом
[13:12:47] <ermine> поставила lablgtk - оно переставило всё что могло найти - lwt, ocamlnet, чота там еще
[13:14:43] <f[x]> ты довольна этим али нет?
[13:17:13] <ermine> этой фичой - вполне
[13:17:38] <ermine> но пока багрепоты не фиксят
[13:17:49] <ermine> надо чоль почитать более подробно доку
[13:19:49] Kakadu вошёл(а) в комнату
[13:37:30] <komar> Отговорите тыкать в скалу.
[13:40:41] <ermine> скала рулез
[13:41:00] <ermine> жаль что на андроиде она не родная
[13:41:03] <komar> Отговорила.
[13:41:08] <komar> Спасибо.
[13:41:40] <ermine> андроид юзать?
[13:41:59] <Typhon> komar: это с++11 так назвали?
[13:55:02] Typhon вышел(а) из комнаты: Replaced by new connection
[13:55:12] Typhon вошёл(а) в комнату
[13:59:13] komar вышел(а) из комнаты: Logged out
[14:05:07] f[x] вышел(а) из комнаты
[14:07:26] komar вошёл(а) в комнату
[14:07:34] komar вышел(а) из комнаты: Logged out
[14:18:03] komar вошёл(а) в комнату
[14:19:17] komar вышел(а) из комнаты: Logged out
[14:24:26] komar вошёл(а) в комнату
[15:01:13] akovbovich вошёл(а) в комнату
[15:04:01] komar вышел(а) из комнаты: Logged out
[15:04:34] strobegen вошёл(а) в комнату
[15:07:40] komar вошёл(а) в комнату
[15:15:45] akovbovich вышел(а) из комнаты
[15:17:47] strobegen вышел(а) из комнаты: Replaced by new connection
[15:17:48] strobegen вошёл(а) в комнату
[15:19:48] Typhon вышел(а) из комнаты: Replaced by new connection
[15:19:58] Typhon вошёл(а) в комнату
[15:22:10] Typhon вышел(а) из комнаты: Replaced by new connection
[15:22:20] Typhon вошёл(а) в комнату
[15:36:59] strobegen вышел(а) из комнаты
[15:45:42] <gds> кстати вот, может кто-нибудь из вас поможет с красотой?  http://gds.psto.net/tsigii
[15:52:43] ermine прочитала первое слово...
[15:54:02] <gds> ermine: не ссы, ты тоже чоткий пасан.
[15:58:03] <ermine> gds: я задачку не поняла, начиная с узла, из которого не выходит ребер
[15:58:39] <ermine> а вообще подумалось что надо определять является ли граф плоским или нет
[15:58:58] <ermine> (в доку гугла не смотрела, картинку не видела)
[16:00:13] <ermine> плоский граф, емнип - это граф, который можно представить в виде выпуклого многоукольника
[16:00:27] <gds> ну, в любом ациклическом графе есть узлы, из которых ничего не выходит.
[16:01:15] <ermine> ну и хрен с узлами, зачем они вообще нужны?
[16:08:58] <gds> в них -- данные.  Эти данные надо менять до какого-то предела вверх по стрелкам.
[16:15:23] <aleksey> gdтопологическая сортировка тебе нужна
[16:16:07] <ermine> gds: а мосты кенинсберга ты видел?
[16:16:13] aleksey вышел(а) из комнаты
[16:16:35] aleksey вошёл(а) в комнату
[16:17:35] <aleksey> gds: просто запускаешь dfs пока не останется непосещённых вершин, и порядок выхода из вершин и будет тем что ты ищешь
[16:17:59] <ermine> опять он про dfs
[16:18:54] <aleksey> ermine: я не виноват, что куча алгоритмов на графах базируются на dfs :)
[16:19:27] <ermine> aleksey: кормен?
[16:19:51] <aleksey> ermine: кормен это человек
[16:20:23] <gds> aleksey: топологическая сортировка -- не совсем то: представь, что есть куча вершин, из которых не выходят стрелки.  Топологическая сортировка поместит их в конец, все.  Но мне не нужно обходить их всех, если хочу пораскрашивать граф от одной, конкретно заданной вершины.
[16:20:37] <ADEpt> aleksey: человек и фолиант :)
[16:21:01] <aleksey> gds: тогда сначала выкинь лишнее
[16:21:19] <ermine> aleksey: ну ясно что не окасаки
[16:21:22] <aleksey> gds: тоже с помощью dfs, только по инвертированным рёбрам
[16:22:11] <gds> aleksey: про dfs -- интересно, но непонятно.  вот, будет у меня (ты же картинку видел?) пути ZGEBA ZGBA ZGCA ZHCA ZHDA ZJIFDA.  Как из них получить упорядочивание вершин в нужном мне виде?
[16:22:21] <aleksey> gds: или вообще инвертируй рёбра, запусти dfs из Z, порядок выхода из вершин и даст ответ задом-наперёд
[16:22:49] <ermine> ADEpt: а пчу вы не сманили aleksey в js за двойное бабло?
[16:24:56] <ADEpt> ermine: он не хочет
[16:25:20] <ADEpt> aleksey: ты ж не хочешь?
[16:25:35] <aleksey> в лондон переезжать не хочу
[16:25:46] <gds> счастливые вы.  для вас js это janestreet.
[16:25:54] <ADEpt> :)))
[16:26:01] <ermine> ADEpt: предложили мало...
[16:26:29] <ermine> не заинтересовали
[16:33:05] <gds> aleksey: объясни тупому, как из набора путей обхода получить нужную последовательность?
[16:34:39] <Kakadu> Ты не можешь патологическую сортировку написать?
[16:35:09] <gds> Kakadu: могу, но "топологическая сортировка -- не совсем то: представь, что есть куча вершин, из которых не выходят стрелки.  Топологическая сортировка поместит их в конец, все.  Но мне не нужно обходить их всех, если хочу пораскрашивать граф от одной, конкретно заданной вершины."
[16:35:23] <gds> это я понял уже потом, когда, как обещал в псачике, взял бамажку и ручку.
[16:35:27] <aleksey> обозначим вход в вершину >A, а выход A>, тогда dfs по тому графу будет таким:
>Z >G >E >B >A A> B> E> >C C> G> >H >D D> >J >I >F F> I> J> Z>
[16:36:23] <aleksey> оставим только выходы, и запишем в обратном порядке: Z J I F D G C E B A
[16:36:53] <aleksey> H пропустил
[16:37:31] <gds> а почему в A входим только один раз -- как-то помечаем вершины в процессе?
[16:37:47] <aleksey> dfs только один раз посещает каждую вершину
[16:39:09] <aleksey> dfs v =
  used.(v) <- true
  foreach u, (v, u) \in E
     if not used.(u)
     then dfs u
  add(v)
[16:41:14] <gds> ага!  понял.
вход и выход в вершину v -- соответственно, вход и выход в dfs v, так?
[16:42:04] <aleksey> ага
[16:48:12] <gds> aleksey: благодарю за помощь!
наверное, на моих графах сработает за разумное время.
но ещё интересно, можно ли модифицировать этот алгоритм, если в процессе обхода стало понятно, что дальше вершин G H D идти не надо, то есть, посещать E C A B не обязательно?  Сходу думается, что каждую вершину, для которой решили, что "дальше не надо", надо запоминать, а потом, при прогулке по вершинам, смотреть, если все дети вершины есть в "дальше не надо", то вершину пропускать.
Но это не очень хорошо для моих случаев, так как часто будет так, что нужно от вершины идти на пару уровней вверх, не больше.
[16:49:05] strobegen вошёл(а) в комнату
[16:49:57] <aleksey> опо для любых графов, которые в память влезли, сработает быстро :)
[16:50:47] <aleksey> оно ж за время пропорциональное размеру графа работает
[16:50:59] <aleksey> а почему не надо дальше GHD идти?
[16:53:29] <gds> процедура обработки вершины у меня долгая, поэтому для некоторых вершин, например, для G H D (но тут зависит от того, как поменялось Z), я решаю, что значения в этих вершинах не изменились, поэтому идти вверх и менять там не нужно.
[16:54:01] <aleksey> тогда просто в dfs не надо из них ходить по их рёбрам
[16:56:45] <gds> проблема в том, что для того, чтобы узнать значение в D (и понять, что D -> A не нужно), мне нужно иметь обновлённые значения в H Z F, а dfs как раз для того и нужен, чтобы определить, что для вычисления значения в D нужно пройти H F I J.
[16:57:14] <gds> если окажется, что я "сам не знаю, чего хочу" -- так и скажи, и не трать время на меня.
[16:57:17] <aleksey> а, тогда в лоб проверять изменилось ли что-то хоть у одного потомка
[16:59:50] <aleksey> хотя если граф здоровый, а изменяется чуть-чуть, то можно лучше
[17:00:00] <gds> но если начну сверху, с A, то буду по всему графу бегать, не очень ок.
[17:00:23] <gds> да, обычно меняется чуть-чуть.  А как можно лучше?
[17:04:10] <aleksey> помечаешь Z, вершины всё так же рассматриваешь в порядке топологической сортировки, но обрабатываешь только помеченные, если в верщине произошло изменение, то помечаешь всех предков, а с текущей вершины пометку убераешь.  как только помеченных вершин стало 0, дальше работать не надо
[17:06:51] strobegen вышел(а) из комнаты
[17:10:10] <gds> aleksey: благодарю!  Алгоритм идеален для моих применений.  Не знаю, буду ли это выбрасывать в опенсорс, но на всякий случай впишу тебя в "авторы идеи".
[17:10:45] <aleksey> gds: я не автор топологической сортировки :)
[17:11:43] <gds> ты применил её и "пометки" из последнего сообщения к моей проблеме, этого достаточно.
[17:14:17] strobegen вошёл(а) в комнату
[17:17:41] <aleksey> по любому это уже было 10 раз придумано :)
[17:25:49] zinid вышел(а) из комнаты
[17:40:45] Sun][ вышел(а) из комнаты
[17:52:09] komar вышел(а) из комнаты: Logged out
[18:00:36] Kakadu вышел(а) из комнаты
[18:13:34] komar вошёл(а) в комнату
[18:31:30] strobegen вышел(а) из комнаты
[18:37:51] strobegen вошёл(а) в комнату
[18:40:50] f[x] вошёл(а) в комнату
[18:55:53] strobegen вышел(а) из комнаты
[19:00:32] strobegen вошёл(а) в комнату
[19:46:02] Sun][ вошёл(а) в комнату
[20:02:50] f[x] вышел(а) из комнаты
[20:03:14] Typhon вышел(а) из комнаты
[20:14:46] komar вышел(а) из комнаты: Logged out
[20:15:38] strobegen вышел(а) из комнаты
[20:32:18] strobegen вошёл(а) в комнату
[20:37:37] Sun][ вышел(а) из комнаты
[20:38:54] Sun][ вошёл(а) в комнату
[20:42:48] f[x] вошёл(а) в комнату
[20:57:22] f[x] вышел(а) из комнаты
[21:03:11] f[x] вошёл(а) в комнату
[21:03:22] <f[x]> а вы это видели -> https://github.com/lucasaiu/ocaml
[21:07:50] <f[x]> ох ты ж, не заметил сразу - forked from camlunity/ocaml-patches
[21:15:33] f[x] вышел(а) из комнаты
[21:17:10] <ermine> что будем с этим делать?
[21:36:56] Kakadu вошёл(а) в комнату
[22:21:21] komar вошёл(а) в комнату
[22:31:23] ermine вышел(а) из комнаты
[22:32:22] komar вышел(а) из комнаты: Replaced by new connection
[22:32:26] komar вошёл(а) в комнату