Finding minimum in list

[DrD]

I'm looking for ideas to efficiently locate the second value, of the minimum value of all first values, within a list of paired lists. For example, I would like set var R=2, from the minimum of all first values, {1,2 }, in this example list:

L0:={{5,1},{1,2},{1.25,3},{1.167,5}};
R:=2; // from item in red's second value

-Dale-

[Han]

(03-22-2017 03:14 PM)DrD Wrote:  I'm looking for ideas to efficiently locate the second value, of the minimum value of all first values, within a list of paired lists. For example, I would like set var R=2, from the minimum of all first values, {1,2 }, in this example list:

L0:={{5,1},{1,2},{1.25,3},{1.167,5}};
R:=2; // from item in red's second value

-Dale-

I don't suppose you have already tried something like:

Code:

EXPORT MINFIRST()
BEGIN
  L1:=MAKELIST(L0(J,1),J,1,SIZE(L0));
  M:=MIN(L1);
  M:=POS(L1,M);
  RETURN(L0(M,2)); // R:=L0(M,2);
END;

In the event of two or more sublists having the same minimal first values, the first occurrence will be used. Did you have any other conditions for such cases?

[Didier Lachieze]

or:

Code:

L1:=SORT(L0,1);
R:=L1(1,2);

[Han]

(03-22-2017 04:06 PM)Didier Lachieze Wrote:  or:

Code:

L1:=SORT(L0,1);
R:=L1(1,2);

Nicely done (and I think you may have even brought attention to a minor bug).

SORT(L0) gives me a syntax error whereas providing the actual list itself is fine.

EDIT: Perhaps the little bug isn't so little after all. SORT({{1}, {3,4}, "12" }) does not seem to behave gracefully (no error, in fact no result whatsoever).

[Han]

Here's some code to do a time comparison, should you also need speed in addition to succinctness.

Code:

EXPORT MAKEL0(K)
BEGIN
  L0:=MAKELIST({IP(RANDOM*10), IP(RANDOM*10)},J,1,K);
END;

EXPORT MINFIRST1()
BEGIN
  L1:=MAKELIST(L0(J,1),J,1,SIZE(L0));
  R:=MIN(L1);
  R:=POS(L1,R);
  RETURN(L0(R,2));
END;

EXPORT MINFIRST2()
BEGIN
  L1:=SORT(L0,1);
  RETURN(L1(1,2));
END;

EXPORT TIMEM()
BEGIN
  LOCAL T1,T2;
  T1:=TEVAL(MINFIRST1());

  T2:=TEVAL(MINFIRST2());

  RETURN({T1,T2});
END;

Run with TIMEM(<blah>) where <blah> is an integer; you'll need large lists to see any differences in time (which, depending on your project's needs, may or may not realize any significant speed differences).

I'll update with anyone else's code should more be provided.

[DrD]

(03-22-2017 03:30 PM)Han Wrote:  I don't suppose you have already tried something like:

Code:

EXPORT MINFIRST()
BEGIN
  L1:=MAKELIST(L0(J,1),J,1,SIZE(L0));
  M:=MIN(L1);
  M:=POS(L1,M);
  RETURN(L0(M,2)); // R:=L0(M,2);
END;

In the event of two or more sublists having the same minimal first values, the first occurrence will be used. Did you have any other conditions for such cases?

In my particular application it so happens that I do want the first occurrence if there are the multiple elements with the same first value. I haven't specifically tried this approach, but I have used loop constructs that did pretty much the same thing. Thank you for your idea!

Thanks Didier! I think your approach is exactly what I was hoping for. I did not use the SORT command, but now that I see it in action, I should have! I don't think it gets any more efficient than that to accomplish my objective.

-Dale-

[Han]

(03-22-2017 05:29 PM)DrD Wrote:  In my particular application it so happens that I do want the first occurrence if there are the multiple elements with the same first value. I haven't specifically tried this approach, but I have used loop constructs that did pretty much the same thing. Thank you for your idea!

Thanks Didier! I think your approach is exactly what I was hoping for. I did not use the SORT command, but now that I see it in action, I should have! I don't think it gets any more efficient than that to accomplish my objective.

-Dale-

This is only tangential to your posts, but loops are generally slower than using MAKELIST. Even creating a custom function that replicates the content within a loop, and using that function with MAKELIST, would gain you a bit more speed (more significant if you are working with many iterations/large sets).

SORT works well for small lists, and even handles lists within lists using SORT(list, index) -- which, by the way, is not documented in the Help screen. For much larger sets, the SORT algorithm would lose out to MAKELIST and MIN (the latter is linear time in the size of the list). Even the fastest sorting algorithm is still around \( O(n \log n ) \), i.e. not linear.

Of course, nothing beats the code brevity of SORT.

[Tyann]

Quote:SORT works well for small lists, and even handles lists within lists using SORT(list, index) -- which, by the way, is not documented in the Help screen.

Merci, je découvre cette possibilité grâce à vous.

Thank you, I discover this possibility thanks to you.

[DrD]

I didn't like my loop approach very well, either. I was hoping for a better way! Han's ideas were a lot better than mine, and Didier's sort approach was right on. So thanks for the ideas, and I hope I can reciprocate somewhere down the line! Maybe other people will find these techniques useful, as well.

-Dale-

[DrD]

(03-22-2017 03:30 PM)Han Wrote:  In the event of two or more sublists having the same minimal first values, the first occurrence will be used. Did you have any other conditions for such cases?

My application needs the first occurrence of multiple sublists which have the same minimum first values. At first, I thought this is what the SORT command would do. However, I've found that isn't always true :

L0:={{10,1},{2,2},{2,4},{8,9},{8,1}};
SORT(L0,1); // ==> {{2,4},{2,2},{8,9},{8,1},{10,1}}

The set of sublists with 2 as the first value get reversed in the SORT procedure, whereas the set of sublists with 8 as the first value do not get reversed. SORT cannot be relied upon to return the first occurrence for same sublist first values. This behavior can be difficult to debug, in otherwise normally functional code!

[Han]

(03-25-2017 02:25 PM)DrD Wrote:  

(03-22-2017 03:30 PM)Han Wrote:  In the event of two or more sublists having the same minimal first values, the first occurrence will be used. Did you have any other conditions for such cases?

My application needs the first occurrence of multiple sublists which have the same minimum first values. At first, I thought this is what the SORT command would do. However, I've found that isn't always true :

L0:={{10,1},{2,2},{2,4},{8,9},{8,1}};
SORT(L0,1); // ==> {{2,4},{2,2},{8,9},{8,1},{10,1}}

The set of sublists with 2 as the first value get reversed in the SORT procedure, whereas the set of sublists with 8 as the first value do not get reversed. SORT cannot be relied upon to return the first occurrence for same sublist first values. This behavior can be difficult to debug, in otherwise normally functional code!

SORT likely uses an unstable algorithm (perhaps they are using quicksort for speed and memory). The code I provided should be stable.

[John P]

My two cents to the discission. It works in CAS and HOME on the latest emulator.

EXPORT COLEXTR(l,c,fl)
//l: array, c: col you consider
//fl: flag, fl=0 for min, fl=any other
//integer for max.
BEGIN
local tc=mat2list(col(l,c));
if fl==0
then return(l(pos(tc,min(tc))));
else return(l(pos(tc,max(tc))));
end;
END;

If you also need position you can create local var. ex. tp, and change the lines in the then and else blocks to: tp:=pos(tc,min(tc)); tp:=pos(tc,max(tc)); and put return(l(tp),tp); outside of the if construct.

[cyrille de brébisson]

Hello,

SORT does indeed use a quick sort type algo which does not guaranty that 2 elements with the same value end up in the same order in the output list as they were in the input list.

The algo is stable in the fact that it will always return the same results. There is no random selection in it (which is one way to implement QS).

Cyrille

[DrD]

Thanks for your explanation, Cyrille. Didier's short SORT minimum finder seemed like the perfect solution when a sublist tuplet contains both data and a reference pointer.
As you point out, there is no guarantee that the sort order will keep the first occurrence of same data values at the head of the result list. So tracking the second element reference pointer takes a little more work, I learned that the hard way!

[DrD]

Just for general information ... I want to share: The SORT command will take an optional list as the sort index parameters. (To sort on the first, and then on the second of a sub list containing same valued 1st element pairs):

L0:={{8,9},{2,4},{8,1},{2,2},{10,1}};
SORT(L0,{1,2}); ==> {{2,2},{2,4},{8,1},{8,9},{10,1}}

-Dale-

[Didier Lachieze]

(03-29-2017 10:54 AM)DrD Wrote:  The SORT command will take an optional list as the sort index parameters.

Good to know, thanks for sharing !