Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2      [все]
 Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Как известно, в .NET есть строки, в том числе одна пустая.
Сколько их всего?
Как известно, максимальный размер строки = 2 гб, или 1 073 741 823 символов в кодировке utf-16, последняя в свою очередь может закодировать 1 112 064 символов.
Символ может быть закодирован 2 или 4 байтами.
Если бы все помещались в 2 байта, то все просто, то все просто - геометрическая програссия
65536*(1-65536^1 073 741 823)/(1-65536)
Но есть и 4 байта, тогда строка, скажем из 10 байт, может быть представлена так
22222 - 63488(1-63488^5)/(1-63488)
2422 - 63488 * 1048576 * 63488 * 63488
244 - 63488 * 1048576 * 1048576
4222 - 1048576 * 63488 * 63488 * 63488
442 - 1048576 * 1048576 * 63488
Как же быть?
14 авг 19, 10:36    [21948890]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Ничего не понял что считаем. Сколько уникальных строк можно сформировать в .NET ?

Если так, то 65536 тут не уместно, т.к. в UTF-16 есть неиспользованные коды

В общем случае можно смело ответить дофига, т.к. 655361 073 741 823 = 217 179 869 168 ~= 105 153 960 750
Дальше можно не считать, т.к. это уже мелочи по сравнению с этим числом.
14 авг 19, 10:48    [21948910]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
KreatorXXI
Member

Откуда: Москва
Сообщений: 780
ЕвгенийВ,

тут .Net наверно не причём. В utf-16 для символа строго два байта. Переменная длина в utf-8. А что вообще надо.
14 авг 19, 10:52    [21948914]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
KreatorXXI
В utf-16 для символа строго два байта.

Не строго, есть 4-хбайтные, т.к. в юникоде на сегодня более миллиона символов, что никак не входит в 65536 (216).
14 авг 19, 11:54    [21948997]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
KreatorXXI
Member

Откуда: Москва
Сообщений: 780
Dima T
KreatorXXI
В utf-16 для символа строго два байта.

Не строго, есть 4-хбайтные, т.к. в юникоде на сегодня более миллиона символов, что никак не входит в 65536 (216).

В Википедии вот так:
Символы же в диапазоне 10000..10FFFF (больше 16 бит) кодируются по следующей схеме:
Из кода символа вычитается 10000. В результате получится значение от нуля до FFFFF, которое помещается в разрядную сетку 20 бит.
Старшие 10 бит (число в диапазоне 0000..03FF) суммируются с D800, и результат идёт в ведущее (первое) слово, которое входит в диапазон D800..DBFF.
Младшие 10 бит (тоже число в диапазоне 0000..03FF) суммируются с DC00, и результат идёт в последующее (второе) слово, которое входит в диапазон DC00..DFFF.

Я так понял, хитро кодируются. В принципе может это и не важно. Сейчас utf-8 рулит.
14 авг 19, 12:05    [21949021]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
ЕвгенийВ, тема топика - криптография? Какая решается задача - непонятно.

Несмотря на действующее ограничение в 2Гб текстовые данные все равно обрабатываются
в любом размере. Есть лог-файлы гораздо больше 2Гб и как-то с ними мы умудряемся работать.

Поэтому если надо - можно пренебрегать этим ограничением. Но изначально надо поставить задачу.
14 авг 19, 12:33    [21949092]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Dima T

Если так, то 65536 тут не уместно, т.к. в UTF-16 есть неиспользованные коды

Не используемые это какие?
14 авг 19, 12:44    [21949112]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
ЕвгенийВ
Dima T
Если так, то 65536 тут не уместно, т.к. в UTF-16 есть неиспользованные коды

Не используемые это какие?

Вот таблица юникода, полистай, там есть пустые клетки
14 авг 19, 13:02    [21949142]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Dima T
ЕвгенийВ
пропущено...

Не используемые это какие?

Вот таблица юникода, полистай, там есть пустые клетки

1. Есть незаполненные значения, скажем выделили какому нибудь алфавиту диапазон из 100 символов, а в нем только 90, но это будут валидные значения.
2. Есть повторяющиеся символы.
3. Есть неправильно сформированные строки.
msdn
Обратите внимание, что String , поскольку экземпляр состоит из последовательной коллекции единиц кода UTF-16, можно String создать объект, который не является правильно сформированной строкой в Юникоде. Например, можно создать строку с младшим суррогатом без соответствующего старшего символа-заместителя. Хотя некоторые методы, такие как методы кодирования и декодирования объектов в System.Text пространстве имен, могут выполнять проверки, чтобы гарантировать, что строки имеют правильный формат, String члены класса не гарантируют, что строка имеет правильный формат.

Нужны все строки всех строк, правильных, повторяющихся и не заполненных, за исключением 3 пункта.
14 авг 19, 15:08    [21949341]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9288
KreatorXXI
В utf-16 для символа строго два байта
Для кодовой точки, мопвашуять, для кодовой точки.
Символы (глифы) состоят из одной или нескольких кодовых точек и этот факт не зависит от способа кодирования.
14 авг 19, 17:04    [21949466]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
KreatorXXI
Member

Откуда: Москва
Сообщений: 780
Basil A. Sidorov,

Вы пример какой-нибудь приведите. А то непонятно.
14 авг 19, 17:46    [21949512]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
KreatorXXI
Member

Откуда: Москва
Сообщений: 780
KreatorXXI,

снимается вопрос. Есть символы из двух двухбайтовых слов, т.н. суррогатные пары.
14 авг 19, 17:54    [21949520]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
KreatorXXI
Member

Откуда: Москва
Сообщений: 780
ЕвгенийВ
Нужны все строки всех строк, правильных, повторяющихся и не заполненных, за исключением 3 пункта.


На Википедии (https://ru.wikipedia.org/wiki/UTF-16) есть пример функции по декодированию. В ней зашито определение недопустимых диапазонов. Достаточно всё просто. Можно этим воспользоваться.
14 авг 19, 18:02    [21949525]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
Вроде в Unicode символы могут быть составные.

Например буква отдельно и аксент марки отдельно. Тогда, наверное, их кол-во врят ли ограничено (насколько помню, древне греческие буквы до 4 разных (или больше?) акцент марков в написании могут иметь).

Но давно с этим разбирался. И в то время, полноценно Unicode почти никто не поддерживал
14 авг 19, 18:03    [21949526]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
ЕвгенийВ
Нужны все строки всех строк, правильных, повторяющихся и не заполненных, за исключением 3 пункта.

Зачем? По пьяне поспорили кто точнее посчитает?
14 авг 19, 20:26    [21949607]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9288
KreatorXXI
Вы пример какой-нибудь приведите. А то непонятно.
"Cyrilic letter yo" - представлена как отдельной кодовой точкой, так и парой - "Cyrilic letter e" и акцентирующий код (диакритический знак). Второй пример - "иван-краткий".
Это если совсем наглядно и не выходя за пределы кириллицы.

P.S.
Вот реально несложные вещи, изложенные на сайте консорциума во введении к стандартам и в ЧАВО.

P.P.S.
Что за эпидемия стильно-модно-молодёжных сайтов началась-то ...
14 авг 19, 20:38    [21949619]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Dima T
Зачем? По пьяне поспорили кто точнее посчитает?

Нужна формула, которая по данному N (количеству char) даст количество строк.
14 авг 19, 21:34    [21949640]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
ЕвгенийВ
Dima T
Зачем? По пьяне поспорили кто точнее посчитает?

Нужна формула, которая по данному N (количеству char) даст количество строк.

Есть ответ дофига, т.е. больше чем атомов во вселенной. Зачем дальше считать?
14 авг 19, 21:40    [21949644]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Dima T
Есть ответ дофига, т.е. больше чем атомов во вселенной. Зачем дальше считать?

Хочу все знать, интересует сама методика подсчета таких сумм.
14 авг 19, 22:00    [21949650]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
ЕвгенийВ
Dima T
Есть ответ дофига, т.е. больше чем атомов во вселенной. Зачем дальше считать?

Хочу все знать, интересует сама методика подсчета таких сумм.

В фундаментальных науках обычно говорят не о подсчёте а об оценке. Тоесть.
Мы берем предположение что будет текст который на 99% состоит из обычных
символов unidoce (двухбайтных) и на 1% из т.н. code-points со средней длиной
2 char (четырехбайтных).

Дальше - школа. Втрой класс. Работа с дробями и пропорциями. Считаем
по вашим-же формулам в первом посте.

Гнаться за супер-точностью порядка копеек в младших разрядах нет
смысла т.к этот ответ ни на что не влияет. А для принятия решения
в физике например просто берут старшие 10 десятичных разрядов
и порядок числа а младшие - тупо игнорируют. По аналогии с типом
double. Он работает похожим образом только основание системы не 10
а 2.

Такие-же методики грубых оценок и сравнений к примеру использует
Брюс Шнайер в своей книге "Практическая Криптография".
14 авг 19, 22:12    [21949659]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
ЕвгенийВ
интересует сама методика подсчета таких сумм.

Тогда вам в школьную математику, раздел комбинаторика. В простейшем случае это перемноженные количества возможных значений для каждой из позиций. То есть, например, в двузначном числе в первой позиции 10 возможных значений и во второй 10. Поэтому всего двузначных чисел существует 10*10 = 100. Если в первой позиции вместо цифр будут латинские буквы, то количество достигнет 26*10 = 260. И так далее по аналогии.
15 авг 19, 14:55    [21950159]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
Dimitry Sibiryakov,

комбинаторика это не школьный курс, не надо передергивать, комбинаторику преподают на 1-2 курсах института, в профильных техникумах
15 авг 19, 15:24    [21950211]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Roman Mejtes
Dimitry Sibiryakov,

комбинаторика это не школьный курс, не надо передергивать, комбинаторику преподают на 1-2 курсах института, в профильных техникумах

Вроде как 10-11 класс. В техникумы обычно после 9-го идут, поэтому там ускоренно проходят программу 10-11 классов. Институты с мат.уклоном наверно углубленно изучают.
15 авг 19, 15:35    [21950228]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Да комбинации юникодов автор правильно посчитал в 1 посту. Его вопрос касался длинных Unicode-последовтательностей.
15 авг 19, 15:41    [21950240]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Да комбинации юникодов автор правильно посчитал в 1 посту. Его вопрос касался длинных Unicode-последовтательностей.

Получается если все символы 2 байта, то 634881 073 741 823 комбинаций
Если один 4-байтный, то 634881 073 741 821 * 1 112 0641
два 4-байтных - 634881 073 741 819 * 1 112 0642
и т.д. до 634881 * 1 112 064536 870 911

Т.е. каждое последующее произведение получается делением на 634882 и умножением на 1 073 741 823. Или по другому это геометрическая прогрессия. Дальше посчитать по формуле суммы N элементов геометрической прогрессии.
15 авг 19, 16:20    [21950281]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Я думаю что максимальный размер строки как был так и остался равен 2 гигабайтам.
Но автор ищет логический смысл. Тоесть смысл в символах класса кодовая точка.
А этот класс мы не можем точно посчитать. Только оценить. Типа верхняя граница.
Если 100% символов строки будут из кодовых точек. И наоборот.

Или некая средняя оценка где мы просто берем пропорцию. Если я правильно его понял.
15 авг 19, 16:23    [21950286]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
исходный вопрос автора "строка в .NET"

Подозреваю, что ".NET", как и 99 % остальных языков программирования, никак корректность строк не проверяют. Некоректная Unicode строка это тоже вполне себе "строка в .NET"

Т.ч. все подробности про Unicode - в топку.
15 авг 19, 16:45    [21950308]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Dima T
Получается если все символы 2 байта, то 634881 073 741 823 комбинаций
Если один 4-байтный, то 634881 073 741 821 * 1 112 0641
два 4-байтных - 634881 073 741 819 * 1 112 0642
и т.д. до 634881 * 1 112 064536 870 911

Т.е. каждое последующее произведение получается делением на 634882 и умножением на 1 073 741 823. Или по другому это геометрическая прогрессия. Дальше посчитать по формуле суммы N элементов геометрической прогрессии.

Напутал немного, точнее не учел что 4-хбайтовые разряды могут быть в любом месте, т.е. каждое из слагаемых это только сколько значений могут принять все разряды, надо каждый умножить на количество комбинаций как могут быть расположены 2х и 4хбайтовые символы.

Например для двух 4-байтных - 634881 073 741 819 * 1 112 0642 * (1 073 741 819 + 2)! / (1 073 741 819! * 2!)

Геометрическая прогрессия отменяется, но т.к. тут факториалы добавились, то есть такое подозрение что самый большой элемент будет в середине последовательности, когда 2х и 4байтныйх поровну, и будет центр на много порядков выше краев, т.е. достаточно посчитать 10-100 средних элементов чтобы получить итого с высокой точностью.

PS Боюсь для записи итого в виде 10^X потребуется очень много циферок для записи X.
15 авг 19, 17:27    [21950371]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Я думаю что максимальный размер строки как был так и остался равен 2 гигабайтам.
Но автор ищет логический смысл. Тоесть смысл в символах класса кодовая точка.
А этот класс мы не можем точно посчитать. Только оценить. Типа верхняя граница.
Если 100% символов строки будут из кодовых точек. И наоборот.

Или некая средняя оценка где мы просто берем пропорцию. Если я правильно его понял.

Я так понял что надо вычислить сколько может быть уникальных строк в кодировке UTF-16 размером до 1 073 741 823 * 2 байт.
15 авг 19, 17:30    [21950376]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Dima T
mayton
Я думаю что максимальный размер строки как был так и остался равен 2 гигабайтам.
Но автор ищет логический смысл. Тоесть смысл в символах класса кодовая точка.
А этот класс мы не можем точно посчитать. Только оценить. Типа верхняя граница.
Если 100% символов строки будут из кодовых точек. И наоборот.

Или некая средняя оценка где мы просто берем пропорцию. Если я правильно его понял.

Я так понял что надо вычислить сколько может быть уникальных строк в кодировке UTF-16 размером до 1 073 741 823 * 2 байт.

В общем и целом, но важней как считать, методика.
Для 10 байт = 5 char
‭1 031 490 117 213 424 000 759 808‬ +
‭ 268 333 472 997 988 892 672‬ * 2 +
‭ 69 805 794 224 242 688‬ * 2 +

А вообщем?
15 авг 19, 17:46    [21950392]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Укладка рюкзака.

Чьорт. Это задача уже поздаколебала.
15 авг 19, 17:52    [21950402]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
ЕвгенийВ
...А вообщем?

Где-то в 4-5 классе школы была такая задача на мат. кружке

но давно это было, т.ч. ответ я уже не помню, искать в википедии тоже лениво
15 авг 19, 18:27    [21950429]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
https://ru.wikipedia.org/wiki/Комбинаторика

если я правильно понимаю, это будет
https://ru.wikipedia.org/wiki/Размещение
15 авг 19, 18:29    [21950430]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Leonid Kudryavtsev
Member

Откуда:
Сообщений: 7827
1 + n + n**2 + n**3 +... n**m

дофига
15 авг 19, 18:33    [21950432]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
mayton
Укладка рюкзака.

Чьорт. Это задача уже поздаколебала.

Не, тут рюкзак бесконечен, т.е. тут задача определить подходящий размер рюкзака.
15 авг 19, 19:21    [21950454]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
Dima T
Member

Откуда:
Сообщений: 13915
Leonid Kudryavtsev
1 + n + n**2 + n**3 +... n**m

дофига

Я так и сказал в начале 21948910, но оказалось намного порядков больше 21950371
15 авг 19, 19:23    [21950455]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
Leonid Kudryavtsev
1 + n + n**2 + n**3 +... n**m

дофига

Не забудь прибавить String.Empty!
15 авг 19, 20:21    [21950486]     Ответить | Цитировать Сообщить модератору
 Re: Сколько строк в .NET  [new]
hVostt
Member

Откуда:
Сообщений: 15810
Leonid Kudryavtsev
Подозреваю, что ".NET", как и 99 % остальных языков программирования, никак корректность строк не проверяют.


В .NET у строк есть метод Normalize, которые в том числе проверяет корректность строки.

Если 99% любых остальных языков будут проверять корректность всех строк всегда, производительность ПО встанет раком.

И что там за таинственный 1%, можно поинтересоваться? :)
29 авг 19, 21:31    [21960151]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2      [все]
Все форумы / Программирование Ответить