3
$\begingroup$

Background

I am using Mathematica to solve a traveling-salesman-like problem. I implemented two different algorithms that are able to solve this type of problem and both algorithms yield the same result, which is good.

Problem

However, one algorithm takes approximately 20 times longer than the other (measured with Timing). After analyzing the slow algorithm with the tool RuntimeTools`Profile (see here) I found out that about 70% of the execution time is used to read floating-point numbers from long lists.

To isolate the problem, I wrote the following example Mathematica code:

testFunc := Block[{len, idx, dummyVar, timingResult, randomArray},
   len = 15000;
   testTime = 0.;
   randomArray = Table[RandomReal[{1, 100000}], {len}];
   Do[
      idx = RandomInteger[{1, len}];
      timingResult = Timing[randomArray[[idx]]];
      testTime += timingResult[[1]];
      , {1200000}
   ];
];

After executing this function, the value of the variable testTime which represents the CPU time in seconds spent to read values from randomArray is 2.49.
Just out of curiosity, I wrote some C++ code to see how long it would take to read values from an array the same number of times in C++:

#include <iostream>
#include <ctime>
#include <time.h>
#include <stdlib.h>


using namespace std;

int main() {
    srand(time(NULL));
    const int len = 15000;
    clock_t testTime = 0;
    double randomArray[len];
    double min = 1;
    double max = 100000;
    for (int i = 0; i < len; i++) {
        randomArray[i] = min + ((double)rand() / RAND_MAX) * (max-min);
    }

    double dummyVar;
    for (int i = 0; i<1200000; i++) {
        int idx = rand() % len;
        clock_t c_start = clock();
        dummyVar = randomArray[idx];
        clock_t c_end = clock();
        testTime += (c_end-c_start);
    }

    cout<<"CPU time: "<<1000.0 * testTime / CLOCKS_PER_SEC<<" ms"<<endl;
    return 0;
}

The output of this code is that 0.4427 seconds were needed to read values from randomArray.

Question

Is there a way to make reading from long lists in Mathematica more efficient? Or is there another data type in Mathematica that is better suited for my purposes?

After googling on this topic and not finding a solution for quite some time, I would be very happy about some help. Thank you in advance!

$\endgroup$
  • 1
    $\begingroup$ In general in Mathematica, looping over lists is the slowest way to go. Vectorizing your operations (operating on an entire list at once with a built-in Listable function) will give you the biggest speed gains. You could also try using Compile. See mathematica.stackexchange.com/a/29351/8253 and Leonid Shifrin's online book (mathprogramming-intro.org) for these and other tips. $\endgroup$ – Simon Rochester Dec 11 '16 at 1:13
  • $\begingroup$ @SimonRochester. The question has nothing to do with looping. The OP is timings are measuring the time it takes Part to access an element in a long list. $\endgroup$ – m_goldberg Dec 11 '16 at 1:27
  • $\begingroup$ @m_goldberg Sure, I'm just saying that with a vectorized algorithm, it wouldn't be necessary to access each element individually with Part. Of course, it may be that such an algorithm isn't feasible for this problem -- then one of Leonid's many other pieces of advice will probably be useful :) $\endgroup$ – Simon Rochester Dec 11 '16 at 1:56

Your Answer

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

Browse other questions tagged or ask your own question.