Телеграмм чат группы clojure_ru страница 5049

parrot.ru

Рейтинг популярных групп и каналов

В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

Clojure — русскоговорящее сообщество

567 membersпожаловаться на группу

2020 February 07

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

Я когда думал об этой задаче тоже сначала пошел в сторону алгоритмов типа твоего, с явным запоминанием выбранного/оставшегося, но когда мне подсказали первый, я помню впечатлился и реализовал по нему. Собственно, в применении к случайному графу: мы знаем наши вершины, комбинаторно генерируем ленивую последовательность всех возможных ребер, ее длину мы знаем заранее и можем взять равномерно рандомно сколько нам надо - дешево, потоково и сердито )

источник

11:34пожаловаться #1

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

Я когда думал об этой задаче тоже сначала пошел в сторону алгоритмов типа твоего, с явным запоминанием выбранного/оставшегося, но когда мне подсказали первый, я помню впечатлился и реализовал по нему. Собственно, в применении к случайному графу: мы знаем наши вершины, комбинаторно генерируем ленивую последовательность всех возможных ребер, ее длину мы знаем заранее и можем взять равномерно рандомно сколько нам надо - дешево, потоково и сердито )

Я помню, что там есть какая-то магическая константа на вероятность ребра. Если вероятность меньше, то будет лес (почти наверное), если больше, то связный, если ровно, то какое-то интересное поведение.

источник

11:42пожаловаться #2

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

это уже если смотреть в сторону неравномерного распределения и неравных вероятностей ребер.

источник

11:43пожаловаться #3

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

это уже если смотреть в сторону неравномерного распределения и неравных вероятностей ребер.

Вероятности равные, но у нас не стоит задачи набрать k ребер

источник

11:45пожаловаться #4

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

а, понятно. не думал в такой постановке

источник

11:46пожаловаться #5

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

Нашел, у Райгородского про связность случайных графов.

(ln n)/n - магическая "константа". n - число вершин в графе.

источник

11:48пожаловаться #6

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

Ну это я так, если вдруг пригодится что-то странное с графами делать)

источник

11:49пожаловаться #7

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

Да, интересно, спасибо. Фамилия Райгородского дополнительно мотивирует почитать )

источник

11:50пожаловаться #8

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

Вопрос к опытным писателям transducer'ов: как бы вы запрограммировали (на Clojure) функцию выбора n случайных элементов из последовательности? Равномерное распределение. Последовательность конечная, ее длина считается известной изначально.

Кстати, вдогонку - условие конечности последовательности необходимо для содержательной постановки задачи как таковой. Без него мы придем к тому самому красивому парадоксу двух конвертов, который меня впечатлил в свое время, и который я не сразу понял как разрешить )

источник

12:20пожаловаться #9

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

Оказывается, задача набрать k элементов из n, это reservoir sampling

источник

12:30пожаловаться #10

a

akater in Clojure — русскоговорящее сообщество

Не понял при чем здесь трансдьюсеры, но вот как - с вероятностью n/k берем первый элемент, ииии..... все ))) пришли к той же задаче на остатке элементов, рекурсия )

Да. Я как раз к тому, что чтобы эффективно записать это решение в функциональном стиле, видимо, неизбежно нужно захватывать переменную в одном из внутренних трансдьюсеров (а именно, счетчик в take).

Рассматривались ли варианты допускать подобное в Clojure? Может, к этому есть прагматические претензии? Не считается ли это «недостаточно функциональный стиль»?

(Изначально забыл сказать, что «выборка без повторения», но все верно поняли.)

источник

12:33пожаловаться #11

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

Вы намекаете что в данном случае у нас получается свертка в качестве ядра которой не чистая функция? И как оно будет жить если применять трансдьюсеры?

источник

12:35пожаловаться #12

MB

Mikhail Borisov in Clojure — русскоговорящее сообщество

https://en.m.wikipedia.org/wiki/Reservoir_sampling

Reservoir sampling

Reservoir sampling is a family of randomized algorithms for choosing a simple random sample without replacement of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large to fit all n items into main memory. The population is revealed to the algorithm over time, and the algorithm cannot look back at previous items. At any point, the current state of the algorithm must permit extraction of a simple random sample without replacement of size k over the part of the population seen so far.

источник

12:38пожаловаться #13

ST

Sergey Trofimov in Clojure — русскоговорящее сообщество

Да. Я как раз к тому, что чтобы эффективно записать это решение в функциональном стиле, видимо, неизбежно нужно захватывать переменную в одном из внутренних трансдьюсеров (а именно, счетчик в take).

Рассматривались ли варианты допускать подобное в Clojure? Может, к этому есть прагматические претензии? Не считается ли это «недостаточно функциональный стиль»?

(Изначально забыл сказать, что «выборка без повторения», но все верно поняли.)

вот это является решением («переменная» внутри distinct)?

(->> 
    (partial rand-int 100)
    (repeatedly)
    (distinct)
    (take 10))
=> (56 17 47 26 65 86 92 4 0 36)

источник

12:44пожаловаться #14

ST

Sergey Trofimov in Clojure — русскоговорящее сообщество

Да. Я как раз к тому, что чтобы эффективно записать это решение в функциональном стиле, видимо, неизбежно нужно захватывать переменную в одном из внутренних трансдьюсеров (а именно, счетчик в take).

Рассматривались ли варианты допускать подобное в Clojure? Может, к этому есть прагматические претензии? Не считается ли это «недостаточно функциональный стиль»?

(Изначально забыл сказать, что «выборка без повторения», но все верно поняли.)

или вот это (есть изначальная конечная последовательность без повторений)?

(->> 
    (range 100)
    (shuffle)
    (take 10))
=> (14 31 71 78 76 40 92 16 2 98)

источник

12:46пожаловаться #15

ST

Sergey Trofimov in Clojure — русскоговорящее сообщество

Да. Я как раз к тому, что чтобы эффективно записать это решение в функциональном стиле, видимо, неизбежно нужно захватывать переменную в одном из внутренних трансдьюсеров (а именно, счетчик в take).

Рассматривались ли варианты допускать подобное в Clojure? Может, к этому есть прагматические претензии? Не считается ли это «недостаточно функциональный стиль»?

(Изначально забыл сказать, что «выборка без повторения», но все верно поняли.)

«Рассматривались ли варианты допускать подобное в Clojure?»
полно такого в кложе, если я что-то правильно понял

источник

12:47пожаловаться #16

a

akater in Clojure — русскоговорящее сообщество

Вы намекаете что в данном случае у нас получается свертка в качестве ядра которой не чистая функция? И как оно будет жить если применять трансдьюсеры?

Я мало знаком с трансдьюсерами, если этот счетчик в принципе невозможно захватить, то вопрос отпадает.

Это параметр nv, https://github.com/clojure/clojure/blob/ee3553362de9bc3bfd18d4b0b3381e3483c2a34c/src/clj/clojure/core.clj#L2861 как я понимаю.

Решение в функциональном стиле было бы какое-то такое (на несуществующем лиспе):


(take n
      (mask 
       (map (lambda (left-in-seq)
       (probability≥ (/ left-to-take left-in-seq)
       (random 0 1)))
     (reverse (iota (length seq))))
       seq))

NB: Все-таки от того, что в функции есть внутренний параметр, который не возвращается, она не перестает быть чистой же.

clojure/clojure

The Clojure programming language. Contribute to clojure/clojure development by creating an account on GitHub.

источник

12:52пожаловаться #17

AI

Andrey Ivanov in Clojure — русскоговорящее сообщество

Она перестает быть чистой из-за рандома и отсутствия ссылочной прозрачности. Но в нечистых ФЯ типа Кложи это не редкость, как уже писали выше

источник

12:54пожаловаться #18

ST

Sergey Trofimov in Clojure — русскоговорящее сообщество

Я мало знаком с трансдьюсерами, если этот счетчик в принципе невозможно захватить, то вопрос отпадает.

Это параметр nv, https://github.com/clojure/clojure/blob/ee3553362de9bc3bfd18d4b0b3381e3483c2a34c/src/clj/clojure/core.clj#L2861 как я понимаю.

Решение в функциональном стиле было бы какое-то такое (на несуществующем лиспе):


(take n
      (mask 
       (map (lambda (left-in-seq)
       (probability≥ (/ left-to-take left-in-seq)
       (random 0 1)))
     (reverse (iota (length seq))))
       seq))

NB: Все-таки от того, что в функции есть внутренний параметр, который не возвращается, она не перестает быть чистой же.

clojure/clojure

The Clojure programming language. Contribute to clojure/clojure development by creating an account on GitHub.

трансдьюсеры могут иметь внутреннее состояние, и это нормально

источник

12:54пожаловаться #19

a

akater in Clojure — русскоговорящее сообщество

Sergey Trofimov

трансдьюсеры могут иметь внутреннее состояние, и это нормально

А захватывать это внутренее состояние извне считается неприлично?

(В Ваше последнее решение я пока не въехал.)

источник

12:55пожаловаться #20