[Tutor] Traversing lists or getting the element you want.

[spir]

On 02/02/2014 09:46 PM, Kipton Moravec wrote:
> I am new to Python, and I do not know how to traverse lists like I
> traverse arrays in C. This is my first program other than "Hello World".
> I have a Raspberry Pi and they say Python is the language of choice for
> that little machine. So I am going to try to learn it.

Traversing an array of 'n' float item in C, using index instead of pointer, may 
translate to:
     float item;
     uint i;	// 0 <= i < n !!!
     for (i=0 ; i<n ; ++i) {
         item = items[i];
         // use item
      }
In python there is a range() function (xrange in python2) translating the same isea:
      for i range(n):	# 0 <= i < n !!!
         item = items[i];
         # use item
Works, but this is not the python way. Python also has a builtin *idiom* to 
traverse a list (or any other collection or "traversable"):
     for item in items:
         # use item

> I have data in the form of x, y pairs where y = f(x) and is non linear.
> It comes from a .csv file.
>
> In this case x is an integer from 165 to 660 so I have 495 data sets.
>
> I need to find the optimal locations of three values of x to piecewise
> linear estimate the function.
>
>
> So I need to find i, j, k so 165 < i < j < k < 660 and the 4 line
> segments [(165, f(165)), (i, f(i))], [(i, f(i)), (j, f(j))], [(j, f(j),
> (k, f(k))], [(k, f(k)), (660, f(660))].
>
>
> The value I need to minimize is the square of the difference between the
> line estimate and the real value at each of the 495 points.
>
>
> I can do this in C. To keep it simple to understand I will assume the
> arrays x[] and y[] and minsum, mini, minj, and mink are global.
>
>
> I have not tested this but this is what I came up with in C. Assuming
> x[] and y[] are already filled with the right values.
>
>
> int x[495];
> double y[495];
> max_elements = 495;
> double minsum;
> int mini, minj, mink
>
>
> void minimize(int max_elements)
>
> {
>      minsum = 9999999999999.0; // big big number

This is more or less a logical error (but one very very frequent). What if the 
array is empty? This gives: min(nothing_at_all)=9999999999999.0. min(nothing) is 
undefined, an anomaly or error. You should probably:
* refuse an empty array (the caller should not call the func at all)
* start with the first item as (temporary) min value
(Same for all similar 'reduce' functions.)

I understand you're not writing a simple min func here (instead minimising 
deviations to a hypothetical average) but the thinking pattern is the same. A 
sane min func may look like --i take the opportuity to show you some python code:

def min_nums (nums):
     n = len(nums)
     assert n > 0, "are you kidding?"

     min = nums[0]
     for i in range(2, n):
         num = nums[i]
         if num < min:
             min = num
     return min

nums = [6,4,5,8,3,1,2,7,8]
print(min_nums(nums))
print(min_nums([]))

>      for (i=2; i<max_elements-6;i++)
>          for (j=i+2; j< max_elements -4; j++)
>               for (k=j+2; k< max_elements-2;k++)
>               {
>                  sum = error(0,i);
>                  sum += error(i,j);
>                  sum += error(j,k);
>                  sum += error(k,495)
>
>                  if (sum < minsum)
>                  {
>                      minsum = sum;
>                      mini = i;
>                      minj = j;
>                      mink = k;
>                  }
>               }
> }

You could export in a sub-func the detail computation of the minimised element. 
Then, you could test it apart, and your minimise func would be barely more 
complicated than the one above (mine).

> double error(int istart, int iend)
> {
>
> // linear interpolation I can optimize but left
> // it not optimized for clarity of the function
>
>      int m;
>
>      double lin_estimate;
>
>      double errorsq;
>
>      errorsq = 0;
>
>      for (m=istart; m<iend; m++)

See range() or better "for item in items".

>      {
>          lin_estimate = y[istart] + ((y[iend] – y[istart]) *
>                         ((x[m] – x[istart]) / (x[iend] – x[istart])));
>
>          errorsq += (lin_estimate – y[m]) * (lin_estimate – y[m]);
>      }
>
>      return (errorsq);
>
> }
>
>
>
> At the end the three values I want are mini, minj, mink;
> or x[mini], x[minj], x[mink]
>
>
> So how do I do this (or approach this) in Python?
>
>
> Kip

Apart for the traversing idiom ('range' or 'for...in') the code is similar. (It 
also has '+=' and friends). (According to Guido van Rossum, Python was in fact 
designed to please C/Unix hackers; apart from the indented syntax and some 
idioms, it is indeed very similar, including a number of "unguessable" terms.)

d