Pull to refresh
15
0
Send message
хорошо, но в приведенном случае: c/a*b == (c/a)*b, то есть порядок могло нарушить увеличение приоритета умножения: c/a*b != c/(a*b).
сходу не могу придумать, можете ли привести пример, где увеличение приоритета именно деления приведет к результату, отличному от результата с равными приоритетами?
какой был бы смысл давать делению больший приоритет? выражения (a*b)/c и a*(b/c) математически эквивалентны.
По моему кеш проца оказывает минимальное влияние в данном случае. Основное это доступ к элементам — в java массивы хранятся построчно, поэтому доступ по столбцам гораздо менее эффективен, что можно подтвердить следующим тестом:
class A {
    public static void main(String[] args) {
    int n = 8000;
     
    int g[][] = new int[n][n];
    long st, en;
     
    // one
    st = System.nanoTime();
    for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
    g[i][j] = 1;
    }
    }
    en = System.nanoTime();
    System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
     
    // two
    st = System.nanoTime();
    for(int j = 0; j < n; j++) {
    for(int i = 0; i < n; i++) {
    g[i][j] = 1;
    }
    }
    en = System.nanoTime();
    System.out.println("\nTwo time " + (en - st)/1000000.d + " msc");
    }
    }

у меня 70.225679 msc против 2943.409599 msc.

Если вопрос именно по симметричной матрице, то в java 2d массив — это именно массив массивов ( в отличие например от С), поэтому у каждого массива может быть свой размер — можно хранить и заполнять только нижний треугольник матрицы.
в статье приведена эта ссылка
хорошо, у вашего представления свои достоинства, для каких то задач оно подойдет лучше.
в статье про id Tech 6 говорится что
является возможным сжатие SVO до уровня 1,15 битов на один воксел

возможно использовалось похожее представление на предложенное вами.
получается у вас для каждой последовательности должна храниться маска всех предыдущих уровней?
можете привести пример, как в вашем способе будет выглядеть запись дерева, где корень разбит на 8, затем самый левый потомок на восемь и у него самый левый на восемь?
и как вычислять координаты листьев при таком представлении?
хорошо, а если разбить 3-тий уровень? в данном подходе затраты на хранение будут расти с каждым уровнем.
а что будет при разбиении например каждого листа на предыдущем уровне на 8 частей — придется хранить всю эту информацию, по байту на каждое разбиение.
в приведенном способе обход осуществляется сразу по листьям.
да, это полное разбиение пространства, на этом и основан алгоритм.
да, думал речь идет про 60 бит (3 по 20) для кода.
я не понял как у вас получилось 39 бит и что значит 606 бит на уточнение координат. то есть по вашему для хранения приведенного выше дерева нужно 39 + 606 = 645 бит против 60 предложенных в статье?
что будет происходить при более глубоком дереве — нужно сохранять весь путь?
Итого на структуру дерева — 39 бит (против 60 в вашем примере) плюс 606 бит на уточнение координат.

хорошо, в предложенном в статье способе 60 бит не хранятся, а вычисляются. Храниться только 4 бита на лист — все больше ни чего — ни предыдущие уровни, ни каких масок и тд.
Возможно тогда напишу статью с более подробным описанием самого представления.
в записи дерева ошибка, правильно так:
                       000000
                         | 
   =======================================================
   000000 001000 010000 011000 100000 101000 110000 111000
                   |
      =======================================================
      010000 010001 010010 010011 010100 010101 010110 010111

[2|2 3|3 3|3 3|3 3|3 2|2 2|2 2|0] (считаем что 0 — отсутствие элемента, нумерация уровней с 1).
Если я правильно понял, вы описали линейное представление октодерева, кодируемое из иерархического:
                      000000
                         | 
   ================================================
   000000 001000 010000 011000 100000 101000 111000
                   |
      =======================================================
      010000 010001 010010 010011 010100 010101 010110 010111


то есть для листьев сохраняется весь путь по дереву. Чем глубже дерево, тем больше будет этот путь — по 3 бита на уровень (2^3 = 8 частей). Тогда для дерева глубиной 16 необходимо 45 бит на лист + глубина. И код Мортона здесь не нужен.
В описываемом в статье способе листья дерева располагаются вдоль кривой(Лебега, Гильберта и тд) и храниться только их глубина, то есть все дерево из примера будет храниться как
[1|2 2|2 2|2 2|2 2|1 1|1 1|1 1|1] (здесь запись x|y означает десятичную запись числа, где каждый элемент представляет байт — 0000|0000) — используется 4 бита на лист. Далее только по этому значению глубины можно вычислить вещественные координаты каждого листа.

Information

Rating
Does not participate
Registered
Activity