[dom] Промежуточные результаты

[Дмитрий Мурыгин]

Еще некоторые результаты:

1. Была найдена статья (https://scholarship.rice.edu/bitstream/handle/1911/96345/TR06-38870.pdf?sequence=1), посвященная алгоритму, который реализован в файлах библиотеки all.h. Согласно этой статье, алгоритм Ленгауэра-Тарьяна, который мы реализуем, на практике работает медленнее алгоритма статьи. При этом, алгоритм, основанный на микродеревьях и имеющий линейную сложность, на практике оказывается медленнее даже алгоритма Ленгауэра-Тарьяна. Соответственно, какой бы алгоритм из найденных мы не реализовали, на практике он окажется медленнее уже реализованного.
2. После дополнительного тестирования имеются следующие результаты нашей реализации алогритма Ленгауэра-Тарьяна:
    1) Тест из 4000 вершин. Работает в 3 раза медленнее.
    2) Тест из 100000 вершин. Работает в 100 раз медленнее.
  На данный момент идет поиск улучшения нашей реализации. Будем стремиться к результату на 30% медленнее.


--
С уважением,
Дмитрий Мурыгин
427 группа, IV курс, ВМК, МГУ
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://compilers.ispras.ru/pipermail/dom/attachments/20180411/84cfb193/attachment.html>