По поводу отношения между строками треугольника по модулю 2
Согласно OEIS, каждый элемент представим в виде произведения чисел Ферма a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}
От себя добавлю, что степени alpha_i соответствуют бинарному представлению k. А это значит, что для четных k бинарное представление k+1 будет отличаться от k лишь единицей в младшем разряде и a(2^n+k+1) = a(2^n+k)F_0 = 3a(2^n+k), 0 <= k <= 2^n - 2, k = 2t
Для нечетных k ясно, что отношение a(2^n+k+1)/a(2^n+k) меньше 2, поскольку в бинарном представлении alpha_n-1 у них совпадает, а числа Ферма возрастают быстрее, чем степень двойки. В силу самоподобия треугольника часто будут встречаться значения 5/3, 17/15
Отдельно отмечу, что a(2^n)/a(2^n-1) = (a(2^n-1) + 2)/a(2^n-1) в силу построения треугольника и тоже является дробным
1) Да, длинная REPEATABLE READ будет препятствовать сборке мусора. И для больших БД в версионниках классический backup - вообще долгая вещь, поэтому, насколько я в курсе, там используются инкрементальный backup и/или репликация
2) Из документации наACCESS EXCLUSIVE
Acquired by the DROP TABLE, TRUNCATE, REINDEX, CLUSTER, VACUUM FULL, and REFRESH MATERIALIZED VIEW (without CONCURRENTLY) commands. Many forms of ALTER INDEX and ALTER TABLE also acquire a lock at this level. This is also the default lock mode for LOCK TABLE statements that do not specify a mode explicitly.
Ну практически все операции - это изменения метаданных... Чтобы backup таблицы мог нормально выполняться во время ее удаления - это немного чересчур...
3) Ваша цитата - это перевод с английского той, которую я приводил. На мой взгляд, эта часть документации не очень удачна и может привести к путанице, о чем я написал. В этой цитате говорится о блокировке в режиме SHARE, а не ACCESS SHARE. Блокировка в режиме ACCESS SHARE, которая используется в pg_dump, конфликтует только с ACCESS EXCLUSIVE. Блокировка в режиме SHARE конфликтует много с чем и используется только при создании индекса.
То, что бесплатного REPEATABLE READ не бывает, соглашусь
When acquiring locks automatically for commands that reference tables, PostgreSQL always uses the least restrictive lock mode possible. LOCK TABLE provides for cases when you might need more restrictive locking. For example, suppose an application runs a transaction at the READ COMMITTED isolation level and needs to ensure that data in a table remains stable for the duration of the transaction. To achieve this you could obtain SHARE lock mode over the table before querying. This will prevent concurrent data changes and ensure subsequent reads of the table see a stable view of committed data, because SHARE lock mode conflicts with the ROW EXCLUSIVE lock acquired by writers, and your LOCK TABLE name IN SHARE MODE statement will wait until any concurrent holders of ROW EXCLUSIVE mode locks commit or roll back. Thus, once you obtain the lock, there are no uncommitted writes outstanding; furthermore none can begin until you release the lock.
To achieve a similar effect when running a transaction at the REPEATABLE READ or SERIALIZABLE isolation level, you have to execute the LOCK TABLE statement before executing any SELECT or data modification statement. A REPEATABLE READ or SERIALIZABLE transaction's view of data will be frozen when its first SELECT or data modification statement begins. A LOCK TABLE later in the transaction will still prevent concurrent writes — but it won't ensure that what the transaction reads corresponds to the latest committed values.
При беглом прочтении может сложиться впечатление (у меня сложилось), что LOCK TABLE блокирует таблицу от изменений (что в общем случае неверно). То, что для блокировки нужно указать IN SHARE MODE, а не IN ACCESS SHARE замыливается.
Сама по себе - никак не предохраняет, ни от вставки, ни от изменения, ни от удаления. Просто в этой транзакции будет видно состояние БД на момент старта транзакции
Поэтому и называется Repeatable - повторные чтения в рамках транзакции будут возвращать одинаковый результат
С точки зрения целостности все хорошо – используется уровень изоляции SET TRANSACTION ISOLATION LEVEL REPEATABLE READ. Он достаточно жесткий, т.е. работа параллельных процессов на запись во время длительного бэкапа будет парализована. Каждая таблица блокируется полностью до окончания команд COPY.
Нет, REPEATABLE READ в PG не блокирует запись, это же версионник
All statements of the current transaction can only see rows committed before the first query or data-modification statement was executed in this transaction.
Речь о воспроизводимом чтении - т.е. backup будет видеть только данные, существовавшие на момент его старта, параллельная запись в БД может выполняться
UPD. Запись в таблицу все же блокируется в ходе backup, здесь я неправ Но блокировка выполняется отдельным оператором LOCK TABLE
К сожалению, "Орел" они сворачивают. С сайта производителя ОС Astra Linux Common Edition, доступная для физических лиц, на данный момент неактуальна, не получает обновления и не лицензируется для использования юридическими лицами.
Загружаем в регистр сразу несколько пикселей, можно начать с 4-х пикселей(16 байт) в 128-битный регистр (лучше конечно, 32 байта в 256-битный, но код будет существенно длиннее). 4-й байт для каждого пикселя тоже загружаем
Теперь строим отдельно 3 регистра, содержащих только r-компоненты, g-компоненты, b-компоненты соответственно. Строить проще всего через shuffle-инструкцию - выделяем нужные байты из исходного регистра, и располагаем их в требуемых местах в выходном регистре так, чтобы каждая компонента занимала 4 байта. Это требуется для последующего вызова gather-инструкций
В 256-битные регистры загружаем 64-битные элементы массивов tr_r, t_g, t_b через gather-инструкции, используя регистры с этапа 2 как индексы
Складываем их между собой, прибавляя вектор констант с (инициализированный вне цикла), получаем 4 64-битных числа x в одном регистре
Поскольку SCALE == 8, то последняя итерация заключается в выделении определенных байтов из результата 4, выполняем его снова через shuffle, получаем 4 пикселя в 128-битном регистре.
Дополнительно нужно взять alpha-компоненту с исходного регистра 1, чтобы не потерять ее при выгрузке. Для выбора из 2-х регистров по маске тоже есть соответствующая инструкция
Выгружаем 128-битный регистр как единое целое
Как-то так. Ну и отдельно нужно обработать хвост, не кратный 4
И разумеется, проверить, что результат выполнения соответствует оригинальному коду :)
На рисунке 2 представлено распределение вариантов цепочек из N сигналов в которых существуют ряды из субрядов длиной k
Вы считаете эти комбинации, причем k означает «ровно k и не более».
Я ориентировался на подпись к рис. 2
Рис. 2. Число возможных вариантов субряда из k одинаковых сигналов, в последовательности из N значений.
и считал именно количество вариантов субрядов одинаковых сигналов длиной k, причем полагал, что субряд длиной k может являться частью субряда длиной k+1.
Дело не в том, что вы обрадовались, дело в том, что вы использовали формулы без должного обоснования. В моем комментарии сначала идут 2 абзаца с фактами.
Я вот, например, до сих пор не понимаю, применимо ли понятие цуга к данному случаю или нет. Если один цуг единичной длины — элементарное событие (выпадение орла), тогда формула Ф.6.1 должна давать 1/2 для n=1, w=1.
Если же речь идет о выпадении монеты любой стороной, тогда для цуга единичной длины Ф.6.1. должна выдать 1.
У нас же получается 1/16.
Если же цуг — это что-то совершенно другое, тогда непонятно, а применимы ли эти формулы вообще.
С формулировкой теоремы тоже неясно — эти 2 варианта не эквивалентны.
Вероятность встретить подпоследовательность из k одинаковых значений подряд в 2 раза выше, чем из вероятность встретить подпоследовательность из k орлов подряд.
Вы пишете
Вот я и заменил формулировку «серия из гербов» на «выпадения одинаковых сторон монеты подряд». С другой стороны это переводное издание и, вполне возможно, что в оригинале была другая формулировка.
Предполагаю, что это одно и то же.
Я уже вставил цитату из перевода, чтобы было ясно, что во всем абзаце речь идет именно о выпадении гербов и ошибку перевода можно исключить.
Плюс в предыдущей статье я приводил ссылку на пост из ЖЖ Орел или решка? Там автор подсчитал вероятности выпадения последовательности одинаковых значений и проверил это моделированием.
Еще раз приведу цитату оттуда
Ого, то есть получить семь орлов или решек подряд при ста подбрасываниях не только вполне вероятно, но шансов что выпадет семь или больше вообще около 54%
И еще одна цитата
Если бросать монетку не сто раз, а больше, то будет увеличиваться и вероятность получить все более длинную максимальную последовательность орлов или решек подряд. Правда, вероятность эта растет крайне медленно. Если посмотреть на графики, то видно, что даже в случае 100000 подбрасываний за шанс фифти-фифти пролезает только последовательность длиной 17.
Т.е. по-видимому, встретить последовательность длиной log2(n) или больше — порядка 50%, а не 100%. Это, конечно, не непреложная истина, но утверждение, явно заслуживающее проверки.
1. На первый взгляд, если судить по абзацу ниже (Филатов, вторая упоминающаяся работа)
один цуг единичной длины вроде должен соответствовать элементарному событию. Но если это не так, тогда применимость понятия «цуг» в нашем случае неочевидна, ее нужно исследовать отдельно. Не говоря о том, что формулы Филатова тоже нуждаются в проверке соответствия источникам.
2. Точная формулировка теоремы неясна — в первоисточнике («Парадоксы теории вероятностей» Г. Секей.) явно идет речь про последовательность гербов.
В этой статье идет другая формулировка.
При бросании монеты N раз, серия выпадения одинаковых сторон монеты подряд длины log2(N) наблюдается с вероятностью, стремящейся к 1, при N стремящемся к бесконечности.
Возможно, само утверждение верно, но у нас нет никаких оснований, ни прямых, ни косвенных, утверждать, что это теорема Эрдеша-Реньи.
Я когда увидел у Филатова О.В. формулы 6.1-6.3 и подставив туда log(2)N и увидел что сходится. Просто обрадовался.
Извините, но это подгон. Закономерность, очевидно, есть — хотя вполне возможно, что Эрдеш и Реньи не имеют к ней отношения. Но ее исследовать нужно более тщательно. Вы же торопитесь рассмотреть следствия.
«Алгоритмы. Построение и анализ.» Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Можно найти как djvu в поисковиках. Поскольку книга не бесплатная, то подобные ссылки на хабре не приветствуются, так что не могу.
Только она никак не проверяет инкремент версий, соответственно, изменение поведения Remove на ней не должно было отразиться
Есть встроенная Hashset.RemoveWhere(Predicate)
Исходя из формулы выше, не должна ломаться :)
По поводу отношения между строками треугольника по модулю 2
Согласно OEIS, каждый элемент представим в виде произведения чисел Ферма
a(2^n+k) = Product_{i=0..n-1} F_i^(alpha_i) * F_n, alpha_i in {0, 1}
От себя добавлю, что степени alpha_i соответствуют бинарному представлению k.
А это значит, что для четных k бинарное представление k+1 будет отличаться от k лишь единицей в младшем разряде и
a(2^n+k+1) = a(2^n+k)F_0 = 3a(2^n+k), 0 <= k <= 2^n - 2, k = 2t
Для нечетных k ясно, что отношение a(2^n+k+1)/a(2^n+k) меньше 2, поскольку в бинарном представлении alpha_n-1 у них совпадает, а числа Ферма возрастают быстрее, чем степень двойки. В силу самоподобия треугольника часто будут встречаться значения 5/3, 17/15
Отдельно отмечу, что a(2^n)/a(2^n-1) = (a(2^n-1) + 2)/a(2^n-1) в силу построения треугольника и тоже является дробным
Раз речь о PG, то можно упомянуть, что Repeatable Read там не позволяет фантомных чтений
https://www.postgresql.org/docs/current/transaction-iso.html
В методе 2 указателей еще
if (sum < target) нужно?1) Да, длинная REPEATABLE READ будет препятствовать сборке мусора. И для больших БД в версионниках классический backup - вообще долгая вещь, поэтому, насколько я в курсе, там используются инкрементальный backup и/или репликация
2) Из документации на
ACCESS EXCLUSIVEНу практически все операции - это изменения метаданных... Чтобы backup таблицы мог нормально выполняться во время ее удаления - это немного чересчур...
3) Ваша цитата - это перевод с английского той, которую я приводил. На мой взгляд, эта часть документации не очень удачна и может привести к путанице, о чем я написал. В этой цитате говорится о блокировке в режиме SHARE, а не ACCESS SHARE.
Блокировка в режиме ACCESS SHARE, которая используется в pg_dump, конфликтует только с ACCESS EXCLUSIVE. Блокировка в режиме SHARE конфликтует много с чем и используется только при создании индекса.
То, что бесплатного REPEATABLE READ не бывает, соглашусь
Да, вы правы, почитал https://www.postgresql.org/docs/current/explicit-locking.html. Собственно, да, в Firebird так же было, соответствует ожиданиям
Просто у LOCK TABLE есть отдельная страница в документации https://www.postgresql.org/docs/current/sql-lock.html. И вот там есть такое
При беглом прочтении может сложиться впечатление (у меня сложилось), что LOCK TABLE блокирует таблицу от изменений (что в общем случае неверно). То, что для блокировки нужно указать
IN SHARE MODE, а не IN ACCESS SHARE замыливается.Сама по себе - никак не предохраняет, ни от вставки, ни от изменения, ни от удаления. Просто в этой транзакции будет видно состояние БД на момент старта транзакции
Поэтому и называется Repeatable - повторные чтения в рамках транзакции будут возвращать одинаковый результат
Нет, REPEATABLE READ в PG не блокирует запись, это же версионник
В https://www.postgresql.org/docs/current/sql-set-transaction.html для REPEATABLE READ
Речь о воспроизводимом чтении - т.е. backup будет видеть только данные, существовавшие на момент его старта, параллельная запись в БД может выполняться
UPD. Запись в таблицу все же блокируется в ходе backup, здесь я неправ
Но блокировка выполняется отдельным оператором LOCK TABLE
К сожалению, "Орел" они сворачивают. С сайта производителя
ОС Astra Linux Common Edition, доступная для физических лиц, на данный момент неактуальна, не получает обновления и не лицензируется для использования юридическими лицами.
Загружаем в регистр сразу несколько пикселей, можно начать с 4-х пикселей(16 байт) в 128-битный регистр (лучше конечно, 32 байта в 256-битный, но код будет существенно длиннее). 4-й байт для каждого пикселя тоже загружаем
Теперь строим отдельно 3 регистра, содержащих только r-компоненты, g-компоненты, b-компоненты соответственно. Строить проще всего через shuffle-инструкцию - выделяем нужные байты из исходного регистра, и располагаем их в требуемых местах в выходном регистре так, чтобы каждая компонента занимала 4 байта. Это требуется для последующего вызова gather-инструкций
В 256-битные регистры загружаем 64-битные элементы массивов tr_r, t_g, t_b через gather-инструкции, используя регистры с этапа 2 как индексы
Складываем их между собой, прибавляя вектор констант с (инициализированный вне цикла), получаем 4 64-битных числа x в одном регистре
Поскольку SCALE == 8, то последняя итерация заключается в выделении определенных байтов из результата 4, выполняем его снова через shuffle, получаем 4 пикселя в 128-битном регистре.
Дополнительно нужно взять alpha-компоненту с исходного регистра 1, чтобы не потерять ее при выгрузке. Для выбора из 2-х регистров по маске тоже есть соответствующая инструкция
Выгружаем 128-битный регистр как единое целое
Как-то так. Ну и отдельно нужно обработать хвост, не кратный 4
И разумеется, проверить, что результат выполнения соответствует оригинальному коду :)
В тексте
Вы считаете эти комбинации, причем k означает «ровно k и не более».
Я ориентировался на подпись к рис. 2
и считал именно количество вариантов субрядов одинаковых сигналов длиной k, причем полагал, что субряд длиной k может являться частью субряда длиной k+1.
Лучше добавить k >= N/2 к условию k < N в формуле Pn(k) — так будет наглядней.
Я так понял, что подпоследовательности длины 3 включают в себя подпоследовательности длины 2.
Я вот, например, до сих пор не понимаю, применимо ли понятие цуга к данному случаю или нет. Если один цуг единичной длины — элементарное событие (выпадение орла), тогда формула Ф.6.1 должна давать 1/2 для n=1, w=1.
Если же речь идет о выпадении монеты любой стороной, тогда для цуга единичной длины Ф.6.1. должна выдать 1.
У нас же получается 1/16.
Если же цуг — это что-то совершенно другое, тогда непонятно, а применимы ли эти формулы вообще.
С формулировкой теоремы тоже неясно — эти 2 варианта не эквивалентны.
Вероятность встретить подпоследовательность из k одинаковых значений подряд в 2 раза выше, чем из вероятность встретить подпоследовательность из k орлов подряд.
Вы пишете
Я уже вставил цитату из перевода, чтобы было ясно, что во всем абзаце речь идет именно о выпадении гербов и ошибку перевода можно исключить.
Плюс в предыдущей статье я приводил ссылку на пост из ЖЖ Орел или решка? Там автор подсчитал вероятности выпадения последовательности одинаковых значений и проверил это моделированием.
Еще раз приведу цитату оттуда
И еще одна цитата
Т.е. по-видимому, встретить последовательность длиной log2(n) или больше — порядка 50%, а не 100%. Это, конечно, не непреложная истина, но утверждение, явно заслуживающее проверки.
Итак,
000 — 2*
001 — 1
010 — 0
011 — 1
100 — 1
101 — 0
110 — 1
111 — 2*
Итого 8
*В последовательностях 000 и 111 — 2 подпоследовательности длины 2 одинаковых значений.
В таблице вижу 4.
один цуг единичной длины вроде должен соответствовать элементарному событию. Но если это не так, тогда применимость понятия «цуг» в нашем случае неочевидна, ее нужно исследовать отдельно. Не говоря о том, что формулы Филатова тоже нуждаются в проверке соответствия источникам.
2. Точная формулировка теоремы неясна — в первоисточнике («Парадоксы теории вероятностей» Г. Секей.) явно идет речь про последовательность гербов.
В этой статье идет другая формулировка.
Возможно, само утверждение верно, но у нас нет никаких оснований, ни прямых, ни косвенных, утверждать, что это теорема Эрдеша-Реньи.
Извините, но это подгон. Закономерность, очевидно, есть — хотя вполне возможно, что Эрдеш и Реньи не имеют к ней отношения. Но ее исследовать нужно более тщательно. Вы же торопитесь рассмотреть следствия.