ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Воскресный Java-шахматун и оптимизация списков
14 сообщений из 14, страница 1 из 1
Воскресный Java-шахматун и оптимизация списков
    #39532957
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Привет.

В продолжение темы 1000 ферзей.

Пятничная задачка для ума за 1 миллион $

Я решил сделать отдельную ветку т.к. в вышеуказанном топике собрались теоретики и прочие
шахматисты разной толщины. А у меня есть практичные вопросы по Java Collections.

Есть функция. Рекурсивная. Она интенсивно копирует списки. Но копирует с опциями.
Например - добавляет элемент в хвост (это просто). Это одная опция. И режет серединку.
Как из яблока. Это другая опция.

Фрагмент:
Код: java
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.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
....

    public static List<Integer> headElements(@Nonnull List<Integer> arg) {
        int n = arg.size();
        return arg.stream().limit(n - 1).collect(Collectors.toList());
    }
    public static List<Integer> subList(@Nonnull List<Integer> arg, int i) {
        if (arg == null) {
            throw new IllegalArgumentException("Array cannot be null!");
        }
        int n = arg.size();
        if (i < 0 || i >= n) {
            throw new IllegalArgumentException("Index is out of range");
        }
        if (i == 0) {
            if (n == 1) {
                return Collections.emptyList();
            } else {
                // TODO: Investigate for performance
                return arg.stream().skip(1).collect(Collectors.toList());
            }
        }
        if (i == n - 1) {
            // TODO: Investigate for performance
            return arg.stream().limit(n - 1).collect(Collectors.toList());
        }
        // TODO: Investigate for performance
        List<Integer> res = new ArrayList<>(arg.stream().limit(i).collect(Collectors.toList()));
        res.addAll(arg.stream().skip(i + 1).collect(Collectors.toList()));
        return res;
    }

    public static boolean isConsistent(@Nonnull List<Integer> q, int candidate) {
        int n = q.size();
        for (int i = 0; i < n; i++) {
            int qi = q.get(i);
            int deltai = n - i;
            int deltaRow = qi - candidate;
            if (Math.abs(deltaRow) == deltai) {
                return false;
            }
        }
        return true;
    }

    private static void printSolution(@Nonnull List<Integer> queens) {
        out.printf("Queens : %s\n", formatQueens(queens));
        out.printf("----------------\n");
        int n = queens.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                out.print(queens.get(i) == j ? "Q" : "*");
                out.print(" ");
            }
            out.println();
        }
        out.println();
    }

    // TODO: Replace with Guava or smth else
    static List<Integer> fromArray(@Nonnull int[] array) {
        List<Integer> res = new ArrayList<>(array.length);
        for (int elem : array) {
            res.add(elem);
        }
        return res;
    }


    public static String formatQueens(List<Integer> list) {
        StringBuilder sb = new StringBuilder("");
        sb.append(join(",", valueOf(list)));
        sb.append("");
        return sb.toString();
    }

    public static String formatOffset(int n){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<n; i++) sb.append(".");
        return sb.toString();
    }

    public static void process(int n, int level, @Nonnull List<Integer> candidates, @Nonnull List<Integer> selected) {
        //out.printf("%s %d %d %s %s \n", formatOffset(level), n, level, formatQueens(candidates), formatQueens(selected));
        if (selected.size() == n) {
            // TODO: Improove overloaded isConsistent
            if (isConsistent(headElements(selected), tailElement(selected))) {
                solutions++;
                printSolution(selected);
            }
        } else {
            for (int i = 0; i < candidates.size(); i++) {
                int newCandidate = candidates.get(i);
                if (isConsistent(selected, newCandidate)) {
                    List<Integer> newSelected = new ArrayList<>(selected);
                    newSelected.add(newCandidate);
                    process(n, level + 1, subList(candidates, i), newSelected);
                }
            }
        }
    }




Вобщем задача №1 - оптимизировать расчет ферзей по скорости. Алгоритм пока не трогаем.
Считаем что он - ОК. Оптимизируем работу со списками.

Открытые вопросы:
Java Arrays/Linked-lists? Прочие экзотические структуры.

Версионные коллекции? Помогут? Scala?

Коллекции примитивов против коллекции Objects.

Оптимизировать isConsistent.?

Полный вариант сорца здесь
https://sourceforge.net/p/chess-experiments/code/HEAD/tree/trunk/mayton/queen-problem/src/main/java/mayton/chess/MtnQueensGenerator.java

Спасибо всем кто откликнулся.
...
Рейтинг: 0 / 0
08.10.2017, 16:40
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39533682
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Здесь попробую свернуть. Эта штука красиво выглядит. Как в ФП. Но на деле - жжот мегафлопы мать их так.
Код: java
1.
if (isConsistent(headElements(selected), tailElement(selected))) {


Возможно просто переписать перегруженный isConsistent.
...
Рейтинг: 0 / 0
09.10.2017, 20:58
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39533699
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Закатал в бетон. И хотя рефакторинг я считаю удачным - никакого перформанса не получил.
Видимо эта функция просто редко вызывается на фоне других узлов дерева поиска.
...
Рейтинг: 0 / 0
09.10.2017, 21:53
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39533728
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Зарефакторил больше операций в streams.
...
Рейтинг: 0 / 0
10.10.2017, 00:18
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534021
Andrei T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Andrei T
Участник
maytonarg.stream().skip(1).collect(Collectors.toList())
arg.stream().limit(n - 1).collect(Collectors.toList())


Вот это вот замени на Arrays.copyOfRange. У тебя сейчас headElements тета(n) от размера списка (внутри фактически цикл).
...
Рейтинг: 0 / 0
10.10.2017, 13:31
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534036
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Blazkowicz
Участник
maytonЗарефакторил больше операций в streams.
О каких вообще стримах и коллекциях речь если хочется производительности? Только массивы! Только хардкор!
...
Рейтинг: 0 / 0
10.10.2017, 13:54
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534237
Локшин Марк
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Локшин Марк
Участник
mayton,

А можно в целом объяснить суть сего опуса? В исходном топике на первой странице фигурирует информация, что задача является NP-полной. Вы пытаетесь оптимизировать вычисления для NP-полной задачи?
...
Рейтинг: 0 / 0
10.10.2017, 17:17
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534360
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Локшин Маркmayton,

А можно в целом объяснить суть сего опуса? В исходном топике на первой странице фигурирует информация, что задача является NP-полной. Вы пытаетесь оптимизировать вычисления для NP-полной задачи?
Я пытаюсь улучшить классический "переборный" алгоритм который висит в википедии.

Я не претендую на NP/P. Это сложная материя. Особенно в части формального
математического доказательства. Именно так как это делает Дональд Кнут.
...
Рейтинг: 0 / 0
10.10.2017, 22:26
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534361
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Andrei Tmaytonarg.stream().skip(1).collect(Collectors.toList())
arg.stream().limit(n - 1).collect(Collectors.toList())


Вот это вот замени на Arrays.copyOfRange. У тебя сейчас headElements тета(n) от размера списка (внутри фактически цикл).
Есть у меня соображения. Я думаю вообще от копирований уйти.

За CopyOfRange - спасибо. Это гуд.
...
Рейтинг: 0 / 0
10.10.2017, 22:27
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39534374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ахтунг. Brainstorm!

Окей. Шахматуны. Посмотрите на трассу аргументов к рекурсивной
функции. (точками обзначен левел рекурсии и в квадратных скобках - массивы).
И скажите что вы видете?

java -jar QueenProblem-1.0-SNAPSHOT.jar 9 > queens-9x9.lst
Код: sql
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.
 [0, 1, 2, 3, 4, 5, 6, 7, 8] [] 
. [1, 2, 3, 4, 5, 6, 7, 8] [0] 
.. [1, 3, 4, 5, 6, 7, 8] [0, 2] 
... [1, 3, 5, 6, 7, 8] [0, 2, 4] 
.... [3, 5, 6, 7, 8] [0, 2, 4, 1] 
..... [5, 6, 7, 8] [0, 2, 4, 1, 3] 
...... [5, 6, 7] [0, 2, 4, 1, 3, 8] 
..... [3, 5, 6, 8] [0, 2, 4, 1, 7] 
..... [3, 5, 6, 7] [0, 2, 4, 1, 8] 
.... [1, 3, 5, 7, 8] [0, 2, 4, 6] 
..... [3, 5, 7, 8] [0, 2, 4, 6, 1] 
...... [5, 7, 8] [0, 2, 4, 6, 1, 3] 
....... [7, 8] [0, 2, 4, 6, 1, 3, 5] 
..... [1, 5, 7, 8] [0, 2, 4, 6, 3] 
..... [1, 3, 5, 7] [0, 2, 4, 6, 8] 
...... [1, 5, 7] [0, 2, 4, 6, 8, 3] 
....... [5, 7] [0, 2, 4, 6, 8, 3, 1] 
....... [1, 7] [0, 2, 4, 6, 8, 3, 5] 
.... [1, 3, 5, 6, 8] [0, 2, 4, 7] 
..... [3, 5, 6, 8] [0, 2, 4, 7, 1] 
...... [5, 6, 8] [0, 2, 4, 7, 1, 3] 
....... [6, 8] [0, 2, 4, 7, 1, 3, 5] 
...... [3, 5, 6] [0, 2, 4, 7, 1, 8] 
....... [3, 6] [0, 2, 4, 7, 1, 8, 5] 
..... [1, 5, 6, 8] [0, 2, 4, 7, 3] 
...... [1, 5, 6] [0, 2, 4, 7, 3, 8] 
.... [1, 3, 5, 6, 7] [0, 2, 4, 8] 
..... [3, 5, 6, 7] [0, 2, 4, 8, 1] 
...... [5, 6, 7] [0, 2, 4, 8, 1, 3] 
..... [1, 5, 6, 7] [0, 2, 4, 8, 3] 
... [1, 3, 4, 6, 7, 8] [0, 2, 5] 
.... [3, 4, 6, 7, 8] [0, 2, 5, 1] 
..... [3, 4, 7, 8] [0, 2, 5, 1, 6] 
...... [3, 7, 8] [0, 2, 5, 1, 6, 4] 
..... [3, 4, 6, 7] [0, 2, 5, 1, 8] 
...... [3, 6, 7] [0, 2, 5, 1, 8, 4] 
.... [1, 3, 4, 6, 8] [0, 2, 5, 7] 
..... [3, 4, 6, 8] [0, 2, 5, 7, 1] 
...... [4, 6, 8] [0, 2, 5, 7, 1, 3] 
....... [4, 6] [0, 2, 5, 7, 1, 3, 8] 
........ [4] [0, 2, 5, 7, 1, 3, 8, 6] 
......... [] [0, 2, 5, 7, 1, 3, 8, 6, 4] 
Found solution : [0, 2, 5, 7, 1, 3, 8, 6, 4]




P.S. Исходник обновлен.
...
Рейтинг: 0 / 0
11.10.2017, 00:16
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39535063
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Второй массив работает как стек или queue. Убрал из аргументов. Пускай mutable, зато быстро.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
static List<Integer> selected = new ArrayList<>();
    
    public static void process(int n, int level, @Nonnull List<Integer> candidates) {
        recursiveProcessCallbacks++;
        out.printf("%s %s %s \n", formatOffset(level), formatQueens(candidates), formatQueens(selected));
         if (selected.size() == n) {
            if (isConsistent(selected)) {
                solutions++;
                printSolution(selected);
            }
        } else {
            for (int i = 0; i < candidates.size(); i++) {
                int newCandidate = candidates.get(i);
                if (isConsistent(selected, newCandidate)) {
                    selected.add(newCandidate);
                    process(n, level + 1, subList(candidates, i));    
                    selected.remove(selected.size()-1);
                }
            }
        }
    }



Что с первым массивом? Тут похитрее будет...
...
Рейтинг: 0 / 0
11.10.2017, 22:11
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39536264
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Продолжаю двигаться в сторону оптимизации копирований.

Трассировка переменных стека показывает что я играю с вырезанием элемента из
массива. На верхнем уровне эта операция может быть заменена как работа с
двумя очередями (queue/deck) и одной переменной. Это уход от иммутабельности,
зато перорманс.

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
  def process(n: Int, level: Int, candidates: List[Int], selected: List[Int]): Unit = {
    printf("%s %s %s \n", formatOffset(level,'.'), formatQueens(candidates), formatQueens(selected))
    if (selected.size == n) {
      if (isConsistent(selected)) {
        solutions += 1
        printSolution(selected,level)
      }
    } else {
      var i = 0
      while (i < candidates.size) {
        val newCandidate = candidates(i)
        if (isConsistent(selected, newCandidate)) {
          // TODO: Optimize
          var newSel: List[Int] = selected.++(List(newCandidate))
          process(n, level + 1, subList(candidates, i), newSel)
        }
        i = i + 1
      }
    }
  }



Сорцы обновил. +Есть порт на Scala.
...
Рейтинг: 0 / 0
14.10.2017, 12:40
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39536364
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Убрал массивы. Теперь алгоритмы готовы к работе с Collections/Deque/Streams.

Кое-где алгоритм должен иметь сведенья о размере коллекции (стрима). Придется
передавать размер отдельным аргументом. Зато стримы открывают новые возможности.
...
Рейтинг: 0 / 0
14.10.2017, 21:56
| Ответить | Цитировать | Написать  
Воскресный Java-шахматун и оптимизация списков
    #39536639
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мой перфекционизм насытился. Java/Scala варианты готовы. Надо теперь написать процедуру
проверки канонического решения.

Например для доски 5х5 существует 10 расстановок. Но при этом канонических всего две.
Их видно визуально. Я их называю "Пятёрка" игральных костей и "Ковш".

Подозреваю что нужно будет крутить аффинные преобразования на плоскости. Интересно
как их соптимизировать для доски 27х27 ?

Код: java
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.
77.
78.
79.
[0, 2, 4, 1, 3]
-----
Q * * * * 
* * Q * * 
* * * * Q 
* Q * * * 
* * * Q * 

[0, 3, 1, 4, 2]
-----
Q * * * * 
* * * Q * 
* Q * * * 
* * * * Q 
* * Q * * 

[1, 3, 0, 2, 4]
-----
* Q * * * 
* * * Q * 
Q * * * * 
* * Q * * 
* * * * Q 

[1, 4, 2, 0, 3]
-----
* Q * * * 
* * * * Q 
* * Q * * 
Q * * * * 
* * * Q * 

[2, 0, 3, 1, 4]
-----
* * Q * * 
Q * * * * 
* * * Q * 
* Q * * * 
* * * * Q 

[2, 4, 1, 3, 0]
-----
* * Q * * 
* * * * Q 
* Q * * * 
* * * Q * 
Q * * * * 

[3, 0, 2, 4, 1]
-----
* * * Q * 
Q * * * * 
* * Q * * 
* * * * Q 
* Q * * * 

[3, 1, 4, 2, 0]
-----
* * * Q * 
* Q * * * 
* * * * Q 
* * Q * * 
Q * * * * 

[4, 1, 3, 0, 2]
-----
* * * * Q 
* Q * * * 
* * * Q * 
Q * * * * 
* * Q * * 

[4, 2, 0, 3, 1]
-----
* * * * Q 
* * Q * * 
Q * * * * 
* * * Q * 
* Q * * *
...
Рейтинг: 0 / 0
16.10.2017, 01:24
| Ответить | Цитировать | Написать  
14 сообщений из 14, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Воскресный Java-шахматун и оптимизация списков
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=59&msg=39536639&tid=2122533]:
 0ms
get settings:
 8ms
get forum list:
 16ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 55ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 1ms
others: 210ms
total:  358ms
созд. / загр.: 358ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]