ds_list_sort_assoc

Daniel · 2011-12-28 20:37:42

I was trying to think of a way to sort a list in-place and to sort a SECOND list in the same way, such that if each item in list 1 was "mapped" to an item in link 2, it would remain at the same index after. Something like this:

Original Lists:
Daniel 200
Xot 100
icuurd 150

Would be sorted to:
Xot 100
icuurd 150
Daniel 200

I needed to keep it efficient and in-place, so I came up with this (it relies on gQuery, but the function names are pretty obvious, and we all know what a foreach does)

I want to know if there's any way to make this more efficient. What I did is copy the list being sorted into a new list, sort that original list in-place, then swap each index for its real position in the second list by looking up the old position using the copy list and its new position in the sorted list.

Expandvar gQ_keys;
gQ_keys=ds_list_create()
ds_list_copy(gQ_keys,argument0)
if argument_count>2
    ds_list_sort(argument0,argument[2])
else ds_list_sort(argument0,true)
show_debug_message('gQ: Assoc Sorting '+string(argument0)+' linked to '+string(argument1))
for(each(argument0) as key_value()) {
    gQ_temp = ds_list_find_index(gQ_keys,value);
    if key!=gQ_temp {
        ds_list_swap(argument1,key,gQ_temp)
        ds_list_swap(gQ_keys,key,gQ_temp) } }
ds_list_destroy(gQ_keys)

icuurd12b42 · 2011-12-29 21:34:51

I usually cheat by appending a tag and "stringafy" my data

In the case of the example wanted result, you sort by score but want to keep the name associated with the score

Format the score so it looks like "000100" (you need enough leading 0s) and append + chr(0) (\0) + "Xot"

000200\0Daniel
000100\0Xot
000150\0icuurd

ds_list_sort will sort properly by value

to extract, you can real(value); real automatically stops at \0, you can get the name by extracting the string at position 8 for the length of 9999, string_copy(value,8,9999). string_copy stops when it hit the end or 9999, whatever comes first.

So now you get the wanted result.

Now you can use the same method to stuff the list index of the linked item located in the second list, the important bit is the formatting of the leading value you sort on with the leading 0s because the sort is sting based.

you get the list size to know what index the value will be at and append that to the string value

index = ds_list_size(l1)
ds_list_add(l1,ZeroLeadingFormatedValue + chr(0) + string(index));
ds_lisd_add(l2,Name);

l1
000200\00
000100\01
000150\02

l2
Daniel
Xot
icuurd

sort l1

score = ds_list_find_falue(l1,0);
origIndex = real(string_copy(value,8,9999));
name = ds_list_find_value(l2,origIndex);

you can sort match the l2 list to l1 by making another list, l3 and insert, in order, the items located in l2 using the index stored as "extra data" of l1.

Last edited by icuurd12b42 (2011-12-29 21:39:35)

Daniel · 2011-12-29 21:44:12

I like that cheat, but it seems like it might start to fall apart if I want to sort by a list containing a string beginning with "0", wouldn't it? The sorting would be fine, but when re-formatting, that leading 0 would be stripped? If I'm going to stringify things, I can put everything into a map where the thing-to-be-sorted becomes the Keys, and their associated value become the Values, then simply read out the map back into the lists? It's linear (as far as GM is concerned).

Unless your way DOES retain leading 0's that are meant to be there. I just can't see it doing so.

icuurd12b42 · 2011-12-29 22:08:14

the leading 0 is for proper sorting of numerical values and (a benefit mainly) to force an alignment at character 8. for sorting on a string, you would not need to place leading 0 but then the extra data would not be at position 8

values, name
one, xot
two, icuurd
three, paul
four, daniel

single list example
one\0Xot
two\0icuurd
three\0paul
four\0daniel

after sort
four\0daniel
one\0Xot
three\0paul
two\0icuurd

but now you need to find chr(0) to split the string and separate the left (of \0) data from the right... use the gmlscript's split function

the ds_list_sort should still work properly

Daniel · 2011-12-29 23:51:22

I'm suggesting it breaks when the sorting list has terms beginning with 0, such as "0fred", because it would remove the zero.

Also, gQuery has it's own explode function which I would be using. smile

icuurd12b42 · 2011-12-30 00:40:28

How does the 0 get trimmed out of 0fred?? there is no code there to trim out zeros from strings, apart from the real() call on the numerical value (if you choose that method instead of the split() method)

"000200\0Daniel" means "000200chr(0)Daniel"... splits using chr(0) to "000200" and "Daniel", real(000200) brings it back to 200 numerical

"000101\00fred" means 000101chr(0)0fred, splits to 101 and 0Fred

0Fred\00Fred splits to 0Fred 0Fred

Last edited by icuurd12b42 (2011-12-30 00:41:51)

Daniel · 2011-12-30 01:07:28

Ohhhh! I was unaware that you could still deal with strings which had a nul in them. Nice idea!

icuurd12b42 · 2011-12-30 15:36:23

Yeah, GM supports nul in the string buffer without breaking things unlike old c char* based functions. The only function that seems to care about nul in the string is the real() function which stops at the first nul it sees; a fluke that you can take advantage of.

It also means chr(0) is the safest delimiter tag you can use to split data

paul23 · 2011-12-30 23:02:37

I just use instances to hold the data in these cases: prevents any programming errors on the algorithm level.

BlueMoonProductions · 2012-10-13 13:51:25

Even though this topic is more than half a year old, I'll just throw this in here: This already exists - it's called ds_priority_ .

xot · 2012-10-13 17:23:42

Huh? ds_priority_ does not sort two associated lists.

On another subject, looking at this topic, it should be pointed out that you can no longer use chr(0) in strings since they are now NULL terminated in the GM:Studio code base.

Not sure the first solutions is all that optimal either since it does not appear to be stable. I could be wrong but it just looks like no thought was given to stability.

BlueMoonProductions · 2012-10-23 17:21:04

uh? ds_priority_ does not sort two associated lists.

It does, or at least, it does what this script tries to do. If you take the list from OP:

Daniel 200
Xot 100
icuurd 150

You can use the names as values, and the number behind it (the score?) as priority.

xot · 2012-10-23 17:53:04

Look, I get what you're saying. I really do.

Yes, you can feed two associated lists into a priority queue, using the sorting list to establish priority. And elements will be sorted. You can then extract the contents of the priority queue back into two lists. To rebuild your lists, you need empty the priority queue from the min or max ends one by one. And this is where you can get yourself into trouble. If you have elements with equal values, and use ds_priority_find_priority() to retrieve the associated values, the results could be spurious. Who knows which priority it will return when two elements are equal? Is it consistent? Can it be predicted? I don't know. To be safe, you'd be better off sorting a list of unique indices (0..n) using the values from the sorting list as priority. Then you can reconstruct your lists using the sorted indices by emptying the priority queue as described above.

My point is, sorting two lists with a priority queue is a multistep, nontrivial process with serious potential pitfalls. You can't just say, "priority queues already do this". They can be utilized to do this. I use them in just such a way with a similar script. It sorts grid rows by a given column (or vice versa). It could be used as the basis for a script to sort multiple associated lists, or as an intermediate step between scripts that transfer lists to and from grids.

Expand//  Usage:      ds_grid_sort(grid,index,reverse,columns)
//  Args:       grid        grid data structure
//              index       column (or row) to sort by
//              reverse     sort in reverse order, optional
//              columns     sort columns rather than rows, optional
//  Return:     nothing
//  Author:     xot, copyright (c) 2007
{
    var grd,ind,rev,col,w,h,copy,cur,next,m,n,prid,val;
    grid  = argument0;
    index = argument1;
    rev   = argument2;
    col   = argument3;
    w = ds_grid_width(grid);
    h = ds_grid_height(grid);
    copy = ds_grid_create(w,h);
    prid = ds_priority_create();
    if (rev) { cur = h - 1; next = -1; }else{ cur = 0; next = 1; }
    if (col) { m = h - 1; n = w - 1; }else{ m = w - 1; n = h - 1; }
    for (val=0; val<=n; val+=1) {
        if (col) ds_priority_add(prid,val,ds_grid_get(grid,val,index));
        else     ds_priority_add(prid,val,ds_grid_get(grid,index,val));
    }
    repeat (ds_priority_size(prid)) {
        val = ds_priority_delete_min(prid);
        if (col) ds_grid_set_grid_region(copy,grid,val,0,val,m,cur,0);
        else     ds_grid_set_grid_region(copy,grid,0,val,m,val,0,cur);
        cur += next;
    }
    ds_priority_destroy(prid);
    ds_grid_copy(grid,copy);
    ds_grid_destroy(copy);
}

forger · 2013-01-18 03:25:32

ds_priority??It's so long time.
GM supports nul in the string buffer,but it didn't work.

xot · 2013-01-18 07:07:34

Strings with nulls are not supported in GM:Studio.

icuurd12b42 · 2013-01-27 19:12:53

xot wrote:

Strings with nulls are not supported in GM:Studio.

And I am not happy about that. I had a one way discussion with who's it about that in regards to my gmbinfile dll

GM strings are character buffers where as Studio you dont have the ability to buffer data anymore because the darn thing (studio) is c string based... Which, if you ask me, is not very smart. Back to the 80's lol

Last edited by icuurd12b42 (2013-01-27 19:15:11)

GMLscripts.com

#1 2011-12-28 20:37:42

ds_list_sort_assoc

#2 2011-12-29 21:34:51

Re: ds_list_sort_assoc

#3 2011-12-29 21:44:12

Re: ds_list_sort_assoc

#4 2011-12-29 22:08:14

Re: ds_list_sort_assoc

#5 2011-12-29 23:51:22

Re: ds_list_sort_assoc

#6 2011-12-30 00:40:28

Re: ds_list_sort_assoc

#7 2011-12-30 01:07:28

Re: ds_list_sort_assoc

#8 2011-12-30 15:36:23

Re: ds_list_sort_assoc

#9 2011-12-30 23:02:37

Re: ds_list_sort_assoc

#10 2012-10-13 13:51:25

Re: ds_list_sort_assoc

#11 2012-10-13 17:23:42

Re: ds_list_sort_assoc

#12 2012-10-23 17:21:04

Re: ds_list_sort_assoc

#13 2012-10-23 17:53:04

Re: ds_list_sort_assoc

#14 2013-01-18 03:25:32

Re: ds_list_sort_assoc

#15 2013-01-18 07:07:34

Re: ds_list_sort_assoc

#16 2013-01-27 19:12:53

Re: ds_list_sort_assoc

Board footer