Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Блоги > e4xu

Всякие разные штуки сомнительной полезности сделанные в свободное от работы время.
Оценить эту запись

Цикл в стиле Python

Запись от wvxvw размещена 17.12.2011 в 15:42

Где-то когда-то очень давно мне попалась на глаза интересная идея по оптимизации циклов. Не знаю почему именно она у меня ассоциируется с Python. Возможно, если вы лучше с ним знакомы, то поделитесь знаниями.
Идея заключалась в том, что вместо того, чтобы проверять условие выхода из цикла на каждом витке, выйти из цикла по ошибке. Некоторые ошибки, такие как RangeError в AS3 это оружие, которое редко когда удается использовать в мирных целях.
Ниже - мой тест производительности разных вариантов одного и того же цикла.
Поразительным образом, вариант с выходом по ошибке оказался на много быстрее остальных...

Код AS3:
package
{
	import flash.display.Sprite;
	import flash.utils.getTimer;
 
	public class PythonLoopTest extends Sprite
	{
		public function PythonLoopTest()
		{
			super();
			this.test();
		}
 
		private function test():void
		{
			var t:int;
			var vector:Vector.<int> = new Vector.<int>(1e7, true);
 
			for (var i:int = 1e7 - 1; i >= 0; i--)
				vector[i] = 1e7 - i;
			t = getTimer();
			testPythonLoop(vector);
			trace(getTimer() - t);
			t = getTimer();
			testFor(vector);
			trace(getTimer() - t);
			t = getTimer();
			testWhile(vector);
			trace(getTimer() - t);
			t = getTimer();
			testPlainFor(vector);
			trace(getTimer() - t);
//			254
//			1186
//			1174
//			1191
		}
 
		private static function testPythonLoop(vector:Vector.<int>):void
		{
			var position:int;
 
			try
			{
				for (;vector[position] = vector[position++];) { };
			}
			catch (error:RangeError) { };
		}
 
		private static function testFor(vector:Vector.<int>):void
		{
			for (var position:int = vector.length - 1; 
				position >= 0; 
				vector[position] = vector[position--]) { };
		}
 
		private static function testWhile(vector:Vector.<int>):void
		{
			var position:int = vector.length - 1;
 
			while (position >= 0)
				vector[position] = vector[position--];
		}
 
 
		private static function testPlainFor(vector:Vector.<int>):void
		{
			var size:int = vector.length;
 
			for (var position:int;
				position < size; 
				vector[position] = vector[position++]) { };
		}
	}
}
Просто для справки:

Код:
#! /usr/bin/python

numbers = [1, 2, 3]
mask = 'key: %(key)u value: %(value)u'
number = 0

print 'first loop:'

for index in range(len(numbers)):
   print mask % { 'key': index, 'value': numbers[index] }

print 'second loop:'

try:
    while True:
        print mask % { 'key': number, 'value': numbers[number] }
        number += 1
except Exception, e:
    print 'finished'
Так пожалуй, выглядел бы код на Python, я не нашел никаких предпосылок к тому, чтобы второй вариант использовался чаще. Да и вообще не нашел таких
Всего комментариев 14

Комментарии

Старый 17.12.2011 23:21 TanaTiX вне форума
TanaTiX
 
Аватар для TanaTiX
Немного подправил 2ю функцию - получил другие результаты:

Код AS3:
		private static function testFor(vector:Vector.<int>):void
		{
			var length:int = vector.length - 1;
			for (var position:int = 0; position < length; vector[position] = vector[position++])
			{ };
		}
Цитата:
151
108
876
867
Могу объяснить несколькими моментами. Если не выносить в переменную значение длины массива, то при каждом обращении мы должны его определять, т.е. определять свойство length массива/вектора. Если переменную выносить отдельно - все происходит быстрее. И где-то читал, что сложение происходит быстрее вычитания. И оператор <=. Не уверен как именно он работает, но была информация, что при таком условии происходит 2 проверки вместо одной.
С другими методами не баловался, но учитывая, что их показатели примерно одинаковы, то можно предположить схожее поведение в похожих условиях.
Старый 18.12.2011 00:00 silin вне форума
silin
 
Аватар для silin
>>Если не выносить в переменную значение длины массива, то при каждом обращении мы должны его определять
не причем здесь это, обращение к vector.length только одно, при инициализации цикла
вот так будет тот же результат
Код AS3:
private static function testFor(vector:Vector.<int>):void
{
	for (var position:int = vector.length - 1; position >= 0; vector[position] = vector[position--]) { };
}
но что это за магическое ускорение при записи цикла в одну строчку - полная загадка
Старый 18.12.2011 00:01 wvxvw вне форума
wvxvw
 
Аватар для wvxvw
А чем это вариант принципиально отличается от testPlainFor()? Ну, кроме того, что не заглядывает в последний элемент вектора Странно, как такой результат мог получиться.

Есть предположение, что влияют опкоды-указатели строки Надо бы потестить в релизном режиме, просто лень было перекомпилировать.
Обновил(-а) wvxvw 18.12.2011 в 00:04
Старый 18.12.2011 00:15 silin вне форума
silin
 
Аватар для silin
дада, в релизной флешке результат
232
175
161
162

а некоторые уже руки стали потирать как мы все ускорим/оптимизируем
Старый 18.12.2011 00:28 samana вне форума
samana
 
Аватар для samana
Цитата:
Сообщение от silin
обращение к vector.length только одно, при инициализации цикла
Получается что нет, и обращение происходит постоянно каждый раз при очередном цикле. В примерчике, выводиться только ноль и всё.
Код AS3:
var vec:Vector.<int> = Vector.<int>([1,2,3,4,5,6,7,8,9]);
for (var i:int = 0; i < vec.length; i++) 
{
	vec.splice(0,vec.length);
	trace(i);//0....
}
Старый 18.12.2011 00:40 silin вне форума
silin
 
Аватар для silin
в этом раскладе да, но речь была о варианте for (var i:int = vec.length-1; i >=0; i--)
Старый 18.12.2011 01:09 samana вне форума
samana
 
Аватар для samana
Цитата:
Сообщение от silin
в этом раскладе да, но речь была о варианте for (var i:int = vec.length-1; i >=0; i--)
Вы правы, прошу прощения, не доглядел... )
Старый 18.12.2011 01:10 wvxvw вне форума
wvxvw
 
Аватар для wvxvw
Хех, жалко что нет инстументов управлять "джампами". Так бы можно было вместо исключения просто перейти на метку за циклом. Т.е. проверка-то все равно неизбежна, но в случае с смассивом мы проверяем 2 раза. Один раз счетчик с индексом сверяем, второй раз - не вышли ли за пределы массива.
Старый 18.12.2011 21:55 dimarik вне форума
dimarik
 
Аватар для dimarik
Хочется возвратиться к машкодам? )
Старый 19.12.2011 01:22 wvxvw вне форума
wvxvw
 
Аватар для wvxvw
Ну как бы в этом случае видно, что делается лишняя работа - жалко однако И это совсем не обязательно машинные коды, в том же eLisp'e есть например такое:

Код:
(let ((i 0))
  (catch 'break
    (while t
      (incf i)
      (when (> i 42) throw 'break))))
Но если бы мы не объявили метку break, то из цикла бы выходили дальше по стеку. В eLisp'e по другоми и не выйти досрочно из цикла
Старый 19.12.2011 14:40 iNils вне форума
iNils
 
Аватар для iNils
Цитата:
А чем это вариант принципиально отличается от testPlainFor()? Ну, кроме того, что не заглядывает в последний элемент вектора Странно, как такой результат мог получиться.
Берем твой код
Код AS3:
private static function testFor(vector:Vector.<int>):void
{
	for (var position:int = vector.length - 1; 
		position >= 0; 
		vector[position] = vector[position--]) { };
}
И получаем 788 (на моей машине).
Теперь всего лишь пишем for в одну строчку
Код AS3:
private static function testFor(vector:Vector.<int>):void
{
	for (var position:int = vector.length - 1; position >= 0; vector[position] = vector[position--]) { };
}
Результат - 93

Поэтому можешь дальше продолжать писать по 80 символов строке
Старый 19.12.2011 15:02 silin вне форума
silin
 
Аватар для silin
дык это же дебаговые штуки (что-то там с трассировкой строк), в релизной сборке их нет, можно хоть в 10 строк писать -результат не меняется

ps. надо бы сабж переименовать во что-то типа "как получить 10кратный прирост производительности в дебаговом режиме" Ж)
Старый 19.12.2011 15:05 iNils вне форума
iNils
 
Аватар для iNils
Так результаты wvxvw в дебаговом режиме и были представлены, иначе сразу же было видно, что писать просто не о чем.
Старый 20.12.2011 01:00 wvxvw вне форума
wvxvw
 
Аватар для wvxvw
Мы ж вроде уже выяснили, что это изза того, что код выполняется в отладчике...
А по поводу "не о чем писать" - ну, я не знаю, по-моему подход к решению проблемы не традиционный может быть интересен вне зависимости от результата. Кто знает, может если копнуть глубже - окажется возможным соптимизировать именно таким способом, просто об этом раньше не подумали.

ЗЫ. Я за много лет кропотливого труда не написал ни одного цикла с миллионными итерациями, только для тестов. А сверять файлы новые / старые из прошлой / позапрошлой ревизии приходится чуть более чем каждый день... Мне удобно, когда я могу три файла одновременно видеть на экране и не скроллить.
 

 


Часовой пояс GMT +4, время: 00:31.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.