1

我正在尝试将快速选择从 Ruby 转换为 Python。Ruby代码如下：

class SortableArray
    attr_reader :array
    def initialize(array)
        @array = array
    end
    def quickselect!(kth_lowest_value, left_index, right_index)
        # If we reach a base case - that is, that the subarray has one cell,
        # we know we've found the value we're looking for:
        if right_index - left_index <= 0
            return @array[left_index]
        end
        # Partition the array and grab the index of the pivot:
        pivot_index = partition!(left_index, right_index)
        # If what we're looking for is to the left of the pivot:
        if kth_lowest_value < pivot_index
            # Recursively perform quickselect on the subarray to
            # the left of the pivot:
            quickselect!(kth_lowest_value, left_index, pivot_index - 1)
            # If what we're looking for is to the right of the pivot:
        elsif kth_lowest_value > pivot_index
            # Recursively perform quickselect on the subarray to
            # the right of the pivot:
            quickselect!(kth_lowest_value, pivot_index + 1, right_index)
        else # if kth_lowest_value == pivot_index
            # if after the partition, the pivot position is in the same spot
            # as the kth lowest value, we've found the value we're looking for
            return @array[pivot_index]
        end
    end
    
    def partition!(left_pointer, right_pointer)
        # We always choose the right-most element as the pivot.
        # We keep the index of the pivot for later use:
        pivot_index = right_pointer
        # We grab the pivot value itself:
        pivot = @array[pivot_index]
        # We start the right pointer immediately to the left of the pivot
        right_pointer -= 1
        while true
            # Move the left pointer to the right as long as it
            # points to value that is less than the pivot:
            while @array[left_pointer] < pivot do
                left_pointer += 1
            end
            # Move the right pointer to the left as long as it
            # points to a value that is greater than the pivot:
            while @array[right_pointer] > pivot do
                right_pointer -= 1
            end
            # We've now reached the point where we've stopped
            # moving both the left and right pointers.
            # We check whether the left pointer has reached
            # or gone beyond the right pointer. If it has,
            # we break out of the loop so we can swap the pivot later
            # on in our code:
            if left_pointer >= right_pointer
                break
            # If the left pointer is still to the left of the right
            # pointer, we swap the values of the left and right pointers:
            else
                @array[left_pointer], @array[right_pointer] = @array[right_pointer], @array[left_pointer]
            # We move the left pointer over to the right, gearing up
            # for the next round of left and right pointer movements:
                left_pointer += 1
            end
        end
        # As the final step of the partition, we swap the value
        # of the left pointer with the pivot:
        @array[left_pointer], @array[pivot_index] = @array[pivot_index], @array[left_pointer]
        # We return the left_pointer for the sake of the quicksort method
        # which will appear later in this chapter:
        return left_pointer
    end
end



array = [0, 50, 20, 10, 60, 30]
sortable_array = SortableArray.new(array)
p sortable_array.quickselect!(1, 0, array.length - 1)

当我将它转换为 python 时，它只有在我return在 if 和 elif 条件（第 28 和 30 行）之后放置 a 时才起作用，如下所示：

def partition(left_p, right_p, arr=[]):
    pivot_index = right_p
    pivot = arr[pivot_index]
    right_p -= 1

    while True:
        while arr[left_p] < pivot:
            left_p += 1
        while arr[right_p] > pivot:
            right_p -= 1

        if left_p >= right_p:
            break
        else:
            arr[left_p], arr[right_p] = arr[right_p], arr[left_p]
            left_p += 1

    arr[left_p], arr[pivot_index] = arr[pivot_index], arr[left_p]
    return left_p

def quickselect(kth_lowest_value, left_index, right_index, arr=[]):
    print(arr)
    if right_index - left_index <= 0:
        return arr[left_index]
    pivot_index = partition(left_index, right_index, arr)

    if kth_lowest_value < pivot_index:
        return quickselect(kth_lowest_value, left_index, pivot_index-1, arr)
    elif kth_lowest_value > pivot_index:
        return quickselect(kth_lowest_value, pivot_index+1, right_index, arr)
    else:
        print(f"item = {arr[pivot_index]}")
        return arr[pivot_index]


array = [200, 97, 100, 101, 211, 107, 63, 123, 11, 34]
index = quickselect(6, 0, len(array)-1, array)
print(index)

为什么它在没有返回的情况下在 Ruby 中工作？是因为它在课堂上吗？

4

1 回答 1

2

Ruby 代码不是很地道。--分支return中的最后一个是红鲱鱼，与条件链中的其他分支不一致。- -链中的其他分支也有一个隐含的。ifelsifelsereturnifelsifelse

概括上述思想，在所有 Ruby 函数和方法中，如果控制到达函数末尾而没有遇到 a return，则返回值是最后一个计算的表达式的值。在条件链中，那将是采用哪个分支。

一个最小的例子是：

def foo(n)
  if n == 0
    "zero"
  elsif n == 1
    "one"
  else
    "something else"
  end
end

puts foo(0) # => zero
puts foo(1) # => one
puts foo(2) # => something else

将returns 添加到上述任何或所有分支不会改变行为，通常会被省略。

另一方面，Python 的隐式返回总是None. 返回非None值涉及使用显式return（我猜“显式优于隐式” ？）。

def foo(n):
    if n == 0:
        return "zero"
    elif n == 1:
        return "one"
    else:
        return "something else"

print(foo(0)) # => zero
print(foo(1)) # => one
print(foo(2)) # => something else

关于 Ruby 代码的另一个注意事项：通常!在函数/方法名称用于就地算法之后，即修改输入的算法或其他更危险的非爆炸方法版本。由于quickselect!不修改任何类状态，因此令人困惑的是它有一个爆炸。

于 2021-08-16T16:24:25.860 回答