5
$\begingroup$

This a very useful function, but it is very slow:

FindShortestTour[{{0, 0}, {0.2`, 0}, {2, 1}, {2, 2}, {2, 2.5`}, {1.5`,
6}, {1.6`, 7}, {1.4`, 8}, {1.9`, 10}}]; // AbsoluteTiming

{1.80721, Null}

I tested just 9 points, which cost me almost $2s$. I think there is a bug is behind this behavior. So I reported to Wolfram Support (CASE:3847386), but I received a response like:

Thank you for contacting Wolfram Technical Support.

I followed your example and evaluated it on my machine:

FindShortestTour[{{0, 0}, {0.2`, 0}, {2, 1}, {2, 2}, {2, 2.5`}, {1.5`, 6}, {1.6`, 7}, 
      {1.4`, 8}, {1.9`, 10}}]; // AbsoluteTiming
(* {0.0847348,Null} *)

Please consider resetting Mathematica and see if the issue can be resolved.

My processor is a Intel® Core™ i5-6500 Processor, and when I run Needs["Benchmarking`"]; Benchmarking`BenchmarkReport[], my system scored $1.29$ WolframMark points. Many time show it is a very low efficency function:

Table[
 First[
  FindShortestTour[
   {{0, 0}, {0.2`, 0}, {2, 1}, {2, 2}, {2, 2.5`}, {1.5`, 6}, {1.6`, 7},
    {1.4`, 8}, {1.9`, 10}}]; // AbsoluteTiming
 ], 
 5
]

{2.43196,2.01361,2.37832,1.97023,1.78632}

I would like to confirm whether some bug in this function is causing this behavior.


Update

This is a regression of version 11.0, and just on Windows:

test on windows

enter image description here

test on mac

enter image description here

test on linux

enter image description here

$\endgroup$
  • $\begingroup$ I get 0.089819 seconds on a Mac running v. 10.4. $\endgroup$ – David G. Stork Feb 23 '17 at 2:51
  • $\begingroup$ @DavidG.Stork Thanks,desire to see a v11.0.1 tester,which can help me give a further response. $\endgroup$ – yode Feb 23 '17 at 2:58
  • $\begingroup$ I get 0.005714 seconds on a MacBookPro (new model), Version 11.0.1 of Mathematica $\endgroup$ – mgamer Feb 23 '17 at 6:09
  • $\begingroup$ I get {0.007223, Null} on my i5 6400 running 11.0. On that benchmark function I get between 1.89 and 2.20 $\endgroup$ – bobbym Feb 23 '17 at 15:07
  • $\begingroup$ Can we confirm this as Windows-specific? On my mac I get less than 10 ms for any version, but my deskmate uses windows and found in version 11 that RepeatedTiming was taking longer than he was interested in letting it run. $\endgroup$ – Jason B. Feb 23 '17 at 17:24
3
$\begingroup$

This is a comment, to confirm that I see the unreasonably slow results as well. My system is a reasonably recent dual-core laptop running Win7-64. I tried the same calculation on MMA 11 and 10.4.

My results (shown below) seem to support the observation that FindShortestTour is awfully slow on recent MMA implementations on the Windows platform; notice also that there the performance seems to have worsened from MMA 10.4 to MMA 11.0 on Windows.

pts = {{0, 0}, {0.2, 0}, {2, 1}, {2, 2}, {2, 2.5}, {1.5, 6}, {1.6, 7}, {1.4, 8}, {1.9, 10}};

$Version
(* "10.4.0 for Microsoft Windows (64-bit) (February 26, 2016)" *)

FindShortestTour[pts]; // RepeatedTiming
(* {6.738, Null} *)

$Version
(* "11.0.1 for Microsoft Windows (64-bit) (September 20, 2016)" *)

FindShortestTour[pts]; // RepeatedTiming
(* {7.24, Null} *)
$\endgroup$
  • $\begingroup$ The WL just think this phenomenon appear in specific machine. $\endgroup$ – yode Feb 23 '17 at 16:57
  • $\begingroup$ @yode Perhaps others with MMA 11 on Windows machines will chime in as well and report their experience. $\endgroup$ – MarcoB Feb 23 '17 at 19:16
  • 1
    $\begingroup$ On my 8-years old Lenovo R500 laptop running Windows 7 x64 I get timings 0.0426 sec with version 11.0.0 and 0.044 sec with version 10.4.1. My laptop has Intel processor (Mobile DualCore Intel Core 2 Duo P8400, 2400 MHz). Which processor is installed on your system? $\endgroup$ – Alexey Popkov Feb 24 '17 at 6:27
0
$\begingroup$

I don't know why the GraphComputation`LegacyFindShortestTour always faster than FindShortestTour

SeedRandom[1]
pts = RandomReal[1, {10, 2}];

GraphComputation`LegacyFindShortestTour

AbsoluteTiming[First[GraphComputation`LegacyFindShortestTour[pts]]]

{0.00929029,2.90719}

FindShortestTour

AbsoluteTiming[First[FindShortestTour[pts]]]

{0.687586,2.90719}

$\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.