about average_median.py

[1170300620]

Is there any other algorithm to complete it? Origin algorithm costs too much when it's used for big data by using the sorted() function.
1c9d995

[1170300620]

Actually, I think there may be another place to improve:

The computing process of the value med can be simply written as:
med = (sorted_list[ ( len(sorted_list) - 1 ) / 2 ] + sorted_list[ len(sorted_list) / 2] ) / (float) 2
Then just return med and end it.

[PatOnTheBack]

@1170300620 Are you saying that the variables mid_index_1 and mid_index_2 should not be used at all?

The reason I wrote several lines was so that the code would be easier to read.

[PatOnTheBack]

@1170300620

med = (sorted_list[ ( len(sorted_list) - 1 ) / 2 ] + sorted_list[ len(sorted_list) / 2] ) / (float) 2

This is invalid syntax. It should be float(2) instead of (float) 2. :)

After fixing that syntax error, your code works well. I am just concerned that it might be less clear for beginners.

[PatOnTheBack]

I just looked at the source code for Python 3.7.3

Apparently, they used sorting in their algorithm too. You can find this file in
Lib/statistics.py of the Python Source folder.

# FIXME: investigate ways to calculate medians without sorting? Quickselect?
def median(data):
    """Return the median (middle value) of numeric data.

    When the number of data points is odd, return the middle data point.
    When the number of data points is even, the median is interpolated by
    taking the average of the two middle values:

    >>> median([1, 3, 5])
    3
    >>> median([1, 3, 5, 7])
    4.0

    """
    data = sorted(data)
    n = len(data)
    if n == 0:
        raise StatisticsError("no median for empty data")
    if n%2 == 1:
        return data[n//2]
    else:
        i = n//2
        return (data[i - 1] + data[i])/2

[1170300620]

Oh,

@1170300620

med = (sorted_list[ ( len(sorted_list) - 1 ) / 2 ] + sorted_list[ len(sorted_list) / 2] ) / (float) 2

This is invalid syntax. It should be float(2) instead of (float) 2. :)

After fixing that syntax error, your code works well. I am just concerned that it might be less clear for beginners.

Oh, you're right. This change is not clear actually.

[1170300620]

About the Python 3.7 built-in sorted() function :
https://en.m.wikipedia.org/wiki/Timsort
The main algorithm used to complete sorted() function is called Timsort, the average time complexity of which is O(nlogn).
I think the median() may have better performance by using the divide and conquer algorithm. The bfprt algorithm is a good choice, the time complexity of which is O(n). It's more complex but quicker.

[PatOnTheBack]

@1170300620 Unless you want to make your own pull request for this, I can look into it next week.

[PatOnTheBack]

@1170300620 When I added a merge sort, which is a divide and conquer algorithm, it did not improve the performance.

def merge_sort(collection):
    """Pure implementation of the fastest merge sort algorithm in Python.

    Taken from: /sorts/merge_sort_fastes.py
    """
    start, end = [], []
    while len(collection) > 1:
        min_one, max_one = min(collection), max(collection)
        start.append(min_one)
        end.append(max_one)
        collection.remove(min_one)
        collection.remove(max_one)
    end.reverse()
    return start + collection + end

I replaced the call to sorted with merge_sort when I ran the program.

When, I compared the default sorted with merge_sort, this is what I got.

python average_median.py
--- 7.29560852051e-05 seconds ---

python average_median_merge.py 
--- 8.29696655273e-05 seconds ---

[HarsheetKakar]

can we do this with randomized selection algorithm(order statistics) it has a better average case complexity

[github-actions]

Stale issue message