Приложение odlk3

Message boards : News : Приложение odlk3
Message board moderation

To post messages, you must log in.

1 · 2 · 3 · Next

AuthorMessage
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 78 - Posted: 23 Jun 2017, 8:45:07 UTC

odlk3 является немного изменённым приложением odlk2. Во входном файле задания помимо начального квадрата и количества проверяемых квадратов добавлен граничный квадрат. Приложение завершает работу, если проверено необходимое количество квадратов или если дошло до граничного квадрата. Такая модификация позволила быстро генерировать задания - вместо перебора необходимого количества квадратов генератор пропускает довольно большой диапазон для следующего задания. Количество квадратов в диапазоне точно не известно, но примерно равно 10^8. При получении результата ассимилятор, если приложение не дошло до граничного квадрата, создаёт новое задание, где в качестве начального квадрата будет последний проверенный, а граничный остаётся тем же самым. Сейчас в задании проверяется по 10^6 квадратов. Таким образом из одного задания, созданного генератором получается примерно ещё 100 заданий, которые будут созданы при получении результатов.
ID: 78 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 79 - Posted: 23 Jun 2017, 9:31:28 UTC - in response to Message 78.  
Last modified: 23 Jun 2017, 9:32:22 UTC

Эта идея бродила у меня в голове с самого начала :)
Да, конечно: самогенерация! Задания по проверке на ОДЛК одновременно генерируют задания для следующей проверки на ОДЛК.
Собственно, это то же самое, что делали мы в ручном проекте с помощью пакетного файла.

Тут главное - правильно следить за граничными квадратами.
В пакетном файле всё чётко выполняется.
ID: 79 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
citerra

Send message
Joined: 18 May 17
Posts: 29
Credit: 142,510
RAC: 58
Message 80 - Posted: 23 Jun 2017, 10:09:31 UTC - in response to Message 78.  

odlk3 является немного изменённым приложением odlk2. Во входном файле задания помимо начального квадрата и количества проверяемых квадратов добавлен граничный квадрат. Приложение завершает работу, если проверено необходимое количество квадратов или если дошло до граничного квадрата. Такая модификация позволила быстро генерировать задания - вместо перебора необходимого количества квадратов генератор пропускает довольно большой диапазон для следующего задания. Количество квадратов в диапазоне точно не известно, но примерно равно 10^8. При получении результата ассимилятор, если приложение не дошло до граничного квадрата, создаёт новое задание, где в качестве начального квадрата будет последний проверенный, а граничный остаётся тем же самым. Сейчас в задании проверяется по 10^6 квадратов. Таким образом из одного задания, созданного генератором получается примерно ещё 100 заданий, которые будут созданы при получении результатов.

Вот два задания
input_odlk3_65_0002440.txt
65 1000000
0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
1 9 2 5 3 4 7 0 6 8
2 0 1 3 8 9 4 5 7 6
5 3 7 0 4 6 9 8 1 2
6 8 4 9 7 5 1 2 3 0
9 4 5 8 1 2 6 3 0 7
8 6 9 1 0 3 2 7 4 5
7 5 6 2 9 0 3 1 8 4
3 7 8 6 2 1 0 4 5 9

0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
1 9 2 6 3 4 7 0 5 8
2 0 1 3 8 9 4 5 6 7
5 3 7 0 4 6 9 8 1 2
6 4 8 9 7 5 1 2 3 0
9 7 5 8 1 2 6 3 0 4
8 6 9 1 0 3 2 7 4 5
7 5 4 2 9 0 3 1 8 6
3 8 6 5 2 1 0 4 7 9

и input_odlk3_65_0002441.txt
65 1000000
0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
1 9 2 6 3 4 7 0 5 8
2 0 1 3 8 9 4 5 6 7
5 3 7 0 4 6 9 8 1 2
6 4 8 9 7 5 1 2 3 0
9 7 5 8 1 2 6 3 0 4
8 6 9 1 0 3 2 7 4 5
7 5 4 2 9 0 3 1 8 6
3 8 6 5 2 1 0 4 7 9

0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
5 3 2 1 8 4 9 0 6 7
1 0 5 3 2 9 4 8 7 6
2 7 1 9 4 6 0 3 5 8
6 9 8 0 7 5 1 2 3 4
9 4 7 8 3 0 6 5 1 2
8 6 9 2 0 1 3 7 4 5
7 5 4 6 9 3 2 1 8 0
3 8 6 5 1 2 7 4 0 9

Второй квадрат у первого задания является стартовым для второго.
И так для всех соседних заданий.
ID: 80 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
citerra

Send message
Joined: 18 May 17
Posts: 29
Credit: 142,510
RAC: 58
Message 81 - Posted: 23 Jun 2017, 10:39:31 UTC - in response to Message 80.  

Думаю так сделано для проверки. После положительного результата, можно будет переходит на изначальный вариант.
ID: 81 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 82 - Posted: 23 Jun 2017, 14:15:01 UTC - in response to Message 80.  

Второй квадрат у первого задания является стартовым для второго.
И так для всех соседних заданий.

Так и задумано - это задания созданные генератором. После их выполнения будут созданы новые задания на основе этих. Например для задания input_odlk3_65_0011284.txt:
65 1000000
0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 6 2 9 3 4 5 0 7 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 7 9 1 2
6 8 0 1 7 5 9 2 3 4
7 9 4 8 1 2 6 5 0 3
8 4 9 2 0 1 3 7 6 5
9 5 7 6 2 3 1 4 8 0
3 7 6 5 8 0 2 1 4 9

0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 7 2 5 3 4 9 0 6 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 1 9 7 2
6 8 0 9 7 5 2 1 3 4
7 9 4 8 0 2 6 5 1 3
8 4 9 6 2 1 3 7 0 5
9 5 6 2 1 3 7 4 8 0
3 6 7 1 8 0 5 2 4 9

После завершения было создано задание input_odlk3_65_0011284_00001.txt
65 1000000
0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 6 2 9 3 4 5 0 7 8
2 7 1 3 6 9 4 8 0 5
8 0 7 5 4 6 9 2 1 3
6 3 8 2 7 5 1 9 4 0
7 9 0 8 1 2 6 5 3 4
5 4 9 0 8 1 3 7 6 2
9 5 6 1 0 3 2 4 8 7
3 8 4 6 2 0 7 1 5 9

0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 7 2 5 3 4 9 0 6 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 1 9 7 2
6 8 0 9 7 5 2 1 3 4
7 9 4 8 0 2 6 5 1 3
8 4 9 6 2 1 3 7 0 5
9 5 6 2 1 3 7 4 8 0
3 6 7 1 8 0 5 2 4 9

ID: 82 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 83 - Posted: 23 Jun 2017, 15:24:11 UTC - in response to Message 78.  

Progger
по-моему, считать стали намного активнее :)
ID: 83 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 84 - Posted: 23 Jun 2017, 16:34:55 UTC - in response to Message 83.  

Да. Раньше многим хостам заданий не хватало - теперь хватает всем. Через день можно будет узнать, сколько проект способен находить решений в сутки. Я наконец смогу снова запустить boinc-клиент, а то всё время уходило на генерацию заданий :)
ID: 84 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
citerra

Send message
Joined: 18 May 17
Posts: 29
Credit: 142,510
RAC: 58
Message 85 - Posted: 23 Jun 2017, 18:56:19 UTC - in response to Message 84.  
Last modified: 23 Jun 2017, 18:56:50 UTC

Выходной файл
odlk3_22623_1498192546.581509_1_r283568046_0
0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
6 3 2 5 1 4 9 0 7 8
1 7 5 3 0 9 4 8 6 2
9 8 1 0 4 6 3 2 5 7
2 4 8 9 7 5 0 1 3 6
5 9 7 8 3 2 6 4 1 0
8 0 9 6 2 3 1 7 4 5
7 5 6 1 9 0 2 3 8 4
3 6 4 2 8 1 7 5 0 9

X
65 1000000
0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
6 3 2 5 1 4 9 0 7 8
1 7 6 3 8 9 4 2 0 5
2 0 8 9 4 6 1 5 3 7
9 8 4 2 7 5 0 3 1 6
5 9 7 8 3 0 6 1 4 2
8 6 9 1 0 2 3 7 5 4
7 5 1 6 9 3 2 4 8 0
3 4 5 0 2 1 7 8 6 9

0 2 3 4 5 7 8 6 9 1
4 1 0 7 6 8 5 9 2 3
6 3 2 9 1 4 7 0 5 8
1 0 5 3 2 9 4 8 6 7
2 7 8 0 4 6 9 1 3 5
8 9 1 2 7 5 0 3 4 6
9 4 7 8 0 3 6 5 1 2
5 8 9 6 3 1 2 7 0 4
7 5 6 1 9 2 3 4 8 0
3 6 4 5 8 0 1 2 7 9

Как я понимаю
Первый квадрат - ОДЛК
Второй квадрат - старт для следующего задания,
т.е генерация передвинулась на сторону клиента.
Гениально!
ID: 85 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 86 - Posted: 24 Jun 2017, 4:07:59 UTC - in response to Message 78.  
Last modified: 24 Jun 2017, 4:14:10 UTC


Количество квадратов в диапазоне точно не известно, но примерно равно 10^8.

Progger
почему же не известно? :)
У Белышева есть программа moschnometr.exe - мощность заданного интервала измеряет, то есть считает, сколько в этом интервале СН ДЛК.

Например, в этом интервале, приведённом вами (линейка №65):

0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 6 2 9 3 4 5 0 7 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 7 9 1 2
6 8 0 1 7 5 9 2 3 4
7 9 4 8 1 2 6 5 0 3
8 4 9 2 0 1 3 7 6 5
9 5 7 6 2 3 1 4 8 0
3 7 6 5 8 0 2 1 4 9

0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 7 2 5 3 4 9 0 6 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 1 9 7 2
6 8 0 9 7 5 2 1 3 4
7 9 4 8 0 2 6 5 1 3
8 4 9 6 2 1 3 7 0 5
9 5 6 2 1 3 7 4 8 0
3 6 7 1 8 0 5 2 4 9

программа Белышева насчитала ---

. . . . . . . . . . . 
СНДЛК: 260000000 время: 1715 сек
СНДЛК: 261000000 время: 1732 сек
СНДЛК: 262000000 время: 1748 сек
СНДЛК: 263000000 время: 1761 сек
СНДЛК: 264000000 время: 1775 сек
СНДЛК: 265000000 время: 1788 сек
СНДЛК: 266000000 время: 1806 сек

Стоп:

0 2 3 4 5 7 8 6 9 1
4 1 5 7 9 8 0 3 2 6
1 7 2 5 3 4 9 0 6 8
2 0 1 3 6 9 4 8 5 7
5 3 8 0 4 6 1 9 7 2
6 8 0 9 7 5 2 1 3 4
7 9 4 8 0 2 6 5 1 3
8 4 9 6 2 1 3 7 0 5
9 5 6 2 1 3 7 4 8 0
3 6 7 1 8 0 5 2 4 9

Найдено СНДЛК: 266991307
Время работы:   1824.75 сек

Вот и всё известно :)

Программа Белышева выложена на форуме boinc.ru.
ID: 86 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 87 - Posted: 24 Jun 2017, 8:32:44 UTC - in response to Message 84.  

Да. Раньше многим хостам заданий не хватало - теперь хватает всем. Через день можно будет узнать, сколько проект способен находить решений в сутки.

Обработала решения за 23 июня (только первичная обработка). Получено 1689 уникальных КФ!
Здорово!
Думаю, что 2000 КФ в сутки вполне реально получать в проекте.
А если к проекту будут подключаться новые участники, тогда и больше может быть.

Ждём новых участников!
ID: 87 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 89 - Posted: 24 Jun 2017, 13:14:50 UTC - in response to Message 86.  

Найдено СНДЛК: 266991307

Неплохо. Я боялся разброс может оказаться в десятки раз от запланированного.
ID: 89 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 90 - Posted: 24 Jun 2017, 14:42:03 UTC - in response to Message 89.  
Last modified: 24 Jun 2017, 14:47:30 UTC


Неплохо. Я боялся разброс может оказаться в десятки раз от запланированного.

Вы почти угадали :)

Кстати, это не что иное, как мой давнишний метод интервалов.
Я начала его ещё для БД КФ прежнего формата (от нормализованных ДЛК).
Потом продолжила для КФ нового формата (от СН ДЛК).
Представьте, что в БД есть 100000 КФ ОДЛК. При этом нам известны минимальная и максимальная КФ.
Значит, в БД мы имеем 99999 интервалов. Проверить каждый из этих интервалов на наличие в нём других КФ ОДЛК - вот и всё решение задачи :)
Правда, дело осложняется тем, что есть интервалы разнолинеечные, то есть в них начальная и конечная КФ из разных линеек. С этими интервалами сложнее, надо думать, как их проверять.
А с однолинеечными интервалами всё очень просто.
Есть очень короткие интервалы, которые проверить вообще дело нескольких минут. Я такие на своём ПК запросто проверяю.
Есть интервалы более длинные, а есть и огромные. Но все они конечные в том смысле, что есть начальная КФ и конечная КФ.
Все КФ между ними генерируются и проверяются программой Белышева.
ID: 90 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 92 - Posted: 25 Jun 2017, 4:36:05 UTC - in response to Message 84.  
Last modified: 25 Jun 2017, 8:33:02 UTC

Да. Раньше многим хостам заданий не хватало - теперь хватает всем. Через день можно будет узнать, сколько проект способен находить решений в сутки.

Обработала результаты за 24 июня (только первичная обработка). Получено 1929 уникальных КФ ОДЛК!

Да, новая генерация заданий даёт отличные результаты.

Progger
пора подумать о новом алгоритме :)

P.S. Поясню о первичной обработке. Это обработка непосредственно по программе поиска ортогональных ДЛК к найденным КФ ОДЛК.
Есть ещё вторичная обработка - это обработка всех найденных уникальных КФ ОДЛК программой Белышева Канонизатор ЛК по ДЛК.
При вторичной обработке от однушек, как правило, бывает мало новых решений. Исключение составляют однушки SODLS.
Вторичная обработка выполняется довольно долго, в отличие от первичной обработки.
ID: 92 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 93 - Posted: 26 Jun 2017, 4:35:25 UTC

Обработала результаты за 25 июня (только первичная обработка).
Получено 2157 уникальных КФ ОДЛК!
Рубеж в 2000 КФ в сутки взят.

Я сделала сравнение с решениями, полученными 24 июня, боялась повторений :)
Нет, всё замечательно: пересечений нет в порциях решений за эти двое суток.
Относительно БД, составляемой в моём ручном проекте, решения за последние двое суток тоже уникальны.
ID: 93 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 94 - Posted: 26 Jun 2017, 5:36:16 UTC - in response to Message 92.  
Last modified: 26 Jun 2017, 7:23:47 UTC

пора подумать о новом алгоритме :)

Да. Если что-то изменилось в алгоритме, пришлите новую версию, если не изменилось - я доделаю ту, что была.
ID: 94 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 95 - Posted: 26 Jun 2017, 9:18:58 UTC - in response to Message 94.  
Last modified: 26 Jun 2017, 9:20:11 UTC

Progger
всё отправила на e-mail.

С нетерпением жду реализации. Алгоритм довольно сложный. Но решения должны быть очень интересные.
ID: 95 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 215 - Posted: 1 Aug 2017, 7:24:08 UTC
Last modified: 2 Aug 2017, 0:45:27 UTC

Решения за июль в этом алгоритме немного обрабатывала вторично (только программой Белышева Канонизатор ЛК по ДЛК; метод перестановок элементов для решений этого алгоритма почти ничего не даёт).
Для этого, конечно, сначала делала первичную обработку, но результаты пока не добавляла в БД.
Выкладываю то, что у меня получилось. Первая колонка - дата, вторая колонка - количество КФ ОДЛК, полученных первичной обработкой, третья колонка - количество КФ ОДЛК, полученных вторичной обработкой.

1.07.17 2667 2
2.07.17 1934 8
3.07.17 1719 4
4.07.17 1569 2
5.07.17 1086 5
6.07.17 1237 8
7.07.17 1036 2
8.07.17 1059 0
9.07.17 1379 2
10.07.17 1136 2
11.07.17 1243 4
12.07.17 1067 4
13.07.17 1615 4
14.07.17 2040 10
15.07.17 2015 6
16.07.17 1842 2
17.07.17 1547 8
18.07.17 1718 8
19.07.17 1404 0
20.07.17 1840 6
21.07.17 2187 2
22.07.17 2230 12
23.07.17 2385 4
24.07.17 1713 2
25.07.17 1712 4
26.07.17 2336 16
27.07.17 2121 8
28.07.17 1864 0
29.07.17 1969 6
30.07.17 1927 4
31.07.17 2158 6

Можно просуммировать посуточные данные и получить количество КФ ОДЛК, найденных в этом алгоритме за месяц.
https://yadi.sk/i/S417t0IpwnP6r
ID: 215 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 217 - Posted: 2 Aug 2017, 1:17:38 UTC
Last modified: 2 Aug 2017, 1:18:14 UTC

Просуммировала.
В этом алгоритме найдено КФ ОДЛК за июль -

первичная обработка: 53755
вторичная обработка: 151
всего: 53906

Жду общий файл результатов за июль, чтобы проверить первичную обработку сразу всех решений.
При вторичной обработке, вполне вероятно, какие-то решения упущены: не проверила все решения на карусели (метод перестановки элементов). Хотя и очень редко, но решения всё же бывают.
https://yadi.sk/i/S417t0IpwnP6r
ID: 217 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Progger
Project administrator
Project developer

Send message
Joined: 15 May 17
Posts: 84
Credit: 49,401
RAC: 117
Message 220 - Posted: 2 Aug 2017, 7:55:33 UTC - in response to Message 217.  

ID: 220 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 956
Credit: 0
RAC: 0
Message 222 - Posted: 2 Aug 2017, 10:43:51 UTC - in response to Message 220.  

Progger
ага, спасибо :)
Но... у вас в общий файл вошли все решения (от обоих алгоритмов). А я не обрабатывала не уникальные решения от симметричных ДЛК.
Поэтому результаты получились разные.
У меня от обоих алгоритмов (без не уникальных решений в алгоритме odlksym) всего получилось 54462 КФ ОДЛК (первичная и вторичная обработка).
Первичная обработка вашего общего файла дала 54729 КФ ОДЛК.
Разница приходится точно на не уникальные решения от симметричных ДЛК.
БД не приняла ни одной КФ ОДЛК из разницы этих результатов. Значит, всё нормально.

На данный момент наша БД содержит 154595 уникальных КФ ОДЛК.
Пришлю вам, чтобы выложить.

Вообще июльские результаты получились хорошие.
Спасибо всем участникам!
https://yadi.sk/i/S417t0IpwnP6r
ID: 222 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · 3 · Next

Message boards : News : Приложение odlk3


©2017 (C) Progger