VPF::Построение распределенной системы на J2EE

sandello

Дата 4.5.2006, 06:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 295
Регистрация: 18.5.2005
Где: Пермь

Репутация: нет
Всего: 2

Прежде, чем распараллеливать, просто реши задачу. Тут решения я не увидел.

--------------------

jimur

Дата 5.5.2006, 06:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

Как это нельзя параллелить?
Берешь данную ячейку, ее строку и столбец и отправляешь на расчет
Результат - или точно число или варанты для ячеек
Отлично параллелится на 9 потоков.

Тебе алгоритм написать? smile

onsh76

Дата 5.5.2006, 10:00 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 93
Регистрация: 20.11.2005
Где: Beautiful BC

Репутация: 4
Всего: 5

В добавление к сказанному jimur:
предлагаю разбить бизнес логику на stateless - (там где не требуется тракировать статус отслеживаемой логики) и statefull(соотв-но наоборот). Сделай stateless компоненты распределенными, а statefull будет давать задания распр-ным компонентам по мере надобности и отслеживать результаты вычисления.

zone51

Дата 5.5.2006, 12:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

jimur,

Цитата

Берешь данную ячейку, ее строку и столбец и отправляешь на расчет
Результат - или точно число или варанты для ячеек
Отлично параллелится на 9 потоков.

Понимаете, я никак не могу вьехать: распарралелить, это значит что некоторые действия вычисляются парралельно..но вы же посмотрите, ну возьму я как вы сказали ячейку, ну отправлю на вычисление, но в этот же момент никакая другая ячейка вычисляцца не сможет, ведь пример:
вычисляю ячейку (1,1) и парралельно вычисляю (1,5). На 2 удаленные машины одновременно посылаются кроме других аргументов одна и та же строка, первая строка, в которой еще нет ячейки (1,1) и (1,5). На первой машине получится результат допустим 5, и вторая машина даст тот же результат, ведь она еще не знает что первая дала 5, строка на обе машины послалась исходная. Вот где вопрос, ведь все цифры в столбцах, строках и регионах должны быть разные.

p.s. А алгоритм писать не надо..просто я хочу просечь несколько логических фишек.

onsh76,

Цитата

Сделай stateless компоненты распределенными, а statefull будет давать задания распр-ным компонентам по мере надобности и отслеживать результаты вычисления.

А о каких соб-но компонентах идет речь? или в общем смысле? я буду делать на RMI, то есть по удаленным машинам рассаживаю объекты, а на клиентской запускаю приложение, которое соб-но и общается с удаленными объектами.

Это сообщение отредактировал(а) zone51 - 5.5.2006, 12:22

--------------------

The truth is out there

jimur

Дата 5.5.2006, 20:44 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

ээх...
что-то типа этого:

Код


final byte[] allValues = new byte[9*9];
while (!isSolved()) {
for (int i =0; i<3;i++) {
for (int k =0; k<3;k++) {
byte[] column = new byte[3*9];
byte[] row = new byte[9*3];
byte[] current = new byte[3*3];
fillValues(i,k, column, row, current);// заполняем
byte[] result = sentToRemoteHostToSolve(column, row, current);// решаем на других хостах
}
collectResults(); // ждем и собираем решения
fillAllValues(); // заполняем результаты в общую матрицу значений
// повторяем до тех пор пока не будут известны все значения
}

зы: вместо отправки/ожидания можно использовать несколько локальных потоков с удаленным вызовом
зы: модель можно улучшить чтобы в результатах были альтернативы, что ускорит решение

Это сообщение отредактировал(а) jimur - 5.5.2006, 20:45

zone51

Дата 5.5.2006, 21:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

jimur,

Цитата

byte[] column = new byte[3*9];
byte[] row = new byte[9*3];

Извините нифига не понял, почему 27 элементов?

Цитата

byte[] result = sentToRemoteHostToSolve(column, row, current);

Неужели я так плохо знаю RMI? Я думал там просто пойдет разбиение задачи на подзадачи, и уже эти подзадачи по машинам..

Цитата

sentToRemoteHostToSolve

Это функция RMI или условное обозначение пользовательской функции? Спасибо.

--------------------

The truth is out there

jimur

Дата 5.5.2006, 21:50 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

Цитата(zone51 @ 5.5.2006, 21:19

)

Извините нифига не понял, почему 27 элементов?

Всего 9*9 = 81 элемент
При расчете блока 3*3 нужно учитывать строку и столбец в которые он попадает, соотвественно столбец из трех рядов чисел и строка из трех рядов.

Цитата(zone51 @ 5.5.2006, 21:19

)

Подзадачей и будет обработка данного набора данных. Итого можно обрабатывать на 9 машинах.

Цитата(zone51 @ 5.5.2006, 21:19

)

Это функция RMI или условное обозначение пользовательской функции?

Второе

Методы написать? ;)

zone51

Дата 6.5.2006, 13:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

jimur,
Все, понял как вы делали, а скажите, разве теоретически нельзя по тому же принципу распарралелить на 81 машину? я не собираюся так делать, просто интересно.
И самый главный вопрос так это все те же "грабли", с которых я так и не могу слезть: посылаю я все 9 блоков одновременно?
Что значит ждем результатов и собираем значения? но ведь опять же, где гарантии того, что во всех строках и столбцах все цифры будут разные?

Цитата

final byte[] allValues = new byte[9*9];
while (!isSolved()) {
for (int i =0; i<3;i++) {
for (int k =0; k<3;k++) {
byte[] column = new byte[3*9];
byte[] row = new byte[9*3];
byte[] current = new byte[3*3];
fillValues(i,k, column, row, current);// заполняем
byte[] result = sentToRemoteHostToSolve(column, row, current);// решаем на других хостах
}
collectResults(); // ждем и собираем решения
fillAllValues(); // заполняем результаты в общую матрицу значений
// повторяем до тех пор пока не будут известны все значения
}

Ну послал я все блоки, они вычислились, но ведь на все блоки я послал Исходные данные, без учета результата просчета других блоков.Как быть? Обьясните пожалуйста

Это сообщение отредактировал(а) zone51 - 6.5.2006, 22:47

--------------------

The truth is out there

Ivan Kolesnikov

Дата 7.5.2006, 06:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 113
Регистрация: 9.3.2005
Где: г. Новокузнецк

Репутация: 1
Всего: 6

Привет! Я понял идею jimur.
Он предлагает разбить задачу на 9 (на большее число нельзя) подзадач, решения которых не влияют друг на друга, далее получаем ответ от этих задач, объединяем его вместе и создаем новых 9 задач и т.д., если решение одной из подзадачи не может быть найдено, то производим откат.

Хотя возможно на некотором шаге нам удастся создать только меншьшее число не пересекающихся подзадач.

Разбивать нужно обяхательно так, чтобы решения не влияли друг на друга.

Например для приведенного примера можно искать следующие решения параллельно (выделены *)

Код


7.*25..98
..6....1*
...61*3..
9....1.*.
.*..8.4.9
..75*28.1
.94..3*..
*...4923.
61.*...4.

--------------------

zone51

Дата 7.5.2006, 10:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

Ivan Kolesnikov,
мысль перехватил, опробовал. все хорошо да вот загвоздка: что делать если в ходе вычисления очередной цифры оказалось, что эта цифра число 10, т е все цифры 1-9 есть либо в строке либо в столбце либо в регионе? Буду очень благодарен за помощь. Помогите если можно.

Это сообщение отредактировал(а) zone51 - 8.5.2006, 22:33

--------------------

The truth is out there

jimur

Дата 8.5.2006, 23:39 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

Хорошая задачка smile

Решение ниже smile

Зачем выносить на удаленные машины то, что локально делается на 10-30ms smile

Код


public final class SudokuSolver extends AbstractBlocksTask {
    private static final int[][] TASK_BLOCKS_MAP =
            new int[][]{
                    {0, 1, 2, 3, 6}, {1, 0, 2, 4, 7}, {2, 0, 1, 5, 8},
                    {3, 4, 5, 0, 6}, {4, 3, 5, 1, 7}, {5, 3, 4, 2, 8},
                    {6, 7, 8, 0, 3}, {7, 6, 8, 1, 4}, {8, 6, 7, 2, 5},
            };

    public SudokuSolver(final Block[] blocks) {
        super(blocks); // 9
        if (blocks == null || blocks.length != 9) {
            throw new IllegalArgumentException();
        }
    }

    public static void main(final String[] args) {
        final long st = System.currentTimeMillis();
        final Block[] blocks = new Block[]{
                Block.buildBlock(5, 3, 0, 6, 0, 0, 0, 9, 8),
                Block.buildBlock(0, 7, 0, 1, 9, 5, 0, 0, 0),
                Block.buildBlock(0, 0, 0, 0, 0, 0, 0, 6, 0),
                Block.buildBlock(8, 0, 0, 4, 0, 0, 7, 0, 0),
                Block.buildBlock(0, 6, 0, 8, 0, 3, 0, 2, 0),
                Block.buildBlock(0, 0, 3, 0, 0, 1, 0, 0, 6),
                Block.buildBlock(0, 6, 0, 0, 0, 0, 0, 0, 0),
                Block.buildBlock(0, 0, 0, 4, 1, 9, 0, 8, 0),
                Block.buildBlock(2, 8, 0, 0, 0, 5, 0, 7, 9),
        };
        final SudokuSolver sudokuSolver = new SudokuSolver(blocks);
        final int result = sudokuSolver.process();
        if (result == 162) {
            sudokuSolver.printResult();
            System.out.println("Solved, processing time is " + (System.currentTimeMillis()-st) + " ms");
        } else {
            System.out.println("Error, result = " + result);
        }
    }

    private void printResult() {
        for (Block block : blocks) System.out.println(block);
    }

    protected void calculate() {
        final Task[] tasks = new Task[9];
        for (int i = 0; i < tasks.length; i++) {
            tasks[i] = new Task(new Block[]{blocks[TASK_BLOCKS_MAP[i][0]],
                    blocks[TASK_BLOCKS_MAP[i][1]], blocks[TASK_BLOCKS_MAP[i][2]],
                    blocks[TASK_BLOCKS_MAP[i][3]], blocks[TASK_BLOCKS_MAP[i][4]]});
        }

        for (Task task : tasks) task.process();

        for (int i = 0; i < tasks.length; i++) {
            final Task task = tasks[i];
            for (int k = 0; k < 5; k++) {
                final Block[] resultblocks = task.getBlocks();
                blocks[TASK_BLOCKS_MAP[i][k]].merge(resultblocks[k]);
            }
        }
    }
}

abstract class AbstractBlocksTask {
    Block[] blocks; //0-current; 1,2 - goriz ; 3,4 -vert

    protected AbstractBlocksTask(final Block[] blocks) {
        this.blocks = blocks;
    }

    public int process() {
        int prevCheckSum = sumCheckSums();
        int curCheckSum = 0;
        while (curCheckSum != prevCheckSum) {
            if (curCheckSum > 0) prevCheckSum = curCheckSum;
            calculate();
            curCheckSum = sumCheckSums();
        }
        return curCheckSum;
    }

    protected abstract void calculate();

    private int sumCheckSums() {
        int checkSum = 0;
        for (int i = 0; i < blocks.length; i++) checkSum += blocks[i].checkSum();
        return checkSum;
    }

    public final Block[] getBlocks() {
        return blocks;
    }
}

final class Block {
    private final byte[] locs;
    public static final int GORIZONTAL_MASK = 0x38;// 111000
    public static final int VERTICAL_MASK = 0x7;// 000111
    private static final int[] LINE_MASKS = new int[]{0x1, 0x2, 0x4, 0x8, 0x10, 0x20};
    private static final int[] HELP_LINE_MASKS = new int[]{0x38, 0x38, 0x38, 0x7, 0x7, 0x7,};

    protected Block(final byte[] locs) {
        this.locs = locs;
        for (int i = 0; i < locs.length; i++) {
            if (locs[i] == 0) locs[i] = 0x3f;
        }
    }

    public final boolean isFull() {
        boolean b = true;
        for (int i = 0; b && i < locs.length; i++) b = b && isDefined(locs[i]);
        return b;
    }

    public static boolean isDefined(final int loc) {
        return bitSum(loc & 0x7) == 1 && bitSum(loc & 0x38) == 1;
    }

    private static int bitSum(final int loc) {
        int r = 0;
        for (int i = 0; i < 6; i++) r += (loc >> i) & 1;
        return r;
    }

    public String toString() {
        final byte[] bytes = new byte[9];
        for (int i = 0; i < locs.length; i++) {
            if (isDefined(locs[i])) {
                bytes[((locs[i] & 0x38) >> 4) * 3 + ((locs[i] & 0x7) >> 1)] = (byte) (i + 1);
            }
        }
        String s = "";
        for (int i = 0; i < bytes.length; i++) {
            s += bytes[i];
            if (((i + 1) % 3) == 0) s += "\n";
        }
        return s;
    }

    // to test
    byte getLoc(final int num) {
        return locs[num - 1];
    }

    public int checkSum() {
        int sum = 0;
        for (int i = 0; i < locs.length; i++) sum += bitSum(locs[i]);
        return sum;
    }

    public static Block buildBlock(final int... nums) {
        final byte[] locs = new byte[9];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                locs[nums[i] - 1] = (byte) ((((i % 3 == 0 ? 1 : ((i % 3) << 1)) | ((i / 3 == 0 ? 1 : (i / 3 << 1)) << 3))));
            }
        }
        return new Block(locs);
    }

    public static void intersect(final int mask, final Block... blocks) {
        for (int k = 0; k < blocks.length; k++) {
            final Block b1 = blocks[k];
            for (Block b2 : blocks) {
                if (b1 != b2) {
                    for (int i = 0; i < 9; i++) {
                        if (bitSum(b2.locs[i] & mask) == 1) {
                            b1.locs[i] = (byte) (~(b2.locs[i] & mask) & b1.locs[i]);
                        } else if (bitSum(b1.locs[i] & mask) == 1) {
                            b2.locs[i] = (byte) (~(b1.locs[i] & mask) & b2.locs[i]);
                        }
                    }
                }
            }
        }
        for (Block b1 : blocks) b1.fillLine();
    }

    private void fillLine() {
        for (int i = 0; i < LINE_MASKS.length; i++) {
            final int lineMask = LINE_MASKS[i];
            final int[] alts = new int[9];
            final int altCounter = fillAlts(lineMask, alts);
            processAlts(i, altCounter, alts);
        }
    }

    private int fillAlts(final int lineMask, final int[] alts) {
        int altCounter = 0;
        for (int k = 0; k < locs.length; k++) {
            if (bitSum(locs[k] & lineMask) == 1) {
                alts[altCounter] = k;
                altCounter++;
            }
        }
        return altCounter;
    }

    private void processAlts(final int lineIndex, final int altCounter, final int[] alts) {
        final int[] defined = new int[9];
        int defCounter = 0;
        final int[] undefineds = new int[2];
        undefineds[0] = -1;
        for (int k = 0; k < alts.length && k < altCounter; k++) {
            if (isDefined(locs[alts[k]])) {
                defined[defCounter] = alts[k];
                defCounter++;
            } else {
                undefineds[undefineds[0] == -1 ? 0 : 1] = alts[k];
            }
        }
        if (altCounter == 3) {
            if (defCounter == 2) {
                locs[undefineds[0]] = (byte) (LINE_MASKS[lineIndex] | (HELP_LINE_MASKS[lineIndex] ^ locs[defined[0]] ^ locs[defined[1]]));
            } else if (defCounter == 1) {
                final int undefIndex = bitSum(locs[undefineds[0]] & HELP_LINE_MASKS[lineIndex]) == 2 ? 0 : 1;
                locs[undefineds[undefIndex]] = (byte) (LINE_MASKS[lineIndex] |
                        ((locs[undefineds[undefIndex]] ^ locs[defined[0]]) & HELP_LINE_MASKS[lineIndex]));
            }
        } else if (defCounter == 3) {
            for (int i = 0; i < locs.length; i++) {
                if (!isDefined(locs[i])) locs[i] = (byte) (locs[i] & ~LINE_MASKS[lineIndex]);
            }
        }
    }

    public boolean isSolved(final int num) {
        return isDefined(locs[num - 1]);
    }

    public void merge(final Block b2) {
        for (int i = 0; i < locs.length; i++) locs[i] = (byte) (locs[i] & b2.locs[i]);
    }
}

final class Task extends AbstractBlocksTask {
    public Task(final Block[] blocks) {
        super(blocks);        //0-current; 1,2 - goriz ; 3,4 -vert
    }

    protected void calculate() {
        Block.intersect(Block.GORIZONTAL_MASK, blocks[0], blocks[1], blocks[2]);
        Block.intersect(Block.VERTICAL_MASK, blocks[0], blocks[3], blocks[4]);
    }
}

zone51, с тебя причитается ;)

zone51

Дата 8.5.2006, 23:49 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

jimur,

Цитата

zone51, с тебя причитается ;)

Само собой

Цитата

Зачем выносить на удаленные машины то, что локально делается на 10-30ms

Ну поймите вы, задача у меня такая, поставили и все тут..ща разберусь с вашим алгоритмом, огромное спасибо..Насколько я понял это нераспределенное решение..эххх.. smile

зы. посмотрел исходник и офигел, мне до такого уровня еще расти и расти..огромное спасибо, но перед тем как я разберусь с исходником, может подскажите что делать со случаем 10-ки если на каждом шаге выбираются независимые клетки из каждого района?

Это сообщение отредактировал(а) zone51 - 9.5.2006, 00:00

--------------------

The truth is out there

jimur

Дата 9.5.2006, 00:34 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

Так это же рутина ...

1. делаем сериализуемой задачу:

Код


final class Task extends AbstractBlocksTask implements Serializable {

2. заходим сюда и внимательно читаем
RMI tutorial
3. создаем удаленный процессор

Код


public class RemoteProcessor implements Remote {
    public static void main(final String[] args) {
        if (System.getSecurityManager() == null) {
            System.setSecurityManager(new RMISecurityManager());
        }
        try {
            final String name = "//Sudoku/Solver";
            final SudokuSolver solver = (SudokuSolver) Naming.lookup(name);
            solver.add(new RemoteProcessor());
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public final int process(final Task task) {
        return task.process();
    }
}

4. из солвера делаем удаленный сервер

Код


public final class SudokuSolver extends AbstractBlocksTask implements Remote {
...
    private final List<RemoteProcessor> remoteProcessors = new ArrayList<RemoteProcessor>(9);
    public void add(final RemoteProcessor remoteProcessor) {
        remoteProcessors.add(remoteProcessor);
    }

    public static void main(final String[] args) {
        ...
        if (System.getSecurityManager() == null) {
            System.setSecurityManager(new RMISecurityManager());
        }
        String name = "//Sudoku/Solver";
        try {
            Naming.rebind(name, sudokuSolver);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
...
//        for (Task task : tasks) task.process();
        remoteProcess(tasks);
    private void remoteProcess(final Task[] tasks) {
        // тут делишь задачи на потоки и запускашь remoteProcessor.process(task)
        // ну и дожидаешься всех ответов
    }

...
}

Это сообщение отредактировал(а) jimur - 9.5.2006, 00:39

zone51

Дата 9.5.2006, 01:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 370
Регистрация: 17.2.2006

Репутация: нет
Всего: 1

Уважаемый jimur, спасибо огромное, мне это очень помогло, но все таки, подскажите пожалуйста, Как разбивать задачу на потоки, алгоритм, вот в чем вопрос. Огромное спасибо.

Цитата

может подскажите что делать со случаем 10-ки если на каждом шаге выбираются независимые клетки из каждого района?

Как правильно распарралелить задачу, вот в чем вопрос, я просто застрял в начале smile

Это сообщение отредактировал(а) zone51 - 9.5.2006, 10:21

--------------------

The truth is out there

jimur

Дата 9.5.2006, 12:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 73
Регистрация: 21.4.2006

Репутация: 1
Всего: 3

Так в алгоритме уже заложено это разбиение.
Мы имеем 9 _независимых_ задач, которые можно испольнять параллельно.

Код с потоками попозже кину - времени пока нет.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java EE (J2EE) и Spring \| Следующая тема »