Всем привет!
ситуация такая... есть строка "аааабаааабаааабаааа" нужно найти третий символ "б".
я знаю только как возвратить индекс первого вхождения одной подстроки в другую, короче говоря я могу найти только первый символ "б" =)
более сложная ситуация... нужно в строке "аааабаааабаааабаааа" найти ЧЕТВЕРТЫЙ символ "б" (я считать умею =), т.е. нужно определить количество символов "б" в строке (как?), ну тут допустим 3 и вычесть это число из общего 4-3=1 а потом найти первый символ "б"... сложность с нахождение количества определенных символов.
http://vbnet.ru/forum/show.aspx?id=167726
http://vbnet.ru/forum/show.aspx?id=170334
http://vbnet.ru/forum/show.aspx?id=168616
http://vbnet.ru/forum/show.aspx?id=170297
Ну ты понял, да?
Я в шоке, челоек разработал свой алгоритм шифрования, издает свои Best Practices по работе с СУБД, а на такой ерунде застрял!
Private Function FindChar(ByVal source As String, ByVal [char] As Char, ByVal position As Integer) As Integer
Dim Positions As New List(Of Integer)
Dim LastPosition = source.IndexOf([char]
Do While LastPosition >= 0
If Positions.Count = position Then Return LastPosition
Positions.Add(LastPosition)
LastPosition = source.IndexOf([char], LastPosition + 1)
Loop
Return Positions(position Mod Positions.Count)
End Function
Параметр position - не нужно объяснять что zero-based?
сложность с нахождение количества определенных символов.
Сложности ровным счетом никакой.
В моем примере это количество можно вытянуть из Positions.Count или (если сможешь конечно, в чем я сомневаюсь), можешь переписать так чтоб для определения только количества список не требовался.
http://vbnet.ru/forum/show.aspx?id=167726
http://vbnet.ru/forum/show.aspx?id=170334
http://vbnet.ru/forum/show.aspx?id=168616
http://vbnet.ru/forum/show.aspx?id=170297
Ну ты понял, да?
понял... понял... все темы кроме криптографии закрыты! ответы ваши я прочитал... так что ваши труды не пропадут
да и притом я сказал что некогда... там объяснять много(в теме про криптографию) + я еще решил усовершенствовать алгоритм, эта тема кстати напрямую контактирует с криптографией... потом сами поймете... вот этот код(выше), который я надеюсь работает, усилит алгоритм минимум в 2 раза но времени реально не хватает!!! уже неделю в студию не заходил!
я еще решил усовершенствовать алгоритм, эта тема кстати напрямую контактирует с криптографией... потом сами поймете... вот этот код(выше), который я надеюсь работает, усилит алгоритм минимум в 2 раза
Нифига себе! Аж в 2 раза??? Пентагон, ЦРУ, ФСБ и НАСА распускают своих сотрудников и ждут когда же наконец смогут получить в свои руки абсолютную криптографию!!!
Нифига себе! Аж в 2 раза??? Пентагон, ЦРУ, ФСБ и НАСА распускают своих сотрудников и ждут когда же наконец смогут получить в свои руки абсолютную криптографию!!!
1) в вашем примере есть ошибка! неправильный результат выдает
2) я сделал проще и без List что повысит скорость (я надеюсь):
Private Function FChar(ByVal _Text As String, ByVal _Char As Char, ByVal _Position As Integer) As Integer
Dim d_SelectedChar As Integer = 0
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text.ToCharArray
d_SelectedChar += 1
If d_Char = _Char Then
d_NumberChar += 1
If d_NumberChar = _Position Then
Return d_SelectedChar - 1
End If
End If
Next
Return Nothing
End Function
Private Function QChar(ByVal _Text As String, ByVal _Char As Char) As Integer
Dim d_SelectedChar As Integer = 0
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text.ToCharArray
d_SelectedChar += 1
If d_Char = _Char Then
d_NumberChar += 1
End If
Next
Return d_NumberChar
End Function
Кстати я только что позвонил в Пентагон и сказал что с кодом ___Pavel___ скорость кардинально повысилась, они уже демонтирует из подвалов свои суперкомпьютеры, поторопись пожалуйста со своим криптокодом!
Это серьезное заявление следует подкрепить примером данных на которых код дает неверное значение и указать какое же все-таки будет верное.
а что тут проверять-то? сами вставьте код и посмотрите там результат даже близко на правильный не похож!
вот ваш код:
Private Function FindChar(ByVal source As String, ByVal [char] As Char, ByVal position As Integer) As Integer
Dim Positions As New List(Of Integer)
Dim LastPosition = source.IndexOf([char]
Do While LastPosition >= 0
If Positions.Count = position Then Return LastPosition
Positions.Add(LastPosition)
LastPosition = source.IndexOf([char], LastPosition + 1)
Loop
Return Positions(position Mod Positions.Count)
End Function
MsgBox(FindChar("aaaabaaaabaaaabaaaa", "b"c, 2))
выдает результат 14!!! хотя ИНДЕКС 2 символа "б" = 9! мой код определяет это безошибочно!
Кстати я только что позвонил в Пентагон и сказал что с кодом ___Pavel___ скорость кардинально повысилась, они уже демонтирует из подвалов свои суперкомпьютеры, поторопись пожалуйста со своим криптокодом!
этот код будет использоваться тысячи и сотни тысяч раз при выполнении шифрования/дешифрования! если каждый раз БЕСТОЛКУ юзать list это дас о себе знать! Причем замечу что обе функции (FChar и QChar) будут использоваться для каждого шифруемого символа!
Параметр position - не нужно объяснять что zero-based?
Видимо все-таки нужно. Ох уж эти школьники, воспитаные на VB6...
http://en.wikipedia.org/wiki/Zero-based
В VB6 у строк, списков и т.п. индексация начиналась с единицы
Это значит - чтоб получить первый символ строки, нужно вызвать Mid ("...", 1, 1), т.е. у первого символа строки индекс - 1.
Почему так, даже думать не надо - потому что это унаследовано еще с самых первых "бейсиков"
В то же время во всем компьютерном мире индексация начинается с _нуля_. То есть - первый элемент в списке имеет индекс 0.
Вот когда в Microsoft разрабатывали Common Language Specification это и предусмотрели. А VB .NET, как язык, соответствующий этой спецификации, также получил zero-based индексацию.
По сути к языку она отношения не имеет - речь идет о том как индексы обрабатываются в класса FCL, но если почитать рекомендации по разработке в .NET Framework (на этом сайте даже выкладывалась огромная статья в переводе Надежды Шатохинй) - везде рекомендуется использовать именно zero-based индексацию, чтоб разработчики, использующие компоненты, написанные другими, не гадали, не листали документацию, а были уверены что индексация начинается с 0.
Я, разумеется, предполагал что ___Pavel___ не сразу въедет в фишку, поэтому даже напомнил об этом, и что - за своей занятостью лучший криптоаналитик мира не заметил эту мелочь. ну что ж, бывает.
PS Если не догнал, еще раз поясню.
Чтоб получить индекс _второго_ символа подставь в мою функцию параметра 1 и все будет пучком!
Я как сознательный гражданин Украины и житель планеты Земля, чрезвычайно обеспокоен положением информционной безопасности страны и планеты.
И обеспокоен был я ровно до того момента как узнал, что господин ___Pavel___ разработал свой собственный алгоритм криптографии, являющийся абсолютным алгоритмом и в ближайшее время планирует предоставить его общественности.
Я был рад принять, по просьбе ___Pavel___, разумеется, посильное участие в улучшении этого алгоритма. И поэтому хочу проанализировать код который предложил ___Pavel___ и оценить, насколько эффективно его использовании в столь сложном алгоритме криптографии!!!
Задача ставилась несложная - а именно - подсчитать количество определенных символов в строке.
___Pavel___ предложил свой код:
Private Function QChar(ByVal _Text As String, ByVal _Char As Char) As Integer
Dim d_SelectedChar As Integer = 0
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text.ToCharArray
d_SelectedChar += 1
If d_Char = _Char Then
d_NumberChar += 1
End If
Next
Return d_NumberChar
End Function
И у меня нет никаких оснований сомневаться в его идеальности!
Единственное чего я хочу - это узнать, насколько хуже я разбираюсь в оптимизации программ и узнать, насколько медленнее будет выполняться мой код, решающий аналогичную задачу.
Чтоб меня не обвинили в плагиате, я не стал копировать код, который написал ___Pavel___ и написал свой, конечно, так как смог.
Private Function CountSymbols(ByVal source As String, ByVal symbol As Char) As Integer
Dim Count = 0
Dim Position = source.IndexOf(symbol)
Do While Position >= 0
Count += 1
Position = source.IndexOf(symbol, Position + 1)
Loop
Return Count
End Function
Превое что бросается в глаза - это явная неоптимальность моего алгоритма (он содержит на 2 строчки меньше кода, а следовательно делает меньше полезной работы!!!)
Я сделал проверку и убедился что функции выдают одинаковый результат.
Теперь стоит выполнить проверку скорости работы - то есть узнать какой код будет работать быстрее.
Итак, прогоняю на строке "aaaabaaaabaaaabaaaa" - разницы, разумеется, никакой.
Поэтому берем задачу потяжелее - файл с исходным кодом на 240 килобайт - соединяем 1000 раз, получаем файл размером 240 мегабайт.
После этого ищем там символы.
Алгоритм работы следующий
Запускается программа, загружает с диска файл, и по нему прогоняет каждый код по 10 раз (строка все-таки большая и может "вылезти" в файл подкачки - если прогнать несколько раз, то вероятность что приложению будут выделены необходимые 450+ мегабайт из 2 ГБ установленых на компьютере будет очень высока).
Запущен диспетчер задач для анализа работы программы, запуск...
Итак, запуск кода ___Pavel___
Первые 3 прохода - отличный результат.
00:00:01.706
00:00:01.733
00:00:01.756
Дальше... ЯМА!
Причем не просто яма - компьютер перестает отвечать на запросы, музыка которая играла на фоне останавливается...
Первая мысль - "Дэвид Блэйн!!! Если ты еще раз так сделаешь то я на тебя СТУКАНУ!!!!!!!!"
Катастрофа - немедленно открываем Диспетчер задач.
Мда, немедленно при таких условиях длилось секунд 10.
Открываю и тупо о***еваю...
Working Set: 1.6 GB
Commit Size: 2.1 GB
Открываю вкладку Performance - так и есть, вся память забита...
Ладно, подождем, не будет же оно вечно висеть, плюс эксперимент нужно довести до конца.
Что стряслось? Открываю диспетчер задач и смотрю график памяти.
По анализу графика и вывода консоли можно предположить что:
Приложения начало "выбивать" себе очень много памяти.
У него это получалось (еще бы, 2 гигабайта "на борту", и работало все быстро. Потом вдруг вентиль перекрыли (память собственно кончилась) - и случилась большая яма...
Длилась она пока не включился сборщик мусора.
Сборщик память освободил, и последующая работа велась уже параллельно со сборщиком мусора.
Возникает вопрос - нафига для анализа 240-мегабайтового файла нужно столько памяти???
Первое что приходит в голову - исходный код сохранен в кодировке UTF-8, но посколько в нем практически все содержимое - латинские символы, то занимают по 1 байту.
А при загрузке в память данные загружаются в 2-байтовых Char'ах, т.е. в памяти загруженные данные занимают не 240 мегабайт а около 480.
Да, 480, но не 2 гигабайта. Откуда 2 гигабайта?
Для этого нужно проанализировать исходный код функции QChar
И, прошу прощения, о****еть.
For Each d_Char As Char In _Text.ToCharArray
Ужас. Кроме того что сама строка весит 500 мегабайт, она еще клонируется в массив, т.е. "выбивает" себе еще 500 мегабайт!!!
Что дальше? Функция отработала первый раз, начинает работать второй раз - и тут она опять выбивает себе 500 мегабайт. И третий раз тоже!
А на четвертый раз происходит ***здец - сборщик мусора никуда не торопился, ведь памяти хватает.
Функйия опять себе просит 500 мегабайт памяти, ааааааа... нету... И начинается своппинг, причем очень жестокий.
После этого сборщик мусора оживает, быстренько уничтожает ненужные массивы, и в дальнейшем уже работает параллельно с работой функции, то есть не дает опять довести занимаемую память до критической точки.
Итак, первое что нужно сделать - убрать ToCharArray, что я и делаю.
Private Function QChar(ByVal _Text As String, ByVal _Char As Char) As Integer
Dim d_SelectedChar As Integer = 0
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text
d_SelectedChar += 1
If d_Char = _Char Then
d_NumberChar += 1
End If
Next
Return d_NumberChar
End Function
Никаких аномалий, и даже небольшой выигрыш в 30% (собственно на алгоритме криптографии этот небольшой выигрыш будет совсем не лишним!)
Смотрим где же ___Pavel___ потерял свои милисекунды?
Минуточку, а что это?
d_SelectedChar += 1
Счетчик не используется, а просто крутится без дела! Непорядок, нужно его убрать.
Private Function QChar(ByVal _Text As String, ByVal _Char As Char) As Integer
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text
If d_Char = _Char Then
d_NumberChar += 1
End If
Next
Return d_NumberChar
End Function
Что еще можно разогнать?
Не нравится мне цикл For Each, хоть убей, можно заменить на обычный For
Private Function QChar(ByVal _Text As String, ByVal _Char As Char) As Integer
Dim d_NumberChar As Integer = 0
Dim Length = _Text.Length
For i = 0 To Length - 1
If _Text(i) = _Char Then
d_NumberChar += 1
End If
Next
Return d_NumberChar
End Function
Что еще можно оптимизировать в этом мега коде я не знаю, похоже это потолок, но и этот потолок ниже чем показывает мой код.
Во всех тестах я искал латинскую букву "a" - в английском языке эта буква очень распространена, а, значит, и в исходном коде встречается часто.
(фактически этот символ занимает 4.4% всего файла).
Рассмотрим другую задачу. Символ "я" в этом файле вообще не встречается. Посмотрим, как поведут себя оба кода.
Мой код демонстрирует практически вполтора раза бОльшую скорость в этом случае.
В чем причина сего грустного положения дел?
Чтоб понять причину, нужно знать как работает магическая функция IndexOf. То есть посмотреть ее исходный код.
Открываем рефлектор и видим что никакого исходного кода нету!
<MethodImpl(MethodImplOptions.InternalCall)> _
Public Function IndexOf(ByVal value As Char, ByVal startIndex As Integer, ByVal count As Integer) As Integer
Опять хочется обвинить в этом Дэвида Блэйна, но... Идем в MSDN и смотрим чтоб значит InternalCall у атбирута MethodImpl.
А значит это что метод реализуется в самом Runtime - и, как я могу предположить, реализуется он не на управляемом коде, а на высокооптимизированном _неуправляемом_ коде, написанном на C++ или даже ассемблере, с которым управляемый код просто не сможет тягаться.
Итак, мега-криптография была на грани провала, но я исправил ситуацию (разумеется, если пан ___Pavel___ скопирует себе мой пример кода).
Но возникло следующее заявление:
этот код будет использоваться тысячи и сотни тысяч раз при выполнении шифрования/дешифрования! если каждый раз БЕСТОЛКУ юзать list это дас о себе знать! Причем замечу что обе функции (FChar и QChar) будут использоваться для каждого шифруемого символа!
Итак, похоже проблема с List...
А что, собственно, такое этот List? Это обычный класс внутри которого лежит массив. И я лично никогда не жаловался на его производительность, но вот пан ___Pavel___ жалуется, и при этом без List пишет гораздо более тормознутый код, чем я с List
Но ставим это на его совести - потому что он вдруг поменял условия алгоритма так, что его можно решить и без List.
Итак, следующая функция на экзекуции:
Private Function FChar(ByVal _Text As String, ByVal _Char As Char, ByVal _Position As Integer) As Integer
Dim d_SelectedChar As Integer = 0
Dim d_NumberChar As Integer = 0
For Each d_Char As Char In _Text.ToCharArray
d_SelectedChar += 1
If d_Char = _Char Then
d_NumberChar += 1
If d_NumberChar = _Position Then
Return d_SelectedChar - 1
End If
End If
Next
Return Nothing
End Function
Извини, ___Pavel___, на сей раз обойдемся без эталонной функции от Steel Brand, тем более что ты сам сможешь ее сделать, модифицировав ту которую я сделал в первом сообщении, и без бенчмарков (можешь не сомневаться - мой код будет работать быстрее, причины я написал в предыдущем сообщении).
Но, собственно, .ToCharArray нужно и отсюда.
Кроме того, есть у меня мнение, что на обычном цикле For можно выиграть в скорости, и избавиться от d_SelectedChar - советую проверить оба варианта.
Ага, так вот в чем собственно проблема алгоритма (хотя я о нем только слышал - но не видел)...
Как сказал Павел, эти функции будут использовать при обработке каждого символа в исходной строке.
Проведем небольшой анализ.
Скорее всего скорость работы QChar линейно зависит от длинны строки, то есть для обработки строки которая в 10 раз короче нужно в 10 раз меньше времени.
Итак. у нас строка, но не на 240 мегабайт, а на 24 килобайта, т.е. в 10000 раз короче.
Следовательно на нее функция будет тратить не 0.4 секунды, а 0.00004.
Функция будет вызвана для каждого символа:
0.00004 * 24 000 = 0.96
то есть грубо говоря секунда. Ну это правда, учитывая только одну фукнцию, а собственно наверняка будут и другие которые будут участвовать в шифровании, но вряд ли будет намного больше времени, скорее всего просто в несколько раз больше.
А вот что будет на строке из 240 000 000 символов?
Как мы уже знаем, функция на этом объеме работает около 0.4 секунды.
Посмотрим, сколько же времени понадобится чтоб обработать всю строку.
0.4 * 240 000 000 = 96000000
Три года на шифрование 240 мегабайт. Многовато, как для абсолютной криптографии...
Что-то мне подсказывает что демонтировать из Пентагона суперкомпьютеры пока не стоит...
Если не понял - твой алгоритм будет иметь экспоненциальную сложность, то есть для обработки строки длинной N символов потребуется ON^2 времени.
Кстати алгоритм AES, который ты всеми силами хочешь превзойти, на шифрование 240 мегабайт данных тратит не 3 года, а намного меньше времени:
Причем очень важная его особенность - данные шифруются/дешифруются небольшими блоками. Для того чтоб начать шифрование/дешифрование, не нужно иметь сразу все 240 мегабайт, достаточно первых нескольких десятков килобайт!
Например, на исходном компьютере данные еще не закончили шифроваться, а на компьютере получателе они уже дешифруются.
Вобщем не знаю даже что ты теперь будешь говорить в свое оправдание...
я офигел... яб стока не написал
итак... да! публично соглашаюсь с тобой о великий
но есть пару нюансов:
1) я знаю что индексация символов начинается с 0
2) глупо в переменную с наименованием position передовать значение индекса, а не номера символа, т.е. нормальный человек впишет туда 2 если ему нужен индекс ВТОРОГО символа, а не 1 ))
3) мне плевать на ваш AES, мой лучше + мой класс шифрует лишь одну строку, т.е. передаешь строку, а она возвращается зашифрованной/расшифрованной, а файл можно разбить самому до того как туда передавать
хотите могу убрать эти 2 функции, но они реально повышают эффективность в несколько раз... потом в теме криптографии объясню...