Optimization for loop @ Matlab

[Sheogorath]

Καλησπέρα σε όλους,

 

Έχω γράψει έναν κώδικα για LSB stenography στο Matlab, αλλά ένα for loop είναι απίστευτα αργό. Με το κλασσικό tic toc είδα ότι παίρνει κάπου 400 δευτερόλεπτα για να τελειώσει, ενώ άλλα με παρομοιο αριθμό επαναλήψεων χρειάζονται μονοψήφιο αριθμό δευτερολέπτων.

 

Το loop είναι το παρακάτω

 

for i=1:8:1080

    for j=1:1920

        p=p+1;

        if p>378*679

            break;

        end

        for k=1:3

            str1=dec2bin(secret(p,k),8);

            for n=0:7

                str2=dec2bin(reference(i+n,j,k),8);

                str2(8)=str1(n+1);

                reference(i+n,j,k)=bin2dec(str2);

            end

        end

    end

end

 

Με την reference να είναι η μεγάλη εικόνα και η secret η 8 φορές μικρότερη που αντικαθιστά το 8ο μπιτ σε κάθε byte της μεγάλης.

 

parloop δεν μπορεί να γίνει γιατί χτυπάει στην γραμμή με την ανάθεση στον πίνακα reference αλλά και προφανώς θα είχε θέμα με την αλλαγή τιμής στο p=p+1.

 

Καμία ιδέα για το τι μπορεί να γίνει, αν μπορεί να γίνει κάτι? Έχω κάνει καμία γερή πατατιά εκεί μέσα?

[Caiden]

Με μια προχειρη ματια απο κινητο, θα υπολογιζα το 378×679 εξω απο τις for μια φορα και μονο. Με αυτη την μικρη αλλαγη κερδιζεις 200.000+ υπολογισμους, που βεβαια δεν ξερω αν βελτιωσει τον χρονο σου σημαντικα.

[Sheogorath]

Έχεις δίκιο, αλλά και πάλι, τίποτα δεν έκανε. Ο χρόνος δεν έπεσε αρκετό για να φανεί πάνω απο το deviation απο run σε run.

 

Ευχαριστώ πάντως! Καμία άλλη ιδέα? Η κλήση της συνάρτησης καθυστερεί απο ότι κατάλαβα.

[Kercyn]

Μήπως τα πολλά dec2bin σε καθυστερούν; Σχετικά βρήκα την ίδια ερώτηση σε SO και Mathworks, ίσως πάρεις κάποια ιδέα.

[GReaperEx]

Stenography? Περίεργο, να θέλεις να δημιουργήσεις συντομεύσεις λέξεων μέσω matlab... Ακόμα πιο περίεργο είναι ότι ο κώδικας μοιάζει με τεχνική steganography... Περίεργα πράματα.

[Sheogorath]

Stenography? Περίεργο, να θέλεις να δημιουργήσεις συντομεύσεις λέξεων μέσω matlab... Ακόμα πιο περίεργο είναι ότι ο κώδικας μοιάζει με τεχνική steganography... Περίεργα πράματα.

Και εμένα δεν μου κολούσε, αλλά το steganography χτυπάει στο spelling check του Chrome. Βιαζόμουν εκείνη την ώρα και λέω, μάλλον λάθος το θυμάμαι.

[Sheogorath]

Επειδή θα τρελαθώ, αυτό

                if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)

                    reference(i+n,j,k)=reference(i+n,j,k)+1;

                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)

                    reference(i+n,j,k)=reference(i+n,j,k)-1;

                end

δεν είναι ισοδύναμο με

reference(i+n,j,k)=bin2dec(str2);

 

ρίχνει τον χρόνο κάτω απο το μισό (~180 δευτερα) αλλά βγάζει μαύρη εικόνα.

 

 

Αυτό αλλάζοντας μόνο την παραπάνω γραμμή (reference(i+n,j,k)=bin2dec(str2);) και κρατώντας τον άλλο κώδικα ίδιο με το 1ο ποστ.

 

Αν πάλι αλλάξω και την dec2bin με του τύπου στο λινκ, με if κτλ, πέφτει ο χρόνος στα 80 δευτερα, αλλά η φωτογραφία είναι με 30 μοίρες κλιση.

 

for i=1:8:s_Mask1

    for j=1:s_Mask2

        p=p+1;

        if p>limit

            break;

        end

        for k=1:s_Mask3

            str1=dec2bin_2(secret(p,k));

            for n=0:7

                str2=dec2bin_2(reference(i+n,j,k));

                str2(8)=str1(n+1);

                if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)

                    reference(i+n,j,k)=reference(i+n,j,k)+1;

                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)

                    reference(i+n,j,k)=reference(i+n,j,k)-1;

                end

            end

        end

    end

end

 

Ο κώδικας που εμφανίζει μαύρη εικόνα με του matlab, με την δικιά μου dec2bin_2 περνάει την σωστή εικόνα αλλά με κλίση. 

 

Καμία ιδέα?

Και η πλάκα είναι αυτή η γραμμή (3ος τρόπος) θεωρητικά ισοδύναμη

 

reference(i+n,j,k)=str2(1)*2^7+str2(2)*2^6+str2(3)*2^5+str2(4)*2^4+str2(5)*2^3+str2(6)*2^2+str2(7)*2^1+str2(1);

 

βγάζει σκουπίδια.

Ξέρω, και σε for loop την έβαλα str2(m)*2^(8-m) αλλά λέω μπας και έκανα τίποτα λάθος έτσι.

 

Τελικά με την matlabίστικη dec2bin βγάζει άσπρη εικόνα. Με την δική μου βγάζει μόνο σκουπίδια.

 

Θα τρελαθώ. Πάω να δω αν δουλεύει έστω στα 400 δευτερα.

update, τώρα δουλεύει στα 82 δευτερόλεπτα με

 

limit=382*679;

for i=1:8:1080

    for j=1:1920

        p=p+1;

        if p>limit

            break;

        end

        for k=1:3

            str1=dec2bin_2(secret(p,k));

            for n=0:7

                str2=dec2bin_2(reference(i+n,j,k));

                str2(8)=str1(n+1);

                 if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)

                    reference(i+n,j,k)=reference(i+n,j,k)+1;

                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)

                    reference(i+n,j,k)=reference(i+n,j,k)-1;

                end

            end

        end

    end

end

 

Ευχαριστώ!

 

Bonus η εικόνα, αν θέλετε να δείτε τι έχει απο "πίσω".

(τοπίο είναι)

Επεξ/σία 10 Μαΐου 2017 από Sheogorath

[Dr.Fuzzy]

Η χρήση for-loops είναι αντίθετη στη φιλοσοφία της γλώσσας MATLAB στην οποία τα πάντα ειναι optimized για πράξεις με πίνακες και ως συνέπεια καθυστερούν παρά πολυ. Προσπάθησε να κανεις τον κώδικα σου vectorized και να μην γράφεις κώδικα όπως πχ, θα έγραφες C διότι το αποτέλεσμα θα ειναι παρά πολυ αργό όπως στην περίπτωση σου. Επίσης τα if θα μπορούσες να τα αντικαταστήσεις με find. Μπορεις να χρησιμοποιήσεις και τον profiler του MATLAB για να δεις το χρόνο που χρειάζεται το κάθε τμήμα του κώδικα σου.

[Sheogorath]

Το γνωρίζω ότι πρακτικά γράφω C, αλλά το συγκεκριμένο πρόβλημα δεν βρήκα τρόπο να το κάνω vectorized.

 

Για το find θα το κοιτάξω.

[solarpower]

                 if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)

                    reference(i+n,j,k)=reference(i+n,j,k)+1;

                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)

                    reference(i+n,j,k)=reference(i+n,j,k)-1;

                end

Έστω Α=str2(8) και Β=mod(reference(i+n,j,k),2)

1) είναι λάθος να χρησιμοποιείς συνέχεια το reference(i+n,j,k), αλλά σωστό να το βάλεις σε μια μεταβλητή, έτσι δυο φορές το χρειάζεσαι μια για να το πάρεις και μια για να του αλλάξεις τιμή.

2) 'Οπως βλέπω έχεις τα Α και Β ως bit, άρα εδώ η απόφαση έχει να κάνει με μια "πύλη", και όταν αυτό ασχολείται με τα "ανόμοια", τότε είναι σίγουρα το XOR. Θα παρεις δηλαδή το 1 όταν έχεις 0 και 1 ή 1 και 0 στο πρώτο if και δεν χρειάζεσαι δεύτερο, το αν θα είναι -1 ή 1 θα εξαρτηθεί από το 0 ή 1 του Α, πχ το Α*2-1 δίνει -1 αν το Α είναι 0 ή  1 αν το Α είναι 1.

[Dr.Fuzzy]

Για παράδειγμα, δοκίμασε να διώξεις το k loop:

k=[1:3];
limit=382*679;
for i=1:8:1080
    for j=1:1920
        p=p+1;
        if p>limit
            break;
        end
            str1=dec2bin_2(secret(p,k));
            for n=0:7
                str2=dec2bin_2(reference(i+n,j,k));
                str2(8)=str1(n+1);
                 if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)
                    reference(i+n,j,k)=reference(i+n,j,k)+1;
                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)
                    reference(i+n,j,k)=reference(i+n,j,k)-1;
                end
            end
    end
end

[Sheogorath]

 

                 if (str2(8)==1)&&(mod(reference(i+n,j,k),2)==0)

                    reference(i+n,j,k)=reference(i+n,j,k)+1;

                elseif (str2(8)==0)&&(mod(reference(i+n,j,k),2)==1)

                    reference(i+n,j,k)=reference(i+n,j,k)-1;

                end

Έστω Α=str2(8) και Β=mod(reference(i+n,j,k),2)

1) είναι λάθος να χρησιμοποιείς συνέχεια το reference(i+n,j,k), αλλά σωστό να το βάλεις σε μια μεταβλητή, έτσι δυο φορές το χρειάζεσαι μια για να το πάρεις και μια για να του αλλάξεις τιμή.

2) 'Οπως βλέπω έχεις τα Α και Β ως bit, άρα εδώ η απόφαση έχει να κάνει με μια "πύλη", και όταν αυτό ασχολείται με τα "ανόμοια", τότε είναι σίγουρα το XOR. Θα παρεις δηλαδή το 1 όταν έχεις 0 και 1 ή 1 και 0 στο πρώτο if και δεν χρειάζεσαι δεύτερο, το αν θα είναι -1 ή 1 θα εξαρτηθεί από το 0 ή 1 του Α, πχ το Α*2-1 δίνει -1 αν το Α είναι 0 ή  1 αν το Α είναι 1.

 

Όσο αφορά το 1), γιατί είναι λάθος, αφού σε αυτόν τον πίνακα γίνονται οι αλλαγές?

 

Για το 2ο, σωστά, θα μπορούσα αν το κάνω και έτσι, thanks mate.

[Dr.Fuzzy]

Για το 2ο, σωστά, θα μπορούσα αν το κάνω και έτσι, thanks mate.

Μπορείς να απαλλαγείς και απο τα υπόλοιπα loop (ξεκίνα απο μέσα προς τα έξω ένα-ενα) και θα βελτιωθεί ο χρόνος δραματικά. Αυτό ονομάζεται code vectorization στο MATLAB.

[Sheogorath]

Το δοκιμάζω και αυτό άμεσα. Με παρόμοιο τρόπο με το Κ υποθέτω.

[Dr.Fuzzy]

Το δοκιμάζω και αυτό άμεσα. Με παρόμοιο τρόπο με το Κ υποθέτω.

Ναι η βασική ιδέα είναι αυτή.