Table.sort should use a stable sort algorithm

Question

question

Serge A asked May 28, '21 Serge A edited Oct 8, '21

Table.sort should use a stable sort algorithm

Apparently, Table.sort is not stable (see the video attached):

How to reproduce: create a global table GlobalTable1 and run this script:

Table t = Table("GlobalTable1");
t.setSize(20, 4);
for (int i = 1; i <= t.numRows; i++) {
t[i][1] = 0;
t[i][2] = uniform(0, 1000);
t[i][3] = uniform(0, 1000);
t[i][4] = uniform(0, 1000);
}
t.setColHeader(1, "Time");
t.setColHeader(2, "A");
t.setColHeader(3, "B");
t.setColHeader(4, "C");

Each time you call

Table("GlobalTable1").sort("Time")

the order of rows in the global table will be different.

So, if you call Table.sort on Reset, and the order of rows impacts simulation, then the results will be different each time you run this simulation.

Why it matters: If Table.sort is not stable, then simulation results may change according to how many times it is called. This may be an issue if input or configuration data have to be sorted on reset or during simulation run, because each subsequent reset and run will produce different results. So simulation results are not reproducible if Table.sort is used (FlexSim has to be restarted to reproduce the first simulation run).

Software Version:

FlexSim 21.1.3

flexsim 21.1.3 table sort

h510jjg8vf.mp4 (548.0 KiB)

· 3

5 |100000

Attachments: Up to 12 attachments (including images) can be used with a maximum of 23.8 MiB each and 47.7 MiB total.

Jeanette F ♦♦ commented · Jun 11, 2021 at 03:03 PM

Hi @Serge A , was Jason L's answer helpful? If so, please click the red "Accept" button at the bottom of one of their answers. Or if you still have questions, add a comment and we'll continue the conversation.

If we haven't heard back from you within 3 business days we'll auto-accept an answer, but you can always unaccept and comment back to reopen your question

0 ·

Serge A Jeanette F ♦♦ commented · Jun 14, 2021 at 08:29 AM

I don't think that adding a row number column to every table is an acceptable workaround that works in all situations.

IMO the choice of the unstable sort as a Table.sort algorithm is not justified in the context of simulation because it easily breaks reproducibility of the results. I'd like to promote this question to a feature request to change Table.sort algorithm.

0 ·

Eric M Serge A commented · Jun 15, 2021 at 04:44 PM

Hi @Serge A, please check out the article: How do I submit feature requests or bug reports? to send in a feature request. Include a link to this question as well, so they can see what's been discussed. Thanks!

0 ·

Answer 1 · 2021-05-28T14:52:09Z

Serge A answered May 28, '21 Serge A edited Jun 14, '21

Workaround 1

This is a workaround, sorttable_stable_inplace command, implemented in Flexscript.

user library with this command: SortLib.fsx

just user command subtree: sorttable_stable_inplace.fsx

Save SortLib.fsx in %userprofile%\Documents\FlexSim 2021 Projects\libraries, load it from Flexsim (File / Open User Libraries...).

Stable in-place sort of a table.

Parameters

(treenode table[, Array sortcolumns, Array sortdirs])

Description

Unlike sorttable and Table.sort, which are not stable, this command sorts a table and preserves the relative order of the elements with equivalent sortcolumns' values (default: first column).

Sorting directions are ascending by default (empty sortdirs), pass 0 as the n-th element to sort a column in descending order. Normally, sortdirs has the same length as sortcolumns.

For simplicity of implementation this command uses insertion sort algorithm, which can be O(N^2) in the worst case.

Usage is similar to Table.sort:

Table mytable = Table("MyGlobalTable");
sorttable_stable_inplace(mytable, ["ColumnHeader1", "ColumnHeader2"], [1/*ascending*/, 0/*descending*/]);

Multiple calls to sorttable_stable_inplace will not change the order of table rows.

This command is probably not very efficient on data bundle tables, because there's no efficient way to swap data bundle entries.

Workaround 2

Another workaround is to use SQL query and ORDER BY, which is a stable sort. This workaround requires to create a second temporary table where sorted results can be cloned to.

// ORDER BY is a stable sort
Table sorted = Table.query("SELECT * FROM GlobalTable1 ORDER BY A");
sorted.cloneTo(Table("GlobalTable2"));
Table("GlobalTable2").cloneTo(Table("GlobalTable1"));

sorttable-stable-inplace.fsx (3.1 KiB)

sortlib.fsx (7.1 KiB)

5 |100000

Attachments: Up to 12 attachments (including images) can be used with a maximum of 23.8 MiB each and 47.7 MiB total.

Answer 2 · 2021-05-28T12:26:29Z

Jason Lightfoot answered May 28, '21 Serge A commented Jun 1, '21

This is normal - you need to add another field to the array of fields by which the sort is performed. If other fields also have duplicates then it might be simpler to add a unique index and sort by that as a secondary field.

· 6

5 |100000

Attachments: Up to 12 attachments (including images) can be used with a maximum of 23.8 MiB each and 47.7 MiB total.

Serge A commented · May 28, 2021 at 02:39 PM

The point is I don't want to sort by other fields (because I want the records to remain in the same relative order).

0 ·

Jason Lightfoot ♦♦ Serge A commented · May 28, 2021 at 11:29 PM

They will if you apply the secondary index while they're in the correct relative order.

0 ·

Serge A Jason Lightfoot ♦♦ commented · Jun 01, 2021 at 07:35 AM

If we initialize the table like this:

Table t = Table("GlobalTable1");
t.setSize(20, 4);
for (int i = 1; i <= t.numRows; i++) {
    t[i][1] = 0;
    t[i][2] = uniform(0, 1000);
    t[i][3] = uniform(0, 1000);
    t[i][4] = uniform(0, 1000);
}
t.setColHeader(1, "Time");
t.setColHeader(2, "A");
t.setColHeader(3, "B");
t.setColHeader(4, "C");

then Table.sort with secondary indices will sort these secondary columns, which is exactly what I want to avoid:

Table t = Table("GlobalTable1");
t.sort(["Time", "A", "B", "C"]); // orders by A

Table.sort, as it is implemented now, orders the table by the first secondary index "A". Stable sort by "Time" column should leave the table unchanged.

0 ·

Show more comments

question