AMcoder - javascript, python, java, html, php, sql

Ստեղծեք 3 վեկտորներից եռյակների զույգերի բոլոր հնարավոր համակցությունները՝ իրենց սկզբնական կոորդինատներով

Հաշվի առնելով 3 տող A,B,C վեկտորները Matlab-ում, ես ուզում եմ ստեղծել D մատրիցը, որը հաղորդում է A,B,C-ից եռյակների զույգերի բոլոր հնարավոր համակցությունները A,B,C-ում դրանց սկզբնական կոորդինատների հետ միասին:

Ես գրել եմ կոդ, որն անում է այն, ինչ ուզում եմ։ Քանի որ ես փորձում եմ հնարավորինս օպտիմալացնել իմ կոդը (կոդը պետք է կրկնվի միլիոնավոր անգամներ), ես կցանկանայի իմանալ՝ կարո՞ղ եք ավելի արդյունավետ լուծումներ մտածել: Օրինակ, իմ ծածկագրում ես նախապես չեմ հատկացնում D մատրիցը, քանի որ չգիտեմ, թե ինչպես ստանալ յուրաքանչյուր զույգ եռյակի ինդեքսը, և դա արդյունավետ չէ:

Ստորև բերված կոդը դա ավելի լավ կբացատրի.

clear 
A=[1 2];
B=[-4 -2 5];
C=[8 9 -3 0];

sA=size(A,2);
sB=size(B,2);
sC=size(C,2);
sT=sA*sB*sC;

%Generate the matrix D of dimension [sT*(sT-1)/2]x[12]
%reporting all the possible combinations of pairs of triplets from A,B,C
%together with their original coordinates in A,B,C

[ca, cb, cc] = ndgrid(A, B, C);
T = [ca(:), cb(:), cc(:)];  %matrix of dimension sTx3 reporting all the possible triplets 
                            %from A,B,C

[ca, cb, cc] = ndgrid(1:sA, 1:sB, 1:sC);
Tcoord = [ca(:), cb(:), cc(:)];  %matrix of dimension sTx3 reporting the coordinates of all 
                                 %the possible triplets from A,B,C

D=[];
for w=1:sA*sB*sC
    for r=w+1:sA*sB*sC 
        D=[D; T(w,:) T(r,:) Tcoord(w,:) Tcoord(r,:)];
    end
end

Պատասխանները:


1

Վերջին nested for loop-ը, որը լրացնում է D մատրիցը, կարող է շատ ավելի արդյունավետ լինել: OP-ը տեղում է իր հայտարարության մեջ.

Օրինակ, իմ ծածկագրում ես նախապես չեմ հատկացնում D մատրիցը, քանի որ չգիտեմ, թե ինչպես ստանալ յուրաքանչյուր զույգ եռյակի ինդեքսը, և դա արդյունավետ չէ:

Մենք կարող ենք վեկտորացնել աշխատանքի մեծ մասը այդ օղակներում՝ նկատելով, որ կա մի օրինաչափություն, որին OP-ն ակնարկում է D մատրիցայի վերջնական չափի վերաբերյալ իրենց մեկնաբանություններում (այսինքն՝ Generate the matrix D of dimension [sT*(sT-1)/2]x[12]): Այդ առաջին հարթությունը ծանոթ կլինի բոլորին, ովքեր բավականին քիչ են աշխատել շարքերի և հաջորդականությունների հետ: Դա Եռանկյունի թվերի բանաձեւն է:

Սա նկատի ունենալով, մենք կարող ենք տեսնել, որ վերջնական արդյունքում առաջին 3 սյունակները (և 7-ից 9-րդ սյունակները) կրկնվում են 23 անգամ, այնուհետև 22 անգամ և այսպես շարունակ, մինչդեռ 4-ից 6-ը (և 10-ից 12-րդ) սյունակները վերջին 23 շարքերը T/Tcoord, վերջին 22 շարքերը T/Tcoord և այլն: Կոդում մենք ունենք.

D1 = zeros(sT * (sT - 1) / 2, 12);
s = 1;
e = sT - 1;

for w = 1:(sT - 1)
    D1(s:e,[1:3,7:9]) = repmat([T(w,:),Tcoord(w,:)], sT - w, 1);
    D1(s:e,[4:6,10:12]) = [T((w+1):sT,:),Tcoord((w+1):sT,:)];
    s = e + 1;
    e = e + (sT - (w + 1));
end

Եվ յուրաքանչյուր մեթոդ գործարկելով 200 անգամ՝ օգտագործելով tic և toc, մենք տեսնում ենք, որ մենք ունենք արդյունավետության գրեթե 35% աճ:

% OP's setup code goes here

tic
for i=1:200
    D=[];
    for w=1:sA*sB*sC
        for r=w+1:sA*sB*sC
            D=[D; T(w,:) T(r,:) Tcoord(w,:) Tcoord(r,:)];
        end
    end
end
toc

tic
for i = 1:200
    D1 = zeros(sT * (sT - 1) / 2, 12);
    s = 1;
    e = sT - 1;

    for w = 1:(sT - 1)
        D1(s:e,[1:3,7:9]) = repmat([T(w,:),Tcoord(w,:)], sT - w, 1);
        D1(s:e,[4:6,10:12]) = [T((w+1):sT,:),Tcoord((w+1):sT,:)];
        s = e + 1;
        e = e + (sT - (w + 1));
    end
end
toc

% Gives same result
isequal(D, D1)

% Timing for 200 runs on 24 total combinations
Elapsed time is 2.09613 seconds.
Elapsed time is 1.35988 seconds.
ans = 1

Եթե ​​մուտքային վեկտորները մեծացնենք, ապա արդյունավետության էլ ավելի մեծ բարելավում ենք տեսնում: Ստորև բերված են յուրաքանչյուր մեթոդի վրա 15 անգամ վազելու արդյունքները հետևյալ վեկտորների վրա.

A=[1 2 3 4 23];
B=[-4 -2 5 74];
C=[8 9 -3 0];

% Timing for 15 run on 80 total combinations
Elapsed time is 4.00448 seconds.
Elapsed time is 0.379919 seconds.
ans = 1

Դա ավելի քան 10 անգամ ավելի արագ է: Բացը երկրաչափականորեն աճում է, քանի որ ձեր մուտքային վեկտորների չափը մեծանում է:

A=[1 2 3 4 23];
B=[-4 -2 5 74 28];
C=[8 9 -3 0 -100 -5];

% Timing for 1 run on 150 total combinations
Elapsed time is 3.63065 seconds.
Elapsed time is 0.0481789 seconds.
ans = 1

Դա մոտ 75 անգամ ավելի արագ է!!!


Թարմացնել

OP-ը մեկնաբանություններում տվել է շատ ավելի բարձր պատասխան.

indices=nchoosek((1:1:sT),2);
D=[T(indices(:,1),:) T(indices(:,2),:) Tcoord(indices(:,1),:) Tcoord(indices(:,2),:)];

Ահա այն կոդը, որը ես համեմատել եմ.

clear 
A=[1 2 3 4 23 24 25 26];
B=[-4 -2 5 74 28 10 11 12 13];
C=[8 9 -3 0 -100 -5 60 120];

sA=size(A,2);
sB=size(B,2);
sC=size(C,2);
sT=sA*sB*sC;

tic
for i = 1:10
    [ca, cb, cc] = ndgrid(A, B, C);
    T = [ca(:), cb(:), cc(:)];
    [ca, cb, cc] = ndgrid(1:sA, 1:sB, 1:sC);
    Tcoord = [ca(:), cb(:), cc(:)];

    D1 = zeros(sT * (sT - 1) / 2, 12);
    s = 1;
    e = sT - 1;

    for w = 1:(sT - 1)
        D1(s:e,[1:3,7:9]) = repmat([T(w,:),Tcoord(w,:)], sT - w, 1);
        D1(s:e,[4:6,10:12]) = [T((w+1):sT,:),Tcoord((w+1):sT,:)];
        s = e + 1;
        e = e + (sT - (w + 1));
    end
end
toc

tic
for i = 1:10
    indices=nchoosek((1:1:sT),2);
    D=[T(indices(:,1),:) T(indices(:,2),:) Tcoord(indices(:,1),:) Tcoord(indices(:,2),:)];
end
toc

isequal(D, D1)

Եվ ահա արդյունքները.

% Timing for 10 runs on 576 total combinations
Elapsed time is 1.9834 seconds.
Elapsed time is 0.13818 seconds.
ans = 1

Իմ տրամադրած բարելավված լուծումն ավելի լավն է, քան բնօրինակը լավ տարբերությամբ, բայց չի համապատասխանում OP-ի թարմացված լուծմանը: Այն ավելի արագ և էլեգանտ է պատվիրում, կարող եմ ավելացնել:

02.08.2018
  • Շնորհակալություն։ Ինչ վերաբերում է indices=nchoosek((1:1:sT),2); D=[T(indices(:,1),:) T(indices(:,2),:) Tcoord(indices(:,1),:) Tcoord(indices(:,2),:)];ին: 03.08.2018
  • Նոր նյութեր

    Օգտագործելով Fetch Vs Axios.Js-ը՝ HTTP հարցումներ կատարելու համար
    JavaScript-ը կարող է ցանցային հարցումներ ուղարկել սերվեր և բեռնել նոր տեղեկատվություն, երբ դա անհրաժեշտ լինի: Օրինակ, մենք կարող ենք օգտագործել ցանցային հարցումը պատվեր ներկայացնելու,..

    Տիրապետել հանգստության արվեստին. մշակողի ուղեցույց՝ ճնշման տակ ծաղկելու համար
    Տիրապետել հանգստության արվեստին. մշակողի ուղեցույց՝ ճնշման տակ ծաղկելու համար Ինչպե՞ս հանգստացնել ձեր միտքը և աշխատեցնել ձեր պրոցեսորը: Ինչպես մնալ հանգիստ և զարգանալ ճնշման տակ...

    Մեքենայի ուսուցում բանկային և ֆինանսների ոլորտում
    Բարդ, խելացի անվտանգության համակարգերը և հաճախորդների սպասարկման պարզեցված ծառայությունները բիզնեսի հաջողության բանալին են: Ֆինանսական հաստատությունները, մասնավորապես, պետք է առաջ մնան կորի..

    Ես AI-ին հարցրի կյանքի իմաստը, այն ինչ ասում էր, ցնցող էր:
    Այն պահից ի վեր, երբ ես իմացա Արհեստական ​​ինտելեկտի մասին, ես հիացած էի այն բանով, թե ինչպես է այն կարողանում հասկանալ մարդկային նորմալ տեքստը, և այն կարող է առաջացնել իր սեփական արձագանքը դրա..

    Ինչպես սովորել կոդավորումը Python-ում վագրի պես:
    Սովորելու համար ծրագրավորման նոր լեզու ընտրելը բարդ է: Անկախ նրանից, թե դուք սկսնակ եք, թե առաջադեմ, դա օգնում է իմանալ, թե ինչ թեմաներ պետք է սովորել: Ծրագրավորման լեզվի հիմունքները, դրա..

    C++-ի օրական բիթ(ե) | Ամենաերկար պալինդրոմային ենթաշարը
    C++ #198-ի ամենօրյա բիթ(ե), Ընդհանուր հարցազրույցի խնդիր. Ամենաերկար պալինդրոմային ենթատող: Այսօր մենք կանդրադառնանք հարցազրույցի ընդհանուր խնդրին. Ամենաերկար palindromic substring...

    Kydavra ICAReducer՝ ձեր տվյալների ծավալայինությունը նվազեցնելու համար
    Ի՞նչ է ICAReducer-ը: ICAReducer-ն աշխատում է հետևյալ կերպ. այն նվազեցնում է նրանց միջև բարձր փոխկապակցված հատկանիշները մինչև մեկ սյունակ: Բավականին նման է PCAreducer-ին, չնայած այն..