LINUX.ORG.RU

Простите бога ради ``\/^.^\/``

 , , , ,


2

1

Но что-то я туплю конкретно.

Есть к примеру такая сетка 8x8

 _0_1_2_3_4_5_6_7                         _0__1__2__3__4__5__6__7
0|0 0 0 0 0 0 0 0                        0|0  1  2  3  4  5  6  7
1|0 0 0 0 0 0 0 0                        1|8  9  10 11 12 13 14 15
2|0 0 0 0 0 0 0 0 (с вот таким порядком) 2|16 17 18 19 20 21 22 23
3|0 0 0 0 0 x 0 0 ---------------------> 3|24 25 26 27 28 x  30 31 
4|0 0 0 0 0 0 0 0                        4|32 33 34 35 36 37 38 39
5|0 0 0 0 0 0 0 0                        5|40 41 42 43 44 45 46 47
6|0 0 0 0 0 0 0 0                        6|48 49 50 51 52 53 54 55
7|0 0 0 0 0 0 0 0                        7|56 57 58 59 60 61 62 63 

Тут позиция по ординатам x = 3x5, номер x = 29

Как быстро преобразовывать позицию x в координату x:y и обратно, без циклов.

Ну например ячейка 43 вычисляем 5x3, есть позиция 5x3 вычисляем 43.

Реальная сетка у меня 255x255 то есть 65536 позиций. Так что switch() не прокатит.

Я вот прям чёт не догоняю и меня переклинило уже, аж прям бесит и ощущение что я придурок =(


UDP: >>>>>> Решено

UDP:2 >>>> Фикс косяка

строка = цел(значение / колво-столбцов)

столбец = остаток-от-деления(значение / колво-столбцов)

bvn13 ★★★★★ ()

эээ кажется всё

просто, нет?

x = N mod 255 y = N / 255

деление целочисленно, x и y возможно нужно поменять местами.

sshestov ()

Попробуй восьмиричную систему счисления

deterok ★★★★★ ()

i*N+j, где i - номер строки, j - номер столбца, N - количество столбцов.

Конец рабочего дня, ещё и не так клинить может.

grem ★★★★★ ()
Последнее исправление: grem (всего исправлений: 2)

Берешь строку, например 3, берешь солбец, например 5 суммируешь like strings (3 и 5 в 35) и переводишь получившееся число из 8 СС в 10 и получишь 29. Если сетка всегда равносторонняя, то просто берешь длину стороны матрицы за СС. Т.е. в твоем случае надо взять 255 ричную СС. И когда у тебя X будет на каком-то 10x10 ты просто конвертируешь 10x10 -> AxA складываешь AA и конвертируешь из 255 в 10 СС получаешь свое 2560.

Соответственно матрицу нигде хранить не надо

UPD: Если у тебя не равносторонний квадрат, например 25510

То алгоритм примерно такой Берешь строчку, например 254 и столбец например 9, приводишь оба числа к наименьшей СС. т.е. в данном случае к десятичной (254 преобразовывать не надо в нашем случае т.к. оно уже в 10 и будет 254). Складываешь по тому же принципу 254 и 9 получаешь 2549 и следом это переводишь из той системы счисления к которой приводил числа в 10 (здесь у нас как раз и получиться 2549)

deterok ★★★★★ ()
Последнее исправление: deterok (всего исправлений: 2)

1 координата: делишь на 8, округляешь вниз до целых.
2 координата: берёшь остаток от деления на 8.
/thread.

anonymous ()

если не 255х255, а 256х256 со значениями индексов 0...255, то можно брать младший и второй байты, через маски и сдвиги, ну или деление и остаток, как ранее предлагали.

Elyas ★★★★★ ()

Делаем два списка: четных чисел и нечетных…

x = n & 255;
y = n >> 8;
Deleted ()

Решено

@bvn13 спасибо, @sshestov спасибо, @deterok спасибо (внезапно, попробую), @grem спасибо, @anonymous спасибо, @Elyas спасибо, @erthink спасибо

Чтобы соответствовало таблице, на коленке сделал вот так, может кому пригодится, себе переделаю для моей размерности. Всё робит, спасибо ещё раз всем за варианты.

Эх, глупа моя черешня :D

#include <stdint.h>
#include <math.h>

typedef struct
{
    uint8_t h;
    uint8_t w;
}pose;

uint8_t pose_to_num(uint8_t h,uint8_t w)
{
  return h*8+w;
}

pose num_to_pose(uint8_t num)
{
   uint8_t h = floor(num / 8.5);
   uint8_t w = ((num % 8) == 0)?7:(num % 8) -1;
   return (pose){h,w};
}

int main(int argc, char *argv[])
{
    uint8_t num=0;
    for (int h = 0; h < 8; ++h)
    {
        for (int w = 0; w < 8; ++w)
        {
            num++;
            printf("[%i %i]-[%i]\n",num_to_pose(num).h,num_to_pose(num).w,pose_to_num(h,w));
        }
    }

    return 0;
}

Вывод


dron@gnu:~$ gcc rrr.c -lm;./a.out
[0 0]-[0]
[0 1]-[1]
[0 2]-[2]
[0 3]-[3]
[0 4]-[4]
[0 5]-[5]
[0 6]-[6]
[0 7]-[7]
[1 0]-[8]
[1 1]-[9]
[1 2]-[10]
[1 3]-[11]
[1 4]-[12]
[1 5]-[13]
[1 6]-[14]
[1 7]-[15]
[2 0]-[16]
[2 1]-[17]
[2 2]-[18]
[2 3]-[19]
[2 4]-[20]
[2 5]-[21]
[2 6]-[22]
[2 7]-[23]
[2 0]-[24]
[3 1]-[25]
[3 2]-[26]
[3 3]-[27]
[3 4]-[28]
[3 5]-[29]
[3 6]-[30]
[3 7]-[31]
[3 0]-[32]
[4 1]-[33]
[4 2]-[34]
[4 3]-[35]
[4 4]-[36]
[4 5]-[37]
[4 6]-[38]
[4 7]-[39]
[4 0]-[40]
[4 1]-[41]
[5 2]-[42]
[5 3]-[43]
[5 4]-[44]
[5 5]-[45]
[5 6]-[46]
[5 7]-[47]
[5 0]-[48]
[5 1]-[49]
[6 2]-[50]
[6 3]-[51]
[6 4]-[52]
[6 5]-[53]
[6 6]-[54]
[6 7]-[55]
[6 0]-[56]
[6 1]-[57]
[6 2]-[58]
[7 3]-[59]
[7 4]-[60]
[7 5]-[61]
[7 6]-[62]
[7 7]-[63]
dron@gnu:~$ 

LINUX-ORG-RU ★★★★★ ()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)
Ответ на: Решено от LINUX-ORG-RU

Пардон нужен фикс


-pose num_to_pose(uint8_t num)
-{
-   uint8_t h = floor(num / 8.5);
-   uint8_t w = ((num % 8) == 0)?7:(num % 8) -1;
-   return (pose){h,w};
-}

+pose num_to_pose(uint8_t num)
+{
+   uint8_t h = ((num % 8) == 0)?floor(num/8.5):floor(num/8);
+   uint8_t w = ((num % 8) == 0)?7:(num % 8) -1;
+   return (pose){h,w};
+}
LINUX-ORG-RU ★★★★★ ()
Последнее исправление: LINUX-ORG-RU (всего исправлений: 1)
Ответ на: Решено от LINUX-ORG-RU

Re: Решено

uint8_t h = floor(num / 8.5);

uint8_t h = ceil(num / 8);

uint8_t w = ((num % 8) == 0)?7:(num % 8) -1;

uint8_t w = num % 8;

anonymous ()
Ответ на: комментарий от LINUX-ORG-RU

сказочный... деление ЦЕЛЫХ решает оригинальную задачу, модуль при этом вычисляется бесплатно (при оптимизациях), флор аппаратный. битовое решение выше для стороны 2^N еще быстрее. какие нах флоаты? код ни один не правильный, если это попытка обернуть 1-based num, то его просто надо сдвинуть на 1

anonymous ()
Ответ на: комментарий от anonymous

код ни один не правильный

Покажи, как надо.

anonymous ()
Ответ на: комментарий от LINUX-ORG-RU

Что за бред? Нафига тут вообще флоаты?

SZT ★★★★★ ()
Ответ на: комментарий от SZT

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

SZT ★★★★★ ()
Последнее исправление: SZT (всего исправлений: 1)

Ты чо, пьяный?

int d = 29
int xmask = 7; //0x111
int yshift = 3;
int x = d & xmask; //5
int y = d >> yshift; //3
Как-то так, на плюсах не тестил.

crutch_master ★★★★★ ()

Реальная сетка у меня 255x255 то есть 65536 позиций.

256. Тоже самое, только xmask = 255 и yshift = 8.

crutch_master ★★★★★ ()
Ответ на: Re: Решено от anonymous

Re: Решено

uint8_t h = floor(num / 8.5);

uint8_t h = ceil(num / 8);

uint8_t h = ceil((num-1) / 8);

uint8_t w = ((num % 8) == 0)?7:(num % 8) -1;

uint8_t w = num % 8;

uint8_t w = (num-1) % 8;

anonymous ()

Ребята, я дико извиняюсь

... я как бы за программированием не особо слежу

А что, правда, что финты со сдвигами или преобразованиями типов могут чисто гипотетически быть быстрее, чем просто целочисленное деление и деление по модулю? Они разве при компиляции сами не компилируются нормальным образом?

И это, хоть какая-нибудь практическая польза может быть от такой оптимизации?

sshestov ()
Ответ на: Ребята, я дико извиняюсь от sshestov

А что, правда, что финты со сдвигами или преобразованиями типов могут чисто гипотетически быть быстрее, чем просто целочисленное деление и деление по модулю?

Ну, если деление компилятором не свернётся в сдвиг.

И это, хоть какая-нибудь практическая польза может быть от такой оптимизации?

Да, деление - сложная операция.

crutch_master ★★★★★ ()
Ответ на: комментарий от crutch_master

ну вот и вопрос:

разве деление не свернется в сдвиг автоматом и может ли в принципе влиять такая сложная операция как целочисленное деление на общую производительность (на фоне всего остального и 300 закладок в хроме)

sshestov ()
Ответ на: ну вот и вопрос: от sshestov

разве деление не свернется в сдвиг автоматом

Если оно на переменную, то как оно свернётся? Если на константу, то может и свернётся во время компиляции. В любом случае явное лучше неявного.

и может ли в принципе влиять такая сложная операция как целочисленное деление на общую производительность

Ну если у тебя преобразование цвета пикселей, которое делается делением вместо сдвига 60 раз в секунду по 6 мил. штук, по double вместо byte, да, будет очень заметно.

crutch_master ★★★★★ ()

Фантастический тупняк астрономических размеров :) Задача школьной информатики )))

Ничего страшного, я тебя утешу, со всеми бывает, всё нормально. Когда я затуплю на ЛОРе вы меня тоже простите заранее :)

I-Love-Microsoft ★★★★★ ()

Ближайший процессорный div (целочисленный, с остатком). В одном регистре окажется строка, в другом - столбец. Быстрее придумать сложно.

В обратную сторону - просто умножение со сложением на ЯВУ.

AlexAT ()
Последнее исправление: AlexAT (всего исправлений: 4)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.