Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34

[branch] Алгоритм A-star (А*), оптимизация

07.02.2015, 22:32. Показов 3048. Ответов 31
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Данная тема является ответвлением темы: Алгоритм A-star (А*), оптимизация

x5reunion, Кстати,
Вместо
C#
1
public Point TileCoordinates { get; set; }
быстрее будет работать
C#
1
public Point TileCoordinates;
2
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
07.02.2015, 22:32
Ответы с готовыми решениями:

Алгоритм A-star (А*), оптимизация
Всем привет пытаюсь допилить алгоритм Astar и подстроить его под свои нужды. Я добавил почти весь код, если вдруг кому то будет...

Dragon Branch
Здравствуйте, появилась проблема с программой Dragon Branch. В браузерах появилась реклама на всех страницах, переадресация на другие сайты...

Вместо master branch
Добрый день! подскажите пожалуйста, как можно исправить ошибку (работаю в eclipse с ruby on rails) создаю новый проект File - New...

31
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
07.02.2015, 23:09
Storm23, не будет.
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 00:17  [ТС]
Цитата Сообщение от Psilon Посмотреть сообщение
Storm23, не будет.
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using System;
using System.Diagnostics;
 
namespace ConsoleApplication161
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = new Foo();
            var b = new Boo();
 
            var sw = Stopwatch.StartNew();
            for (int i = 0; i < 10000000; i++)
                a.A = i;
            sw.Stop();
 
            Console.WriteLine(sw.Elapsed);
 
            sw = Stopwatch.StartNew();
            for (int i = 0; i < 10000000; i++)
                b.A = i;
            sw.Stop();
 
            Console.WriteLine(sw.Elapsed);
 
            Console.ReadLine();
        }
    }
 
    class Foo
    {
        public int A { get; set; }
    }
 
    class Boo
    {
        public int A;
    }
}
1
3 / 3 / 1
Регистрация: 25.03.2014
Сообщений: 45
08.02.2015, 01:23
Спасибо впринципе мне нужно будет добавлять еще пару вещей все это может оказаться полезным чтобы выиграть время.
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 01:35
Storm23,
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация  
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 01:41
Ну и да, нормальный бенч (с учетом перестановок и т.п.):
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
using System;
using System.Diagnostics;
 
namespace ConsoleApplication161
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 100, M = 1000000;
            var a = new Foo();
            a.A = 10;
            a.B = 10;
            Console.WriteLine("{0} - {1}", a.A, a.B);
                       
            unchecked
            {
                int trash = 0;
                Stopwatch sw1 = new Stopwatch(), sw2 = new Stopwatch();
                for (int i = 0; i < N; i++)
                {
                    if (i%2 == 0)
                    {
                        for(int j = 0; j < M; j++)
                        {
                            sw1.Start();
                            a.A = j;
                            sw1.Stop();
 
                            sw2.Start();
                            a.B = j;
                            sw2.Stop();
 
                            trash += a.A + a.B;
                        }
                    }
                    else
                    {                        
                            for (int j = 0; j < M; j++)
                            {
                                sw2.Start();
                                a.B = j;
                                sw2.Stop();
 
                                sw1.Start();
                                a.A = j;
                                sw1.Stop();
 
                                trash += a.A + a.B;
                            }                        
                    }
                }
                Console.WriteLine(trash);
                Console.WriteLine(sw1.Elapsed);
                Console.WriteLine(sw2.Elapsed);
            }
        }
    }
 
    class Foo
    {
        public int A { get; set; }
        public int B;
    }
}
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация  
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 01:56
http://ideone.com/uOuFpK

Даже на моно разница составляет три тысячную, причем в пользу свойства

В общем и целом разница на уровне статистической ошибки.
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 02:03  [ТС]
Psilon,
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация   [branch] Алгоритм A-star (А*), оптимизация  
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 02:05
Storm23, возьми код с ideone по ссылке, какие у тебя результаты будут? Потому что тот код, что ты привел в качестве бенча - некорректный.
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 02:05  [ТС]
Цитата Сообщение от Psilon Посмотреть сообщение
нормальный бенч
C#
1
2
3
                            sw1.Start();
                            a.A = j;
                            sw1.Stop();
Вы меряете единичное присвоение поля/свойства с помощью Stopwatch?
Ну сами подумайте - ведь вызов и отработка вызовов sw1.Start() и sw1.Stop() - намного дольше чем присвоение. Т.е. фактически вы меряете эти методы а не присвоение.
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 02:07
http://habrahabr.ru/company/enterra/blog/191636/

Добавлено через 1 минуту
Цитата Сообщение от Storm23 Посмотреть сообщение
Вы меряете единичное присвоение поля/свойства с помощью Stopwatch?
Ну сами подумайте - ведь вызов и отработка вызовов sw1.Start() и sw1.Stop() - намного дольше чем присвоение. Т.е. фактически вы меряете эти методы а не присвоение.
ок:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using System;
using System.Diagnostics;
 
namespace ConsoleApplication161
{
    class Program
    {
        static void Main(string[] args)
        {
            const int N = 100, M = 100000, K = 100;
            var a = new Foo {A = 10, B = 10};
 
            unchecked
            {
                int trash = 0;
                Stopwatch sw1 = new Stopwatch(), sw2 = new Stopwatch();
                for (int i = 0; i < N; i++)
                {
                    if (i % 2 == 0)
                    {
                        for (int j = 0; j < M; j++)
                        {
                            sw1.Start();
                            for (int k = 0; k < K; k++)
                            {
                                a.A = j + k;
                            }
                            sw1.Stop();
 
                            sw2.Start();
                            for (int k = 0; k < K; k++)
                            {
                                a.B = j + k;
                            }
                            sw2.Stop();
 
                            trash += a.A + a.B;
                        }
                    }
                    else
                    {
                        for (int j = 0; j < M; j++)
                        {
                            sw2.Start();
                            for (int k = 0; k < K; k++)
                            {
                                a.B = j + k;
                            }
                            sw2.Stop();
 
                            sw1.Start();
                            for (int k = 0; k < K; k++)
                            {
                                a.A = j + k;
                            }
                            sw1.Stop();
 
                            trash += a.A + a.B;
                        }
 
                    }
                }
                Console.WriteLine(trash);
                Console.WriteLine("Время доступа к свойству = {0}", sw1.Elapsed);
                Console.WriteLine("Время доступа к полю = {0}", sw2.Elapsed);
                Console.WriteLine("Разница между ними составляет {0:P} в пользу {1}", Math.Abs(1 - sw1.ElapsedTicks / (double)sw2.ElapsedTicks), sw1.Elapsed < sw2.Elapsed ? "Свойства" : "Поля");
            }
        }
    }
 
    struct Foo
    {
        public int A { get; set; }
        public int B;
    }
}
На моем компе разница составляет тысячные доли, при любых значениях параметров M N K, причем иногда в пользу поля, иногда - свойства. В целом - на уровне погрешности.
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация  
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 02:12  [ТС]
Psilon, Что я делаю не так?
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация  
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 02:18
Storm23, даже хз, у меня вот тоже аномалии случаются



можно попробовать выставить параметры побольше, чтобы он хотя бы секунд 20 работал.


А вообще разницы в релизе быть не должно, т.к. все авто-свойства инлайнятся, и методы становятся теми же полями. Компилятор всегда инлайнит методы, тело которых меньше 64 байт, это в стандарте описано. Пока гуглил нашел тему прямо подходящую:
http://stackoverflow.com/quest... properties

Алсо мнение ганса - самого прошаренного человека в шарпе (после Скита, Хелсберга и Липперта)
http://stackoverflow.com/a/3265377/2559709

Perf is a non-issue and should never be considered.
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 02:24  [ТС]
Цитата Сообщение от Psilon Посмотреть сообщение
даже хз, у меня вот тоже аномалии случаются
Psilon, это не аномалия. Я давно заметил что поля в два раза быстрее работают чем свойства на моей машине. Кроме того я это наблюдал это и на машинах ползователей. Ваш проц может быть дает одинаковый результат - это тоже возможно. Какой отсюда мы можем сделать вывод? Отсюда можно сделать вывод о том, что на некторых машинах скорость доступа к полю и свойствам - одинакова, а на некоторых - доступ к полю быстрее. А поскольку мы хотим что бы алгоритм работал максимально эффективно - мы должны использовать поля вместо свойств. Логично?
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 02:31
Storm23, не логично Обясняю:

1. Даже в теории все авто-свойства инлайнятся, и на уровне маш. команд доступ к полю не отличается от доступа к свойствам.
2. Если перейти к практики, то это подтверждается не только на моей машине, а у всех людей, что я встречал - можете даже ознакомиться с темой, которая уже поднималась https://www.cyberforum.ru/post3293683.html
3. Если откинуть нашу с вашей практику и посмотреть в гугл, то все бенчмарки говорят за идентичность результатов
4. Один из крутейших людей мире .Net говорит, что это даже не микро, а нано-оптимизация, которая в реальном приложении никогда не возникнет. И я с ним согласен - у полей есть куча минусов, а плюсов в теории нет, и на практике они сомнительны.

Выводы - у вас на компьютере возможна какая-то аномалия (вроде версии фреймворка 1.1 - понятия не имею ), и в данном вопросе вы не совсем правы.
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 02:31  [ТС]
Что касается инлайна свойств. Смотрим ildasm код:
Что тут сказать? Я бы конечно мог верить тем кто говорят про инлайн, но своим глазам я верю больше
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация  
0
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 02:48
Storm23, при отладке всегда запускается дебаг-версия... Хвостовые рекурсии тоже шарп умеет разворачивать, только вот в дебаге он этого никогда не покажет

И это не ildasm, а обычный dasm. На уровне IL'а инлайнинг не производится, он делается JIT'ом

Ну а чтобы не быть голословным, залез посреди ночи на рабочие компы и вот результаты. Программа для тестирования прилагается
Миниатюры
[branch] Алгоритм A-star (А*), оптимизация   [branch] Алгоритм A-star (А*), оптимизация   [branch] Алгоритм A-star (А*), оптимизация  

[branch] Алгоритм A-star (А*), оптимизация  
Вложения
Тип файла: rar test.rar (2.9 Кб, 6 просмотров)
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 03:23  [ТС]
Ваш exe у меня тоже дает выигрыш поля но не очень большой. Около 3%.
А попробуйте-ка мой exe.
Вложения
Тип файла: zip ConsoleApplication163.zip (2.6 Кб, 7 просмотров)
1
Master of Orion
Эксперт .NET
 Аватар для Psilon
6102 / 4958 / 905
Регистрация: 10.07.2011
Сообщений: 14,522
Записей в блоге: 5
08.02.2015, 03:27
Storm23,
262620032
Время доступа к свойству = 00:00:00.4637754
Время доступа к полю = 00:00:00.4571035
Разница между ними составляет 1,46% в пользу Поля
0
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
08.02.2015, 03:36  [ТС]
Цитата Сообщение от Psilon Посмотреть сообщение
Разница между ними составляет 1,46% в пользу Поля
Все таки в пользу поля
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
08.02.2015, 03:36
Помогаю со студенческими работами здесь

Типы оптимизация: черная оптимизация, серая оптимизация и белая оптимизация
Много много лет назад, на заре становления профессии &quot;оптимизатора&quot; в какой то умной книжке был создан миф. Это миф о цветовой индефикации...

Алгоритм и его оптимизация
Проблемы с воображением ((( Нужно написать программу а потом её как либо оптимизировать что бы при сравнении получившиеся программ в...

Оптимизация, алгоритм не проходит по времени
Последовательность a1, a2, a3, … , an-1, an называется пилообразной, если она удовлетворяет одному из следующих условий: 1) a1 &lt; a2...

Оптимизация функции (Генетический алгоритм)
Задание вот такое: Дана следующая функция: 1. Провести оптимизацию заданной функции в Matlab (с помощью генетического алгоритма): найти...

Оптимизация расшифровки файла | алгоритм хаффмана
Привет, форумчани! Собственно сразу к вопросу. У меня имеется зашифрованный файл весом 390 КБ и считывание (расшифровка) в режиме debug ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Подстановка значения реквизита справочника в табличную часть документа
Maks 10.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .
Очистка реквизитов документа при копировании
Maks 09.04.2026
Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru