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

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

ReAl написав:

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

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

ReAl написав:

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

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

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

leofun01 вебсайт

42 Відповідь від wander

  • wander
  • wander
  • Replace Team
  • Поза форумом
  • Звідки: No-man's land
  • Дата реєстрації: 28.02.2019
  • Повідомлень: 1 349
    • Репутація: 1276

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

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

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

43 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

leofun01 вебсайт

44 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

leofun01 вебсайт

45 Відповідь від ReAl

  • ReAl
  • ReAl
  • Видатний діяч Броунівського Руху
  • Поза форумом
  • Звідки: Бровари
  • Дата реєстрації: 27.04.2016
  • Повідомлень: 1 503
    • Репутація: 1884

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

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

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

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

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

leofun01 вебсайт

47 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

:[

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

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

leofun01 вебсайт

48 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

leofun01 вебсайт

49 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 780
    • Репутація: 13451

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

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

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

koala вебсайт

50 Відповідь від dot

  • dot
  • dot
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 02.09.2017
  • Повідомлень: 937
    • Репутація: 490

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

Красиво.

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

dot вебсайт

51 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 850
    • Репутація: 2513

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

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

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

Vo_Vik вебсайт

52 Відповідь від Vo_Vik

  • Vo_Vik
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 01.10.2012
  • Повідомлень: 4 850
    • Репутація: 2513

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

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

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

Vo_Vik вебсайт

53 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

Vo_Vik написав:

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

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

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

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

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

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

leofun01 вебсайт

54 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

leofun01 вебсайт

55 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

leofun01 вебсайт

56 Відповідь від 221VOLT

  • 221VOLT
  • 221VOLT
  • ♥ pattern matching
  • Поза форумом
  • Звідки: Львів
  • Дата реєстрації: 26.09.2015
  • Повідомлень: 2 719
    • Репутація: 1873

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

leofun01 написав:

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

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

:[

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

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

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

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

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

221VOLT вебсайт

57 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

leofun01 вебсайт

58 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

leofun01 вебсайт

59 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

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

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

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

leofun01 вебсайт

60 Відповідь від leofun01

  • leofun01
  • leofun01
  • Replace Team
  • Поза форумом
  • Дата реєстрації: 15.03.2014
  • Повідомлень: 3 444
    • Репутація: 2771

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

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

leofun01 вебсайт