1
\$\begingroup\$

I have two lists of numbers:

$$\{i_1, i_2, i_3,i_4\}$$ and $$\{j_1,j_2,j_3,j_4\}$$

The problem I want to solve is: Inside a loop, if the following two conditions are satisfied, then it will do something I want, otherwise it just cycle the loop. The conditions are:

  1. Both lists contain four different numbers;
  2. If ignoring the ordering, in other words, we view these two lists as two set, then they are the same.

I want to find a very fast way to get the answer to the problem. I have very slow Fortran code as follows:

if (i2==i1) cycle
if (i3==i1) cycle
if (i3==i2) cycle
if (i4==i1) cycle
if (i4==i2) cycle
if (i4==i3) cycle

if (j2==j1) cycle
if (j3==j1) cycle
if (j3==j2) cycle
if (j4==j1) cycle
if (j4==j2) cycle
if (j4==j3) cycle 
q1=0
q2=0
q3=0
q4=0
if (i1==j1)q1=1
if (i1==j2)q1=2
if (i1==j3)q1=3
if (i1==j4)q1=4
if (i2==j1)q2=1
if (i2==j2)q2=2
if (i2==j3)q2=3
if (i2==j4)q2=4
if (i3==j1)q3=1
if (i3==j2)q3=2
if (i3==j3)q3=3
if (i3==j4)q3=4
if (i4==j1)q4=1
if (i4==j2)q4=2
if (i4==j3)q4=3
if (i4==j4)q4=4

if (q1*q2*q3*q4==24)then
 Something I want to do
endif

I think to find a good program, the following should also be considered as well as cutting down the number of instructions:

  1. The probability to have four different numbers in both lists are about 1/10;
  2. The probability to have for these two lists containing two same set of numbers are very small, about 10^(-11);
  3. I really have to do many loops.

Could someone help me out? I think a good idea can really boost the code.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ What are the ranges of the loops? Are those if statements at the inner-most loop, or are they located at the top level of the loop(s)? \$\endgroup\$ – Kyle Kanos Jun 29 '18 at 14:12
  • \$\begingroup\$ "The probability to have four different numbers in both lists are about 1/10" This is a lottery? \$\endgroup\$ – curiousguy Jun 29 '18 at 16:21
  • \$\begingroup\$ Hi @KyleKanos, thanks for asking, I modify the code in the question, hope it is clear this time. \$\endgroup\$ – xjtan Jun 30 '18 at 14:03
  • \$\begingroup\$ @curiousguy, I am doing some extensive Monte Carlo simulation for a very rare event in clusters and the situation is very challenging. \$\endgroup\$ – xjtan Jun 30 '18 at 14:05
  • \$\begingroup\$ @xjtan I don't understand the loop. Where are the i1,i2,etc values set? Rather than trying to post some partial code, can you instead post the actual code you're using in production? Otherwise, this question makes no sense. \$\endgroup\$ – Kyle Kanos Jun 30 '18 at 15:04
1
\$\begingroup\$

The only way to reduce the number of operations is to sort one of the arrays. But 4 elements is hardly worth it.

Perhaps when adding the numbers to the array then add them in a sorted order, otherwise quicksort is good for arrays under 10 elements in size.

Performing a binary search on a sorted array would give you O(log n) time for each search - with O(n log n) time to compare two full arrays of the same size. Quicksort is O(n log n), with binary search that's roughly O(2[n log n]).

Adding items in a sorted order, then searching, would be a similar complexity: O(n log n) for adding 'n' items, and O(n log n) for searching through n items. I prefer this solution because it's one simple algorithm, and it's cleaner.

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I think for this problem of small size( by small I mean the size of the list is just four), the complexity theory is not very useful here since I am only concern with this particular small system, the thing really matters here is cutting the number of instructions. \$\endgroup\$ – xjtan Jun 30 '18 at 14:07
0
\$\begingroup\$

Though I think the problem here is not speed, but number of code lines. For short code arrays would be best.

As extra in pseudo-code short (readable) code (with arrays):

// Determine equality between i[] and j[].
dim k(1 to 4)     // Indices into j[].
for m = 1 to 4
    k[m] = m
for m = 1 to 4
    found = false
    for n = m to 4
        if (i[m] == j[k[n]])
            found = true
            t = k[m]
            k[m] = k[n]
            break
    next n
    if !found fail
next m

One can roll this out using variables:

// (First version.)
// Determine equality between {i1, i2, i3, i4}] and {j1, j2, j3, j4}.
if i1 != j1
    if i1 != j2
        if i1 != j3
            if i1 != j4
                cycle
            else
                j4 = j1
        else
            j3 = j1
    else
        j2 = j1
if i2 != j2
    if i2 != j3
        if i2 != j4
            cycle
        else
            j4 = j2
    else
        j3 = j2
if i3 != j3
    if i3 != j4
        cycle
    else
        j4 = j3
if i4 != j4
    cycle
success

Which is the same as:

// (Second version.)
// Determine equality between {i1, i2, i3, i4}] and {j1, j2, j3, j4}.
if i1 == j4
    j4 = j1
else if i1 == j3
    j3 = j1
else if i1 == j2
    j2 = j1
else if i1 != j1

if i2 = j4
    j4 = j2
else if i2 = j3
    j3 = j2
eise if i2 != j2
    cycle

if i3 = j4
    j4 = j3
else if i3 != j3
    cycle

if i4 != j4
    cycle

Checking for no duplicates should be done first, and can be for instance:

if ((i1-i2)*(i1-i3)*(i1-i4)*(i2-i3)*(i2-i4) == 0) cycle

(Disregarding overflow of multiplication to 0!)

As code review

The array code version I gave, as that is reminiscant to your use of q1, q2, q3, q4: a kind of indexing. I would use primes in order to prevent a mix-up with 1*4=4 and 2*2=4. (Or OR-ing of bit masks.)

For the rest the code has more the feel of assembly language (my code included).

The main optimisation would be in the prelude to this phase in coding: keeping a set, a sorted unique array.

|improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.