Ticket #1740 (closed: fixed)

Opened 10 years ago

Last modified 5 years ago

Fast Sorting Algorithm

Reported by: Owen Arnold Owned by: Janik Zikovsky
Priority: major Milestone: Iteration 26
Component: Mantid Keywords:
Cc: zikovskyjl@… Blocked By:
Blocking: Tester: Peter Peterson

Description (last modified by Peter Peterson) (diff)

Sorting too slow for EventWorkspaces. std::sort used in EventWorkspace.cpp i.e. std::sort(events.begin(), events.end(), compareEventTof);

Implement faster Counting Sort generic algorithm as a replacement for Quick Sort std::sort. The following implmentation has been prototyped:

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Counting_sort

The counting sort algorithm may also be parallelised using OpenMP.

Change History

comment:1 Changed 10 years ago by Janik Zikovsky

  • Cc zikovskyjl@… added

comment:2 Changed 10 years ago by Peter Peterson

  • Milestone changed from Iteration 25 to Iteration 26

comment:3 Changed 10 years ago by Peter Peterson

  • Description modified (diff)

Another way to do this is to use a merge sort algorithm which can do the sorting in place rather than creating a copy.

comment:4 Changed 10 years ago by Janik Zikovsky

  • Owner changed from Peter Peterson to Janik Zikovsky
  • Status changed from new to accepted

comment:5 Changed 10 years ago by Janik Zikovsky

(In [7923]) Refs #1740: Parallelized sorting of a single event list - first check in. More than 2x faster than the basic algorithm.

comment:6 Changed 10 years ago by Janik Zikovsky

(In [7925]) Refs #1740: Fine-tuning of parallelized sortAll() method.

comment:7 Changed 10 years ago by Janik Zikovsky

  • Status changed from accepted to verify
  • Resolution set to fixed

comment:8 Changed 10 years ago by Peter Peterson

  • Status changed from verify to verifying
  • Tester set to Peter Peterson

comment:9 Changed 10 years ago by Peter Peterson

  • Status changed from verifying to closed

This works as advertised.

comment:10 Changed 5 years ago by Stuart Campbell

This ticket has been transferred to github issue 2587

Note: See TracTickets for help on using tickets.