Что нового

[Процессы] Как ускорить работу программы?

Статус
Закрыто для дальнейших ответов.

forfrends

Новичок
Сообщения
176
Репутация
3
Всем добрый день!
Вот появилась у меня необходимость создать небольшую програмку-генератор набора символов. Длинна слова: 4 - 30 символов, всего используется 4 символа: пробел, скобки и умножение (*)
Все сделал по принципу:
Код:
$Nabor = " ()*"
for $i1 = 1 to n; где n - это количество используемых символов
    for $i2 = 1 to n
        ...
            for $i30 = 1 to n
               ;генерация слова
               $slovo = StringMid($Nabor, $i1, 1) & StringMid($Nabor, $i2, 1) & ... & StringMid($Nabor, $i30, 1) 
            next
        ...
    next
next

В результате программа работает ОООчень медлено. За 12 часов работы не прошло даже 10% комбинаций. Только что проверил - за 988.726 секунд (16 мин.) работы скрипта пройдено всего 130 000 комбинаций... это примерно 135 комбинаций в секунду. Мало...
Характеристики компа:
проц: AMD FX(tm)-6100 Six-Core Processor 6-ти ядерный на 3.9 Ггц
Озу: 8 Гб
Windows 7 64x
Процессор загружен на 0-1%
Как ускорить работу скрипта? Может есть существенные альтернативы для For...Next? Можете что-то посоветовать? Как "загрузить" процессор по-полной?
 

Viktor1703

AutoIT Гуру
Сообщения
1 535
Репутация
410
Может так будет лучше!?

Код:
MsgBox(0, '', Gen(' (*)', 30))

Func Gen($sSymbols, $iCount)

	Local $sResult


	For $i = 1 To $iCount
		$sResult &= StringMid($sSymbols, Random(1, StringLen($sSymbols), 1), 1)
	Next

	Return $sResult
EndFunc
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
Viktor1703, такой вариант не подойдет из-за рандомности. Важно чтобы были испробованы все комбинации, а рандомность этого не дает - нетуверенности что нет повторений комбинаций и не пропущено ни одной комбинации.


Добавлено:
Сообщение автоматически объединено:

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


Добавлено:
Сообщение автоматически объединено:

Тут подумал что уходит лишнее время на постоянные StringMid, лучше брать данные из масива. Изменил код так:
Код:
$Nabor = " ()*"
For $i = 1 To $n
	$f[$i] = StringMid($Nabor, $i, 1)
Next
for $i1 = 1 to $n; где $n - это количество используемых символов
    for $i2 = 1 to $n
        ...
            for $i30 = 1 to $n
               ;генерация слова
               $slovo = $f[$i1] & $f[$i2] & ... & $f[$i30]
            next
        ...
    next
next

В результате процессор загрузился до 3%, но скорость генерации осталась той же - примерно 130-150 комбинаций в секунду.


Добавлено:
Сообщение автоматически объединено:

Еще порылся в программе. Поодключал некоторые функции, в результате скорость возросла до 190 комбинаций в секунду... Но теперь нигде и никак не видно что программа работает (только в диспетчере задачь). :(
может это предел самого Аутоита? :scratch:
 

Viktor1703

AutoIT Гуру
Сообщения
1 535
Репутация
410
Вообще вот все комбинации ( -1) мозги не работаю, выходит 192 комбинации, а надо 193, т.е. последняя комбинация возвращается *))) а нужно )))) нужно как - то ещё раз прокрутить цикл когда в $aComb[$i] будет цифра 4

Код:
#Include <Array.au3>

$aRet = Gen(' (*)')

If IsArray($aRet) Then
	_ArrayDisplay($aRet)
EndIf

Func Gen($sSymbols)

	Local $sResult, $aComb[StringLen($sSymbols)], $aOut[1]

	For $i = 0 To Ubound($aComb) - 1
		$aComb[$i] = 1
	Next


    While 1
		If ($aComb[0] == StringLen($sSymbols)) Then
			ExitLoop
		EndIf

		For $i = 0 To Ubound($aComb) - 1

			$sResult &= StringMid($sSymbols, $aComb[$i], 1)

		Next

		$aOut[0] += 1

		_ArrayAdd($aOut, $sResult)

		$sResult = ''

		For $i = (Ubound($aComb) - 1) To 0 Step -1
			$aComb[$i] += 1
			If $aComb[$i] > StringLen($sSymbols) Then
				$aComb[$i] = 1
			Else
				ExitLoop
			EndIf
		Next
	Wend


	Return $aOut
EndFunc



Добавлено:
Сообщение автоматически объединено:

Пришлось по извращаться....

Код:
#Include <Array.au3>

$aRet = Gen(' (*)')

If IsArray($aRet) Then
	_ArrayDisplay($aRet)
EndIf

Func Gen($sSymbols)

	Local $sResult, $aComb[StringLen($sSymbols)], $aOut[1]

	For $i = 0 To Ubound($aComb) - 1
		$aComb[$i] = 1
	Next

    While 1
		If ($aComb[0] >= StringLen($sSymbols)) Then
			
			For $i = 0 To Ubound($aComb) - 1
				$sResult &= StringMid($sSymbols, StringLen($sSymbols), 1)
			Next

			$aOut[0] += 1

			_ArrayAdd($aOut, $sResult)

			ExitLoop
		EndIf

		For $i = 0 To Ubound($aComb) - 1
			$sResult &= StringMid($sSymbols, $aComb[$i], 1)
		Next

		$aOut[0] += 1

		_ArrayAdd($aOut, $sResult)

		$sResult = ''

		For $i = (Ubound($aComb) - 1) To 0 Step -1
			$aComb[$i] += 1
			If $aComb[$i] > StringLen($sSymbols) Then
				$aComb[$i] = 1
			Else
				ExitLoop
			EndIf
		Next
	Wend

	Return $aOut
EndFunc
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
Viktor1703, хороший пример, только длина генерируемого слова должна быть 30 символов. Как в первом вашем примере.
 

Viktor1703

AutoIT Гуру
Сообщения
1 535
Репутация
410
forfrends

я выставил размер 5 [количество комбинаций: 2501] и у меня появились повторяющиеся комбинации, я полагаю из-за того что длина слова не должна быть больше набора символов иначе будут повторения..
 

winstan

Эксплотатор)
Сообщения
406
Репутация
78
Viktor1703
forfrends
Бедный мой мозг от ваших кодов :shok:
 

inx

Знающий
Сообщения
43
Репутация
12
Не подойдет? :smile:

Код:
Local $file = FileOpen("combinations.txt", 1)
$Letters = StringSplit(" ,(,),*", ",")
Combinator("", 30)
Func Combinator($Str, $MaxLength)
Dim $i
    if StringLen($Str) = $MaxLength Then
		FileWrite($file, $Str & @CRLF)
        Return
    EndIf
    For $i = 1 to $Letters[0]
        Combinator($Str & $Letters[$i], $MaxLength)
    Next
EndFunc


Для 4-30
Код:
Local $file = FileOpen("combinations.txt", 1)
$Letters = StringSplit(" ,(,),*", ",")
For $n = 4 to 30
	Combinator("", $n)
Next
Func Combinator($Str, $MaxLength)
Dim $i
    if StringLen($Str) = $MaxLength Then
		FileWrite($file, $Str & @CRLF)
        Return
    EndIf
    For $i = 1 to $Letters[0]
        Combinator($Str & $Letters[$i], $MaxLength)
    Next
EndFunc
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
длина слова не должна быть больше набора символов иначе будут повторения..
Не совсем так, похожие комбинации будут, а вот одинаковые нет. Пример комбинаций из 2-х символов "+" и "-":
длина 2 символа:
--
-+
+-
++
длина 3 символа:
---
--+
-+-
-++
+--
+-+
++-
+++
длина 4 символа:
----
---+
--+-
--++
-+--
-+-+
-++-
-+++
+---
+--+
+-+-
+-++
++--
++-+
+++-
++++
и так до бесконечности...
 

firex

AutoIT Гуру
Сообщения
943
Репутация
203
forfrends
http://autoit-script.ru/index.php?topic=3411.0
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
firex, я так и сделал :blum:


Добавлено:
Сообщение автоматически объединено:

inx, ваш вариант однозначно лучше всех предыдущих вариантов - за 15 секунд забил файл комбинациями на целых 250 мегабайт! Нотпад++ отказыватся открывать :smile:
Буду пробовать ваш вариант.
Только один вопрос: зачем Dim $i вызывать в функции? Не проще ли один раз в начале программы? Или таким способом переменная обнуляется?


Добавлено:
Сообщение автоматически объединено:

inx, спасибо, понял. А с вложением цикла это просто гениальная идея! Коротко, просто и быстродействено :smile:
 

sims

Осваивающий
Сообщения
184
Репутация
24
AutoIt интерпретируемый ЯП и довольно медленно работающий. Он не предназначен для скоростных вычислений. Если нужна скорость, то лучше компилировать программу, притом желательно в натив, а не в байт-код. Чтобы получить максимальное быстродействие, нужно работать со строками как с массивом символов.

Мне удалось добиться генерации больше 2 миллионов комбинаций в секунду. И это на одном ядре (которое при этом загружено по полной). Если задачу разделить на несколько потоков, а она хорошо делится, то можно добиться еще большей производительности.

Вместо множества вложенных циклов, лучше использовать рекурсию.
 

winstan

Эксплотатор)
Сообщения
406
Репутация
78
sims [?]
добиться генерации больше 2 миллионов комбинаций в секунду
Не плохо, у меня получалось добиваться только около 600-800 тыс комбинаций в секунду, длинной 16 символов при базе в 62 символа.
:whistle: думаю не трудно догодаться для чего я делал, вот тольк интернет не позвлял всёравно столько запросов отправлять
 

sims

Осваивающий
Сообщения
184
Репутация
24
Можете попробовать (файл внизу поста).
После запуска рядом с прогой будет создан текстовый файл GenTest.txt в который запишется результат. На диске должно быть много свободного места. Прога пишет примерно 8 ГБ в минуту при длине 30 символов.
В консоли отображаются текущие данные процесса выполнения. Для закрытия проги, закройте консоль.

http://rghost.ru/52539725
 

Z_Lenar

Продвинутый
Сообщения
209
Репутация
52
forfrends
Вот еще вариант:
Код:
$file = FileOpen('combinations.txt', 2)
$s = ''
Do
	$s = Increment($s)
	FileWriteLine($file,$s)
Until $s = '****'
FileClose($file)

Func Increment($str)
	Switch StringRight($str, 1)
		Case ' '
			Return StringTrimRight($str, 1) & '('
		Case '('
			Return StringTrimRight($str, 1) & ')'
		Case ')'
			Return StringTrimRight($str, 1) & '*'
		Case '*'
			$str = StringTrimRight($str, 1) & '#'
		Case Else
			Return ' '
	EndSwitch

	Do
		$str = StringReplace($str, '*#', '# ')
	Until @extended = 0
	Do
		$str = StringReplace($str, ')#', '* ')
	Until @extended = 0
	Do
		$str = StringReplace($str, '(#', ') ')
	Until @extended = 0
	Do
		$str = StringReplace($str, ' #', '( ')
	Until @extended = 0

	$str = StringReplace($str, '#', '  ')

	Return $str
EndFunc


Запишет от ' ' до '****' включительно
Преимущества в том что можно сохранить последнее значение при выходе из программы. Вызов Increment всегда возвратит следующий возможный вариант перебора (' ' -> '(', '(' -> ')', ')' -> '*', '*' -> ' ').
 

AZJIO

Меценат
Меценат
Сообщения
2 752
Репутация
1 146
Код:
#include <Array.au3>

$width = 8 ; ширина числа
; $sSymbol = "abcdefjhiklmnopqrstuvwxyz"
; $sSymbol = "abcdef"
$sSymbol = " ()*"
$aSymbol = StringSplit($sSymbol, '', 2)
$u = UBound($aSymbol)
$u2 = $u - 1
Local $aRz[$width + 1] = [$width]
Local $s
For $i = 1 To $aRz[0]
	$aRz[$i] = 0
Next
; _ArrayDisplay($aRz, 'aRz')
; _ArrayDisplay($aSymbol, 'aSymbol')

$timer = TimerInit()
For $i = 1 To $u ^ $width ; разрядность в стемени ширины числа захватывает все возможные варианты числа
	For $j = $width To 1 Step -1 ; формаируем массив в числах
		If $aRz[$j] > $u2 Then
			$aRz[$j] = 0
			$aRz[$j - 1] += 1
		EndIf
	Next
	; _ArrayDisplay($aRz, $i) ; пошаговая проверка
	For $j = 1 To $width
		$s &= $aSymbol[$aRz[$j]]
	Next
	$s &= @CRLF
	$aRz[$width] += 1
Next
MsgBox(0, "Время выполнения", 'Время : ' & Round(TimerDiff($timer) / 1000, 2) & ' сек')

; вывод результата
If $u ^ $width < 50 Then
	MsgBox(0, 'Сообщение', $s)
Else
	$hFile = FileOpen(@ScriptDir & '\file.txt', 2)
	FileWrite($hFile, $s)
	FileClose($hFile)
	; MsgBox(0, 'Сообщение', 'Готово')
EndIf
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
Мне удалось добиться генерации больше 2 миллионов комбинаций в секунду
sims, как вы добились такой скорости? Можете привести пример кода?
Предлагаемую вами прогамму не пробовал так как мне не нужна База из n-ного количесттва комбинаций, а нужно по ходу выполнения программы сравнивать, подходит комбинация или нет, и если да, то делать с ней определенные действия, и потом дальше продолжить поиск походящих комбинаций. Их может и не быть а могут быть десятки. Вот почему нужна скорость, так как перебрать 30^n комбинаций (где n может быть от 4 до 9), это не мало..
Как можно разделить задачу на несколько потоков? Я пробовал вариант от inx с вложенным циклом, максимальная скорость - 1300 комбинаций в секунду, ядро загрузил всего на 30-40%

winstan, а как вы добились скорости
600-800 тыс комбинаций в секунду, длинной 16 символов при базе в 62 символа
, при моей базе символов скорость увеличится в разы.


Добавлено:
Сообщение автоматически объединено:

Z_Lenar, спасибо за ваш вариант, максимальная скорость генерации получилась 34497 комбинаций в секунду, При длинне слова 30 символов скорость - 24895 комб/сек.
AZJIO, ваш вариант выдал целых 54631 комбинаций в секунду! Но это при длинне генерируемого слова 8 символов, а нужно 30. Придлинне слова в 9 символов скорость - 52428 комб/сек. Придлинне слова в 10 символов скорость - 48166 комб/сек. 11 символов - 43740 комб/сек. дальше не пробовал тенденция понятна. + кушает ОЗУ, так как создается в памяти масив со всеми комбинациями, и лишь в конце записывается в файл.
Но все же это не 2 млн комбинаций... :-X
 

sims

Осваивающий
Сообщения
184
Репутация
24
forfrends [?]
sims, как вы добились такой скорости? Можете привести пример кода?
Ранее я писал что AutoIt не обладает высоким быстродействием. Такая уж у него архитектура. И если хотите получить миллионы комбинаций в секунду, перепишите код на один из компилируемых ЯП, обладающих должным быстродействием.
Код по сути тупо скопипастил переписал из кода inx с учетом некоторых моментов, ускоряющих работу (например, отказался от строк в пользу массива).
Код:
Global Dim Result.a(32)

Procedure Gen(Pos, MaxLen)
  
  If Pos>=MaxLen 
    If WriteData(0, @Result(), 32) <> 32
      MessageRequester("", "Ошибка записи в файл")
      End
    EndIf
    ProcedureReturn
  EndIf
  
  For i=0 To 3
    Result(Pos)=PeekA(?Label+i)
    Gen(Pos+1, MaxLen)
  Next
  
EndProcedure

If CreateFile(0, GetPathPart(ProgramFilename())+"GenTest.txt")=0
  MessageRequester("", "Ошибка создания файла")
  End
EndIf

Result(30)=#CR : Result(31)=#LF

Gen(0, 30)
MessageRequester("", "Работа программы завершена")
End

DataSection
  Label:
  Data.a ' ', '(', ')', '*'
EndDataSection
Только что проверил. На самом деле этот код выдает 40 миллионов комбинаций в секунду (при длине 30 символов) на одном ядре процессора (если использовать многопоточность, то скорость еще больше возрастет на многоядерных процессорах). До двух миллионов снижает запись на винт.
 
Автор
F

forfrends

Новичок
Сообщения
176
Репутация
3
Спасибо за пример, но я кроме Аутоита нчего не знаю. Пример написан на Си++?
Какой язык посоветуете?
 
Статус
Закрыто для дальнейших ответов.
Верх