а как в C# убрать из списка (List) элементы, которые есть в другом спи
list1 = list1.Except(list2).ToList;
спасибо!
а как рандомно из списка брать значения, ну или перемешать список?
а как рандомно из списка брать значения, ну или перемешать список?
var r = new Random(seed);
// перемешать
list = list.OrderBy(x=>r.Next.ToList;
// выбрать N штук с возвращением
var list2 = Enumerable.Range(0, N)
.Select(x=>list[r.Next(list.Count)])
.ToList;
Stack overflow - это примерно как "ответы на маил.ру", как я убедился на своем опыте
Я лучше тут спрошу
Я лучше тут спрошу
Stack overflow - это примерно как "ответы на маил.ру", как я убедился на своем опытеУроки логики на форум.плакал.
Я лучше тут спрошу
Stack overflow - это примерно как "ответы на маил.ру", как я убедился на своем опытеЛол.
Я лучше тут спрошу
Особенно забавно с учётом того, что по ссылке хоррора, помимо правильного решения, ещё и разжёвано, почему вот так
list = list.OrderBy(x=>r.Next.ToList;
делать не надо.
по ссылке буквоедство. Для случайной выборки или тасовки bias, происходящий из-за System.Random, в большинстве задач не играет практической роли. Нас же спросили "как бы это сделать в C# со списком", а не "какой алгоритм вы посоветуете для быстрого и криптопригодного шафла".
Вроде, автора поста на SO возмущён тем, что вызов одного и того же шафла на System.Random несколько раз подряд приводит к одинаковым последовательностям. Это, однако, объясняется лишь тем, что дефолтный сид — текущее время в миллисекундах. Это мешает лишь в определённых условиях, которые касаются не всех (например, два коротких шафла вызываются подряд, или два не обязательно коротких — одновременно в разных потоках). И это очень легко исправляется: DateTime.Now.Ticks в качестве сида и идентификатор потока, если многопоточность/многозадачность.
Особенно странна претензия к недостаточной случайности System.Random в задаче перемешивания 75 чисел. Казалось бы, недостаточно ровная статистика должна вылезать на больших массивах. Кстати, делать выборку из больших массивов, не помещающихся в память, вообще лучше не так. Не тасовкой Кнута и не рандомной сортировкой.
Вроде, автора поста на SO возмущён тем, что вызов одного и того же шафла на System.Random несколько раз подряд приводит к одинаковым последовательностям. Это, однако, объясняется лишь тем, что дефолтный сид — текущее время в миллисекундах. Это мешает лишь в определённых условиях, которые касаются не всех (например, два коротких шафла вызываются подряд, или два не обязательно коротких — одновременно в разных потоках). И это очень легко исправляется: DateTime.Now.Ticks в качестве сида и идентификатор потока, если многопоточность/многозадачность.
Особенно странна претензия к недостаточной случайности System.Random в задаче перемешивания 75 чисел. Казалось бы, недостаточно ровная статистика должна вылезать на больших массивах. Кстати, делать выборку из больших массивов, не помещающихся в память, вообще лучше не так. Не тасовкой Кнута и не рандомной сортировкой.
по ссылке буквоедствоударим буквоедством по буквоедству!
По ссылке перечислены как минимум несколько проблем:
- количество разных сидов для псевдослучайных последовательностей существенно меньше, чем число возможных перестановок
- даже при использовании "честного" генератора случайных чисел не все перестановки равновероятны
- O(n ln n) вместо O(n)
- количество разных сидов для псевдослучайных последовательностей существенно меньше, чем число возможных перестановок
- даже при использовании "честного" генератора случайных чисел не все перестановки равновероятны
- O(n ln n) вместо O(n)
> количество разных сидов для псевдослучайных последовательностей существенно меньше, чем число возможных перестановок
Это очень огорчительно. Получится только два миллиарда псевдослучайных последовательностей. Эта проблема, кстати, тоже решается примитивным образом (например, случайным переназначением сида).
> даже при использовании "честного" генератора случайных чисел не все перестановки равновероятны
И что? Есть хоть малейшие основания полагать, что автора вопроса это беспокоит?
> O(n ln n) вместо O(n)
Логарифм 75 равен шести, емнип. Как я уже сказал, из реально больших массивов при отсутствии жёстких требований по случайности выборки всё равно надо делать не топN поверх шаффла Кнута, а шаффл поверх случайной последовательной выборки.
Это очень огорчительно. Получится только два миллиарда псевдослучайных последовательностей. Эта проблема, кстати, тоже решается примитивным образом (например, случайным переназначением сида).
> даже при использовании "честного" генератора случайных чисел не все перестановки равновероятны
И что? Есть хоть малейшие основания полагать, что автора вопроса это беспокоит?
> O(n ln n) вместо O(n)
Логарифм 75 равен шести, емнип. Как я уже сказал, из реально больших массивов при отсутствии жёстких требований по случайности выборки всё равно надо делать не топN поверх шаффла Кнута, а шаффл поверх случайной последовательной выборки.
делать не надо.Многообразие методов shuffle раскладывается в следующие координаты:
- сортировка vs Fisher-Yates
- Random vs RNGCryptoServiceProvider
- создание random generator-а внутри Shuffle vs принимание в качестве параметра
list.OrderBy(x=>r.Next.ToList;
В этом коде сделан выбор в пользу "сортировки"(явно) и Random(предположительно: в природе встречается wrapper для RNGCryptoServiceProvider, предоставляющий интерфейс r.Next)
Что именно из этого делать не надо?
> - количество разных сидов для псевдослучайных последовательностей существенно меньше, чем число возможных перестановок
это общая проблема псевдослучайных генераторов и не зависит от метода shuffle. Выход: добавить еще какой-нибудь энтропии.
> - даже при использовании "честного" генератора случайных чисел не все перестановки равновероятны
имхо, Fisher-Yates хуже, чем сортировка из-за ошибок округления, которые сдвигают равновероятность. random.Next(3) даст неравномерное распределение между 0, 1, 2 в отличии от распределения результатов random.Next
> - O(n ln n) вместо O(n)
по производительности сортировка хуже
ps
имхо:
- сортировка vs Fisher-Yates . Сортировка - случайнее, Fisher-Yates - быстрее
- Random vs RNGCryptoServiceProvider. Random - быстрее, RNGCryptoServiceProvider - случайнее.
- создание random generator-а внутри Shuffle vs принимание в качестве параметра. Принимание в качестве параметра генератора безусловно лучше: и более SOLID-но, и более случайно.
Логарифм 75 равен шести, емнип.
Где ты в этом треде увидел число 75?
Как я уже сказал, из реально больших массивов при отсутствии жёстких требований по случайности выборки всё равно надо делать не топN поверх шаффла Кнута, а шаффл поверх случайной последовательной выборки.Обрати внимание, что мой пост был про часть // перемешать, и заканчивай спорить сам с собой.
имхо, Fisher-Yates хуже, чем сортировка из-за ошибок округленияОшибок округления где
Ошибок округления гдеFisher-Yates использует функцию Next(n). Данная функция отображает int (множество мощностью 2^32) в множество мощностью n. Такое отображение не равномерно при n, когда n не является степенью двойки .
Fisher-Yates использует функцию Next(n). Данная функция отображает int (множество мощностью 2^32) в множество мощностью n. Такое отображение не равномерно при n, когда n не является степенью двойки.Отображение делается с помощью modulo?
Отображение делается с помощью modulo?Математика утверждает, что равномерно разбить 2^32 на n кучек(где n не степень двойки) невозможно в независимости от алгоритма.
ps
в .net-е используется перевод int-ов в double, умножение в double-ах, округление до int-а
Математика утверждает, что равномерно разбить 2^32 на n кучек(где n не степень двойки) невозможно в независимости от алгоритма.Имея равномерный генератор на [1, N], можно соорудить равномерный генератор на [1, n], где n < N.
Без плавающей точки и округлений (но с другим нюансом).
Математика утверждает, что равномерно разбить 2^32 на n кучек(где n не степень двойки) невозможно в независимости от алгоритма.Можешь объяснить, почему "в независимости от алгоритма"?
Имея равномерный генератор на [1, N], можно соорудить равномерный генератор на [1, n], где n < N.Можно.
Минусы:
1.
или появляется еще один statefull микросервис (неудобные числа перемещаются в следующий выбор
или уменьшается пространство случайных чисел (неудобные числа drop-аются)
2. требуется математик для проверки, что при сооружении такого генератора нигде не налажали с вероятностями и независимостью
3. требуется математик для обоснования в каких случаях такой генератор может использоваться совместно:
- с исходным Random-ом
- с такими же генераторами, где n имеет другие величины
Можешь объяснить, почему "в независимости от алгоритма"?Преобразование "стабильное"(*): для одного и того же числа на входе всегда выдает одно и то же на выходе.
На входе N чисел
На выходе n кучек
Как не бейся: в часть кучек попадет N/n чисел, а в часть - N/n+1
ps
* (to All) вылетело из головы, как это называется в математике. Подскажите, пожалуйста, термин.
Преобразование "стабильное"(*): для одного и того же числа на входе всегда выдает одно и то же на выходе.На входе N чиселНа выходе n кучекКак не бейся: в часть кучек попадет N/n чисел, а в часть - N/n+1Не понимаю, почему тогда "в независимости от алгоритма", а не "в независимости от формулы". Алгоритм-то сделать можно.
Алгоритм-то сделать можно.Нельзя при заданных условиях.
Под заданными условиями понимается, что:
- алгоритм не запрашивает какие-либо внешние сервисы не указанные явно в задаче
- хранение состояния между вызовами относится к "использованию внешних сервисов" (потребуются внешние сервисы: хранение состояния, идентификация вызовов, обеспечение одновременного доступа и т.д.)
При заданных условиях нельзя.Не нужно никаких условий. Ты написал:
"Fisher-Yates использует функцию Next(n). Данная функция отображает int (множество мощностью 2^32) в множество мощностью n. Такое отображение не равномерно при n, когда n не является степенью двойки."Но при наличии функции Next можно написать Next(n). Я не вижу обоснования, почему для этого конкретного примера нельзя это сделать.
Я не вижу обоснования, почему для этого конкретного примера нельзя это сделать.и не увидишь
Но при наличии функции Next можно написать Next(n). Я не вижу обоснования, почему для этого конкретного примера нельзя это сделать.Текущая реализация Next(n) использует следующие ограничения:
- делает только один вызов Next на один вызов Next(n)
- не имеет состояния
При таких ограничениях невозможно сделать алгоритм дающий равномерное распределение.
Алгоритм возможно сделать при ослаблении ограничений на одно из следующих:
- делает неограниченное кол-во вызовов Next на один вызов Next(n)
- имеет состояние
1) пошла подгонка условий под ответ
2) доказательство-то где? "я не знаю такого способа" не является доказательством
2) доказательство-то где? "я не знаю такого способа" не является доказательством
2) доказательство-то где? "я не знаю такого способа" не является доказательствомсм. выше.
при указанных ограничениях необходимо построить "стабильный" алгоритм, который умеет 2^32 чисел раскладывать равномерно на n кучек, что невозможно.
) пошла подгонка условий под ответКакие ты предлагаешь наложить ограничения на алгоритм Next(n)?
см. выше.
при указанных ограничениях необходимо построить "стабильный" алгоритм, который умеет 2^32 чисел раскладывать равномерно на n кучек, что невозможно.
ну вот ты [опять] выдаешь какие-то рассуждения за доказательство. доказательство - это цепочка рассуждений, каждый переход должен быть чем-то обоснован. а у тебя какие-то "свои" термины и неочевидные утверждения. например
при указанных ограничениях необходимо построить "стабильный" алгоритм, который умеет 2^32 чисел раскладывать равномерно на n кучек, что невозможно.
что такое "стабильный"? и почему нету другого способа достичь желаемого, кроме как создать такой алгоритм.
Какие ты предлагаешь наложить ограничения на алгоритм Next(n)?
я не предлагаю. просто получается как-то так
1) ты говоришь: А невозможно
2) тебе говорят "схуяли" или показывают, что это не так
3) ты говоришь: я имел в виду А невозможно если Б
4) тебе говорят "схуяли" или показывают, что это не так
5) ты говоришь: вообще-то я имел в виду А невозможно если В
...
эдак того и гляди дойдет до
N) ты говоришь: вообще-то я имел в виду А невозможно если А невозможно
что такое "стабильный"? .было выше
и почему нету другого способа достичь желаемого, кроме как создать такой алгоритмлюбой код при указанных ограничениях (нет доступа к внешним сервисам) является "стабильным"
доказательство - это цепочка рассуждений, каждый переход должен быть чем-то обоснован.выше было и доказательство, и переходы, и обоснование каждого перехода
у тебя какие-то "свои" термины и неочевидные утверждения. напримерЯ не знаю алгоритма или сервиса, которые позволяет переводить набор свойств в каноническое название термина обозначающего эти свойства. Подскажи, если умеешь решать эту задачу.
я не предлагаю. просто получается как-то такПрошу прощения, что сразу не зафиксировал полный список ограничений в которых делалось утверждение о невозможности. В свою защиту отмечу, что задача о формировании полного списка ограничений алгоритмически неразрешима .
Преобразование "стабильное"(*): для одного и того же числа на входе всегда выдает одно и то же на выходе.
На входе N чисел
На выходе n кучек
Как не бейся: в часть кучек попадет N/n чисел, а в часть - N/n+1
ps
* (to All) вылетело из головы, как это называется в математике. Подскажите, пожалуйста, термин.
нам же требуется построить равномерно распределенную функцию next(n) имея равномерно распределенную next(N n<N
[мне] не очевидно, что эта задача равносильна построению детерминированной функции "На входе N чисел
На выходе n кучек" (т.е. детерминированного отображения [1,N] -> [1, n], такого чтобы у всех чисел из [1,n] было одинаковое количество праобразов).
Т.е. если бы такая функция была, построение next(n) было бы тривиально. Но в обратную сторону я перехода не вижу навскидку
детерминированной функциикод не бывает недетерминированным при условии ограничений на доступ к внешним сервисам.
код не бывает недетерминированным при условии ограничений на доступ к внешним сервисам.
мы по условию имеем недетерминированную next(N)
мы по условию имеем недетерминированную next(N)Она детерминированная. Её состояние в каждый момент определяется на основе начального значения seed-а.
Псевдослучайный ГСЧ - это детерминированный алгоритм, который делает вид, что он выдает случайные числа.
Другими словами: псевдослучайный алгоритм - это такой алгоритм, который:
- при анализе как черного ящика(рассматривается только вход и выход) ведет себя случайно,
- при анализе как белого ящика(известно внутреннее состояние и внутренняя конфигурация) - ведет себя детерминировано.
я знаю, что такое псевдослучайный ГСЧ. исходная задача была про построение next(n) через next(N) при условии, что next(N) случайная равномерно распределенная функция. предлагаю это дальше и обсуждать, а не уходить в сторону пространных отвлеченных рассуждений
"при условии ограничений на доступ к внешним сервисам." код просто не работает, т.к. у него нет ни проца, ни прочего.У процессора всегда есть доступ к коду, у кода доступа к процессору может не быть, если процессор не предоставил коду такие команды.
В частности это касается и памяти: у кода нет доступа к памяти до тех пор, пока исполнительная система не предоставила таких команд для кода.
я же специально написал, что это офтопик и даже слой поставил, который ты не поленился обратно поменять. мне не интересен этот аспект. мне стало интересно твоё утверждение о невозможности построения next(n)
еще уточню на всякий. меня интересует математический аспект невозможности построения такой next(n). я не собираюсь аппелировать к hardware и каким-либо иным "сервисам"
ЗЫ я не знаю такого способа построения next(n) и не утверждаю, что это возможно. меня просто зацепило то, что ты считаешь, что можешь это [строго] доказать. вот я и пытаюсь получить это доказательство или признание, что ты не можешь этого доказать
ЗЫ я не знаю такого способа построения next(n) и не утверждаю, что это возможно. меня просто зацепило то, что ты считаешь, что можешь это [строго] доказать. вот я и пытаюсь получить это доказательство или признание, что ты не можешь этого доказать
next(N) случайная равномерно распределенная функция. предлагаю это дальше и обсуждать.Именно это и обсуждается.
Next(n) - это композиция двух алгоритмов: одного вызова случайного алгоритма int Next и детерминированного алгоритма, который отображает int на множество n
С этим ты согласен?
Next(n) - это композиция двух алгоритмов: одного вызова случайного алгоритма int Next и детерминированного алгоритма, который отображает int на множество nС этим ты согласен?Я не согласен, ведь int Next - это уже композиция десятков алгоритмов: добавление чисел, запись числа в память, чтение числа из памяти, умножение чисел, добавление данных в стек, и так далее. Что за ерунду ты порешь? Каждый раз, когда ты ошибаешься, начинается какая-то муть с переопределением common sense в пространство, где твоя ошибка выглядит как правильное утверждение.
Next(n) - это композиция двух алгоритмов: одного вызова случайного алгоритма int Next и детерминированного алгоритма, который отображает int на множество n
требование про один вызов появилось самым последним, с ним, конечно, неинтересно. интереснее, если ограничится ограниченным сверху количеством вызовов.
Я не согласен, ведь int Next - это уже композиция десятков алгоритмов: добавление чисел, запись числа в память, чтение числа из памяти, умножение чисел, добавление данных в стек, и так далее.Какая разница как устроена Next если речь идет об устройстве Next(n)?
Какая разница как устроена Next если речь идет об устройстве Next(n)?Так Next(n) тоже устроен как композиция десятков таких примитивных алгоритмов. А изначально речь шла о том, что
Математика утверждает, что равномерно разбить 2^32 на n кучек(где n не степень двойки) невозможно в независимости от алгоритма.А это утверждение неверно. Никаких "заданных условий" тут нет, и не надо их вводить, чтобы превратить это неверное утверждение в верное.
неинтересно. интереснее, если ограничится ограниченным сверху количеством вызовов.имхо, не получится.
При таком варианте задача сводится к построению детерминированного алгоритма, который раскладывает число длиной k-бит на n-кучек. (где k = 32 * ограниченное сверху кол-во вызовов)
ps
сомневаюсь в строгости перехода от k переменного к максимальному k, но при произвольном n - этот переход не существенен
Никаких "заданных условий" тут нет, и не надо их вводить, чтобы превратить это неверное утверждение в верное.Если нет никаких заданных ограничений, то да, я был не прав и Next(n) с равномерным распределением конечно же построить можно. Для этого в Next(n) достаточно вызвать внешний сервис, который вернёт случайное число с равномерным распределением от 0..n-1.
k может делиться на n же
+ тут же есть всякие разные варианты компоновки случайных чисел - необязательно же их конкатенировать. можно получать разные распределения и не очевидно, что нельзя получить искомое
k может делиться на n жеn принимает значения от 2 до длины коллекции при использовании Fisher-Yates.
k необходимо слишком большое, чтобы хотя бы одно число из множества (1..k) делилось на n
+ тут же есть всякие разные варианты компоновки случайных чисел - необязательно же их конкатенировать. можно получать разные распределения и не очевидно, что нельзя получить искомоеСдаюсь. У меня сейчас голова опухнет от раскладывания этого на такие пространства в которых очевидно, что это невозможно.
ведь int Next - это уже композиция десятков алгоритмов:int Next - это композиция алгоритмов:
- алгоритм доступа к небольшому фиксированному куску памяти
- алгоритмы отображения int*int -> int
- алгоритм простой композиции других алгоритмов (без циклов и без рекурсий)
другой вариант представление:
- алгоритм одиночного чтения biginteger(k)
- алгоритм отображения biginteger(k)->biginteger(k)
- алгоритм одиночной записи biginteger(k)
- алгоритм отображения biginteger(k)->int
ps
Такое представление даёт возможность применять всякие автоматизированные штуки:
- доказательство инвариантов,
- доказательство конечности работы,
- измерение производительности кода без самого запуска кода
и т.д.
Каждый раз, когда ты ошибаешься, начинается какая-то муть с переопределением common sense в пространство, где твоя ошибка выглядит как правильное утверждение.Ты поступаешь точно так же, когда твой код проигрывает, ты говоришь, что еще надо написать что-то еще, например, тесты.
Или совсем без аргументов говоришь, что на "больших коммерческих проектах" (c) это работать не будет. А на самом всё прекрасно работает.
Ты поступаешь точно так же, когда твой код проигрывает, ты говоришь, что еще надо написать что-то еще, например, тесты.Я подумал и решил не писать тебе ответ на этот детский выпад. Потому что после общаться с тобой на такие темы не хочется. Ведь ты наверняка сольёшься, а потом меня будут упоминать в теме "бывший студент скинулся с ГЗ".
Далеко не каждый покемон так возбуждается на свою госпожу, как ты возбуждаешься на Шурика.
Далеко не каждый покемон так возбуждается на свою госпожу, как ты возбуждаешься на Шурика.С какой-то стороны верно, я не упускаю возможности попрактиковаться на упёртых баранах. Это развивает некоторые полезные в работе тим лида качества.
я не упускаю возможности попрактиковаться на упёртых баранах.Попрактиковаться в возбуждении на госпожу?
Попрактиковаться в возбуждении на госпожу?Конечно! Советую тебе присоединяться, пока не поздно. Скоро выйдет релиз Controllable Query и захватит мир. И тогда у тебя будет только одна госпожа, а у многих, кто не успел, их будут сотни.
Оставить комментарий
otvertka07
ске?может, уже есть такие функции где-то?