Sorting collections in Apex and "Too many script statements"
by Andrew Waite on September 22, 2008 at 05:46 PM
There's been a little chatter recently about the script statement limit and specifically around sorting algorithms in Apex.
Instead of burying the solution deep in the annals of the discussion boards, Jon has convinced me to start publishing again. For those that haven't been reading this blog since the days it was proudly branded "sforce", my last post was on 6/13/2005!
Needless to say that's been too long and speaking of that, you're probably saying get on with it already so I will :)
It all started with this little post back when Apex was in developer preview at which time we had not yet exposed a sort() method on the collection types (Array/List). We quickly corrected this and for collections of primitives a quick call to sort() will re-order the list in ascending order.
Great for primitives but what about other types? SObjects for example.... perhaps everyone's favorite standard object - Opportunity?
Before you get caught up or miss the obvious reaction to the following example I will admit it's fairly contrived. If all you want to do is sort opportunities on amount you should do so within your SOQL statement directly (see ORDER BY). Please bear with me for this example as I will tie this technique into my next post regarding a sorting and grouping solution as sought by this thread.
While it may be easy to fall back to a custom sorting algorithm a combination of the standard List.sort() method and associative arrays (Maps) can provide a significantly reduced statement footprint.
Let's take a look at some code that demonstrates the approaches:
@IsTest private class sortTest {
/* Test the approach described by the custom sort */
public static testmethod void testCustomSort() {
List<Opportunity> opps = sortTest.getOpps();
Integer before = Limits.getScriptStatements();
sortTest.quicksortOpptys(opps,0,opps.size() - 1);
Integer after = Limits.getScriptStatements();
System.debug('SCRIPT STATEMENTS USED BY THE CUSTOM SORT: ' + (after - before));
sortTest.doAsserts(opps);
}
/* Test the aproach of using the standard list.sort() method and a map */
public static testmethod void testStandardSort() {
List<Opportunity> opps = sortTEST.getOpps();
Integer before = Limits.getScriptStatements();
opps = sortTest.sortStandard(opps);
Integer after = Limits.getScriptStatements();
System.debug('SCRIPT STATEMENTS USED BY THE STANDARD SORT: ' + (after - before));
sortTest.doAsserts(opps);
}
/* Sort the collection of opportunities using the standard collection sort method. */
private static List<Opportunity> sortStandard(List<Opportunity> opps) {
List<Opportunity> resultList = new List<Opportunity>();
/* Create a map of amount to Opportunity collection */
Map<Decimal, List<Opportunity>> oppMap = new Map<Decimal, List<Opportunity>>();
for(Opportunity o:opps) {
if(oppMap.get(o.amount) == null) { oppMap.put(o.amount, new List<Opportunity>()); }
oppMap.get(o.amount).add(o);
}
List<Decimal> keys = new List<Decimal>(oppMap.keySet());
/* Leverage the standard, primitive collection sort method */
keys.sort();
for(Decimal key:keys) { resultList.addAll(oppMap.get(key)); }
return resultList;
}
/* Quicksort method as described on the boards adapted to use an
opportunity collection. */
private static void quicksortOpptys(List<opportunity> a, Integer lo0, Integer hi0) {
Integer lo = lo0;
Integer hi = hi0;
if (lo >= hi) {
return;
} else if( lo == hi - 1 ) {
if (a[lo].amount > a[hi].amount) {
Opportunity o = a[lo];
a[lo] = a[hi];
a[hi] = o;
}
return;
}
Opportunity pivot = a[(lo + hi) / 2];
a[(lo + hi) / 2] = a[hi];
a[hi] = pivot;
while( lo < hi ) {
while (a[lo].amount <= pivot.amount && lo < hi) { lo++; }
while (pivot.amount <= a[hi].amount && lo < hi ) { hi--; }
if( lo < hi ){
Opportunity o = a[lo];
a[lo] = a[hi];
a[hi] = o;
}
}
a[hi0] = a[hi];
a[hi] = pivot;
quicksortOpptys(a, lo0, lo-1);
quicksortOpptys(a, hi+1, hi0);
}
/* Get a recent set of opportunities with non-null amounts for use in each test */
private static List<Opportunity> getOpps() {
/* If your org does not have sufficient data, you can create opportunities with
random amounts here instead of querying. */
return [select name, amount
from opportunity
where amount > 0
order by createddate desc
limit 25];
}
/* Assert the collection is ordered ascending. */
private static void doAsserts(List<Opportunity> opps) {
Decimal assertValue = -1;
for(Opportunity o:opps) {
System.debug('OPPTY VALUE: ' + o.amount);
System.assert(assertValue <= o.amount);
assertValue = o.amount;
}
}
}
If you take the code above and save it into your Developer Edition account as a new class you can run these tests to see how they compare with your data. In my account the results were pretty significant:
SCRIPT STATEMENTS USED BY THE CUSTOM SORT :327
SCRIPT STATEMENTS USED BY THE STANDARD SORT: 76
Moral to the story: associative arrays and methods on the standard types are great assets to minimize the # of script statements needed to achieve the desired outcome.
It's good to be back!
TrackBack
TrackBack URL for this entry: http://www.typepad.com/services/trackback/6a00d8341cded353ef010534c74cd1970c
Listed below are links to weblogs that reference Sorting collections in Apex and "Too many script statements":
All rights reserved Various trademarks held by their respective owners.
General Enquiries: 415-901-7000 | Fax: 415-901-7040 | Sales: 1-800-no-software
Comments
Posted by Jason on September 26, 2008 09:03 AM:
This is actually a very slick method to sort Lists. I've done some testing on Lists of 1000 elements, the maximum size, and with the custom sort it averages about 24,000 script statements. Using the standard functionality the average is about 2,600. This is basically the two for loops of 1000 elements so it would be very difficult to get any more efficient than this method.
Posted by Jason on September 27, 2008 09:46 PM:
Also, the standard sort only sorts ascending so if you would like to sort your list descending you can add this to the end of the sort method. It adds about 2000 additional script statements.
Integer lo = 0;
Integer hi = resultList.size() - 1;
while(lo < hi){
Opportunity o = resultList[lo];
resultList[lo] = resultList[hi];
resultList[hi] = o;
lo++;
hi--;
}
Posted by Jon Mountjoy on September 29, 2008 02:19 AM:
Welcome back Andrew - great post!
Posted by Matt Brown on March 17, 2009 05:09 AM:
Great code for opportunities but how about a simple sort by descending for case create date?
Posted by Jason on April 13, 2009 03:15 PM:
Here is a wiki entry that may help you sort Dates, and any other data type for that matter:
http://wiki.developerforce.com/index.php/Sorting_Tables
Posted by kelly on July 12, 2009 07:26 PM:
hi i have problems about sorting when there are two objects for total .
i define a class MonthTotal
but when i want to sort by the method you supply , there are always errors
my code is behind :
public class SortForPractise {
List opps ;
public String sortField {get; set;}
public String previousSortField {get; set;}
public List getOpps() {
if(opps == null){
for(Expense_Type__c a:[Select e.Name, (Select Apr__c,May__c, Aug__c, Dec__c, Feb__c, Jan__c, Jul__c, Jun__c, Mac__c, Nov__c, Oct__c, Sep__c,t.Hotels__r.Name From Tactics__r t ) from Expense_Type__c e ])
{
opps .add (new MonthTotal(a));
}
return opps ;
}
return opps;
}
public void doSort(){
String order = 'asc';
/*This checks to see if the same header was click two times in a row, if so
it switches the order.*/
if(previousSortField == sortField){
order = 'desc';
previousSortField = null;
}else{
previousSortField = sortField;
}
//To sort the table we simply need to use this one line, nice!
new superSort().sortList(opps.total ,sortField ,order);
}
public class superSort {
/*This method takes 3 arguments, the List of objects to sort, the field to sort,
and the order, asc or desc*/
public void sortList(List items, String sortField, String order){
/*I must give credit where it is due as the sorting algorithm I am using is the
one supplied by Andrew Waite here: http://blog.sforce.com/sforce/2008/09/sorting-collect.html */
Boolean isSortFieldReference = false;
Map referenceName;
/*Determine the type of the field that needs to be sorted, if it is a
reference we will want sort by the name of the related object, not the
ID itself*/
if(items[0].getSObjectType().getDescribe().fields.getMap().get(sortField).getDescribe().getType().Name() == 'REFERENCE'){
isSortFieldReference = true;
referenceName = new Map();
/*Determine the type of this object and populate the Id to Name map*/
Set referenceIds = new Set();
for(sObject s : items){
referenceIds.add((Id)s.get(sortField));
}
String objectID = (String)items[0].get(sortField);
String prefix = objectID.substring(0,3);
String objectType;
Map gd = Schema.getGlobalDescribe();
for(Schema.SObjectType s : gd.values()){
if(prefix == s.getDescribe().getKeyPrefix()){
objectType = s.getDescribe().Name;
}
}
//Query the related objects for the name and populate the Id -> Name map
String queryString = 'select Id, Name from ' + objectType + ' where ID IN :referenceIDs';
for(sObject s : Database.query(queryString )){
referenceName.put((Id)s.get('Id'),(String)s.get('Name'));
}
}
/*Declare a list that will contain the sorted results. I think this is one of the
coolest parts of this method as the system will not let you declare a list of
sObjects (List objects = new List();) but using a
wrapper class you can bypass this system limitation to create this type of list */
List resultList = new List();
//Create a map that can be used for sorting
Map> objectMap = new Map>();
for(sObject ob : items){
if(isSortFieldReference == false){
if(objectMap.get(ob.get(sortField)) == null){
objectMap.put(ob.get(sortField), new List());
}
cObject o = new cObject(ob);
objectMap.get(ob.get(sortField)).add(o);
}else{
if(objectMap.get(referenceName.get((Id)ob.get(sortField))) == null){
objectMap.put(referenceName.get((Id)ob.get(sortField)), new List());
}
cObject o = new cObject(ob);
objectMap.get(referenceName.get((Id)ob.get(sortField))).add(o);
}
}
//Sort the keys
List keys = new List(objectMap.keySet());
keys.sort();
for(object key : keys){
resultList.addAll(objectMap.get(key));
}
//Apply the sorted values to the source list
items.clear();
if(order.toLowerCase() == 'asc'){
for(cObject ob : resultList){
items.add(ob.obj);
}
}else if(order.toLowerCase() == 'desc'){
for(integer i = resultList.size()-1; i >= 0; i--){
items.add(resultList[i].obj);
}
}
}
}
public class cObject{
sObject obj {get; set;}
public cObject(sObject obj){
this.obj = obj;
}
}
public class MonthTotal{
public Expense_Type__c account{get; private set;}
public Tactic__c total{get; private set;}
public Market_Segment__c market{get; private set;}
public double sum{get ; private set;}
public double sum2{get; private set;}
public double sumColumn{get ; private set;}
public MonthTotal(Expense_Type__c a) {
account = a;
total = new Tactic__c( Apr__c =0,Aug__c = 0, Dec__c=0, May__c=0, Feb__c=0, Jan__c=0, Jul__c=0, Jun__c=0, Mac__c=0, Nov__c=0, Oct__c=0, Sep__c=0);
for(Tactic__c o: a.Tactics__r )
{ if(o.Jan__c!= null) total.Jan__c= total.Jan__c+ o.Jan__c;
if(o.Feb__c!= null) total.Feb__c= total.Feb__c+ o.Feb__c;
if(o.Mac__c!= null) total.Mac__c= total.Mac__c+ o.Mac__c;
if(o.Apr__c!= null) total.Apr__c= total.Apr__c+ o.Apr__c;
if(o.May__c!= null) total.May__c= total.May__c+ o.May__c;
if(o.Jun__c!= null) total.Jun__c= total.Jun__c+ o.Jun__c;
if(o.Jul__c!= null) total.Jul__c= total.Jul__c+ o.Jul__c;
if(o.Aug__c!= null) total.Aug__c= total.Aug__c+ o.Aug__c;
if(o.Sep__c!= null) total.Sep__c= total.Sep__c+ o.Sep__c;
if(o.Oct__c!= null) total.Oct__c= total.Oct__c+ o.Oct__c;
if(o.Nov__c!= null) total.Nov__c= total.Nov__c+ o.Nov__c;
if(o.Dec__c!= null) total.Dec__c= total.Dec__c+ o.Dec__c;
}
sum = total.Jan__c+ total.Feb__c + total.Mac__c + total.Apr__c + total.May__c + total.Jun__c + total.Jul__c + total.Aug__c + total.Sep__c + total.Oct__c + total.Nov__c + total.Dec__c;
}
public MonthTotal (Market_Segment__c m) {
market = m;
total = new Tactic__c( Apr__c =0,Aug__c = 0, Dec__c=0, May__c=0, Feb__c=0, Jan__c=0, Jul__c=0, Jun__c=0, Mac__c=0, Nov__c=0, Oct__c=0, Sep__c=0);
for(Tactic__c o: m.Tactics__r )
{ if(o.Jan__c!= null) total.Jan__c= total.Jan__c+ o.Jan__c;
if(o.Feb__c!= null) total.Feb__c= total.Feb__c+ o.Feb__c;
if(o.Mac__c!= null) total.Mac__c= total.Mac__c+ o.Mac__c;
if(o.Apr__c!= null) total.Apr__c= total.Apr__c+ o.Apr__c;
if(o.May__c!= null) total.May__c= total.May__c+ o.May__c;
if(o.Jun__c!= null) total.Jun__c= total.Jun__c+ o.Jun__c;
if(o.Jul__c!= null) total.Jul__c= total.Jul__c+ o.Jul__c;
if(o.Aug__c!= null) total.Aug__c= total.Aug__c+ o.Aug__c;
if(o.Sep__c!= null) total.Sep__c= total.Sep__c+ o.Sep__c;
if(o.Oct__c!= null) total.Oct__c= total.Oct__c+ o.Oct__c;
if(o.Nov__c!= null) total.Nov__c= total.Nov__c+ o.Nov__c;
if(o.Dec__c!= null) total.Dec__c= total.Dec__c+ o.Dec__c;
}
sum2 = total.Jan__c+ total.Feb__c + total.Mac__c + total.Apr__c + total.May__c + total.Jun__c + total.Jul__c + total.Aug__c + total.Sep__c + total.Oct__c + total.Nov__c + total.Dec__c;
}
}
}
please help me very soon
email to kyu@e5systems.com
The comments to this entry are closed.