41 Востаннє редагувалося leofun01 (24.11.2019 00:02:07)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

ReAl написав:

основні втрати часу виконання не тут

Я теж думаю, що найбільші втрати не в перестановках.
Здається проблема в FlipRotate16D (або в FiniteGroupExtension). Але я поки не знаю як це можна переписати.
В методи GetFlip і GetRotate (в класах FlipRotate*) навіть не дивіться, я вже бачу, що мені доведеться їх видалити і створити щось нове, що повністю замінить ті 2 методи.

ReAl написав:

• в них дві зайві команди через те, що short — виправте на (unsigned short) у третій і ці дві зайві команди з'являться

В C# коді я поки залишу short, бо хочу, щоб код був CLS-compliant.

Подякували: 221VOLT1

42

Re: Абстрактна алгебра, теорія груп, скінченні групи.

А профайлером не пробували пройтися? Все ж це краще ніж гадати  %)

Подякували: leofun01, 221VOLT2

43

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Щойно відкрив для себе нові інструменти в VisualStudio :[ *PARDON*

Запустив профілер, результати:
get_CycleLength : 0.936 // int cLen = t.CycleLength;
+ GetLengthTo     : 0.927 // return this.GetLengthTo<T>(None);
  + Add             : 0.830 // sum = sum.Add(t);
    + op_Addition     : 0.332 // p + other.Permutation
    + GetNextVertex   : 0.374 // p.GetNextVertex<P>(other.Vertex)

Тобто 70% процесорного часу витрачається на ті дві операції:

Їх вже нема куди оптимізувати (в межах самого C#).
А це означає, що пора мені переходити на C.

Всім дякую, можна більше не шукати, і спокійно лягати спати.

Потрібний принципово новий підхід до задачі, а це вже моя робота. [:}

Подякували: 221VOLT, ostap34PHP, /KIT\3

44

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Я так розумію, той профілер дає дуже приблизні оцінки, одного разу показав результати (33% + 37%), другого (20% + 52%), третього (45% + 21%), і це при одинакових параметрах (на вхід було подано число 8).

Подякували: 221VOLT1

45

Re: Абстрактна алгебра, теорія груп, скінченні групи.

На жаль, я не знаю цієї математики (ніколи такої не вчив, про групи/поля/кільця і все таке знаю дуже мало з випадкових джерел).
Та ще й за межі C (й пів дюжини асемблерів) далеко не заходив.
Тому мені важко читати цей проект.

Подякували: leofun01, 221VOLT, ostap34PHP3

46 Востаннє редагувалося leofun01 (27.11.2019 07:46:27)

Re: Абстрактна алгебра, теорія груп, скінченні групи.

ReAl написав:

не знаю цієї математики (ніколи такої не вчив, про групи/поля/кільця ...).

Про поля і кільця: я й сам їх ще не вивчив. Поки тільки з групами бавлюся. Не можу пригадати, щоб ми в універі цю тему проходили.

ReAl написав:

важко читати цей проект.

Можу собі уявити. Навіть мені іноді важко його читати.

Стосовно оптимізації: вдалося прискорити виконання програми в рази ... (гілка develop)

dim : Рази
  6 : 3
  7 : 3.5
  8 : 4
  9 : 4.5
 10 : 5

я так розумію, тенденція буде зберігатись аж до dim=16.
Результатом я задоволений, бо тепер програма обробляє до 68000 688000 елементів за секунду, і це з викликами CycleLength (яка є досить важкою операцією в межах проекту), а без неї програми будуть просто літати.

leofun01 написав:

Захотів розвернути масив 500Мб => 100мсек => готово.

:) Як же смішно це тепер виглядає. Зараз можу розвертати десятки масивів довільних розмірів за 1мсек. От тільки класи для зручної роботи з масивами ще не дописані.


upd: Виправив кількість елементів, які програма обробляє за секунду.
Група трансформацій 11-вимірного куба (~8.175*10^10) була опрацьована за 33 години (на Intel Core i5, на одному ядрі із 4-х віртуальних).

Подякували: 221VOLT, ReAl2

47

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Трохи підтягнув себе по Haskell'ю (типи даних, монади) і тепер мені соромно за те, що я колись ляпнув про нього :

Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.

:[

Якраз для задач по теорії груп він прекрасно підходить.

Подякували: 0xDADA11C7, 221VOLT, /KIT\3

48

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Класифікація поворотів гіперкуба
Просто хотів, щоб ви це бачили.

Анімація поворотів гіперкуба (*.gif, 4D)

Simple4A.gif  Simple4B.gif
Simple4C.gif  Simple4D.gif

NonSimple4A.gif NonSimple4C.gif NonSimple4E.gif

Подякували: wander, koala, 221VOLT, dot, Arete, Betterthanyou, ping, vitek8

49

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Я на дискретній математиці любив таке малювати.
Щоправда, 7-вимірний гіперкуб так жодного разу і не домалював.

Подякували: leofun01, 221VOLT2

50

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Красиво.

Подякували: 221VOLT, leofun012

51

Re: Абстрактна алгебра, теорія груп, скінченні групи.

А ті кольорові точки що позначають?

Подякували: leofun01, 221VOLT2

52

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Згідно лінку, виглядає, що то центри сторін 3х вимірних кубів.

Подякували: leofun01, 221VOLT2

53

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Vo_Vik написав:

А ті кольорові точки що позначають?

На всіх анімаціях крім останної це центри гіперкубів у підпросторах заданої вимірності

████ : 0D (точки | вершини)
████ : 1D (центри відрізків | ребр)
████ : 2D (центри квадратів)
████ : 3D (центри кубів)

На останній анімації точки прив'язані до координат в межах 2D підпросторів. Допомагають візуально не загубити квадрати, яким вони належать.

(для коректного відображення цього повідомлення потрібно ввімкнути CSS)

Подякували: 221VOLT1

54

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Читаючи літературу (суху теорію) іноді складно зрозуміти, що там описано і як з цим працювати.
Ось кілька ресурсів, які допоможуть розібрати Orb і Stab :

Подякували: 221VOLT1

55

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Життя - біль. :( Всі дані вказують на те, що в формулах (для обчислення кількості і розмірів класів спряженості) будуть функції з теорії чисел. Тобто ще й туди доведеться пірнути.
Але є і хороші новини: я знайшов спосіб не перебирати всі комбінації.

Подякували: 221VOLT1

56

Re: Абстрактна алгебра, теорія груп, скінченні групи.

leofun01 написав:

Трохи підтягнув себе по Haskell'ю (типи даних, монади) і тепер мені соромно за те, що я колись ляпнув про нього :

Haskell вилетів зі списку першим, через відсутність ООП, і складність підтримки проекту.

:[

Якраз для задач по теорії груп він прекрасно підходить.

сьогодні я познайомився в хаскелі з моноїдами )

прикольненько :)
росту по-трішечки
(споглядаючи цю всю круту математику, наче місяць в небі за вікном )) )

радію з того, що маю справу з такою чудесною мовою,
яку проектували з думкою про користувача цієї мови
(щоб програміст менше мучався)

Подякували: 0xDADA11C7, leofun012

57

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Думки в голос

Що ми маємо по групах трансформацій (симетрій) гіперкубів:

  • В англомовних джерелах їх можна знайти за назвами:

    • hyperoctahedral group

    • hypercube symmetries group

    • automorphism group of the n-dimensional hypercube

    • geometric automorphism group of the hypercube

  • Кількість елементів в групах відома (A000165) n!*2^n.

  • Кількість класів спряженості ніби відома (A000712), але треба розібратися як вони їх порахували.

  • Для обчислення кількості елементів з заданими циклами найефективніше використовувати розбиття (A000041, A211992). Без них довелось би робити повний перебір.

  • Кожен елемент групи може бути представлений як (p,v), де p - перестановка вимірів, v - номер вершини гіперкуба. Для n-вимірного куба: перестановка має довжину n+; номер вершини може бути представлений послідовністю n біт.

  • Кожен елемент групи (p,v) має довжину циклу рівно в { 1 або 2 } рази більшу ніж довжина циклу перестановки p (не плутати з довжиною самої перестановки).

Що треба знайти:

  1. Алгоритм генерації перестановок з заданими довжинами циклів.

  2. Кількість елементів в кожному класі спряженості групи.

Наче не багато залишилося, але в мене вже сил нема.
Тільки не подумайте, що це я свою роботу на вас скидую. Це скоріше нагадування мені майбутньому, щоб не вийшло як в попередні рази.

Результати залию на GitHub протягом 3-х днів.

Подякували: 221VOLT1

58

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Якось так. Але це не все, решту додам пізніше. Не очікував, що обчислення займуть так багато часу. *SCRATCH*

Подякували: 221VOLT1

59

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Кількість класів спряженості ніби відома (A000712), але треба розібратися як вони їх порахували.

По цьому списку буду перевіряти чи правильно порахував класи спряженості.

Кожен елемент групи (p,v) має довжину циклу рівно в { 1 або 2 } рази більшу ніж довжина циклу перестановки p

Вдалося довести. Це випливає з позначення елементів групи і способу їх додавання (композиції).

60

Re: Абстрактна алгебра, теорія груп, скінченні групи.

Цікава стаття про гіпероктагедральні групи (про симетрії гіперкуба). Деякі ідеї в нас зпівпали (наприклад: нумерація вершин гіперкуба).