Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Оптимально (быстро) составить случайным образом слово  [new]
DeColo®es
Member

Откуда: Москва
Сообщений: 5499
Блог
Быстренько переписал авторский вариант на Hekaton
Ускорение - в 20 раз, на 100К паролей - 5,8 секунд против исходных 110
(Тестил на виртуалке в Windows Azure, 1 ядро)

Изменения внес только те, которые были несовместимы с InMemory.
Правда, нужен SQL 2014 Enterprise ;)
18 сен 14, 00:19    [16588195]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Lepsik
Member

Откуда: glubinka
Сообщений: 4256
IF OBJECT_ID('dbo.GetNewWord') IS NOT NULL DROP FUNCTION dbo.GetNewWord;
GO

CREATE FUNCTION dbo.GetNewWord( @id uniqueidentifier ) 
 RETURNS varchar(max)
AS
BEGIN
  declare @limitedSet varchar(max) = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'; -- допустимые символы 
  declare @sqnce varchar(36) = REPLACE( CAST(@id AS varchar(36)), '-', '' ), @code int = 0
  declare @rst varchar(max) = '', @shift int = 0, @step int = 0
  declare @workSet varchar(max) = ''
  SELECT TOP 36 @workSet = @workSet + @limitedSet FROM master..spt_values
  SELECT TOP 32 @shift = @shift + 1, @code = @code + ASCII(SUBSTRING(@sqnce, @shift, 1))-47, @rst = @rst + SUBSTRING(@workSet, @code, 1)  FROM master..spt_values 
  RETURN @rst
END
GO

SELECT dbo.GetNewWord( newid() ) 
18 сен 14, 01:22    [16588263]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
DeColo®es
Изменения внес только те, которые были несовместимы с InMemory.
Правда, нужен SQL 2014 Enterprise ;)


Эххх, хде ж PINTABLE от MS SQL 2000?

ЗЫ. На японском суперкомпьютере было бы ишо быстрее...
18 сен 14, 05:35    [16588372]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
gang
Member

Откуда:
Сообщений: 1394
Lepsik,

Интересный у Вас вариант. Погонял. На генерацию 100 тыс. комбинаций по 16 символов ушло 32 сек. В своем варианте поменял CTE, на использованный Вами spt_values ( (select top(@n) 1 n from master..spt_values (nolock)) n). CTE, конечно, на больших количествах по производительности весьма убог. Получил сокращение времени генерации с 45 до 12 сек. Пробовал еще вместо for xml path ('') собирать строку через переменную, но получилось дольше, ок. 20 сек. Видимо Ваш вариант еще чуть помедленней из-за количества строковых функций + чтений spt_values получается по 2 на 1 строку.
18 сен 14, 10:46    [16589022]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
gang
Lepsik,

Интересный у Вас вариант. Погонял. На генерацию 100 тыс. комбинаций по 16 символов ушло 32 сек. В своем варианте поменял CTE, на использованный Вами spt_values ( (select top(@n) 1 n from master..spt_values (nolock)) n). CTE, конечно, на больших количествах по производительности весьма убог. Получил сокращение времени генерации с 45 до 12 сек. Пробовал еще вместо for xml path ('') собирать строку через переменную, но получилось дольше, ок. 20 сек. Видимо Ваш вариант еще чуть помедленней из-за количества строковых функций + чтений spt_values получается по 2 на 1 строку.


Если задача была "нагенерить чего попало, абы как" - оно может и ничего, но проще и быстрее константу возвращать или ваще ничо не делать.

Если же задача добиться контролируемого распределения вероятности для символов - фуфло чуть более, чем полное.
18 сен 14, 11:11    [16589173]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
Если задача была "нагенерить чего попало, абы как" - оно может и ничего, но проще и быстрее константу возвращать или ваще ничо не делать.

Если ничего не делать, то не получится "нагенерить чего попало, абы как"
Если возвращать константу, то это не будет "составить случайным образом слово"

aleks2
Если же задача добиться контролируемого распределения вероятности для символов - фуфло чуть более, чем полное.


Задача поставленная ТС - "случайным образом сгенерировать из этих символов пароль определенной длины"
18 сен 14, 11:19    [16589219]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
Если задача была "нагенерить чего попало, абы как" - оно может и ничего, но проще и быстрее константу возвращать или ваще ничо не делать.

Если ничего не делать, то не получится "нагенерить чего попало, абы как"
Если возвращать константу, то это не будет "составить случайным образом слово"

aleks2
Если же задача добиться контролируемого распределения вероятности для символов - фуфло чуть более, чем полное.


Задача поставленная ТС - "случайным образом сгенерировать из этих символов пароль определенной длины"


Мне неинтересно устраивать срачь. Тем более, если сильно увлечься - можно пострадать.
Но!

1. newid() возвращает уникальный идентификатор, но никто не обещал, что он обладает случайностью и никто не описал характеристики этой "случайности".

2. У тредстартера явно присутствуют веса (вероятности) символов. Это как-бы намекает на желание иметь ПРЕДСКАЗУЕМЫЕ и КОНТРОЛИРУЕМЫ результаты.
18 сен 14, 11:27    [16589268]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
1. newid() возвращает уникальный идентификатор, но никто не обещал, что он обладает случайностью и никто не описал характеристики этой "случайности".

2. У тредстартера явно присутствуют веса (вероятности) символов. Это как-бы намекает на желание иметь ПРЕДСКАЗУЕМЫЕ и КОНТРОЛИРУЕМЫ результаты.


Вы хотите уверить, что пароль, где каждый символ получен "контролируемого распределения вероятности для символов" лучше пароля, где где каждый символ получен "менее контролируемым распределением" ?
18 сен 14, 11:31    [16589295]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
1. Уточните понятие "лучше".
2. С точки зрения криптографической теории - "лучше" = "наименее предсказуемо и угадываемо".
3. В этом смысле да, пароль, где символы равновероятны - "лучший".
18 сен 14, 11:37    [16589348]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Только newid() не гарантирует даже "равновероятности".
18 сен 14, 11:39    [16589373]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
1. Уточните понятие "лучше".

Вы уточните. Зачем мне для генерации пароля "контролируемого распределения вероятности для символов" ?

aleks2
2. С точки зрения криптографической теории - "лучше" = "наименее предсказуемо и угадываемо".

Я сейчас сгенерировл пароль ну скажем по методу 16588263
Как быстро вы его взломаете ?

aleks2
3. В этом смысле да, пароль, где символы равновероятны - "лучший".

Его туднее взломать ? Он меньше места занимает ?
18 сен 14, 11:42    [16589403]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
1. Уточните понятие "лучше".

Вы уточните. Зачем мне для генерации пароля "контролируемого распределения вероятности для символов" ?

aleks2
2. С точки зрения криптографической теории - "лучше" = "наименее предсказуемо и угадываемо".

Я сейчас сгенерировл пароль ну скажем по методу 16588263
Как быстро вы его взломаете ?

aleks2
3. В этом смысле да, пароль, где символы равновероятны - "лучший".

Его туднее взломать ? Он меньше места занимает ?


1. Мне - вообще не нужен генератор паролей. Он был нужен тредстартеру.

2. Я не буду взламывать - мне это неинтересно.

3. Но пароль с неравномерной вероятностью взламывается быстрее. Ибо количество перебираемых вариантов - меньше (для паролей равной длины).

4. Если очень хочется - я могу вспомнить даже насколько меньше.
18 сен 14, 11:53    [16589492]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
1. Мне - вообще не нужен генератор паролей. Он был нужен тредстартеру.

А что вы тогда решаете свою задачу в чужой теме ?

aleks2
2. Я не буду взламывать - мне это неинтересно.

Я понял. Вам интересна контролируемость распределения.

aleks2
3. Но пароль с неравномерной вероятностью взламывается быстрее. Ибо количество перебираемых вариантов - меньше (для паролей равной длины).

На сколько быстрее ? На пару лет из 100 лет общего времени взлома ?

aleks2
4. Если очень хочется - я могу вспомнить даже насколько меньше.

Пароль с контролируемым распределением занимает меньше места, чем пароль с неконтролируемым распределением ???
18 сен 14, 11:59    [16589543]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
1. Мне - вообще не нужен генератор паролей. Он был нужен тредстартеру.

А что вы тогда решаете свою задачу в чужой теме ?

aleks2
2. Я не буду взламывать - мне это неинтересно.

Я понял. Вам интересна контролируемость распределения.

aleks2
3. Но пароль с неравномерной вероятностью взламывается быстрее. Ибо количество перебираемых вариантов - меньше (для паролей равной длины).

На сколько быстрее ? На пару лет из 100 лет общего времени взлома ?

aleks2
4. Если очень хочется - я могу вспомнить даже насколько меньше.

Пароль с контролируемым распределением занимает меньше места, чем пароль с неконтролируемым распределением ???


Ну если ваша тяга к просвещению неистребима:
для алфавита в N символов количество вариантов X для пароля длиной M символов при равновероятности всех символов

X = 10^(M*lg(N)) -- это абсолютный максимум

для того же алфавита, но с неравной вероятностью символов, заданной вероятностью Pi для каждого символа i

X = 10^( M*( -сумма_по_i(Pi*lg(Pi) ) ) -- это всегда меньше максимума

Остальное считайте сами.
И да, пароль равной сложности при равновероятном распределении занимает МЕНЬШЕ места.
18 сен 14, 12:08    [16589656]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
И да, пароль равной сложности при равновероятном распределении занимает МЕНЬШЕ места.

Т.е. строка в 10 символов может занимать разное место в зависимости от того, как сгенерировано ее содержимое ???

aleks2
X = 10^(M*lg(N)) -- это абсолютный максимум

Для M=10 и N = 62 у меня получилось 8.3929936586923E+17

aleks2
X = 10^( M*( -сумма_по_i(Pi*lg(Pi) ) ) -- это всегда меньше максимума

Если число даже на порядок меньше, чем 8.3929936586923E+17, то я думаю, что за мою жизнь никто не взломает мой пароль
18 сен 14, 12:24    [16589784]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
И да, пароль равной сложности при равновероятном распределении занимает МЕНЬШЕ места.

Т.е. строка в 10 символов может занимать разное место в зависимости от того, как сгенерировано ее содержимое ???

aleks2
X = 10^(M*lg(N)) -- это абсолютный максимум

Для M=10 и N = 62 у меня получилось 8.3929936586923E+17

aleks2
X = 10^( M*( -сумма_по_i(Pi*lg(Pi) ) ) -- это всегда меньше максимума

Если число даже на порядок меньше, чем 8.3929936586923E+17, то я думаю, что за мою жизнь никто не взломает мой пароль


1. Строка из 10 символов занимает ровно десять символов. Но при равной вероятности может оказаться достаточным 9 символов.

2. Это дело хозяйское, но при сильной неравномерности, оно может стать и на 17 порядков меньше. Кстати 10^17 - маловато будет. Считается по современному состоянию вычислительных мощностей, что надо больше 2^1000 или 10^300.

3. И это мы еще не обсудили потенциальные корреляции последовательных символов, при генерации их через newid().
18 сен 14, 12:34    [16589897]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
gang
Member

Откуда:
Сообщений: 1394
Вот так спорят люди умные, аргументы пишут, формулы. А потом приходит пользователь и меняет свой мега устойчивый пароль, сгенеренный по всем правилам и в соответствии с последними веяниями феншуя, на qwerty123. В ТОР 20 популярных паролей стабильно все те же из года в год.
18 сен 14, 12:39    [16589932]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
1. Строка из 10 символов занимает ровно десять символов. Но при равной вероятности может оказаться достаточным 9 символов.

Достаточным для чего ? Для хранения ?

aleks2
2. Это дело хозяйское, но при сильной неравномерности, оно может стать и на 17 порядков меньше.

Доооо, конечно. Сильная неравномерность - это когда я вместо rand/newid буду использовать текущий день года для выбора случайного символа ?

aleks2
Считается по современному состоянию вычислительных мощностей, что надо больше 2^1000 или 10^300.

Вычислительных мощностей у кого ? У Пентагона или у стандартного хакера ?


aleks2
3. И это мы еще не обсудили потенциальные корреляции последовательных символов, при генерации их через newid().

Пока вы обсуждаете, люди просто генерируют пароли, которые вы не взломаете точно.
18 сен 14, 12:44    [16589962]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
gang
А потом приходит пользователь и меняет свой мега устойчивый пароль, сгенеренный по всем правилам и в соответствии с последними веяниями феншуя, на qwerty123.

От дураков ставят другие защиты. Не такие как от умных.
18 сен 14, 12:49    [16589995]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
1. Строка из 10 символов занимает ровно десять символов. Но при равной вероятности может оказаться достаточным 9 символов.

Достаточным для чего ? Для хранения ?

aleks2
2. Это дело хозяйское, но при сильной неравномерности, оно может стать и на 17 порядков меньше.

Доооо, конечно. Сильная неравномерность - это когда я вместо rand/newid буду использовать текущий день года для выбора случайного символа ?

aleks2
Считается по современному состоянию вычислительных мощностей, что надо больше 2^1000 или 10^300.

Вычислительных мощностей у кого ? У Пентагона или у стандартного хакера ?


aleks2
3. И это мы еще не обсудили потенциальные корреляции последовательных символов, при генерации их через newid().

Пока вы обсуждаете, люди просто генерируют пароли, которые вы не взломаете точно.


Блаженны верующие!
Аминь.
18 сен 14, 12:52    [16590031]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
Блаженны верующие!

Нуда, нуда "Я не буду взламывать - мне это неинтересно."
Неинтересно потому, что не получится ?
18 сен 14, 12:54    [16590051]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
Блаженны верующие!

Нуда, нуда "Я не буду взламывать - мне это неинтересно."
Неинтересно потому, что не получится ?


Дарагой, меня на "слабо" не взять.
Я верую в науку и в ее раздел - математику.

А ты волен верить во что хошь.
18 сен 14, 12:56    [16590066]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
Я верую в науку и в ее раздел - математику.

- Какова вероятность, что вы встретите динозавра на прогулке?
- 50%
- ???
- Ну либо встречу, либо не встречу.
18 сен 14, 13:00    [16590092]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
aleks2
Guest
Glory
aleks2
Я верую в науку и в ее раздел - математику.

- Какова вероятность, что вы встретите динозавра на прогулке?
- 50%
- ???
- Ну либо встречу, либо не встречу.


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

Но всеж на, утрись. Четыре пароля, сгенерированные newid():

asMWipxyRU5nsAUfpvNUdxTbhkrM5qN6
hkHL7avQYltwBHL5ezVhmqzH37fBCJTZ
iAWemIM8glsNS3pyQWjrMOPXiCJNQ0dh
dzVW6oGPWentyATWfmHI670cjmsAX28e

надо быть абсолютно тупым модером, вроде тебя, чтобы не узрить закономерностей.
18 сен 14, 13:07    [16590143]     Ответить | Цитировать Сообщить модератору
 Re: Оптимально (быстро) составить случайным образом слово  [new]
Glory
Member

Откуда:
Сообщений: 104760
aleks2
надо быть абсолютно тупым модером, вроде тебя, чтобы не узрить закономерностей.

Мне вот интересно, а вы когда будете взламывать пароль, уже будете заранее знать закономерности, по которым они генерировались ? Или вы у пользователя спросите ?
18 сен 14, 13:11    [16590170]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Microsoft SQL Server Ответить